LeetCode71-80

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

71、简化路径

模拟题

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:
    string simplifyPath(string path) {
        for(int i=1; i<path.length(); i++){
            if(path[i-1]=='/' && path[i]=='/')
                path.erase(i--,1);
        }
        if(path[path.length()-1]=='/')
            path.erase(path.length()-1);
        vector<string> fenduan;
        int pos = 0, index;
        while(pos>=0 && pos<path.length()){
            index = path.find('/', pos+1);
            fenduan.push_back(path.substr(pos, index-pos));
            pos = index;
        }
        string ans = "";
        for(auto i : fenduan){
            if(i=="/.")
                continue;
            else if(i=="/.."){
                index = ans.find_last_of('/');
                if(index>=0 && index<ans.size())
                    ans.erase(index);
            }
            else
                ans += i;
        }
        if(ans.size()==0)
            ans = "/";
        return ans;
    }
};

72、编辑距离

DP 题，状态转移方程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length(), len2 = word2.length();
        int ans[len1+1][len2+1];
        memset(ans, 0, sizeof(ans));
        for(int i=0; i<=len1; i++)
            ans[i][0] = i;
        for(int i=0; i<=len2; i++)
            ans[0][i] = i;
        for(int i=1; i<=word1.length(); i++){
            for(int j=1; j<=word2.length(); j++){
                if(word1[i-1]==word2[j-1])
                    ans[i][j] = ans[i-1][j-1];
                else
                    ans[i][j] = 1+min(ans[i-1][j-1], min(ans[i-1][j], ans[i][j-1]));
            }
        }
        return ans[len1][len2];
    }
};

73、 矩阵置零

模拟题，O(1) 的空间的 trick ，使用矩阵的第一行和第一列记录该行/列中有无 0 元素，同时注意使用 col1_has_zero 和 row1_has_zero 两个变量记录第一行/列有无 0 元素。

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
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool row1_has_zero = false, col1_has_zero = false;
        for(int i=0; i<matrix.size(); i++)
            if(matrix[i][0]==0){
                col1_has_zero = true;
                break;
            }
        for(int i=0; i<matrix[0].size(); i++)
            if(matrix[0][i]==0){
                row1_has_zero = true;
                break;
            }
        for(int i=1; i<matrix.size(); i++){
            for(int j=1; j<matrix[0].size(); j++){
                if(matrix[i][j]==0){
                    matrix[0][j] = matrix[i][0] = 0;
                }
            }
        }
        for(int i=1; i<matrix.size(); i++){
            for(int j=1; j<matrix[0].size(); j++){
                if(!matrix[0][j] || !matrix[i][0]){
                    matrix[i][j] = 0;
                }
            }
        }
        if(row1_has_zero){
            for(int i=0; i<matrix[0].size(); i++)
                matrix[0][i] = 0;
        }
        if(col1_has_zero){
            for(int i=0; i<matrix.size(); i++)
                matrix[i][0] = 0;
        }
    }
};

74、搜索二维矩阵

二分查找，先按照行查找，再按照列查找。

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 {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0 || matrix[0].size()==0)
            return false;
        int L = 0, R = matrix.size()-1, Middle = 0;
        // 二分查找
        while(L<R){
            Middle = (L+R) >> 1;
            if(target<matrix[Middle][0])
                R = Middle - 1;
            else if(target>matrix[Middle][0]){
                if(target<=matrix[Middle][matrix[0].size()-1]){
                    L = Middle;
                    break;
                }
                L = Middle + 1;
            }
            else
                return true;
        }
        return binary_search(&matrix[L][0], &matrix[L][0]+matrix[0].size(), target);
    }
};

75、颜色分类

三路快排原理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void sortColors(vector<int>& nums) {
        // 三路快排原理
        int p0 = 0, p1 = 0, p2 = nums.size()-1;
        while(p1<=p2){
            if(nums[p1]==0){
                swap(nums[p0], nums[p1]);
                p0++;
                p1++;
            }
            else if(nums[p1]==1){
                p1++;
            }
            else{
                swap(nums[p1], nums[p2]);
                p2--;
            }
        }
    }
};

76、最小覆盖子串

双指针 + 滑动窗口

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
class Solution {
public:
    string minWindow(string s, string t) {
        string ans = "";
        if(s.size()==0 || t.size()==0)
            return ans;
        int left = 0, right = 0, matchs = 0;
        int minLen = INT_MAX;
        unordered_map<char, int> window, need;
        for(int i=0; i<t.size(); i++)
            need[t[i]]++;
        int kinds = need.size();
        while(right<s.size()){
            if( ++window[s[right]] == need[s[right++]] )
                matchs++;
            if(matchs==kinds){
                while(left<right){
                    if( --window[s[left]] < need[s[left++]] ){
                        matchs--;
                        break;
                    }
                }
                if(minLen>right-(left-1)){
                    minLen = right - (left-1);
                    ans = s.substr(left-1, minLen);
                }
            }
        }
        return minLen==INT_MAX? "" : ans;
    }
};

77、组合

简单深搜

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
class Solution {
public:
    void DFS(vector<vector<int>>& ans, vector<int>& tmp_ans, int position, int n, int k){
        if(n-position+1+tmp_ans.size() < k)
            return ;
        if(tmp_ans.size()==k){
            ans.push_back(tmp_ans);
            return ;
        }
        for(int i=position; i<=n; i++){
            tmp_ans.push_back(i);
            DFS(ans, tmp_ans, i+1, n, k);
            tmp_ans.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> tmp_ans;
        for(int i=1; i<=n; i++){
            tmp_ans.push_back(i);
            DFS(ans, tmp_ans, i+1, n, k);
            tmp_ans.pop_back();
        }
        return ans;
    }
};

78、子集

深搜，水题一道

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void DFS(vector<vector<int>>& ans, vector<int>& tmp_ans, int position, vector<int>& nums){
        ans.push_back(tmp_ans);
        for(int i=position; i<nums.size(); i++){
            tmp_ans.push_back(nums[i]);
            DFS(ans, tmp_ans, i+1, nums);
            tmp_ans.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> tmp_ans;
        DFS(ans, tmp_ans, 0, nums);
        return ans;
    }
};

79、单词搜索

基础深搜题，注意剪枝即可。

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
class Solution {
public:
    int direct[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};

    bool judge(int n, int m, int row, int col){
        return row>=0 && row<n && col>=0 && col<m;
    }

    bool DFS(vector<vector<char>>& board, string word, vector<vector<bool>>& used, int row, int col, int pos){
        if(pos==word.size()-1)
            return true;
        used[row][col] = true;
        for(int i=0; i<4; i++){
            int tmp_row = row + direct[i][0];
            int tmp_col = col + direct[i][1];
            if(judge(board.size(), board[0].size(), tmp_row, tmp_col) && used[tmp_row][tmp_col]==false && board[tmp_row][tmp_col]==word[pos+1]){
                if(DFS(board, word, used, tmp_row, tmp_col, pos+1))
                    return true;
            }
        }
        used[row][col] = false;
        return false;
    }

    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size(), m = board[0].size();
        vector<vector<bool>> used(n, vector<bool>(m, false));
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if( board[i][j]==word[0] && DFS(board, word, used, i, j, 0) )
                    return true;
            }
        }
        return false;
    }
};

80、删除排序数组中的重复项 II

双指针的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()<=2)
            return nums.size();
        int p_front=2, p_back=2;
        while(p_back<nums.size()){
            if(nums[p_back]==nums[p_front-2])
                p_back++;
            else
                nums[p_front++] = nums[p_back++];
        }
        return p_front;
    }
};

-------------本文结束感谢您的阅读-------------
您的鼓励就是我创作的动力，求打赏买面包~~
0%