LeetCode31-40

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

31、下一个排列

偷个懒，直接使用库函数next_permutation。

1
2
3
4
5
6
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end());
    }
};

32、最长有效括号

用栈进行括号匹配消除，在消除过程中记录最大长度值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestValidParentheses(string s) {
        int ans = 0;
        stack< pair<char, int> > st;
        st.push(make_pair('#', -1));
        for(int i=0; i<s.length(); i++){
            if( st.top().first=='(' && s[i]==')' ){
                st.pop();
                ans = max(ans, i-st.top().second);
            }
            else{
                st.push(make_pair(s[i], i));
            }
        }
        return ans;
    }
};

33、搜索旋转排序数组

变形的二分搜索，关键点一：判断mid到底位于数组的前半段还是后半段；关键点二：判断下一步的搜索方向。

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
38
39
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1, mid;
        while(l<=r){
            mid = (l+r)>>1;
            if( nums[mid] >= nums[l] ){  //落在左边
                if( target > nums[mid] )
                    l = mid + 1;
                else if( target < nums[mid] ){
                    if( target>nums[l] )
                        r = mid - 1;
                    else if( target<nums[l] )
                        l = mid + 1;
                    else
                        return  l;
                }
                else
                    return mid;

            }
            else if( nums[mid] <= nums[r] ){   //落在右边
                if( target < nums[mid] )
                    r = mid - 1;
                else if( target > nums[mid] ){
                    if( target<nums[r] )
                        l = mid + 1;
                    else if( target>nums[r] )
                        r = mid - 1;
                    else
                        return r;
                }
                else
                    return mid;
            }
        }
        return -1;
    }
};

34、在排序数组中查找元素的第一个和最后一个位置

使用模板库里的二分查找函数，lower_bound查找第一个大于或等于某个元素的位置，upper_bound查找第一个大于某个元素的位置。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        int r = upper_bound(nums.begin(), nums.end(), target) - nums.begin();
        vector<int> ans{l,r-1};
        if(l==r)
           ans[0] = ans[1] = -1;
        return ans;
    }
};

35、搜索插入位置

同样偷懒使用库提供的二分查找函数lower_bound。

1
2
3
4
5
6
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    }
};

36、有效的数独

搞个book数组记录，然后直接暴力循环判断就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool book_row[9][9], book_col[9][9], book_cell[9][9];
        memset(book_row, 0, sizeof(book_row));
        memset(book_col, 0, sizeof(book_col));
        memset(book_cell, 0, sizeof(book_cell));
        int num;
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(board[i][j]=='.')
                    continue;
                num = board[i][j] - '0' - 1;
                if(book_row[i][num] || book_col[j][num] || book_cell[i/3*3+j/3][num])
                    return false;
                book_row[i][num] = true;
                book_col[j][num] = true;
                book_cell[i/3*3+j/3][num] = true;
            }
        }
        return true;
    }
};

37、解数独

深搜入门题，注意期间的剪枝操作。

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
38
39
40
41
42
43
44
45
class Solution {
private:
    bool book_row[9][9];
    bool book_col[9][9];
    bool book_cell[9][9];
public:
    bool mySolve(vector< vector<char> >& board, int position){
        if( position==81 )
            return true;
        int row = position/9;
        int col = position%9;
        if(board[row][col]!='.')
            return mySolve(board, position+1);
        for(int i=0; i<9; i++){
            if( !book_row[row][i] && !book_col[col][i] && !book_cell[row/3*3+col/3][i] ){
                board[row][col] = '1'+i;
                book_row[row][i] = true;
                book_col[col][i] = true;
                book_cell[row/3*3+col/3][i] = true;
                if(!mySolve(board, position+1)){
                    board[row][col] = '.';
                    book_row[row][i] = false;
                    book_col[col][i] = false;
                    book_cell[row/3*3+col/3][i] = false;
                }
                else
                    return true;  //唯一解
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char>>& board) {
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if( board[i][j]!='.' ){
                    int num = board[i][j] - '0' - 1;
                    book_row[i][num] = true;
                    book_col[j][num] = true;
                    book_cell[i/3*3+j/3][num] = true;
                }
            }
        }
        mySolve(board, 0);
    }
};

38、报数

模拟题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string countAndSay(int n) {
        string ans = "1";
        for(int step=1; step<n; step++){
            string tmp_ans;
            int sum = 1;
            char ch = ans[0];
            for(int i=1; i<ans.size(); i++){
                if( ch == ans[i] ){
                    sum++;
                    continue;
                }
                tmp_ans += (to_string(sum) + ch);
                ch = ans[i];
                sum = 1;
            }
            tmp_ans += (to_string(sum) + ch);
            ans = tmp_ans;
        }
        return ans;
    }
};

39、组合总和

深搜入门题，注意期间的剪枝操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
private:
    vector< vector<int> > ans;
public:
    void DFS(vector<int>& candidates, int target, int position, vector<int>& tmp_ans){
        if(target==0){
            ans.push_back(tmp_ans);
            return ;
        }
        for(int i=position; i<candidates.size(); i++){
            if( target>=candidates[i] ){  //一个小剪枝
                tmp_ans.push_back(candidates[i]);
                DFS(candidates, target-candidates[i], i, tmp_ans);
                tmp_ans.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());  // 排序为了后期剪枝用
        vector<int> tmp_ans;
        DFS(candidates, target, 0, tmp_ans);
        return ans;
    }
};

40、组合总和 II

在39题的基础上稍微改一下即可，一是13行的禁止元素重复使用，二是15行的去重操作。

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
class Solution {
private:
    vector< vector<int> > ans;
public:
    void DFS(vector<int>& candidates, int target, int position, vector<int>& tmp_ans){
        if(target==0){
            ans.push_back(tmp_ans);
            return ;
        }
        for(int i=position; i<candidates.size(); i++){
            if( target>=candidates[i] ){  //一个小剪枝
                tmp_ans.push_back(candidates[i]);
                DFS(candidates, target-candidates[i], i+1, tmp_ans);
                tmp_ans.pop_back();
                while(i+1<candidates.size() && candidates[i+1]==candidates[i]) // 去重操作
                    i++;
            }
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());  // 排序为了后期剪枝用
        vector<int> tmp_ans;
        ans.clear();
        DFS(candidates, target, 0, tmp_ans);
        return ans;
    }
};
-------------本文结束感谢您的阅读-------------
您的鼓励就是我创作的动力，求打赏买面包~~
0%