876 链表的中间结点

链表中的存储个数，为奇数或者偶数时，其中间结点不变。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *s = head;
        int count=0;
        while(s){
            s=s->next;
            count++;
        }
        for(int i=0;i<(count/2);i++){
            head=head->next;
        }
        return head;
    }
};

19 删除链表的倒数第 N 个结点

一种容易想到的方法是，我们首先从头节点开始对链表进行一次遍历，得到链表的长度 LL。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 L-n+1 L−n+1 个节点时，它就是我们需要删除的节点。

class Solution {
public:
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0, head);
    int length = getLength(head);
    ListNode* cur = dummy;
    for (int i = 1; i < length - n + 1; ++i) {
        cur = cur->next;
    }
    cur->next = cur->next->next;
    ListNode* ans = dummy->next;
    delete dummy;
    return ans;
}

36 有效的数独

有效的数独满足以下三个条件：

同一个数字在每一行只能出现一次；

同一个数字在每一列只能出现一次；

同一个数字在每一个小九宫格只能出现一次。

可以使用哈希表记录每一行、每一列和每一个小九宫格中，每个数字出现的次数。只需要遍历数独一次，在遍历的过程中更新哈希表中的计数，并判断是否满足有效的数独的条件即可。

image-20220208095828443

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int rows[9][9];
        int columns[9][9];
        int subboxes[3][3][9];
        
        memset(rows,0,sizeof(rows));
        memset(columns,0,sizeof(columns));
        memset(subboxes,0,sizeof(subboxes));
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
};

73 矩阵置零

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int rows[200];
        int colums[200];
        int k=0;
        int m = matrix.size();
        int n = matrix[0].size();
        for(int i=0;i<m;i++){
            for(int j =0;j<n;j++){
                if(matrix[i][j]==0){
                    rows[k]=i;
                    colums[k++]=j;
                }
            }
        }
        for(int i=0;i<k;i++){
            for(int j=0;j<m;j++){
                matrix[j][colums[i]]=0;
            }
            for(int j=0;j<n;j++){
                matrix[rows[i]][j]=0;
            }
        }
    }
};