Celery's Blog

0%

LeetCode-Day28

发表于 更新于 Valine：

221. 最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

1
2
3
4
5
6
7
8
输入: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

思路：这里仍然采用了动态规划的思路，dp[i][j]表示以(i, j)为右下角的最大的正方形的边长，当matrix[i][j] = ‘1’时， 就沿着x = j和y = i看看能扩展多长。

如图：

![img](file:///C:\Users\12751\Documents\Tencent Files\1275121799\Image\C2C{A3A8F3A4-FB78-F227-FF39-EB244569E139}.png)

所以Code如下：

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 maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.empty()) {
            return 0;
        }
        int row = matrix.size(), col = matrix[0].size();    
        int dp[row][col] = {{0}};
        int maxN = 0;
        for(int i = 0;i < col;i++) {
            dp[0][i] = matrix[0][i] == '1' ? 1 : 0;
            maxN = max(maxN, dp[0][i]);
        }
        for(int i = 0;i < row;i++) {
            dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
            maxN = max(maxN, dp[i][0]);
        }
        for(int i = 1;i < row;i++) {
            for(int j = 1;j < col;j++) {
                dp[i][j] = 0;
                if(matrix[i][j] == '1') {
                    int count = dp[i - 1][j - 1];
                    while(count >= 0 && matrix[i - dp[i - 1][j - 1] + count][j] == '1' && matrix[i][j - dp[i - 1][j - 1] + count] == '1') {
                        count--;
                        dp[i][j]++;
                    }
                    maxN = max(maxN, dp[i][j]);
                }
            }
        }
        return maxN * maxN;
    }
};

316. 去除重复字母

给定一个仅包含小写字母的字符串，去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1:

1
2
输入: "bcabc"
输出: "abc"

示例 2:

1
2
输入: "cbacdcbc"
输出: "acdb"

思路：贪心算法

这道题的思路首先在于如何处理这个消除字母的标准，也就是如何贪心？

设想一下，如果是我们自己来处理这个问题，我们会如何思考。首先看一下当前字母前面有没有字典序比它大的字母，如果有的话，就看看这个字母后面的串中是不是还会出现，如果不出现，就不要动他了，如果出现了，就把它删掉。

所以，思路就出来了，最终我们采用栈的方法去解决这个问题

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
class Solution {
public:
    string removeDuplicateLetters(string s) {
        if(s.length() == 0) {
            return "";
        } 
        // 统计每个字母的个数
        int word[26] = {0};
        // 统计每个字符现在是否在栈中
        bool isIn[26] = {0};
        // 统计每个字母出现的次数
        for(int i = 0;i < s.length();i++) {
            word[s[i] - 'a']++;
        }
        stack<char> st;
        for(int i = 0;i < s.length();i++) {
            word[s[i] - 'a']--;
            // 如果该字母还没有进栈
            if(!isIn[s[i] - 'a']) {
                while(!st.empty()) {
                    //如果栈顶字母的比当前的s[i]要大并且后面还会出现该字母，则可以考虑删掉，即出栈
                    if(!st.empty() && st.top() > s[i] && word[st.top() - 'a'] > 0) {
                        isIn[st.top() - 'a'] = false;
                        st.pop();		
                    } else {
                        break;	// 处理完就直接出栈
                    }
                }
                // 该字母进栈
                st.push(s[i]);
                isIn[s[i] - 'a'] = true;    
            }
        }
        // 按照出栈的顺序反向建立该string
        string str = "";
        while(!st.empty()) {
            str = st.top() + str;
            st.pop();
        }
        return str; 
    }
};

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 1:

1
2
3
输入: [1,7,4,9,2,5]
输出: 6 
解释: 整个序列均为摆动序列。

示例 2:

1
2
3
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

示例 3:

1
2
输入: [1,2,3,4,5,6,7,8,9]
输出: 2

思路：贪心算法（虽然我也不知道这个竟然算贪心的…）

就是维护一个变量up，表示当前应该寻找的是更大的还是更小的数字来维护这一个摆动序列

例如，示例里面的[1,17,5,10,13,15,10,5,16,8]

当读到1, 17的时候，up应该变成-1，即表示，下一个要寻找的数字应该是比17要小的，如果比17大，则继续往下找比该数字小的数字，知道满足nums[i] >< nums[i - 1]未知，满足之后up就应该变成1，即下一个需要找的数是需要满足nums[i] > nums[i - 1]的。

所以Code如下：

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 wiggleMaxLength(vector<int>& nums) {
        if(nums.size() < 2) {
            return nums.size();
        }
        int sum = 1;
        bool allsame = true;
        int up;
        if(nums[1] > nums[0]) {
            up = 1;
        } else if(nums[1] < nums[0]) {
            up = -1;
        } else {
            up = 0;
        }
        for(int i = 1;i < nums.size();i++) {
            if(nums[i] != nums[i - 1] && allsame) {
                allsame = false;
                up = nums[i] > nums[i - 1] ? -1 : 1;
                sum++;
            } else if(up == 1 && nums[i] > nums[i - 1]) {
                up = -up;
                sum++;
            } else if(up == -1 && nums[i] < nums[i - 1]) {
                up = -up;
                sum++;
            } 
            // cout << "sum = " << sum << endl;
        }    
        if(allsame) {
            return 1;
        }
        return sum < 2 ? 2 : sum;
    }
};

注释：这里比较复杂的是判断初始的情况以及，全部都是同一个数的情况。

初始情况如果是两个数字相同，则当前up的值置为0， 即暂时还不能判断，知道nums[i] != nums[i - 1]，此时需要更新up的值。

如果所有的数字都是同一个的话，就应该返回1.

330. 按要求补齐数组

给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

示例 1:

1
2
3
4
5
6
7
输入: nums = [1,3], n = 6
输出: 1 
解释:
根据 nums 里现有的组合 [1], [3], [1,3]，可以得出 1, 3, 4。
现在如果我们将 2 添加到 nums 中， 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
其和可以表示数字 1, 2, 3, 4, 5, 6，能够覆盖 [1, 6] 区间里所有的数。
所以我们最少需要添加一个数字。

示例 2:

1
2
3
输入: nums = [1,5,10], n = 20
输出: 2
解释: 我们需要添加 [2, 4]。

示例 3:

1
2
输入: nums = [1,2,2], n = 5
输出: 0

思路：贪心算法

直觉：

对于任何缺少的数字，如果我们想让和能覆盖到它，我们必须添加至少一个小于或等于该数字的数字。否则，将无法覆盖到。想象你要给一个人x分钱的零钱，但你没有足够的硬币。你肯定会需要面额小于或等于x的硬币。

算法：

假设 miss 是缺少的数字中最小的，则区间 [1, miss) (左闭右开) 已经被完全覆盖。为了覆盖 miss，我们需要添加某些小于等于 miss 的数字。否则将不可能覆盖到。

例如，数组 nums = [1,2,3,8]， n = 16。已经覆盖到的数字有区间 [1, 6] 和 [8, 14]。换而言之，7, 15, 16 没有覆盖到。如果你加的数字大于 7，则 7 依然覆盖不到。

假设我们添加的数字是 x，则区间 [1, miss) 和 [x, x + miss) 均被覆盖到。由于我们知道 x <= miss，这两个区间必然覆盖了区间 [1, x + miss)。我们希望能够尽可能选择大的 x，这样覆盖的范围就可以尽可能大。因此，最好的选择是 x = miss。

在覆盖到 miss 后，我们可以重新计算覆盖范围，查看新的最小的缺少数字。然后加上该数字。重复操作直到全部数字都被堵盖到。

所以，整个贪心算法的流程如下：

  • 初始化区间[1, miss) = [1, 1) = 空

  • 每当n没有被覆盖

    • 若当前元素nums[i]小于等于miss
      • 将范围扩展到[1, miss + nums[i])
      • 将i增加1
    • 否则，将miss添加到数组，将范围扩展到[1, miss + miss)
    • 增加数字的计数

  • 返回增加的数字

Code如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        int patches = 0, i = 0;
        long miss = 1;
        while(miss <= n) {
            if(i < nums.size() && nums[i] <= miss) {
                miss += nums[i++];
            } else {
                miss += miss;
                patches++;
            }
        }
        return patches;
    }
};