2024/12/02 刷题记录

52. N 皇后 II

class Solution {
public:
    vector<vector<string> > mp;
    vector<bool> shu;
    vector<bool> xie;
    vector<bool> fxie;

    void dfs(vector<string> q, int now, int n){
        if(now == n){
            mp.push_back(q);
            return;
        }
        for(int i = 0; i < q[now].length(); i++){
            if(!shu[i] && !xie[i - now + n] && !fxie[i + now]){
                shu[i] = true;
                xie[i - now + n] = true;
                fxie[i + now] = true;
                q[now][i] = 'Q';
                dfs(q, now + 1, n);
                q[now][i] = '.';
                shu[i] = false;
                xie[i - now + n] = false;
                fxie[i + now] = false;
            }
        }
    }

    int totalNQueens(int n) {
        mp = vector<vector<string> >();
        shu = vector<bool>(n);
        xie = vector<bool>(2 * n);
        fxie = vector<bool>(2 * n);
        string tmp = "";
        for(int i = 0; i < n; i++) tmp += ".";
        dfs(vector<string>(n, tmp), 0, n);
        return mp.size();
    }
};

48. 旋转图像

class Solution {
public:
    void rt(vector<vector<int>>& matrix, int n, int m, int i, int j) {
        swap(matrix[i][j], matrix[j][m - i]);
        swap(matrix[i][j], matrix[m - i][n - j]);
        swap(matrix[i][j], matrix[m - j][i]);
    }

    void rotate(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m / 2; i++) {
            for (int j = 0; j < (n + 1) / 2; j++) {
                rt(matrix, n - 1, m - 1, i, j);
            }
        }
    }
};

160. 相交链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};

206. 反转链表

/**
 * 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* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};