给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
来源：https://leetcode.cn/problems/majority-element/
如果使用二分的快排方法，会在一个几乎全是1，2，3的长字符串TLE。
可以使用摩尔投票算法：维护一个候选人和投票。每次遇到支持者（等于候选人）时，将投票++，否则将投票--。当得票为0的时候，重新进行选举（直接选取当前遇到的元素）。
其正确性可以简单理解为：
不妨假设整个数组的众数记做a，则最初的数组中a的数量大于其余所有数。当采用count计数的时候有两种情况：
1）假设candidate等于a，则当count从1变为0的过程，此区间内a的数量等于其余数的数量，因此以count=0为分界线，数组右端部分的众数仍然为a
2）假设candidate不等于a，则当count从1变为0的过程， 此区间内a的数量小于等于其余数的数量，因此以count=0为分界线，数组右端部分的众数仍然为a
因此，以count=0可以将整个原始数组分为若干部分，count=0右端部分的数组中的众数永远是a，最终必然会筛选出a
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
来源: https://leetcode.cn/problems/perfect-squares/
动态规划的想法应该比较好想，其本质就是（给定n种钱币，凑出总数为m的最少硬币数）的动态规划，大部分人也能想到。
还有一种mathematical的解法，来源于一个数学的结论：四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。这给出了本题的答案的上界。
而只有当 时，n 只能被表示为四个正整数的平方和。
因此，特判4的方式有了，而特判1，只用判定该数本身是不是完全平方数即可。为了解决2，可以逐一用比他小的完全平方数减去，观察剩下的数是否是完全平方数。
附注：关于判断一个数是否是完全平方数，在c++中可以进行如下操作：
int x = (int)sqrt(target);return x*x == target;
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
site: https://leetcode.cn/problems/find-the-duplicate-number/
实现：从下标为0的数组元素开始，不断用当前元素的值，即nums[i]，作为下一个要去的元素的下标。（由于0不在给定的数值范围内，因此0即元素nums[0]不可能在环中）。以如此方式迭代，一定有一个数组元素a，被两个另一个元素b,c指向，因为元素bc的值重复，指向相同的位置a。因此，一定存在一个以元素a为入口的环。元素a的【下标】是我们要找的重复的那个数。
随后，问题变为在一个链表中（初始位置即第一个元素，下标fast=0, slow=0)，寻找环的入口（的下标）。使用弗洛伊德判圈算法即可，之前在链表的习题中已经做过，方法是使用快慢指针。
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
https://leetcode.cn/problems/maximum-product-subarray/
首先，这种区间dp不需要中间变量。在写完后才意识到。
其次，只用忠实记录当前所能得到的最大值和最小值即可。对于一个正数，乘上前面二者，得到的就是他能得到的最大值和最小值。对于负数，乘上最小值和最大值，天然就得到了他的最大值和最小值。
代码：
int maxProduct(vector<int>& nums) {//首先，这种区间dp不需要中间变量！想多了//其次，只用忠实记录最大值和最小值即可。对于一个正数，乘上前面二者，得到的就是他能得到的最大值和最小值。对于负数，乘上最小值，天然就得到了他的最大值int result=nums[0]; //最低不会低于这个值int imax=nums[0];int imin=nums[0];for(int i=1;i<nums.size();i++){int num=nums[i];if(num<0) swap(imax, imin);imax=max(num, imax*num);imin=min(num, imin*num);result=max(result, imax);}return result;}
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
链接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list
自己解的时候，使用了一个栈来保存所有的右节点，然后在找不到右节点的时候弹出。（相当于不递归的前序遍历），然后进行原地修改。
更好的O(1)解法绕过了这个栈。其做法是：先找到左子树的最右节点x，然后将当前的右子树的根节点r“挂在”那里。即将x->right=r（反正x->right本来就是null）。然后就可以放心的将当前节点的右指针连接到左节点那里去，设置左节点为null，然后step到当前节点的下一个节点（即已经设置好的右边），然后继续。
而如果某个节点的左子树不存在，直接step进入他的右边即可。这个右边，可能是先前在某个祖先节点时“挂在”他这里的，但反正顺序正确就行。
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sort-colors
这道题使用常规的快排子过程，就能解决99%。需要注意在对双线快排分区的过程中，没有想好初始化的边界条件。比如用k分隔0、1，用j分隔1、2。在循环变量i遇到0的时候，显然首先将k+1和i互换，然后k++。但是换到i的到底是谁？要考虑清楚。如果此时已经有了1，即j>k，那么换过去的一定是1。将1再换到j的开头即可。如果此时没有1，一方面，考虑到j的语义，我们一定要保证k==j，不能等到k>j了，否则的话j就不承担分隔1和2的任务了（即使此时没有1），因此，只需要互换k+1和i（此时换到i的一定是大2，不用继续处理了），然后【凭空增加一下j】，确保j依旧分割了1和2（即使此时没有1），而不是让j被k拉在后面越来越远。
https://leetcode.cn/problems/merge-intervals/
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路类似贪心：是一个固定做法
如果我们按照区间的左端点排序，那么在排完序的列表中，可以合并的区间一定是连续的。如下图所示，标记为蓝色、黄色和绿色的区间分别可以合并成一个大区间，它们在排完序的列表中是连续的
因此，将输入按照左端点排序后，每次新加入一个区间，检查新区间的左端点是否和当前最后一个区间的右端点能重合。不能重合，直接加入到末尾，如果可以重合，将最后一段的右端点更新为较大值即可。
题目地址：
https://leetcode.cn/problems/next-permutation/
给你一个整数数组 nums ，找出 nums 的下一个排列。
特点：找出尽可能靠右侧的一个数a，使得能在他的右边找到比他更大但是尽可能小的一个数b。将这两个数进行交换。
此时，这个数已经严格变大。但是仍然需要将a右侧的所有数按照从小到大的顺序进行排序。这样可以保证新得到的数是最小的。
剩下的全是技巧：
1. 当找到a时，a的右边一定是单调递减的（否则就能找到更靠右的a）。此时，从右向左寻找b，找到“最小”的使b>a的那个数即可。
2. 交换b和a，使用c++的swap少写三行代码。
3. 将a+1到末尾的所有元素全部反转。建议使用reverse()。回忆一下：a[i]就相当于a+i，那么显然a的下一个元素的迭代器是vector.begin()+i+1。
https://leetcode.cn/problems/jump-game/
这道题想复杂了。其实每个点虽然都是“左右可达”，但是其实是并不需要向左边回溯的。直观上可以证明，如果一个点是“可达”的，那么他左边的所有点都是可达的。
推理：如果一个点是可达的，那么一定存在其左边的一个点作为源点，其从源点到该店的所有点都可达。
不断递推，直到该点为最左边的起始点。
由此可以证明，可达区间一定是覆盖最左边的。因此，使用下标clenth标记当前能到达的最大长度。然后从左到右遍历每个点，更新能跳到的最远距离即可。
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
基本思路其实就是：统计每一位中出现的1的个数，对3求模即可。
class Solution {public://需要求得递推公式: one = one^n&!two// two = two ^ n &!oneint singleNumber(vector<int>& nums) {int one=0,two=0;for(int num:nums){one=(one^num)&(~two);two=(two^num)&(~one);}//由于只有0,1有意义，因此最终出现的two一定为0。return one; //这就是最终答案.}};