lc 51~60

51. N 皇后

DFS + 剪枝

class Solution {
public:
    int m;
    vector<vector<string>> ans;
    vector<string> path;
    vector<bool> col, dg, udg;//存放列，对角线，对角线2(斜向下) 

    vector<vector<string>> solveNQueens(int n) {
        m = n;
        path = vector<string>(n, string(n, '.'));
        col = vector<bool>(n);
        dg = udg = vector<bool>(2 * n);
        dfs(0);
        return ans;
    }

    void dfs(int u){
        if(u == m){
            ans.push_back(path);
            return;
        }
        for(int i = 0; i < m; i++){
            if(!col[i] && !dg[u - i + m] && !udg[u + i]){
                path[u][i] = 'Q';
                col[i] = dg[u - i + m] = udg[u + i] = true;
                dfs(u + 1);
                path[u][i] = '.';
                col[i] = dg[u - i + m] = udg[u + i] = false;                
            }
        }
    }
};

52. N皇后 II

DFS + 剪枝

class Solution {
public:
    int m;
    int cnt;
    vector<bool> col, dg, udg;

    int totalNQueens(int n) {
        m = n;
        col = vector<bool>(n);
        dg = udg = vector<bool>(2 * n);
        dfs(0);
        return cnt;
    }

    void dfs(int u){
        if(u == m){
            cnt++;
            return;
        }
        for(int i = 0; i < m; i++){
            if(!col[i] && !dg[u - i + m] && !udg[u + i]){
                col[i] = dg[u - i + m] = udg[u + i] = true;
                dfs(u + 1);
                col[i] = dg[u - i + m] = udg[u + i] = false;                
            }
        }
    }
};

53. 最大子数组和

DP

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        for(int i = 0, last = 0; i < nums.size(); i++){
            last = nums[i] + max(0, last);
            res = max(res,last);
        }
        return res;
    }
};

54. 螺旋矩阵

蛇形矩阵，y总的方向向量法，非常好

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int m = matrix.size(), n = matrix[0].size();
        if(!m || !n) return ans;
        vector<vector<bool>> st(m, vector<bool>(n));//存放走过没得状态
        //行走周期交替方向矢量：dx(0, 1, 0, -1) dy(1, 0, -1, 0)
        int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}, x = 0, y = 0, seq = 0;
        for(int i = 0; i < m * n; i++){
            st[x][y] = true;
            ans.push_back(matrix[x][y]);
            int a = x + dx[seq], b = y + dy[seq];
            if(a < 0 || a >= m || b < 0 || b >= n || st[a][b]){
                seq = (seq + 1) % 4;
                a = x + dx[seq], b = y + dy[seq];
            }
            x = a, y = b;
        }
        return ans;
    }
};

55. 跳跃游戏

简单贪心

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxPos = 0;
        //在有限的视野范围内移动不断更新最大视野，看最终视野是否达到终点
        for(int i = 0; i <= maxPos && i < nums.size(); i++)
            maxPos = max(i + nums[i], maxPos);
        return maxPos >= nums.size() - 1;
    }
};

56. 合并区间

区间合并，模板

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        if(intervals.empty()) return res;
        sort(intervals.begin(), intervals.end());//按左端点排序
        int l = intervals[0][0], r = intervals[0][1];
        for(int i = 1; i < intervals.size(); i++){
            if(intervals[i][0] > r){
                res.push_back({l, r});
                l = intervals[i][0], r = intervals[i][1];
            }else{
                r = max(r, intervals[i][1]);
            }
        }
        res.push_back({l, r});
        return res;
    }
};

57. 插入区间

区间插入模板

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& a, vector<int>& b) {
        vector<vector<int>> ans;
        //所有区间与新区间的关系无非就三类，1.y<b[0],即无交点，2.y>=b[0]&&x<=b[1]有交集
        //3.y > b[1]无交点
        //先放第一部分
        int k = 0;
        while(k < a.size() && a[k][1] < b[0]) ans.push_back(a[k++]);
        //此时k走到了有交集的部分,需要去更新b[0],b[1]
        if(k < a.size()){
            b[0] = min(b[0], a[k][0]);
            while(k < a.size() && a[k][0] <= b[1]) b[1] = max(b[1], a[k++][1]);
        }
        ans.push_back(b);//!!!!注意这个不要放在if里，不然a空的时候，b就没放
        //放最后一部分
        while(k < a.size()) ans.push_back(a[k++]);
        return ans; 
    }
};

58. 最后一个单词的长度

使用stringstream

class Solution {
public:
    int lengthOfLastWord(string s) {
        stringstream ssin(s);
        int res = 0;
        string word;
        while(ssin >> word) res = word.size();
        return res;
    }
};

双指针

class Solution {
public:
    int lengthOfLastWord(string s) {
        int res = 0, len = s.size();
        //双指针，j指向单词左端，i指向右端
        for(int i = len - 1; i >= 0; i--){
            if(s[i] == ' ') continue;
            int j = i - 1;
            while(j >= 0 && s[j] != ' ') j--;
            return i - j;
        }
        return  0;//随便返回就行，最好0，虽然题中说了必有单词，但防止没吧
    }
};

59. 螺旋矩阵 II

蛇形矩阵简单

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n));
        // vector<vector<bool>> st(n, vector<bool>(n));//这个题不需要了
        int x = 0, y = 0, seq = 0, dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
        for(int i = 1; i <= n * n; i++){
            // st[x][y] = true;
            ans[x][y] = i;
            int a = x + dx[seq], b = y + dy[seq];
            if(a < 0 || a >= n || b < 0 || b >= n || ans[a][b]){
                seq = (seq + 1) % 4;
                a = x + dx[seq], b = y + dy[seq];
            }
            x = a, y = b;
        }
        return ans;
    }
};

60. 排列序列

暴力DFS，1904ms

class Solution {
public:
    string ans;
    vector<bool> st;
    int cnt;

    string getPermutation(int n, int k) {
        st = vector<bool>(n);
        dfs("", 0, k, n);
        return ans;
    }

    void dfs(string s, int u, int k, int n){
        if(u == n){
            cnt++;
            if(cnt == k)
                ans = s;
            return;
        }
        for(int i = 1; i <= n; i++){
            if(!st[i]){
                st[i] = true;
                char a = ('0' + i);
                dfs(s + a, u + 1, k, n);
                st[i] = false;
            }
        }
    }
};

使用next_permutation, 116ms

class Solution {
public:
    string getPermutation(int n, int k) {
        string ans;
        for(int i = 1; i <= n; i++) ans += to_string(i);
        for(int i = 0; i < k - 1; i++) next_permutation(ans.begin(), ans.end());
        return ans;
    }
};

数学 + 缩小问题规模 0ms

class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        //放每一位，后面的排列情况都为后面位数的阶乘，因此一位一位放
        vector<bool> st(n + 1);
        vector<int> factor(n + 1);
        factor[0] = 1;
        for(int i = 1; i <= n; i++)
            factor[i] = factor[i - 1] * i;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(!st[j]){
                    if(k > factor[n - i]){
                        k -= factor[n - i];
                    }else{
                        res += to_string(j);
                        st[j] = true;
                        //选完数字后跳出
                        break;
                    }
                }
            }
        }
        return res;
    }
};