算法

准备考研机试做的Leetcode题目

string：size方法，substr（第一个，长度）
vector：size, push_back, pop_back方法，front、back函数是返回引用
stack: size, empty, top, pop, push
map：map<string, int>，之后可以用find，如果查找不到得到的就是end
stack：push、size、top、pop

73 zeros

矩阵中0的同行同列设置成0：常数空间：直接用第一行记录这一行/列是否为0，再记录一下第一行和第一列需不需要为0

74 Search a 2D Matrix

在一个全部排序好的数组中寻找元素，返回是否在：直接二分

75 Sort Colors

排序一个只有0、1、2的数组：一遍扫描：

  • 三个指针分别指向当前的、0后面的一位、2前方的一位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int i_0 = 0, i, i_2 = nums.size() - 1;  // i是遍历的，i_0是连续的0后面的，i_2是连续的2前面的
        for (i = 0; i <= i_2; i++) {
            if (nums[i] == 0) {  // 这时i_0肯定<=i，所以不会有换掉后的问题
                nums[i] = nums[i_0];
                nums[i_0++] = 0;
            }
            else if (nums[i] == 2) {
                nums[i--] = nums[i_2];  // 因为可能有[1,2,0]这样交换的情况，换过来的有可能是小于1的数，如果不加上i--会有问题
                nums[i_2--] = 2;
            }
        }
    }
};

76. Minimum Window Substring

找到包含有某些指定字母的最小字符串，直接双指针判断，注意substr的用法。用数组记录下来所有的元素需要多少个、已有多少个即可。

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
class Solution {
public:
    string minWindow(string s, string t) {
        int i = 0, j = 0, min_length = s.size(), start = 0, end = -1, len = s.size(), t_len = t.size();
        if (t_len == 0) {
            return "";
        }
        int times[128] = {}, need[128] = {}, need_cnt = 0;
        for (int k = 0; k < t_len; k++) {
            need_cnt += 1;
            need[int(t[k])] += 1;
        }
        while (j < len) {
            if (need[int(s[j])]) {
                if (times[int(s[j])] < need[int(s[j])]) {
                    need_cnt -= 1;
                }
                times[int(s[j])] += 1;
            }
            if (need_cnt <= 0) {
                // 发现所有的字母了！
                while (i < j) {
                    if (!need[int(s[i])]) {
                        i++;
                    }
                    else if (times[int(s[i])] > need[int(s[i])]) {
                        times[int(s[i++])] -= 1;
                    }
                    else {
                        break;
                    }
                }
                if (j - i < min_length) {
                    min_length = j - i;
                    start = i;
                    end = j;
                }
            }
            j++;
        }
        return s.substr(start, end - start + 1);
    }
};

77. Combinations

找到长度为k的在1-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
34
35
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> nums;
        int now_index = 0, now_number = 1;
        while (true) {
            if (k - now_index <= n - now_number + 1) {
                if (now_index == k) {
                    // ok
                    ans.push_back(nums);
                    nums.pop_back();
                    now_index -= 1;
                }
                else {
                    nums.push_back(now_number);
                    now_index += 1;
                    now_number += 1;
                }
            }
            else {
                // try to pop
                if (nums.size() > 0) {
                    nums.pop_back();
                    now_index -= 1;
                    now_number = nums[now_index] + 1;
                }
                else {
                    break;
                }
            }
        }
        return ans;
    }
};

78 subsets

直接用每一个元素在不在集合中判断就行，用幂集对应的性质，用数字控制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        long long nums_all = 1 << nums.size();
        for (int i = 0; i < nums_all; i++) {
            vector<int> temp;
            int i_s = i;
            for (int j = 0; i_s; j++) {
                if (i_s % 2) {
                    temp.push_back(nums[j]);
                }
                i_s /= 2;
            }
            ans.push_back(temp);
        }
        return ans;
    }
};

或者直接递归

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:
    int len2;
    
public:
    vector<vector<int>> get(int i, vector<int>& nums) {
        if (i >= nums.size()) {
            return vector<vector<int>>({vector<int>({})});
        }
        vector<vector<int>> ans = get(i + 1, nums);
        int len = ans.size(), len2 = nums.size();
        for (int j = 0; j < len; j++) {
            vector<int> temp(ans[j]);
            temp.push_back(nums[len2 - i - 1]);
            ans.push_back(temp);
        }
        return ans;
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        len2 = nums.size();
        return get(0, nums);
    }
};

79 word search

直接递归

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class Solution {
private:
    int board_h, board_w, w_len;
    
public:
    bool check(vector<vector<char>>& board, string word, int now_i, int now_j, vector<vector<bool>>& record, int index) {
        if (index < w_len) {
            char w_now = word[index];
            if (now_i > 0) {
                // try left
                if (!record[now_i - 1][now_j] && board[now_i - 1][now_j] == w_now) {
                    record[now_i - 1][now_j] = true;
                    if (check(board, word, now_i - 1, now_j, record, index + 1)) {
                        return true;
                    }
                    record[now_i - 1][now_j] = false;
                }
            }
            
            if (now_i < board_h - 1) {
                // try right
                if (!record[now_i + 1][now_j] && board[now_i + 1][now_j] == w_now) {
                    record[now_i + 1][now_j] = true;
                    if (check(board, word, now_i + 1, now_j, record, index + 1)) {
                        return true;
                    }
                    record[now_i + 1][now_j] = false;
                }
            }
            
            if (now_j > 0) {
                // try left
                if (!record[now_i][now_j - 1] && board[now_i][now_j - 1] == w_now) {
                    record[now_i][now_j - 1] = true;
                    if (check(board, word, now_i, now_j - 1, record, index + 1)) {
                        return true;
                    }
                    record[now_i][now_j - 1] = false;
                }
            }
            
            if (now_j < board_w - 1) {
                // try left
                if (!record[now_i][now_j + 1] && board[now_i][now_j + 1] == w_now) {
                    record[now_i][now_j + 1] = true;
                    if (check(board, word, now_i, now_j + 1, record, index + 1)) {
                        return true;
                    }
                    record[now_i][now_j + 1] = false;
                }
            }
        }
        else {
            return true;
        }
        return false;
    }
    
    bool exist(vector<vector<char>>& board, string word) {
        // search first letter
        char w0 = word[0];
        board_h = board.size();
        board_w = board[0].size();
        w_len = word.size();
        vector<vector<bool>> record;
        for (int i2 = 0; i2 < board_h; i2++) {
            vector<bool> temp;
            for (int j2 = 0; j2 < board_w; j2++) {
                temp.push_back(false);
            }
            record.push_back(temp);
        }
        for (int i = 0; i < board_h; i++) {
            for (int j = 0; j < board_w; j++) {
                if (board[i][j] == w0) {
                    // 从这里开始
                    record[i][j] = true;
                    if (check(board, word, i, j, record, 1)) {
                        return true;
                    }
                    record[i][j] = false;
                }
            }
        }
        return false;
    }
};

80. Remove Duplicates from Sorted Array II

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0, j = 0, now_cnt = 0, len = nums.size(), last_num = 0;
        if (len == 0) {
            return 0;
        }
        for (; i < len; i++) {
            if (nums[i] == last_num) {
                now_cnt ++;
            }
            else {
                last_num = nums[i];
                now_cnt = 1;
            }
            if (now_cnt < 3) {
                nums[j++] = nums[i];
            }
        }
        return j;
    }
};

81 search in rotated sorted array 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
class Solution {
public:
    bool search2(vector<int>& nums, int target, int left, int right, bool ordered) {
        if (left > right) {
            return false;
        }
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            return true;
        }
        if (ordered) {
            if (nums[mid] < target) {
                return search2(nums, target, mid + 1, right, ordered);
            }
            return search2(nums, target, left, mid - 1, ordered);
        }
        return search2(nums, target, left, mid - 1, nums[mid] > nums[left]) || search2(nums, target, mid + 1, right, nums[mid] < nums[right]);
    }
    
    bool search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        if (right < 0) {
            return false;
        }
        return search2(nums, target, left, right, nums[left] < nums[right]);
    }
};

82 remove duplicates from sorted list 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
31
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode new_head(0);
        ListNode* now = &new_head;
        // ListNode* check = head;
        while (head) {
            if (head->next && head->next->val == head->val) {
                // move
                int now = head->val;
                head = head->next;
                while (head) {
                    if (head->val == now) {
                        head = head->next;
                    }
                    else {
                        break;
                    }
                }
            }
            else {
                now->next = head;
                now = head;
                head = head->next;
            }
        }
        now->next = NULL;
        return new_head.next;
    }
};

84. Largest Rectangle in Histogram

直方图中最大的长方形：

一种方法：可以观察到，只需要判断比后面一个大的位置，将它作为右边界即可。因为如果一个的右边界比他右边的低，就可以把他右边的这个带上。

但是每一个右边界对应的位置，他左边所有可能的情况都要找一遍。

另一种方法：https://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html

只储存递增的，因为每一次只需要找它左侧比他低的东西。

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
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        stack<int> increase_index, increase_data;
        heights.push_back(0);
        increase_data.push(0);
        increase_index.push(-1);
        int now_highest = 0;
        int len = heights.size();
        for (int i = 0; i < len; i++) {
            if (heights[i] > now_highest) {
                now_highest = heights[i];
                increase_data.push(now_highest);
                increase_index.push(i);
            }
            else if (heights[i] < now_highest) {
                now_highest = heights[i];
                // check!
                while (increase_data.top() >= now_highest) {
                    if (now_highest == 0 && increase_data.top() == 0) {
                        break;
                    }
                    increase_index.pop();
                    int data = increase_data.top();
                    increase_data.pop();
                    int index = increase_index.top();
                    int temp = (i - index - 1) * data;
                    if (ans < temp) {
                        ans = temp;
                    }
                }
                increase_data.push(now_highest);
                increase_index.push(i);
            }
            else {
                increase_index.pop();
                increase_index.push(i);
            }
        }
        return ans;
    }
};

85. Maximal Rectangle

每行分别作为一个直方图考虑，看它上面的有多少个连续的1就是直方图这个位置有多少个1

86. Partition List

可以选择进行交换，或者是直接新建一个列表来储存小于x的元素。

交换的时候记得换到的位置和要换走的位置前后都要注意考虑！

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
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode newHead(0);
        newHead.next = head;
        ListNode *lastSmaller = &newHead, *nowNode = head, *temp, *temp2, *lastNode = &newHead;
        while (nowNode) {
            if (nowNode->val < x) {
                lastSmaller = nowNode;
            }
            else if (nowNode->val >= x) {
                lastNode = nowNode;
                nowNode = nowNode->next;
                break;
            }
            lastNode = nowNode;
            nowNode = nowNode->next;
        }
        while (nowNode) {
            temp2 = nowNode->next;
            if (nowNode->val < x) {
                temp = lastSmaller->next;
                lastSmaller->next = nowNode;
                lastSmaller = nowNode;
                lastSmaller->next = temp;
                lastNode->next = temp2;
            }
            else {
                lastNode = nowNode;
            }
            nowNode = temp2;
        }
        return newHead.next;
    }
};

87. Scramble String

分治。记得要先判断排序后是不是相同的字符串！这样可以减少很多

89. Gray Code

每个数字和前一个只差二进制的一位，给了二进制表示时候一共n位

其实就是从0开始，先把第n位保持不变，对后面的进行操作（变成了n-1的问题），之后改变第n位，对后面的n-1位进行操作

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:
    void checkPositionN(vector<int>& ans, int N, int& nowNum) {
        // do N-1
        // change
        // do N-1
        if (N < 0) {
            ans.push_back(nowNum);
        }
        else {
            checkPositionN(ans, N - 1, nowNum);
            nowNum = nowNum ^ (1 << N);
            checkPositionN(ans, N - 1, nowNum);
        }
    }
    
    vector<int> grayCode(int n) {
        vector<int> ans;
        // Each time, reverse one
        int now = 0;
        checkPositionN(ans, n - 1, now);
        return ans;
    }
};

300. Longest Increasing Subsequence

动态规划，记录下来长度为n的数组的最后一位，如果发现新的一位的大小小于最后一位的大小，就把最后一位更新为这个

比如长度为2: 1, 3；长度为3: 1, 3, 5；长度为4: 1, 3, 5, 7：

  • 来了一个4，就把长度为3的最后一位更新为4

376. Wiggle Subsequence

摆动子序列只需要观察一位和之前一位的关系即可，不用记录之前的数会是多少。

第5位比第4位小，那把前4位组成的最后一次是增的摆动数列调整一下可以让最后一位变成第四位，从而使得前5位变成最后一次是减少的摆动数列。

最长公共子数列

只需要记录A数组最后一位是第i位和B数组最后一位是第j位的最长公共子序列的长度。

0-1背包问题

按照顺序依次判断放不放，放的话更新当前的空位和价值。数组以物品和空位为下标，a[i][j]记录体积加起来不超过j的物品在判断到i的时候的价值。也可以只保留下标j，因为物品是按照顺序放的。

但是要循环的顺序反过来！！！

416. Partition Equal Subset Sum

直接用动态规划，记录和为i的是否可以达到

494. Target Sum

正的*2-所有的和=规定的数，和416一样

474. Ones and Zeroes

用m个0和n个1组成给定数组中尽可能多的字符串，和背包一样。是多重背包，需要有两个下标分别记录0和1的个数。

找零钱最少硬币数目

完全背包，需要正序遍历！！！

找零钱硬币数组合的数目

完全背包，状态转换方程改为+coins[i-adder]而不是+1

有顺序的完全背包问题

普通完全背包问题是外层循环放第几个物品，现在是内层循环来循环第几个物品

股票问题

记录当前状态，设计状态机。

删掉字符使得两个字符串相等

使用最长公共子序列长度