基本思路：滑动窗口，维护左端点l与右端点r，由于至少有两个数，所以循环终止条件为l < r。通过左端点与右端点可以算出区间和，如果大于目标则右移左端点，小于则右移右端点，等于则将滑动窗口内的数存储在结果中。由于每次只滑动一个数，且要求的是区间和，所以区间和可以在滑动窗口滑动时计算，避免了乘法运算。class Solution { public: vector<vector<int>> FindContinuousSequence(int sum) { vector<vector<int>> res; ...

这道题有一个前置题目，就是将本题的条件改为“一个整型数组里除了一个数字n之外，其他的数字都出现了两次”。先来解决这道前置题目，可以想到用异或运算解决，出现两次的数字异或之后为0，而0^n = n，所以最后得到的数一定是n。接下来解决本题。本题有两个数字只出现一次，所以依次异或一遍得到的是两个数字做异或的结果tmp。我们考虑异或操作是一个位运算，当两个数字的同一位不同时，异或得到该位为1，否则为0。所以，我们可以从tmp中选出为1的一位，然后将原数组分为两组，第一组为该位为1，第二组为该位为0，这样就能将两个只出现一次的数分到两个数组中，且这两个数组都满足“一个整型数组里除了一个数字n之外，其他...

递归思路：空树一定为平衡二叉树一棵树是平衡二叉树，首先需要它的左右子树都是平衡二叉树，这点可以用返回值bool来递归解决一棵树是平衡二叉树，其次需要它自己左右子树的高度差不超过1，这点不能用bool来解决，所以考虑将返回值改成pair<bool, int>，bool存储是否为平衡二叉树，而int存储该二叉树的高度。按照上面两个条件由左右子树的返回值计算该树的返回值。class Solution { public: pair<bool, int> IsBalanced_Solution2(TreeNode* pRoot) { if (!pRoot)...

。。。class Solution { public: int TreeDepth(TreeNode* pRoot) { if (!pRoot) return 0; return max(TreeDepth(pRoot->left), TreeDepth(pRoot->right)) + 1; } };

基本思路：有序数组，所以可以线性时间复杂度遍历找到该长度。优化：有序数组中的查找一般都是将线性查找优化为二分搜索。可以转变一下思路，求出该数组中第一个大于等于k的数的下标，以及第一个大于等于k+1，即大于k的数的下标，这两者相减，即为[k, k+1)区间内的数的个数，也即为k的个数。class Solution { public: int helper(vector<int>& data, int k) { int l = 0, r = data.size() - 1; while (l <= r) { ...

倒推：如果有公共节点，那么从公共节点到链表尾部长度一定相同，又因为两条链表长度和相同，所以两者相减也一定相同。因为没法从尾部出发倒着遍历，所以只能让两个指针分别跑完自己的链表后再从另一个链表开始跑了。最后如果相遇，相遇点就是公共节点（如果没有公共节点，那么由于长度和相同，最终也会相等，只不过都是nullptr）。class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { ListNode* p1 = pHead1, *p2 = pHead2; ...

求逆序对一般使用归并排序的思想。假设目前在递归过程中，左右两个子数组指针为l、r。由于归并排序是先排序左右子数组，所以此时左右子数组已经有序。当data[l] > data[r]时，根据左边子数组有序的性质，左子数组中下标在l之后的数也一定大于data[r]，从而l到左子数组末尾的数与data[r]都构成逆序对。class Solution { public: const int MOD = 1000000007; long long mergeSort(vector<int>& data, int l, int r) { if (l...

因为有大写字母所以不能只申请26空间class Solution { public: int FirstNotRepeatingChar(string str) { vector<int> cnt(58, 0); for (auto &i: str) { cnt[i - 'A']++; } for (int i = 0; i < str.length(); i++) { if (cnt[str[i] - 'A'] == 1) return i; ...

使用三指针法，三指针分别指向2、3、5当前的另一个乘数，由于丑数的质因子只能是2、3、5，所以需要在遍历过程中记录所有的丑数，当作另一个乘数使用。class Solution { public: int GetUglyNumber_Solution(int index) { if (index <= 1) return index; vector<int> tmp(1, 1); int i2 = 0, i3 = 0, i5 = 0, res, i = 2; while (i <= index) { ...

class Solution { public: string PrintMinNumber(vector<int> numbers) { vector<string> ns; for (auto &i: numbers) { ns.push_back(to_string(i)); } sort(ns.begin(), ns.end(), [](string &a, string &b) { return a + b < ...

设当前数为abcde...（n位）。由于a是否为1限制了1的出现次数，因此分为最高位与后面的数字两个子问题，可以递归处理。a=1，则a处的1贡献了bcde...+1次（a0000...也算一次）。a>1，则最高位为1时可贡献1000...次。计算完最高位贡献的1后，递归计算去除最高位后的数字贡献的1即可。class Solution { public: int NumberOf1Between1AndN_Solution(int n) { if (n <= 0) return 0; if (n < 10) return 1; ...

本质上是动态规划，设以下标为i结尾的子数组最大和为dp[i]，转移方程为dp[i] = max(0, dp[i - 1]) + array[i]。（如果之前的子数组对和的贡献度为负，那么不如舍弃之前的子数组直接选择当前元素）然后再使用一个res变量记录dp[i]的最大值。由于dp[i]只与dp[i-1]有关，所以可以优化成一个变量。class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { int res = array[0], sum = 0; fo...

基本思路：寻找最大/最小的k个数，用优先队列（堆）做。因为每次堆超出k个数时需要把堆顶，即最大的那个数pop，所以需要维护大顶堆。class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { priority_queue<int, vector<int>, less<int>> pq; vector<int> res; for (auto &i...

摩尔投票法，因为题目保证有解所以最后可以免去验证的步骤class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { int res, cnt = 0; for (auto &i: numbers) { if (cnt == 0) { res = i; cnt++; } else if (res == i) cn...