2024/12/01 刷题记录

51. N 皇后

经典入门题，四年时间不能说毫无进步只能说原地踏步了hhhhh

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;
            }
        }
    }

    vector<vector<string>> solveNQueens(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;
    }
};

41. 缺失的第一个正数

归位思想

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[nums[i] - 1], nums[i]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

73. 矩阵置零

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int p_hang = -1, p_lie = -1;
        for(int i = 0; i < m; i++){
            bool no_zero = true;
            for(int j = 0; j < n; j++){
                if(!matrix[i][j]){
                    no_zero = false;
                    break;
                }
            }
            if(no_zero){
                p_hang = i;
                break;
            }
        }
        for(int j = 0; j < n; j++){
            bool no_zero = true;
            for(int i = 0; i < m; i++){
                if(!matrix[i][j]){
                    no_zero = false;
                    break;
                }
            }
            if(no_zero){
                p_lie = j;
                break;
            }
        }
        if(p_hang == -1 || p_lie == -1){
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    matrix[i][j] = 0;
                }
            }
            return;
        }
        // cout<<p_hang<<" "<<p_lie<<endl;
        for(int i = 0; i < m; i++){
            if(i == p_hang) continue;
            for(int j = 0; j < n; j++){
                if(j == p_lie) continue;
                if(!matrix[i][j]){
                    matrix[p_hang][j] = 0;
                    matrix[i][p_lie] = 0;
                }
            }
        }
        // for(int i = 0; i < m; i++){
        //     for(int j = 0; j < n; j++){
        //         cout<<matrix[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        for(int i = 0; i < m; i++){
            if(!matrix[i][p_lie]){
                for(int j = 0; j < n; j++) matrix[i][j] = 0;
            }
        }
        for(int j = 0; j < n; j++){
            if(!matrix[p_hang][j]){
                for(int i = 0; i < m; i++) matrix[i][j] = 0;
            }
        }
        // for(int i = 0; i < m; i++){
        //     for(int j = 0; j < n; j++){
        //         cout<<matrix[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
    }
};

54. 螺旋矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int c = 0;
        int x = 0, y = 0;
        int n = matrix.size(), m = matrix[0].size();
        while(ans.size() != matrix.size() * matrix[0].size()){
            ans.push_back(matrix[y][x]);
            // ans.push_back(1);
            if(y == c && x != m - 1 - c){
                x++;
            } else if(x == m - 1 - c && y != n - 1 - c){
                y++;
            } else if(y == n - 1 - c && x != c){
                x--;
            } else if(x == c && y != c + 1){
                y--;
            } else if(x == c && y == c + 1){
                c++;
                x++;
            }
            // cout<<x<<" "<<y<<endl;
        }
        return ans;
    }
};

240. 搜索二维矩阵 II

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            }
            if (matrix[x][y] > target) {
                --y;
            }
            else {
                ++x;
            }
        }
        return false;
    }
};