922

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

示例：

输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

提示：

• 2 <= A.length <= 20000
• A.length % 2 == 0
• 0 <= A[i] <= 1000

方法二： 双指针
思路与算法

最简单的想法可能是再开辟个等大的数组，遍历原数组，遇到奇数就放新数组的奇数位置，偶数就放偶数位置。
但因为现在只要把数分为奇数和偶数两类，可以用交换代替。因为一半奇数一半偶数。只要让偶数位置全是偶数，那么奇数位置也自然都是奇数了。
设置两个指针：

• even_find_odd指针从0开始，判断该位置是不是偶数，如果是指向下一个偶数位置，如果是奇数进入下一步操作。
• odd_find_even从1开始，判断该位置是不是奇数，如果是指向下一个奇数位置，如果是偶数进入下一步操作。
• 这时，even_find_odd指针指的是奇数，而odd_find_even指的是偶数，都与要求刚好相反，那么交换就好辣。
• 这样遍历完后even_find_odd指针经过的位置都变成了偶数，odd_find_even指针经过的位置都变成了奇数。
• even_find_odd就是指在偶数位置找奇数，odd_find_even就是在奇数位置找偶数，不得不说我起名有一手。

vector<int> sortArrayByParityII(vector<int> &A) {
    if (A.empty()) return A;
    int odd_find_even = 1, even_find_odd = 0;
    for (; even_find_odd < A.size(); even_find_odd += 2) {
        if (A[even_find_odd] & 1) {
            while (A[odd_find_even] & 1) {
                odd_find_even += 2;
            }
            swap(A[even_find_odd], A[odd_find_even]);
        }
    }
    return A;
}

1122

给你两个数组，arr1 和 arr2，

• arr2 中的元素各不相同
• arr2 中的每个元素都出现在 arr1 中

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

提示：

• arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• arr2 中的元素 arr2[i] 各不相同
• arr2 中的每个元素 arr2[i] 都出现在 arr1 中

方法一：计数排序

思路与算法

注意到本题中元素的范围为 [0,1000]，这个范围不是很大，我们也可以考虑不基于比较的排序，例如「计数排序」。
具体地，我们使用一个长度为 1001（下标从 0 到 1000）的数组 \textit{frequency}，记录每一个元素在数组 \textit{arr}_1中出现的次数。随后我们遍历数组 \textit{arr}_2，当遍历到元素 x 时，我们将 \textit{frequency}[x] 个 x 加入答案中，并将 \textit{frequency}[x] 清零。当遍历结束后，所有在 \textit{arr}_2中出现过的元素就已经有序了。此时还剩下没有在 \textit{arr}_2中出现过的元素，因此我们还需要对整个数组 \textit{frequency} 进行一次遍历。当遍历到元素 x 时，如果\textit{frequency}[x] 不为 0，我们就将 \textit{frequency}[x] 个 x 加入答案中。

细节

我们可以对空间复杂度进行一个小优化。实际上，我们不需要使用长度为 1001 的数组，而是可以找出数组 \textit{arr}_1中的最大值 \textit{upper}，使用长度为 \textit{upper}+1 的数组即可。

代码

class Solution {
public:
    vector<int> relativeSortArray(vector<int> &arr1, vector<int> &arr2) {
        vector<int> ans;//存放结果，初始化为空
        int maxNum = *max_element(arr1.begin(), arr1.end());//找母数组中最大的值，因为要新建频率数组下标对应次数，下标最大就是最大的值
        vector<int> frequency(maxNum + 1, 0);//下标最大时maxNum，所以数组长度应该+1，初始化为0
        for (int val:arr1) {
            ++frequency[val];//遍历母数组，将值赋给i，将频率数组i对应下标的值+1
        }
        for (int arr1_arr2:arr2) {//顺序遍历arr2查找arr1出现的频率，按arr2顺序遍历就使查找结果维持了arr2顺序不变
            while (frequency[arr1_arr2]--) {//arr1中的arr2值在频率数组对应的下标中，出现几次就循环几次
                ans.push_back(arr1_arr2);//先将arr2对应的值加入结果
            }
        }
        //此时还剩没有出现的值，因为题目要求从小到大，而在创建频率数组的时候，以值作为下标存放次数已经相当于从小到大排好了，直接顺序遍历频率数组
        for (int val = 0; val < maxNum + 1; ++val) {
            while (0 < frequency[val]--) {//写大于0更清晰，表示频率几次循环几次
                ans.push_back(val);
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度：O(m + n + \textit{upper})，其中 m 和 n 分别是数组 \textit{arr}_1 和 \textit{arr}_2 的长度，\textit{upper} 是数组 \textit{arr}_1 中的最大值，在本题中 \textit{upper} 不会超过 1000。遍历数组 \textit{arr}_2的时间复杂度为 O(n)，遍历数组 \textit{frequency} 的时间复杂度为 O(\textit{upper})，而在遍历的过程中，我们一共需要 O(m) 的时间得到答案数组。

空间复杂度：O(\textit{upper})，即为数组 \textit{frequency} 需要使用的空间。注意到与方法一不同的是，方法二的代码使用了额外的空间（而不是直接覆盖数组 \textit{arr}_1存放答案，但我们一般不将存储返回答案的数组计入空间复杂度，并且在我们得到数组 \textit{frequency} 之后，实际上也是可以将返回答案覆盖在数组 \textit{arr}_1上的。如果在面试中遇到了本题，这些细节都可以和面试官进行确认。

402

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

• num 的长度小于 10002 且 ≥ k。
• num 不会包含任何前导零。

示例 1 :

输入: num = “1432219”, k = 3
输出: “1219”
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例 2 :

输入: num = “10200”, k = 1
输出: “200”
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 :

输入: num = “10”, k = 2
输出: “0”
解释: 从原数字移除所有的数字，剩余为空就是0。

方法一：贪心 + 单调栈

对于两个相同长度的数字序列，最左边不同的数字决定了这两个数字的大小，例如，对于 A = 1axxx，B = 1bxxx，如果 a > b 则 A > B。
基于此，我们可以知道，若要使得剩下的数字最小，需要保证靠前的数字尽可能小。

让我们从一个简单的例子开始。给定一个数字序列，例如 425，如果要求我们只删除一个数字，那么从左到右，我们有 4、2 和 5 三个选择。我们将每一个数字和它的左邻居进行比较。从 2 开始，2 小于它的左邻居 4。假设我们保留数字 4，那么所有可能的组合都是以数字 4（即 42，45）开头的。相反，如果移掉 4，留下 2，我们得到的是以 2 开头的组合（即 25），这明显小于任何留下数字 4 的组合。因此我们应该移掉数字 4。如果不移掉数字 4，则之后无论移掉什么数字，都不会得到最小数。
基于上述分析，我们可以得出「删除一个数字」的贪心策略：

给定一个长度为 n 的数字序列 [D_0D_1D_2D_3\ldots D_{n-1}]，从左往右找到第一个位置 i（i>0）使得 D_i<D_{i-1}，并删去 D_{i-1} ；如果不存在，说明整个数字序列单调不降，删去最后一个数字即可。基于此，我们可以每次对整个数字序列执行一次这个策略；删去一个字符后，剩下的 n−1 长度的数字序列就形成了新的子问题，可以继续使用同样的策略，直至删除 k 次。
然而暴力的实现复杂度最差会达到 O(nk)（考虑整个数字序列是单调不降的），因此我们需要加速这个过程。
考虑从左往右增量的构造最后的答案。我们可以用一个栈维护当前的答案序列，栈中的元素代表截止到当前位置，删除不超过 k 次个数字后，所能得到的最小整数。根据之前的讨论：在使用 k 个删除次数之前，栈中的序列从栈底到栈顶单调不降。
因此，对于每个数字，如果该数字小于栈顶元素，我们就不断地弹出栈顶元素，直到

• 栈为空
• 或者新的栈顶元素不大于当前数字
• 或者我们已经删除了 k 位数字

上述步骤结束后我们还需要针对一些情况做额外的处理：

• 如果我们删除了 m 个数字且 m<k，这种情况下我们需要从序列尾部删除额外的 k−m 个数字。
• 如果最终的数字序列存在前导零，我们要删去前导零。
• 如果最终数字序列为空，我们应该返回 0。

最终，从栈底到栈顶的答案序列即为最小数。
考虑到栈的特点是后进先出，如果通过栈实现，则需要将栈内元素依次弹出然后进行翻转才能得到最小数。为了避免翻转操作，可以使用双端队列代替栈的实现。

class Solution {
public:
    string removeKdigits(string num, int k) {
        string ans;
        for (auto &digit:num) {
            while (!ans.empty() && ans.back() > digit && k > 0) {//先判断要不要pop，不为空且末尾数字比要插入的大并且还没删k个
                ans.pop_back();
                --k;
            }
            ans.push_back(digit);
        }
        for (; k > 0; --k) {//如果还没删k个接着删末尾数字，因为是如果没删完，此时ans肯定是非降序排列的
            ans.pop_back();
        }
        while (ans.front() == '0') {//如果最后结果前面有0，就用erase()函数抹去
            ans.erase(ans.begin());
        }
        if (ans.empty()) return "0";//如果直接删完或者剩的全是0被抹去了那么就是空字符串，返回"0"
        return ans;
    }
};

复杂度分析

时间复杂度：O(n)，其中 n 为字符串的长度。尽管存在嵌套循环，但内部循环最多运行 k 次。由于 0<k≤n，主循环的时间复杂度被限制在 2n 以内。对于主循环之外的逻辑，它们的时间复杂度是 O(n)，因此总时间复杂度为 O(n)。

空间复杂度：O(n)。栈存储数字需要线性的空间。

erase()函数

stringl类也是一个容器，提供erase()函数来删除指定元素。
erase()一共三种用法：

• erase(pos,n);
  删除从下标pos开始的n个字符，比如erase(0,1)就是删除第一个字符
• erase(position);
  删除postion处的一个字符（position是一个string类型的迭代器）
• erase(first,last)
  删除从first到last之间的字符（first和last都是迭代器）

所以要删除第一个元素，就是用指向第一个元素的迭代器s.begin()，一开始我不知道用法瞎写了个s.erase(0)，竟然把s删完了。

for(auto c:s)与for(auto& c:s)

一种遍历容器中所有元素的写法

• 首先是左边 for(auto c:s)，就是遍历s容器，每次复制当前次序下相应的元素给c。注意这里是复制，就是要新建个变量c的。而对c进行操作并不会对s中相应的元素造成影响。
• 然后是右边 for(auto& c:s)，是遍历s容器，每次都让c作为s中相应元素的引用，就是把s[i]起个别名叫c，也就是没有新建变量，对c进行操作就是对s中当前次序下的元素进行操作，会影响s中相应的元素。
• 另外这里用的是auto。auto：用来声明自动变量。它是存储类型标识符，表明变量(自动)具有本地范围，块范围的变量声明(如for循环体内的变量声明)默认为auto存储类型。其实大多普通声明方式声明的变量都是auto变量,他们不需要明确指定auto关键字，默认就是auto的了。auto变量在离开作用域是会变程序自动释放，不会发生内存溢出情况(除了包含指针的类)。使用auto变量的优势是不需要考虑去变量是否被释放，比较安全。

406

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意：
总人数少于1100人。

示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

思路与算法

按照 h_i为第一关键字降序，k_i为第二关键字升序进行排序。如果我们按照排完序后的顺序，依次将每个人放入队列中，那么当我们放入第 i 个人时：

第0, \cdots, i-1个人已经在队列中被安排了位置，他们只要站在第 i 个人的前面，就会对第 i 个人产生影响，因为他们都比第 i 个人高；

而第 i+1, \cdots, n-1 个人还没有被放入队列中，并且他们无论站在哪里，对第 i 个人都没有任何影响，因为他们都比第 i 个人矮。

我们可以发现，后面的人既然不会对第 i 个人造成影响，我们可以采用「插空」的方法，依次给每一个人在当前的队列中选择一个插入的位置。也就是说，当我们放入第 i 个人时，只需要将其插入队列中，使得他的前面恰好有 k_i个人即可。

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>> &people) {
        sort(people.begin(), people.end(), [](const vector<int> &x, const vector<int> &y) {
            return x[0] > y[0] || (x[0] == y[0] && x[1] < y[1]);//无名函数自定义排序，就是告诉sort什么逻辑代表x<y
        });//因为k是前面大于或等于h的数目，所以重排后，h相同时，k小的一定再k大的前面，所以先排k小的
        vector<vector<int> > ans;
        for (const vector<int> &person :people) {//按排好的顺序每次拿出一个人进行插入
            ans.insert(ans.begin() + person[1], person);
            //每次插入的位置前面都正好有k人，也就是k个h大于等于要插入的人的h的人，但对已经插入的在要插入位置的后面的人没影响，因为都比要插入的人的h大
        }
        return ans;
    }
};

容器的insert()函数

• C++容器的insert()函数有以下三种用法: 最终*it=val

C++容器的insert()函数有以下三种用法: 最终*it=val;
//用法1:在指定位置it前“插入”值为val的元素,返回指向这个元素的迭代器,
iterator insert( iterator it, const TYPE &val ); 

//用法2:在指定位置it前“插入”num个值为val的元素 
void insert( iterator it, size_type num, const TYPE &val ); 

//用法3:在指定位置it前“插入”区间[start, end)的所有元素. 
void insert( iterator it, input_iterator start, input_iterator end ); 

举例: 
//创建一个vector,置入字母表的前十个字符 
vector <char> charV; 
for( int i=0; i < 10; i++ ) 
  charV.push_back( i + 65 ); 

//插入四个C到vector中 
vector <char>::iterator it = charV.begin(); 
charV.insert( it, 4, 'C' ); 

//显示vector的内容 
for( it = charV.begin(); it != charV.end(); it++ ) 
  cout < < *it; 

这段代码将显示:

CCCCABCDEFGHIJ

• 所以题解中ans.begin() + person[1]代表的是插入到ans.begin() + person[1]指向元素的前面，也就是插入到ans.begin() + person[1]指向的位置也就是前面有person[1]个元素的位置。

1030

给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。

另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。

返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。（你可以按任何满足此条件的顺序返回答案。）

示例 1：

输入：R = 1, C = 2, r0 = 0, c0 = 0
输出：[[0,0],[0,1]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1]

示例 2：

输入：R = 2, C = 2, r0 = 0, c0 = 1
输出：[[0,1],[0,0],[1,1],[1,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。

示例 3：

输入：R = 2, C = 3, r0 = 1, c0 = 2
输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。

提示：

• 1 <= R <= 100
• 1 <= C <= 100
• 0 <= r0 < R
• 0 <= c0 < C

方法一：直接排序

思路及解法

最容易想到的方法是首先存储矩阵内所有的点，然后将其按照哈曼顿距离直接排序。

复杂度分析

时间复杂度：O(RC \log(RC))，存储所有点时间复杂度 O(RC)，排序时间复杂度 O(RC \log(RC))。

空间复杂度：O(\log(RC))，即为排序需要使用的栈空间，不考虑返回值的空间占用。

方法二：桶排序

思路及解法

注意到方法一中排序的时间复杂度太高。实际在枚举所有点时，我们可以直接按照哈曼顿距离分桶。这样我们就可以实现线性的桶排序。

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
        int maxDistance = max(r0, R - 1 - r0) + max(c0, C - 1 - c0);
        //计算最大距离，这个比较巧妙，横纵坐标分开考虑，对于横坐标，到r0最大距离无非两个选择，最左端和最右端，最左端的距离就是r0，
        // 而最右端的距离就是最右端坐标减r0，而这里R是行数，最右端坐标应该是R-1
        vector<vector<vector<int>>> bucket(maxDistance + 1);//因为距离从0开始到maxDistance，所以桶的数量是maxDistance+1
        //这里注意是三个vector：因为一个桶里有多个二维数组，所以坐标的桶排序应该是三维
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {//遍历所有点
                int distance = countDistance(i, j, r0, c0);//计算该点到(r0,c0)距离
                vector<int> temp = {i, j};
                bucket[distance].push_back(move(temp));
            }
        }
        //因为桶是三维的，要输出二维vector要把桶里的坐标依次拿出来
        vector<vector<int> > ans;
        for (int i = 0; i <= maxDistance; ++i) {//遍历每一个桶
            for (auto &out:bucket[i]) {//对每一个桶的所有坐标进行遍历输出
                ans.push_back(out);
            }
        }
        return ans;
    }

    int countDistance(int r1, int c1, int r0, int c0) {//计算任意一点到(r0,c0)的距离
        return abs(r1 - r0) + abs(c1 - c0);
    }
};

Tips

注意到在将坐标放到指定桶中的程序bucket[distance].push_back(move(temp));用到了move()，虽然删除move程序依然正确，但是效率差距明显。。。

查找原因如下：

• 通过move将tmp的左值强制转化为右值引用
• 右值引用直接引用tmp对象，避免拷贝操作，从而减少新对象的创建和释放
• 应该是把tmp转为右值，tmp原本是一个左值，传递右值进push_back就不是拷贝操作了而是移动操作，相当于资源易手不同于直接的拷贝再删除tmp，性能会提高。
• push_back()函数引入对象时候，首先会调用构造函数生成这个对象，然后调用拷贝构造函数将这个对象放入容器中， 最后释放临时对象。但是emplace_back()函数向容器中加入临时对象， 临时对象原地构造，没有赋值或移动的操作。

134

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

*说明: *

• 如果题目有解，该答案即为唯一答案。
• 输入数组均为非空数组，且长度相同。
• 输入数组中的元素均为非负数。

示例 1:

输出:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3

解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

输入:
gas = [2,3,4]
cost = [3,4,3]

输出: -1

解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

方法一：一次遍历
思路与算法

最容易想到的解法是：从头到尾遍历每个加油站，并检查以该加油站为起点，最终能否行驶一周。我们可以通过减小被检查的加油站数目，来降低总的时间复杂度。
假设我们此前发现，从加油站 x 出发，每经过一个加油站就加一次油（包括起始加油站），最后一个可以到达的加油站是 y（不妨设 x<y）。这就说明：

\sum_{i=x}^{y}\textit{gas}[i]<\sum_{i=x}^{y}\textit{cost}[i]

\sum_{i=x}^{j}\textit{gas}[i]≥\sum_{i=x}^{j}\textit{cost}[i](For\ all\ j∈[x,y))

第一个式子表明无法到达加油站 y 的下一个加油站，第二个式子表明可以到达 y 以及 y 之前的所有加油站。
现在，考虑任意一个位于 x,y 之间的加油站 z（包括 x 和 y），我们现在考察从该加油站出发，能否到达加油站 y 的下一个加油站，也就是要判断 \sum_{i=z}^{y}\textit{gas}[i] 与 \sum_{i=z}^{y}\textit{cost}[i] 之间的大小关系。
根据上面的式子，我们得到：

\begin{aligned} \sum_{i=z}^{y}\textit{gas}[i]&=\sum_{i=x}^{y}\textit{gas}[i]-\sum_{i=x}^{z-1}\textit{gas}[i] \\ &< \sum_{i=x}^{y}\textit{cost}[i]-\sum_{i=x}^{z-1}\textit{gas}[i] \\ &< \sum_{i=x}^{y}\textit{cost}[i]-\sum_{i=x}^{z-1}cost[i] \\ &= \sum_{i=z}^{y}\textit{cost}[i] \end{aligned}

其中不等式的第二步、第三步分别利用了上面的第一个、第二个不等式。
从上面的推导中，能够得出结论：从 x,y 之间的任何一个加油站出发，都无法到达加油站 y 的下一个加油站。

在发现了这一个性质后，算法就很清楚了：我们首先检查第 0 个加油站，并试图判断能否环绕一周；如果不能，就从第一个无法到达的加油站开始继续检查。

int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    int num = gas.size();
    int i = 0;
    while (i < num) {
        int sumOfCost = 0;
        int sumOfGas = 0;
        int count = 0;
        while (count < num) {//从i出发能够移动count+1次，移动count次就是回到原点了，终止条件，能移动到(i+count+1)%num处
            int cnt = (i + count) % num;//用取余数直接可以实现循环移动，因为gas[i]>=cos[i]就代表能移动到i+1处，此处不加一
            sumOfCost += cost[cnt];
            sumOfGas += gas[cnt];
            if (sumOfCost > sumOfGas) break;//如果中间出现不能，直接跳出循环，[i,cnt]闭区间所有值都不能到达cnt+1点
            ++count; //计数，count表示从i出发能成功移动count次
        }
        if (count == num) return i;//从i开始能移动num次就是能回到i处了，说明从i开始能实现循环
        i = i + count + 1;
    }
    return -1;//所有点遍历完都不能的话输出-1
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组的长度。我们对数组进行了单次遍历。

• 空间复杂度：O(1)。

283

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

• 必须在原数组上操作，不能拷贝额外的数组。
• 尽量减少操作次数。

解法一：双指针

设两个指针，对于数组来说，下标就是指针。

快指针指向待处理序列头部，就是找非零元素。慢指针指向已经处理好的序列尾部，就是找非零元素要插入的位置。

因为要插入的位置是逐一连续增加的，所以是慢指针。而非零元素位置有可能是跳跃增加的，所以是快指针。

当快指针找完所有非零元素并移动后，此时慢指针指向处理好的非零序列的尾部，此时以该位置为起点到整个序列尾部全部置0即可。

注意到以下性质：

• 慢指针左边均为非零数；
• 快指针左边直到慢指针处均为零。
  因此每次交换，都是将慢指针的零与快指针的非零数交换，且非零数的相对顺序并未改变。

（图源@代码随想录https://leetcode-cn.com/problems/move-zeroes/solution/283-yi-dong-ling-shuang-zhi-zhen-xiang-jie-by-carl/）

class Solution {
public:
    void moveZeroes(vector<int> &nums) {
        int findNoZero = 0;
        int NoZeroInsert = 0;
        for (; findNoZero < nums.size(); ++findNoZero) {
            if (nums[findNoZero] != 0) {
                nums[NoZeroInsert++] = nums[findNoZero];
            }
        }
        while (NoZeroInsert < nums.size()) {
            nums[NoZeroInsert++] = 0;
        }
    }
};

复杂度分析

• 时间复杂度：O(n)，其中 n 为序列长度。每个位置至多被遍历两次。

• 空间复杂度：O(1)。只需要常数的空间存放若干变量。

remove()函数

一开始想使用STL中的remove()函数。
对于remove函数，首先要明白remove函数的实现原理。首先remove函数在STL中的源代码如下:

template <class ForwardIterator, class T>
ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val)
{
    ForwardIterator result = first;
    while (first!=last) 
    {
        if (!(*first == val)) 
        {
            *result = move(*first);
            ++result;
        }
        ++first;
    }
    return result;
}

惊奇的发现，这tm不就是自己写的双指针代码吗，但是我直接使用remove()函数，用时错了一辈。。。应该是调用函数的开销吧。

1.对vector而言

remove的时候只是通过迭代器的指针向前移动来删除，将没有被删除的元素放在链表的前面，并返回一个指向新的超尾值的迭代器。由于remove()函数不是vector成员函数，因此不能调整vector容器的长度。（对vector来说）remove()函数并不是真正的删除，要想真正删除元素则可以使用erase()或者resize()函数。erase()函数可以删除给定区间的元素。它接受两个迭代器参数，这些参数规定了要删除的区间。

2.对list来说

remove()函数作为列表list容器的成员函数，可以从列表容器中删除与x相等的元素，同时会减小列表容器的大小，其减小的数量等于被删除的元素的个数，原型如下：

void remove(const T& x);//删除与x相等的元素

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

• 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
• 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
• 重复直到所有输入数据插入完为止。

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4

示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

方法一：从前往后找插入点

插入排序的基本思想是，维护一个有序序列，初始时有序序列只有一个元素，每次将一个新的元素插入到有序序列中，将有序序列的长度增加 11，直到全部元素都加入到有序序列中。

如果是数组的插入排序，则数组的前面部分是有序序列，每次找到有序序列后面的第一个元素（待插入元素）的插入位置，将有序序列中的插入位置后面的元素都往后移动一位，然后将待插入元素置于插入位置。

对于链表而言，插入元素时只要更新相邻节点的指针即可，不需要像数组一样将插入位置后面的元素往后移动，因此插入操作的时间复杂度是 O(1)，但是找到插入位置需要遍历链表中的节点，时间复杂度是 O(n)，因此链表插入排序的总时间复杂度仍然是 O(n^2)，其中 n 是链表的长度。

对于单向链表而言，只有指向后一个节点的指针，因此需要从链表的头节点开始往后遍历链表中的节点，寻找插入位置。

对链表进行插入排序的具体过程如下。

1. 首先判断给定的链表是否为空，若为空，则不需要进行排序，直接返回。

2. 创建哑节点 dummyHead，令 dummyHead.next = head。引入哑节点是为了便于在 head 节点之前插入节点。

3. 维护 lastOrder 为链表的已排序部分的最后一个节点，初始时 lastOrder = head。

4. 维护 cur 为待插入的元素，初始时 cur = head.next。

5. 比较 lastOrder 和 cur 的节点值。

6. 若 lastOrder.val <= cur.val，说明 cur 应该位于 lastOrder 之后，将 lastOrder 后移一位，curr 变成新的 lastOrder。

7. 否则，从链表的头节点开始往后遍历链表中的节点，寻找插入 cur 的位置。令 pre 为插入 cur 的位置的前一个节点，进行如下操作，完成对 cur 的插入：

lastOrder.next = cur.next
cur.next = pre.next
pre.next = cur

8. 令 cur = lastOrder.next，此时 cur 为下一个待插入的元素。

9. 重复第 5 步和第 6 步，直到 cur 变成空，排序结束。

10. 返回 dummyHead.next，为排序后的链表的头节点。

ListNode *insertionSortList(ListNode *head) {
    if (head == nullptr) return nullptr;
    ListNode *dummyHead = new ListNode(0);
    dummyHead->next = head;
    ListNode *lastOrder = head;
    ListNode *cur = lastOrder->next;
    while (cur != nullptr) {
        if (cur->val < lastOrder->val) {
            ListNode *pre = dummyHead;
            while (pre != cur) {
                if (pre->next->val > cur->val) {
                    lastOrder->next = cur->next;
                    cur->next = pre->next;
                    pre->next = cur;
                    pre = cur;
                } else {
                    pre = pre->next;
                }
            }
            cur = lastOrder->next;
        } else {
            lastOrder = lastOrder->next;
            cur = lastOrder->next;
        }
    }
    return dummyHead->next;
}

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是链表的长度。

• 空间复杂度：O(1)。

148

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

• 你可以在 $$O(n log n)$$ 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 104] 内
• 105 <= Node.val <= 105

方法一：自顶向下归并排序

对链表自顶向下归并排序的过程如下。

找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

对两个子链表分别排序。

将两个排序后的子链表合并，得到完整的排序后的链表。将两个有序的子链表进行合并。

上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1，即当链表为空或者链表只包含 1 个节点时，不需要对链表进行拆分和排序。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return (head== nullptr)?head:mergeSort(head);//判空
    }
    ListNode* mergeSort(ListNode* head){
        if (head->next== nullptr){//递归终止条件：一个节点
            return head;
        }
        ListNode* mid=findMid(head);//找到中心节点并使mid指向它
        ListNode* lf=mergeSort(head);//对前半段递归排序
        ListNode* lr=mergeSort(mid);//对后半段递归排序
        return mergeTwoList(lf,lr);//归并
    }
    ListNode* findMid(ListNode* head){//找中点并拆开链表，中点作为拆开新的一段的起点
        ListNode* slow=head;
        ListNode* fast=head;
        ListNode* rightListTail=head;//用于指向左半边链表的尾巴，以便拆开
        while (fast!= nullptr && fast->next!= nullptr){//循环终止条件，快指针知道最后一个节点或者最后一个节点的后一个空节点
            rightListTail=slow;//每次循环都指向slow前一个节点处
            slow=slow->next;//慢指针移动一次
            fast=fast->next->next;//快指针移动两次
        }
        rightListTail->next= nullptr;//拆开
        return slow;//slow作为找到的中点，并且是拆开后右半边链表的头节点
    }
    ListNode* mergeTwoList(ListNode* lf,ListNode* lr){//采用递归的合并
        if (lf== nullptr) return  lr;
        if (lr== nullptr)return lf;
        if (lf->val<lr->val){
            lf->next=mergeTwoList(lf->next,lr);
            return lf;
        } else{
            lr->next=mergeTwoList(lf,lr->next);
            return lr;
        }
    }
};

242

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:

输入: s = “rat”, t = “car”
输出: false

说明:

• 你可以假设字符串只包含小写字母。

进阶:

• 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

解题思路

• 标签：哈希映射
• 首先判断两个字符串长度是否相等，不相等则直接返回 false
• 若相等，则初始化 26 个字母哈希表，遍历字符串 s 和 t
• s 负责在对应位置增加，t 负责在对应位置减少
  如果哈希表的值都为 0，则二者是字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;
        vector<int> record(26, 0);
        for (int i = 0; i < s.length(); ++i) {
            ++record[s[i] - 'a'];
        }
        for (int i = 0; i < t.length(); ++i) {
            --record[t[i] - 'a'];
        }
        for (int i = 0; i < 26; ++i) {
            if (record[i]) return false;
        }
        return true;
    }
};

452

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x_\text{start}，x_\text{end}， 且满足 x_\text{start} ≤ x ≤ x_\text{end}，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [x_\text{start},x_\text{end}] ，返回引爆所有气球所必须射出的最小弓箭数。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2

示例 4：

输入：points = [[1,2]]
输出：1

示例 5：

输入：points = [[2,3],[2,3]]
输出：1

提示：

• 0 <= points.length <= 104
• points[i].length == 2
• -231 <= xstart < xend <= 231 - 1

贪心经典题目
题解
（题解只看了 代码随想录 的，leetcode-cn.com/problems/minimum-n... @ https://github.com/youngyangyang04）

思路
接下来在想一下如何使用最少的弓箭。

直觉上来看，貌似只射重叠最多的气球，用的弓箭一定最少，那么有没有当前重叠了三个，我射两个，留下一个和后面的一起射这样弓箭用的更少的情况呢？

尝试一下举反例，发现没有这种情况，那么就试一试贪心吧！

算法确定下来了，那么如何模拟气球涉爆的过程呢？是在数组中移除元素还是做标记呢？

如果真实的模拟射气球的过程，应该射一个，气球数组就remove一个元素，这样最直观，毕竟气球被射了。

但又想一下，如果把气球排序之后，从前到后遍历气球，被射过的气球仅仅跳过就行了，没有必要让气球数组remove气球，记录一下箭的数量就可以了。

以上为思考过程，已经确定下来使用贪心了，那么开始解题。

为了让气球尽可能的重叠，需要对数组进行排序。

那么按照气球起始位置排序，还是按照气球终止位置排序呢？

其实都可以！只不过对应的遍历顺序不同，我就按照气球的起始位置排序了。

既然按照其实位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。

从前向后遍历遇到重叠的气球了怎么办？

如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。

以题目示例： [[10,16],[2,8],[1,6],[7,12]]为例，如图：（方便起见，已经排序）

可以看出首先第一组重叠气球，一定是需要一个箭，气球3，的左边界大于了 第一组重叠气球的最小右边界，所以再需要一支箭来射气球3了。

C++代码如下：

class Solution {
public:
    int findMinArrowShots(vector<vector<int>> &points) {
        if (points.size() == 0) return 0;
        sort(points.begin(), points.end(), [](const vector<int> &a, const vector<int> &b) {
            return a[0] < b[0];
        });//无名函数自定义排序
        int ans = 1;//points不为空至少需要一支箭
        for (int i = 1; i < points.size(); ++i) {
            if (points[i - 1][1] < points[i][0]) {// 气球i和气球i-1不挨着，注意这里不是<=
                ++ans;//需要一支箭
            } else {
                points[i][1] = min(points[i - 1][1], points[i][1]);//更新重叠气球最小右边界
            }
        }
        return ans;
    }
};

222

给出一个完全二叉树，求出该树的节点个数。

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例:

输入:
   1
  /   \
  2     3
 / \   /
4   5  6

输出: 6

解法一：普适方法
这个题首先想到的就是DFS与BFS，先借此温习一下二叉树的DFS与BFS

二叉树的DFS

递归版

class Solution {
public:
    void countNodes(TreeNode* root){
        if(!root) return 0;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

迭代版

class DFS {
public:
    int countNodes(TreeNode *root) {
        if (root == nullptr) return 0;
        stack<TreeNode *> s;
        s.push(root);
        int count = 0;
        while (!s.empty()) {
            TreeNode *top = s.top();
            ++count;//每次取栈顶元素并进行相关操作，然后删除
            s.pop();
            if (top->right != nullptr)s.push(top->right);//前序遍历先入栈右子树
            if (top->left != nullptr)s.push(top->left);//再入栈左子树
        }
        return count;
    }
};

二叉树的BFS

class BFS {
public:
    int countNodes(TreeNode *root) {
        if (root == nullptr) return 0;
        queue<TreeNode *> q;
        q.push(root);
        int count = 0;
        while (!q.empty()) {
            TreeNode *front = q.front();
            ++count;//每次取队头元素进行相关操作，然后删除
            q.pop();
            if (front->left != nullptr) q.push(front->left);//先入队左子树
            if (front->right != nullptr)q.push(front->right);//再入队右子树
        }
        return count;
    }
};

解法二：二分查找+位运算

对于任意二叉树，都可以通过广度优先搜索或深度优先搜索计算节点个数，时间复杂度和空间复杂度都是 O(n)，其中 n 是二叉树的节点个数。这道题规定了给出的是完全二叉树，因此可以利用完全二叉树的特性计算节点个数。

规定根节点位于第 0 层，完全二叉树的最大层数为 h。根据完全二叉树的特性可知，完全二叉树的最左边的节点一定位于最底层，因此从根节点出发，每次访问左子节点，直到遇到叶子节点，该叶子节点即为完全二叉树的最左边的节点，经过的路径长度即为最大层数 h。

当 0≤i<h 时，第 i 层包含 2^i个节点，最底层包含的节点数最少为 1，最多为 2^h。

当最底层包含 11 个节点时，完全二叉树的节点个数是

\sum_{i=0}^{h-1}2^i+1=2^h

当最底层包含 2^h个节点时，完全二叉树的节点个数是

\sum_{i=0}^{h}2^i=2^{h+1}-1

因此对于最大层数为 hh 的完全二叉树，节点个数一定在 [2^h,2^{h+1}-1] 的范围内，可以在该范围内通过二分查找的方式得到完全二叉树的节点个数。

具体做法是，根据节点个数范围的上下界得到当前需要判断的节点个数 k，如果第 k 个节点存在，则节点个数一定大于或等于 k，如果第 k 个节点不存在，则节点个数一定小于 k，由此可以将查找的范围缩小一半，直到得到节点个数。

如何判断第 k 个节点是否存在呢？如果第 k 个节点位于第 h 层，则 k 的二进制表示包含 h+1 位，其中最高位是 1，其余各位从高到低表示从根节点到第 kk 个节点的路径，0 表示移动到左子节点，1 表示移动到右子节点。通过位运算得到第 k 个节点对应的路径，判断该路径对应的节点是否存在，即可判断第 k 个节点是否存在。

以上是官方详解，其实意思很简单，因为每个节点都有序号，只要找到最大序号的节点，它的序号就是节点数。而要抓完全二叉树的性质。除了最后一层，每一层都是满的，所以最大序号的节点一定在最后一层。而且可以大致感受到，最后一层节点的序号越大，这个节点就越向右偏，这个规律可以从第二层开始寻找。第二层两个节点2和3，转化为二进制10和11，可以发现第二位是1的就向右偏了一次。再往下一层，四个节点4、5、6、7，转化为二进制100、101、110、111，可以发现他们的最高位都相同，而第二位是否是1影响他们从第0层向第1层时是否向右偏，第三位又影响从第1层向第2层时是否右偏。从而找到最后一层的规律。通过这个规律我们可以写一个找到完全二叉树中是否有该编号的节点的函数。
因为序号最大节点一定在最后一层，最后一层序号有个范围[2^{depth},2^{depth+1}-1]，在一个范围内寻找一个数，并且这个数肯定存在在这个范围内，自然就想到二分查找，其中二分查找特别要注意区间的划分。

class Solution {
public:
    int countNodes(TreeNode *root) {
        if (root == nullptr) return 0;
        int depth = getDepth(root);
        int low = 1 << depth;//最后一层的最左端序号
        int high = (1 << (depth + 1)) - 1;//最后一层的最右端序号
        while (low < high) {
            int mid = low + (high - low + 1) / 2;//只能这样写，因为这个题二分区间划分只能是[low,mid-1]和[mid,high]
            if (isExist(root, depth, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    int getDepth(TreeNode *root) {
        TreeNode *node = root;//不能直接对指针操作，会影响原树
        int depth = 0;
        while (node->left != nullptr) {
            node = node->left;
            ++depth;
        }
        return depth;
    }

    bool isExist(TreeNode *root, int depth, int k) {
        TreeNode *node = root;//不能直接对指针操作，会影响原树
        int bits = 1 << depth - 1;//相当于取最后一排二进制的第二位，第一位都是1，一共depth+1位
        while (bits > 0 && node != nullptr) {//从第二位遍历到最后一位
            if (bits & k) {//用位运算来判断某一位是不是1
                node = node->right;//这一位是1，则应该向右
            } else {
                node = node->left;//否则应该向左，比如8=1000，就是从根节点向左移三次
            }
            bits >>= 1;//检查下一位
        }//遍历结束，有两种情况，node直接遇到空节点或者遍历到最后一层指定节点处，可能为空也可能不为空
        return node != nullptr;//直接返回判断式逻辑结果，不会空返回真，为空返回假，很巧妙
    }
};

二分查找

（引用了@ liweiwei1419 的观点，讲的真的好https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/）

• 首先，二分查找用找到这个数的方法比较麻烦，应该用将这个数不会在的区间划掉，从而缩小区间范围，一直到最后只剩一个数的时候。如果是像这个题一样肯定存在的话直接返回，如果不一定存在则再判断。因此，循环条件是 while(left<right)，退出循环的时候有 left == right 成立，因此无需考虑返回 left 还是 right；
• 始终思考下一轮搜索区间是什么，如果是 [mid, right] 就对应 left = mid ，如果是 [left, mid - 1] 就对应 right = mid - 1，是保留 mid 还是 +1、−1 就在这样的思考中完成；
• 从一个元素什么时候不是解开始考虑下一轮搜索区间是什么 ，把区间分为 2 个部分（一个部分肯定不存在目标元素，另一个部分有可能存在目标元素），问题会变得简单很多，这是一条 非常有用 的经验；
• 每一轮区间被划分成 2 部分，理解 区间划分 决定中间数取法，在调试的过程中理解 区间和中间数划分的配对关系：

  • 划分 [left, mid] 与 [mid + 1, right] ，mid 被分到左边，对应 int mid = left + (right - left) / 2;；
  • 划分 [left, mid - 1] 与 [mid, right] ，mid 被分到右边，对应 int mid = left + (right - left + 1) / 2;。

至于为什么划分是这种对应关系，原因在于区间只有 2 个数的时候，如果中间数的取法不对，一旦进入的分支不能使得区间缩小，会出现 死循环。

• 退出循环的时候有 left == right 成立，此时如果能确定问题一定有解，返回 left 即可，如果不能确定，需要单独判断一次。

137

给你一个字符串 s ，请你根据下面的算法重新构造字符串：

1. 从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
2. 从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
3. 重复步骤 2 ，直到你没法从 s 中选择字符。
4. 从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
5. 从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
6. 重复步骤 5 ，直到你没法从 s 中选择字符。
7. 重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。

在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。

请你返回将 s 中字符重新排序后的 结果字符串 。

示例 1：

输入：s = “aaaabbbbcccc”
输出：“abccbaabccba”
解释：第一轮的步骤 1，2，3 后，结果字符串为 result = “abc”
第一轮的步骤 4，5，6 后，结果字符串为 result = “abccba”
第一轮结束，现在 s = “aabbcc” ，我们再次回到步骤 1
第二轮的步骤 1，2，3 后，结果字符串为 result = “abccbaabc”
第二轮的步骤 4，5，6 后，结果字符串为 result = “abccbaabccba”

示例 2：

输入：s = “rat”
输出：“art”
解释：单词 “rat” 在上述算法重排序以后变成 “art”

示例 3：

输入：s = “leetcode”
输出：“cdelotee”

示例 4：

输入：s = “ggggggg”
输出：“ggggggg”

示例 5：

输入：s = “spo”
输出：“ops”

提示：

• 1 <= s.length <= 500
• s 只包含小写英文字母。

解法一：计数排序
看见仅限小写字母的字符串排序就想起了计数排序（桶排序），设26个桶分别代表a-z，反复从a到z再从z到a循环桶把桶里的字符拿到结果即可。这时要思考的就是循环条件，怎么知道所有桶中的字符全部拿完了。一开始的想法是用一个整数count记录是否添加了最够多的结果，后来看了题解发现直接比较结果字符串与原始字符串的长度更简单。

string sortString(string s) {
    vector<int> record(26, 0);
    string ans;
    for (auto &ch:s) {
        ++record[ch - 'a'];
    }
    while (ans.length() < s.length()) {
        for (int i = 0; i < 26; ++i) {
            if (record[i]) {
                ans.push_back(i + 'a');
                --record[i];
            }
        }
        for (int i = 25; i >= 0; --i) {
            if (record[i]) {
                ans.push_back(i + 'a');
                --record[i];
            }
        }
    }
    return ans;
}

204

统计所有小于非负整数 n 的质数的数量。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

提示：

• 0 <= n <= 5 * 106

方法二：埃氏筛
枚举没有考虑到数与数的关联性，因此难以再继续优化时间复杂度。接下来我们介绍一个常见的算法，该算法由希腊数学家厄拉多塞（\rm Eratosthenes）提出，称为厄拉多塞筛法，简称埃氏筛。

我们考虑这样一个事实：如果 x 是质数，那么大于 x 的 x 的倍数 2x,3x,\ldots 一定不是质数，因此我们可以从这里入手。

我们设 \textit{isPrime}[i] 表示数 i 是不是质数，如果是质数则为 1，否则为 00。从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即 0，这样在运行结束的时候我们即能知道质数的个数。

这种方法的正确性是比较显然的：这种方法显然不会将质数标记成合数；另一方面，当从小到大遍历到数 x 时，倘若它是合数，则它一定是某个小于 x 的质数 y 的整数倍，故根据此方法的步骤，我们在遍历到 y 时，就一定会在此时将 x 标记为 \textit{isPrime}[x]=0。因此，这种方法也不会将合数标记为质数。

当然这里还可以继续优化，对于一个质数 x，如果按上文说的我们从 2x 开始标记其实是冗余的，应该直接从 x\cdot x 开始标记，因为 2x,3x,\ldots这些数一定在 x 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等。

int countPrimes(int n) {
    vector<bool> isPrime(n, true);
    int count = 0;
    for (int i = 2; i < n; ++i) {//1不是素数
        if (isPrime[i]) {//直接通过筛的数组判断
            ++count;//顺便计数，以免再次计数
            if ((long long) i * i < n) {//防止超过整数最大范围
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
    return count;
}

1

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

方法二：哈希表
思路及算法

暴力解法的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> hashTable;//unordered_map内部实现的了一个哈希表
    for (int i = 0; i < nums.size(); ++i) {
        auto it = hashTable.find(target - nums[i]);//寻找是否有匹配的key，复杂度O(1)
        if (it != hashTable.end()) {//判断是否存在的方法
            return {it->second, i};//返回的是value，对应的是下标
        }
        hashTable[nums[i]] = i;//因为是寻找key，所以要把nums[i]作为key用来寻找
    }
    return {};//因为一定存在，所以返回什么都无所谓
}

c++使用unordered_map

查找元素是否存在

若有unordered_map <int, int> mp;查找x是否在map中
    方法1:  若存在  mp.find(x)!=mp.end()，返回指向该key-value的迭代器，->first对应key，->second对应value
    方法2:  若存在  mp.count(x)!=0

插入数据

mp.insert(Map::value_type(1,"Raoul"));

遍历map

 unordered_map<key,T>::iterator it;
    (*it).first;   //the key value
    (*it).second   //the mapped value
    for(unordered_map<key,T>::iterator iter=mp.begin();iter!=mp.end();iter++)
          cout<<"key value is"<<iter->first<<" the mapped value is "<< iter->second;

    //也可以这样
    for(auto& v : mp)
        print v.first and v.second

与map的区别

内部实现机理

• map： map内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素，因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了map的效率。

• unordered_map: unordered_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的

缺点以及适用处

• map

优点：
有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
红黑树，内部实现一个红黑书使得map的很多操作在的时间复杂度下就可以实现，因此效率非常的高

缺点：
空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，孩子节点以及红/黑性质，使得每一个节点都占用大量的空间
适用处，对于那些有顺序要求的问题，用map会更高效一些

• unordered_map

优点：
因为内部实现了哈希表，因此其查找速度非常的快

缺点：
哈希表的建立比较耗费时间
适用处，对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

2

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解法2：
整体思路：

不对齐补零，若链表不为空则用 sum(代表每个位的和的结果)加上，考虑进位。

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode *head = nullptr, *tail = nullptr;//新建和链表头指针与尾指针用于遍历新建链表
        int carry = 0;//进位位，初始化为0
        while (l1 || l2) {//当都两个链表都遍历到末尾时结束循环
            int sum = 0;//计算某一位的和
            if (l1) {//如果l1不指向空，把它指向的值加到sum
                sum += l1->val;
                l1 = l1->next;//加上值后指针后移
            }
            if (l2) {//如果l2不指向空，把它指向的值加到sum
                sum += l2->val;
                l2 = l2->next;//加上值后指针后移
            }
            //这样如果一个数比较短，不会再对它进行操作，每次只是把长的剩余的值加到sum上
            if (!head) {//如果链表为空
                head = tail = new ListNode((sum + carry) % 10);//头节点初始化
            } else {//如果链表不为空，通过tail指针增加节点
                tail->next = new ListNode((sum + carry) % 10);//注意要先加上进位位再mod10，
                tail = tail->next;//tail指针始终指向最后一个数字
            }
            carry = (sum + carry) / 10;//更新进位位，注意要先加上进位位再整除以10
        }
        if (carry) {//注意若两个数的和超过最长的链表的长度，也就是还要再向高位进一位，还要单独判读添加节点
            tail->next = new ListNode(carry);
            tail = tail->next;
        }
        return head;//返回头指针
    }
};

3

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

示例 4:

输入: s = “”
输出: 0

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

思路：
滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度： O(n)

int lengthOfLongestSubstring(string s) {
    if (s.empty()) return 0;//如果为空返回0
    unordered_set<char> lookUp;//定义查找表，即窗口
    int ans = 0;//结果初始化为0
    int left = 0;//窗口左端，初始化为字符串最左边，即为0
    for (int right = 0; right < s.length(); ++right) {//定义窗口右端，即每次要新加入窗口的字符，初始化为0，即窗口最初为空
        while (lookUp.find(s[right]) != lookUp.end()) {//当新字符在已创建的窗口中出现过，缩小窗口
            lookUp.erase(s[left]);//不断擦除最左端元素，直到窗口中没有与新加入窗口的重复的字符
            ++left;//缩小窗口，改变左端指针
        }
        lookUp.insert(s[right]);//新字符加入窗口
        ans = max(ans, right - left + 1);//新窗口窗口与老窗口的最大长度比较
    }
    return ans;
}

更简洁的代码

• 作者：ikaruga
• 链接：leetcode-cn.com/problems/longest-s...
• 来源：力扣（LeetCode）

1. 滑动窗口，保证每个窗口里字母都是唯一的

2. 使用 vector<int> m 来记录一个字母如果后面出现重复时，i 应该调整到的新位置，所以每次更新的时候都会保存 j + 1 ，即字母后面的位置。

3. j 表示子串的最后一个字母，计算子串长度为 j - i + 1

    int lengthOfLongestSubstring(string s) {
        vector<int> m(128, 0);
        int ans = 0;
        int i = 0;
        for (int j = 0; j < s.size(); j++) {
            i = max(i, m[s[j]]);
            m[s[j]] = j + 1;
            ans = max(ans, j - i + 1);
        }
        return ans;
    }

理解：
i = max(i, m[s[j]]);
如果最新加入的字符在原窗口中没有出现，这时m[s[j]]=0，
如果新加入的字符在窗口左边界的左边出现过，m[s[j]]<i，
以上两种情况窗口左边界都不变。
若新加入的字符在窗口中出现过，i（即窗口左边界）会更新为出现过的字符（肯定只出现一次，因为之前都有过查找）的右边那个位置，这样窗口中就没有重复元素了。

m[s[j]] = j + 1;
对于遍历到的每个字符，都把他们对应的表中的数据记录为该字符在字符串中出现的位置+1，也就是当下次再次遇到该字符时滑动窗口左边界应该在的位置。

vector<int> m(128, 0);
因为是字符串，每个字符都对应ASCII码，七位ASCII码128个，直接把字符转换为整数数组下标记录即可，初始化0。

659

给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。

如果可以完成上述分割，则返回 true ；否则，返回 false 。

示例 1：

输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3
3, 4, 5

示例 2：

输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3, 4, 5
3, 4, 5

示例 3：

输入: **[1,2,3,4,4,5]
**输出: False

提示：

• 输入的数组长度范围为 [1, 10000]

算法思路：

1. 首先使用两个哈希 map: record和tail

• record[i]：存储原数组中数字i出现的次数
• tail[i]：存储以数字i结尾的且符合题意的连续子序列个数

2. 先去寻找一个长度为3的连续子序列 i, i+1, i+2，找到后就将 record[i], record[i+1], record[i+2] 中对应数字消耗1个（即-1），并将 tail[i+2] 加 1，即以 i+2 结尾的子序列个数 +1。
3. 如果后续发现有能够接在这个连续子序列的数字 i+3，则延长以 i+2 为结尾的连续子序列到 i+3，此时消耗 record[i+3] 一个，由于子序列已延长，因此tail[i+2] 减 1，tail[i+3] 加 1
4. 在不满足上面的情况下

• 如果 record[i] 为 0，说明这个数字已经消耗完，可以不管了
• 如果 record[i] 不为 0，说明这个数字多出来了，且无法组成连续子序列，所以可以直接返回 false 了

5. 因此，只有检查到某个数时，这个数未被消耗完，且既不能和前面组成连续子序列，也不能和后面组成连续子序列时，无法分割

时间复杂度：O(N)，所有元素遍历一遍 O(N)，循环内部均为常数时间操作 O(1)
空间复杂度：O(N)，使用了两个哈希 map

bool isPossible(vector<int> &nums) {
    unordered_map<int, int> record;
    unordered_map<int, int> tail;
    for (auto &num:nums) {
        ++record[num];//遍历数组，记录各个数字出现的频率
    }
    for (auto &num:nums) {
        if (record[num] == 0) continue;//如果当前数字已经用完，跳到下次循环
        else if (tail[num - 1]) {//如果当前数字能接到尾巴上
            --tail[num - 1];//前面数字不再是尾巴
            ++tail[num];//把它接到尾巴上
            --record[num];//别忘了频率减一
        } else if (record[num + 1] && record[num + 2]) {//如果不能接作尾巴，但能作为头形成三连数序列
            --record[num];
            --record[num + 1];
            --record[num + 2];//组成三连数序列
            ++tail[num + 2];//num+2为尾巴
        } else {//如果都不能，出现孤立的数字，不符合题目要求，直接判false
            return false;
        }
    }
    return true;//遍历完可以完成分割，判true
}

为什么要使用哈希表？
一开始看到数字，要记录出现次数可能会想到使用数组，但是遍历到8、9时，record[num + 1] && record[num + 2]会产生越界，遍历到1时，tail[num-1]也会产生越界。
为了不单独考虑边界情况，直接用unordered_map即哈希表涵盖了越界访问的问题，当key不存在时，record[key]等于0。

621

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的 最短时间 。

示例 1：

输入：tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
示例 2：

输入：tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
[“A”,”A”,”A”,”B”,”B”,”B”]
[“A”,”B”,”A”,”B”,”A”,”B”]
[“B”,”B”,”B”,”A”,”A”,”A”]
…
诸如此类

示例 3：

输入：tasks = [“A”,”A”,”A”,”A”,”A”,”A”,”B”,”C”,”D”,”E”,”F”,”G”], n = 2
输出：16
解释：一种可能的解决方案是：
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A

提示：

• 1 <= task.length <= 104
• tasks[i] 是大写英文字母
• n 的取值范围为 [0, 100]

思路算法：

作者：popopop
链接：leetcode-cn.com/problems/task-sche...
来源：力扣（LeetCode）

参考「桶思想」，详细说明各种情况
建立大小为 n+1 的桶子，个数为任务数量最多的那个任务，比如下图，等待时间 n=2，A 任务个数 6 个，我们建立 6 桶子，每个容量为 3：
我们可以把一个桶子看作一轮任务

1. 先从最简单的情况看起，现在就算没有其他任务，我们完成任务 A 所需的时间应该是 (6-1)*3+1=16，因为最后一个桶子，不存在等待时间。

2. 接下来我们添加些其他任务

可以看到 C 其实并没有对总体时间产生影响，因为它被安排在了其他任务的冷却期间；而 B 和 A 数量相同，这会导致最后一个桶子中，我们需要多执行一次 B 任务，现在我们需要的时间是 (6-1)*3+2=17

前面两种情况，总结起来：总排队时间 = (桶个数 - 1) * (n + 1) + 最后一桶的任务数

3. 当冷却时间短，任务种类很多时

比如上图，我们刚好排满了任务，此时所需时间还是 17，如果现在我还要执行两次任务 F，该怎么安排呢？

此时我们可以临时扩充某些桶子的大小，插进任务 F，对比一下插入前后的任务执行情况：
插入前：ABC | ABC | ABD | ABD | ABD | AB
插入后：ABCF | ABCF | ABD | ABD | ABD | AB
我们在第一个、第二个桶子里插入了任务F，不难发现无论再继续插入多少任务，我们都可以类似处理，而且新插入元素肯定满足冷却要求
继续思考一下，这种情况下其实每个任务之间都不存在空余时间，冷却时间已经被完全填满了。
也就是说，我们执行任务所需的时间，就是任务的数量

这样剩下就很好处理了，我们只需要算两个数：

1. 记录最大任务数量 N，看一下任务数量并列最多的任务有多少个，即最后一个桶子的任务数 X，计算 NUM1=(N-1)*(n+1)+x
2. NUM2=tasks.size()
   输出其中较大值即可
   因为存在空闲时间时肯定是 NUM1 大，不存在空闲时间时肯定是 NUM2>=NUM1

class Solution {
public:
    int leastInterval(vector<char> &tasks, int n) {
        vector<int> list(26, 0);
        for (auto &c:tasks) {
            ++list[c - 'A'];//记录每个字母出现的次数
        }
        sort(list.begin(), list.end(), [](int &x, int &y) {
            return x > y;//默认升序，自定义为降序
        });
        int maxCount = 1;
        while (maxCount < list.size() && list[maxCount] == list[0]) ++maxCount;//记录出现频率与最大次数相同的字母个数
        return max((int) tasks.size(), (list[0] - 1) * (n + 1) + maxCount);//size返回类型为size_t，需要强制转换为int才能比较
    }
};

TIPS

• 贪心题，核心思想：一共出现最多次数个桶，除了最后一个桶，其他桶大小都是固定的n+1，最后一个桶1~n+1，如果所有字母能放下，一定能排列成符合题目要求的间隔。（证明不会）如果放不下，一定能没有冷却时间去安排。（证明不会）
• 可能这就是贪心吧，玄学，不会证明。大致能想象出来，就是从多到少排好，再把某些桶溢出的字母移到没溢出的桶里，这样也满足间隔。

118. 杨辉三角I

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

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

题解：

简单题没什么好说的。

1. 顺序模拟，第一行单独考虑。放1->循环放ans[i - 1][j] + ans[i - 1][j + 1]->放1。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans(numRows);
        for (int i = 0; i < numRows; ++i) {
            ans[i].push_back(1);//放1
            if (i == 0) continue;//第一行的话跳出本轮循环
            for (int j = 0; j < i - 1; ++j) {//中间部分根据上一行相加
                ans[i].push_back(ans[i - 1][j] + ans[i - 1][j + 1]);
            }
            ans[i].push_back(1);//再放1
        }
        return ans;
    }
};

2. 或者每一行resize()大小，用坐标赋值而不用push_back()，这样不用单独考虑第一行了。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);
        for (int i = 0; i < numRows; ++i) {
            ret[i].resize(i + 1);
            ret[i][0] = ret[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
            }
        }
        return ret;
    }
};

861. 翻转矩阵后的得分

有一个二维矩阵 A 其中每个元素的值为 0 或 1 。

移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。

在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。

返回尽可能高的分数。

示例：

输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
输出：39
解释：
转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

提示：

• 1 <= A.length <= 20
• 1 <= A[0].length <= 20
• A[i][j] 是 0 或 1

方法一：贪心

根据题意，能够知道一个重要的事实：给定一个翻转方案，则它们之间任意交换顺序后，得到的结果保持不变。因此，我们总可以先考虑所有的行翻转，再考虑所有的列翻转。

不难发现一点：为了得到最高的分数，矩阵的每一行的最左边的数都必须为 1。为了做到这一点，我们可以翻转那些最左边的数不为 1 的那些行，而其他的行则保持不动。

当将每一行的最左边的数都变为 1 之后，就只能进行列翻转了。为了使得总得分最大，我们要让每个列中 1 的数目尽可能多。因此，我们扫描除了最左边的列以外的每一列，如果该列 0 的数目多于 1 的数目，就翻转该列，其他的列则保持不变。

实际编写代码时，我们无需修改原矩阵，而是可以计算每一列对总分数的「贡献」，从而直接计算出最高的分数。假设矩阵共有 m 行 n 列，计算方法如下：

对于最左边的列而言，由于最优情况下，它们的取值都为 1，因此每个元素对分数的贡献都为 2^{n-1}，总贡献为 m \times 2^{n-1}。

对于第 j 列（j>0，此处规定最左边的列是第 0 列）而言，我们统计这一列 0,1 的数量，令其中的最大值为 k，则 k 是列翻转后的 1 的数量，该列的总贡献为 k \times 2^{n-j-1}。需要注意的是，在统计 0,1 的数量的时候，要考虑最初进行的行反转。而又会注意到，因为最初反转每一行的数字都会跟随第一列数字的翻转而变化，但每一行的数字与第一列数字的关系是不会改变的，因为第一次操作是按行操作。所以只要看某个数字与本行数字是否相同，如果相同，那么第一次操作后该数字一定是1。

• 这个解法的妙处在于没有对原矩阵进行任何操作，而是通过数字之间的关系来直接计算结果，这样就不需要记录或运算出原矩阵的情况了。

class Solution {
public:
    int matrixScore(vector<vector<int>> &A) {
        int rows = A.size();
        int columns = A[0].size();//题目说了A最少一行一列，不用判空
        int ans = rows * (1 << columns - 1);//用移位操作，快，每行首位都是1，移动每行个数减一次
        for (int i = 1; i < columns; ++i) {//遍历每列，第一列已经都是1无需遍历
            int nOnes = 0;//记录每列1的个数
            for (int j = 0; j < rows; ++j) {//遍历每列的每行
                if (A[j][0] == A[j][i]) ++nOnes;//如果这个数与该行第一列相同，则在第一次操作后它一定是1，因为第一列都变成了1
            }
            ans += max(nOnes, rows - nOnes) * (1 << columns - i - 1);//每一列翻转后1的个数就是原来1和0中最多的个数，左移位数与i有关
        }
        return ans;
    }
};

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 109

动态规划

动态规划经典题，终于做出个和官方题解一模一样的答案。
以终点作为原点，建立坐标系。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        //因为后面递推公式从0开始会越界，所以要从1开始并初始化第0行和第0列
        for (int i = 0; i < m; ++i) {//对终点所在列初始化为1
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; ++i) {//对终点所在行初始化为1
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];//递推公式
            }
        }
        return dp[m - 1][n - 1];
    }
};

860. 柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

输入：[5,5,10]
输出：true

示例 3：

输入：[10,10]
输出：false

示例 4：

输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示：

• 0 <= bills.length <= 10000
• bills[i] 不是 5 就是 10 或是 20

贪心

美其名曰贪心题，就是遇到20先看能不能找10+5，不行再找3个5，因为10元作为找零只能在这时用，并且用的纸币数目少。而5在遇到10也有用，所以尽量少用。

bool lemonadeChange(vector<int> &bills) {
    int five = 0, ten = 0;
    for (auto &money:bills) {
        switch (money) {
            case 5:
                ++five;
                break;
            case 10:
                ++ten;
                if (five == 0) return false;
                --five;
                break;
            case 20:
                if (five == 0) return false;
                else if (ten > 0) {
                    --five;
                    --ten;
                } else if (five >= 3) {
                    five -= 3;
                } else return false;
                break;
            default:
                return false;
        }
    }
    return true;
}

TIPS

• 一开始还很sb的用哈希表，直接两个整数记录5和10分别有多少张纸币就完事了呀，太蠢了。
• switch-case语句比多个if-else分支要快，因为看到只有5、10、20三个离散情况，所以直接用了，看起来也更清晰。连续情况当然还是if-else好。

217. 存在重复元素

给定一个整数数组，判断是否存在重复元素。

如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

输入: [1,2,3,1]
输出: true

示例 2:

输入: [1,2,3,4]
输出: false

示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

哈希表

简单题，和官方题解做的一模一样。。。
对于数组中每个元素，我们将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素。

class Solution {
public:
    bool containsDuplicate(vector<int> &nums) {
        unordered_set<int> record;
        for (auto &i:nums) {
            if (record.find(i) != record.end()) return true;
            record.insert(i);
        }
        return false;
    }
};

排序

或者在对数字从小到大排序之后，数组的重复元素一定出现在相邻位置中。因此，我们可以扫描已排序的数组，每次判断相邻的两个元素是否相等，如果相等则说明存在重复的元素。

49. 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]

说明：

• 所有输入均为小写字母。
• 不考虑答案输出的顺序。

排序

由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        unordered_map<string, vector<string>> mp;
        for (auto &s:strs) {
            string t = s;
            sort(t.begin(), t.end());
            mp[t].push_back(s);
        }
        vector<vector<string>> ans;
        for (auto &p:mp) {
            ans.push_back(p.second);//经实验，auto&p取的是键值对，类型为pair，那么p.second就是值
        }
        return ans;
    }
};

738. 单调递增的数字

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例 1:

输入: N = 10
输出: 9

示例 2:

输入: N = 1234
输出: 1234

示例 3:

输入: N = 332
输出: 299

说明: N 是在 [0, 10^9] 范围内的一个整数。

贪心

作者：carlsun-2
链接：leetcode-cn.com/problems/monotone-...

题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例。
例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]–，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
这一点如果想清楚了，这道题就好办了。
局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]–，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。
全局最优：得到小于等于N的最大单调递增的整数。
但这里局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成9。
此时是从前向后遍历还是从后向前遍历呢？
这里其实还有一个贪心选择，对于“遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]–，然后strNum[i]给为9”的情况，这个strNum[i - 1]–的操作应该是越靠后越好。
因为这样才能让这个单调递增整数尽可能的大。例如：对于5486，第一位的5能不减一尽量不减一，因为这个减一对整体损失最大。
所以要从后向前遍历，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]–，然后strNum[i]给为9，这样保证这个减一的操作尽可能在后面进行（即整数的尽可能小的位数上进行）。
确定了遍历顺序之后，那么此时局部最优就可以推出全局，找不出反例，试试贪心。

C++

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strNum = to_string(N);//直接调用整数转化字符串函数
        int toNine = strNum.length();// toNine用来标记赋值9从哪里开始
        // 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
        for (int i = strNum.length() - 1; i > 0; --i) {
            if (strNum[i] < strNum[i - 1]) {
                toNine = i;
                --strNum[i - 1];
            }
        }
        for (int i = toNine; i < strNum.length(); ++i) {
            strNum[i] = '9';
        }
        return stoi(strNum);//stoi将string转换为int，atoi将char数组转换为int
    }
};

Golang

func monotoneIncreasingDigits(N int) int {
    strNum := []byte(strconv.Itoa(N)) //Itoa返回string，再用[]byte()转换为byte数组
    toNine := len(strNum)
    for i := len(strNum) - 1; i > 0; i-- {
        if strNum[i] < strNum[i-1] {
            toNine = i
            strNum[i-1]--
        }
    }
    for i := toNine; i < len(strNum); i++ {
        strNum[i] = '9'
    }

    ans, _ := strconv.Atoi(string(strNum)) //Atoi返回两个参数int和error,第二个参数用_接收（抛弃）
    //由于string可能无法转换为int，所以这个函数有两个返回值：第一个返回值是转换成int的值，第二个返回值判断是否转换成功。
    return ans
}

290. 单词规律

哈希表

能想到用哈希表，但因为这题要求一、一对应，所以要双映射，实现双映射采用两个哈希表。

在本题中，我们需要判断字符与字符串之间是否恰好一一对应。即任意一个字符都对应着唯一的字符串，任意一个字符串也只被唯一的一个字符对应。在集合论中，这种关系被称为「双射」。

想要解决本题，我们可以利用哈希表记录每一个字符对应的字符串，以及每一个字符串对应的字符。然后我们枚举每一对字符与字符串的配对过程，不断更新哈希表，如果发生了冲突，则说明给定的输入不满足双射关系。

在实际代码中，我们枚举 \textit{pattern} 中的每一个字符，利用双指针来均摊线性地找到该字符在 \textit{str} 中对应的字符串。每次确定一个字符与字符串的组合，我们就检查是否出现冲突，最后我们再检查两字符串是否比较完毕即可。

bool wordPattern(string pattern, string s) {
    vector<string> str;
    int head = 0;
    for (; head < s.size(); ++head) {
        int tail = head;
        while (tail < s.size() && s[tail] != ' ')++tail;
        str.push_back(s.substr(head, tail - head));
        head = tail;
    }//截取每一个单词
    if (str.size() != pattern.size()) return false;
    unordered_map<char, string> ps;
    unordered_map<string, char> sp;
    for (int i = 0; i < pattern.size(); ++i) {
        //相互确认
        if (ps.find(pattern[i]) != ps.end() && ps[pattern[i]] != str[i]) return false;
        if (sp.find(str[i]) != sp.end() && sp[str[i]] != pattern[i]) return false;
        //这里不需要else，如果存在替换一样的也行
        ps[pattern[i]] = str[i];
        sp[str[i]] = pattern[i];
    }
    return true;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接