LeetCode51-60

发表于 | 更新于: | 分类于 ， | | 阅读次数:
字数统计: 1.3k 字 | 阅读时长 ≈ 7 分钟

51、N皇后

回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int record[100];
    bool check(int n, int step){
        for(int i=1; i<step; i++)
            if(record[i]==record[step] || fabs(i-step)==fabs(record[i]-record[step]))
                return false;
        return true;
    }
    void DFS(vector<vector<string>> &ans, int n, int step){
        if(step>n){
            vector<string> cur_ans(n,string(n,'.'));
            for(int i=1; i<=n; i++)
                cur_ans[i-1][record[i]-1] = 'Q';
            ans.push_back(cur_ans);
            return ;
        }
        for(int i=1; i<=n; i++){
            record[step] = i;
            if(check(n, step))
                DFS(ans, n, step+1);
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        memset(record, 0, sizeof(record));
        vector<vector<string>> ans;
        for(int i=1; i<=n; i++){
            record[1] = i;
            DFS(ans, n, 2);
        }
        return ans;
    }
};

52、N皇后 II

同上一题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int ans = 0;
    int record[100];
    bool check(int n, int step){
        for(int i=1; i<step; i++)
            if(record[i]==record[step] || fabs(i-step)==fabs(record[i]-record[step]))
                return false;
        return true;
    }
    void DFS(int n, int step){
        if(step>n){
            ans++;
            return ;
        }
        for(int i=1; i<=n; i++){
            record[step] = i;
            if(check(n, step))
                DFS(n, step+1);
        }
    }
    int totalNQueens(int n) {
        memset(record, 0, sizeof(record));
        for(int i=1; i<=n; i++){
            record[1] = i;
            DFS(n, 2);
        }
        return ans;
    }
};

53、最大子序和

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        long long max_sum = -9999999999999, sum = 0;
        for(auto i : nums){
            sum += i;
            max_sum = max(max_sum, sum);
            if( sum<=0 )
                sum = 0;
        }
        return int(max_sum);
    }
};

54、螺旋矩阵

模拟题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int direct[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        int direction = 0, row = 0, col = 0, iter;
        vector<int> ans;
        if(matrix.size()==0)
            return ans;
        int total_nums = 0, rotal = 0;
        while(total_nums < matrix.size() * matrix[0].size()){
            if(direction%2)
                iter = matrix.size() - (2*(rotal/4) + 1);
            else
                iter = matrix[0].size() - (2*(rotal/4) + 1);
            if(direction==0 && rotal>0){
                row += 1;
                col += 1;
            }
            if(matrix.size()*matrix[0].size()-total_nums==1){
                ans.push_back(matrix[row][col]);
                break;
            }
            for(int i=1; i<=iter; i++){
                ans.push_back(matrix[row][col]);
                total_nums++;
                row += direct[direction][0];
                col += direct[direction][1];
            }
            rotal += 1;
            direction = (direction+1)%4;
        }
        return ans;
    }
};

55、跳跃游戏

判断能否到达最后一个位置，倒序遍历判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int len = nums.size();
        int pos = -1;
        for(int i=len-2; i>=0; i--){
            if(nums[i]==0 && pos==-1)
                pos = i;
            else if(pos-i < nums[i])
                pos = -1;
        }
        return pos==-1? true : false;
    }
};

56、合并区间

模拟题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    static bool cmp(vector<int>& vec1, vector<int>& vec2){
        if(vec1[0]!=vec2[0])
            return vec1[0] < vec2[0];
        return vec1[1] < vec2[1];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector< vector<int> > ans;
        if(intervals.size()==0)
            return ans;
        sort(intervals.begin(), intervals.end(), cmp);
        vector<int> tmp_ans = intervals[0];
        for(int i=1; i<intervals.size(); i++){
            if(tmp_ans[1] >= intervals[i][0])
                tmp_ans[1] = max(intervals[i][1], tmp_ans[1]);
            else{
                ans.push_back(tmp_ans);
                tmp_ans = intervals[i];
            }
        }
        ans.push_back(tmp_ans);
        return ans;
    }
};

57、插入区间

模拟题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        if(intervals.size()==0){
            intervals.push_back(newInterval);
            return intervals;
        }
        int pos = -1, i = 0, j = 0;
        for(i=0; i<intervals.size(); i++){
            if(newInterval[0]>intervals[i][0]){ //²åÔÚ i+1 µÄλÖÃ
                pos = i;
            }
            else
                break;
        }
        pos++;
        for(i=pos-1; i>=0; i--){
            if(intervals[i][1]>=newInterval[0]){
                newInterval[0] = min(intervals[i][0], newInterval[0]);
                newInterval[1] = max(newInterval[1], intervals[i][1]);
            }
            else
                break;
        }
        for(j=pos; j<intervals.size(); j++){
            if(newInterval[1]>=intervals[j][0]){
                newInterval[0] = min(intervals[j][0], newInterval[0]);
                newInterval[1] = max(newInterval[1], intervals[j][1]);
            }
            else
                break;
        }
        intervals.erase(intervals.begin()+(i+1), intervals.begin()+j);
        intervals.insert(intervals.begin()+(i+1),newInterval);
        return intervals;
    }
};

58、最后一个单词的长度

水题

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int lengthOfLastWord(string s) {
        s.erase(0, s.find_first_not_of(" "));  //find_ 返回下标
        s.erase(s.find_last_not_of(" ")+1);
        if(s.size()==0)
            return 0;
        int index = s.find_last_of(" ");
        if(index==s.size())
            return s.size();
        return s.size()-index-1;
    }
};

59、螺旋矩阵 II

模拟题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector< vector<int> > ans(n, vector<int>(n));
        int direct[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        int direction = 0, row = 0, col = 0, iter;
        int total_nums = 1, rotal = 0;
        while(total_nums<=n*n){
            iter = n - (2*(rotal/4) + 1);
            if(direction==0 && rotal>0){
                row += 1;
                col += 1;
            }
            if(n*n==total_nums){
                ans[row][col] = total_nums++;
                break;
            }
            for(int i=1; i<=iter; i++){
                ans[row][col] = total_nums++;
                row += direct[direction][0];
                col += direct[direction][1];
            }
            rotal += 1;
            direction = (direction+1)%4;
        }
        return ans;
    }
};

60、第k个排列

逆康拓展开的应用, 康拓展开公式为：
$$
X=a[n]\times(n-1)!+a[n-1]\times(n-2)!+…+a[i]\times(i-1)!+…+a[1]\times0!
$$
其中 a[n] 代表当前位置之前比自己小的未出现过的数字的个数。例如：

计算34152 的康托展开值为：
$$
X = 2 \times 4! + 2 \times 3! + 0 \times 2! + 1 \times 1! + 0 \times 0! = 61
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string getPermutation(int n, int k) {
        string ans = "";
        int nums[9] = {1, 1, 2, 6, 24, 120, 720, 720*7, 720*56};
        bool book[10];
        for(int i=0; i<10; i++)
            book[i] = false;
        k = k-1;
        for(int i=n-1; i>=0; i--){
            int large_num = k/nums[i];
            k %= nums[i];
            for(int i=1; i<=n; i++){
                if(large_num==0){
                    for(int j=i; j<=n; j++){
                        if(book[j]==false){
                            ans += '0' + j;
                            book[j] = true;
                            break;
                        }
                    }
                    break;
                }
                if(book[i]==false)
                    large_num--;
            }
        }
        return ans;
    }
};
-------------本文结束感谢您的阅读-------------
您的鼓励就是我创作的动力，求打赏买面包~~
0%