LeetCode 分类刷题笔记_leedcode做分类笔记

第一周：贪心算法

2021年3月22日 - 2021年3月~日

贪心的定义：

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

Easy：

1. 分割平衡字符串（1221）

在一个 平衡字符串 中，‘L’ 和 ‘R’ 字符的数量是相同的。给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
注意：分割得到的每个字符串都必须是平衡字符串。返回可以通过分割得到的平衡字符串的 最大数量 。

示例：
输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' > 和 'R' 。
1
2
3
4

理解：
只需要遍历一遍数组，用一个变量记录之前的“R”、“L”是否平衡。如果平衡，则当前状况就可以作为一个切分，因为所求为最大切分的数量，则局部最优即可。

一般方法解决：

class Solution {
public:
    int balancedStringSplit(string s) {
        int count = 0, res = 0;
        for (char i : s){
            if (i == 'L'){ count += 1; }
            else{ count -= 1; }
            if (count == 0){ res += 1; }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

可用栈解决：

class Solution {
public:
    int balancedStringSplit(string s) {
        stack<char> st;
        int res = 0;
        for (char i : s){
            if (st.empty() || st.top() == i){ st.push(i); }
            else{
                st.pop();
                if (st.empty()){ res += 1; }
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. 可以形成最大正方形的矩形数目（1725）

给你一个数组 rectangles ，其中 rectangles[i] = [li, wi] 表示第 i 个矩形的长度为 li 、宽度为 wi 。
如果存在 k 同时满足 k <= li 和 k <= wi ，就可以将第 i 个矩形切成边长为 k 的正方形。例如，矩形 [4,6] 可以切成边长最大为 4 的正方形。
设 maxLen 为可以从矩形数组 rectangles 切分得到的 最大正方形 的边长。
返回可以切出边长为 maxLen 的正方形的矩形 数目 。

示例：
输入：rectangles = [[5,8],[3,9],[5,12],[16,5]]
输出：3
解释：能从每个矩形中切出的最大正方形边长分别是 [5,3,5,5] 。最大正方形的边长为 5 ，可以由 3 个矩形切分得到。
1
2
3
4

理解：
遍历一遍数组，记录当前切出的最大正方形边长及个数，每次遇到新的最大正方形，更新最大边长值及个数。

class Solution {
public:
    int countGoodRectangles(vector<vector<int>>& rectangles) {
        int res = 1, temp = 0;
        for (auto i : rectangles){
            int x = min(i[0], i[1]);
            if (temp < x){
                temp = x;
                res = 1;
            }
            else if (temp == x){ res++; }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Medium：

1. 十-二进制数的最少数目（1689）

如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1 ，那么该数字就是一个 十-二进制数 。
例如，101 和 1100 都是 十-二进制数，而 112 和 3001 不是。
给你一个表示十进制整数的字符串 n ，返回和为 n 的 十-二进制数 的最少数目。

示例：
输入：n = "32"
输出：3
解释：10 + 11 + 11 = 32
1
2
3
4

理解：
每一位数字都要被 n 个 1 拆分，则将问题转换成了求十进制数字最大数字位，当遍历到 9 时可直接返回。

class Solution {
public:
    int minPartitions(string n) {
        char res = '0';
        for (char i : n){
            if (i == '9') { return 9; }
            if (res < i) { res = i; }
        }
        return int(res)-int('0');
    }
};
1
2
3
4
5
6
7
8
9
10
11

2. 用户分组（1282）

有 n 位用户参加活动，他们的 ID 从 0 到 n - 1，每位用户都恰好属于某一用户组。给你一个长度为 n 的数组 groupSizes，其中包含每位用户所处的用户组的大小，请你返回用户分组情况（存在的用户组以及每个组中用户的 ID）。
你可以任何顺序返回解决方案，ID 的顺序也不受限制。此外，题目给出的数据保证至少存在一种解决方案。

示例：
输入：groupSizes = [3,3,3,3,3,1,3]
输出：[[5],[0,1,2],[3,4,6]]
解释： 
其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。
1
2
3
4
5

理解：
注意关键：保证至少存在一种解决方案！
根据组大小不相同的用户不可能在一个组，进行粗分组，用哈希存储；遍历哈希，如果组大小刚好，则取出；如果组大小溢出，则说明可以被细分为若干组。

哈希辅助存储：

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> res;
        map<int, vector<int>> temp;
        for (int i = 0; i < groupSizes.size(); i++){
            temp[groupSizes[i]].push_back(i);
        }
        map<int, vector<int>>::iterator iter;
        for (iter = temp.begin(); iter != temp.end(); iter++){
            if (iter->first == iter->second.size()){
                res.push_back(iter->second);
            }else{
                vector<int> ttt(iter->first);
                for (int i = 0; i < iter->second.size(); i++){
                    if (i == 0){
                        ttt = {iter->second[i]};
                    }else if (i % iter->first == 0){
                        res.push_back(ttt);
                        ttt = {iter->second[i]};
                    }else{
                        ttt.push_back(iter->second[i]);
                    }
                }
                res.push_back(ttt);
            }
        }
        return res;
    }
};
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

---

。。。。。。