第二章
数组中重复的数字
三种思路：
- 先排序，依次遍历排序后的数组，若存在相邻两元素相等，则存在重复数字
构建一个哈希表(unordered_set)，从头到尾扫描数组，没扫描到一个数字，都可以用O(1)时间来判断哈希表中是否以及包含该数字，若已包含，则存在重复数字，如未包含，则将该数字加入哈希表继续遍历。
class Solution {public:int findRepeatNumber(vector<int>& nums) {// 构建哈希表unordered_set<int> dict;for(int num : nums){// 用O(1)时间判断哈希表中是否已经包含该数字if(dict.find(num) != dict.end()){return num;}// 插入新元素dict.insert(num);}return -1;}};
桶排序：利用数字都在
的条件，把数值为i的数字都放在第i个位置上。class Solution { public: int findRepeatNumber(vector<int>& nums) { for(int i = 0; i < nums.size(); i++){ // 首先比较当前数字是否等于i if(nums[i] == i) continue; // 将nums[i]放到第nums[i]的位置 if(nums[i] != nums[nums[i]]){ swap(nums[i], nums[nums[i]]); }else{ return nums[i]; } } return -1; } };二维数组查找
从二维数组右上角的数字开始，若当前数字等于目标数字，则返回true，若大于目标数字则列号减1（相当于剔除当前数字所在的列），若小于目标数字，则行号加1（相当于当前数字所在的行）。
class Solution { public: bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) { if(matrix.empty()) return false; // 选择二维数组右上角的数组 int i = 0, j = matrix[0].size() - 1; while(i < matrix.size() and j >= 0){ // 如果等于要查找的数字 if(matrix[i][j] == target){ return true; }else if(matrix[i][j] > target){ // 如果大于，剔除这个数字所在的列 j--; }else{ // 如果大于，剔除这个数字所在的行 i++; } } return false; } };替换空格
顺序找到字符串中空格出现的所有位置，用replace函数替换。replace函数参数包括开始替换的位置，被替换字符的长度，和替换字符。
class Solution { public: string replaceSpace(string s) { int index = 0; // 找出s中空格出现的所有位置 while((index = s.find(" ", index)) != string :: npos){ // 用“%20”替换从index开始的1个字符 s.replace(index, 1, "%20"); index += 3; } return s; } };重建二叉树
在前序遍历和中序遍历的数组中找到根节点的位置，根据位置划分数组，分别生成左右子树的前序遍历和中序遍历数组，递归以上步骤。
class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if(preorder.empty() or inorder.empty()) return NULL; TreeNode* root = new TreeNode(0); root->val = preorder[0]; // 在中序遍历数组中找到根节点的位置 int i = 0; while(inorder[i] != preorder[0]){ i++; } // 根据节节点位置划分数组，分别生成左右子树的前序遍历和中序遍历数组 vector<int> preorderLeft(preorder.begin() + 1, preorder.begin() + 1 + i); vector<int> preorderRight(preorder.begin() + 1 + i, preorder.end()); vector<int> inorderLeft(inorder.begin(), inorder.begin() + i); vector<int> inorderRight(inorder.begin() + i + 1, inorder.end()); // 递归重建 root->left = buildTree(preorderLeft, inorderLeft); root->right = buildTree(preorderRight, inorderRight); return root; } };用两个栈实现队列
插入：将当前元素插入s1队尾
删除：如果s1和s2都为空，返回-1；
如果s2非空，s2的栈顶元素就是最先入栈的元素，直接弹出；
如果s2为空且s1不为空，s1的元素逐个压入s2，直到s1仅剩1个元素即为被删除的元素。class CQueue { public: CQueue() { } // 插入s1队尾 void appendTail(int value) { s1.push(value); } int deleteHead() { // 如果s1和s2都为空，返回-1 if(s1.empty() and s2.empty()) return -1; // 如果s2非空 if(!s2.empty()){ // s2的栈顶元素就是最先进入队列的元素 int res = s2.top(); s2.pop(); return res; } // 将s1的数出栈压入s2，直到s1仅剩1一个元素 while(s1.size() > 1){ s2.push(s1.top()); s1.pop(); } // 被删除的元素 int res = s1.top(); s1.pop(); return res; } private: stack<int> s1; stack<int> s2; };斐波那契数列
动态规划：自下而上循环求最优解，用一个dsp数组存储子问题的最优解。
class Solution { public: int fib(int n) { if(n == 0) return 0; if(n == 1) return 1; vector<int> dsp(n + 1, 0); dsp[1] = 1; for(int i = 2; i < dsp.size(); i++){ dsp[i] = (dsp[i - 1] + dsp[i - 2]) % 1000000007; } return dsp[n]; } };旋转数组的最小数字（二分查找）
用两个指针left和right分别指向数组的第一个元素和最后一个元素
如果第一个元素小于最后一个元素，说明数组已经排好序，可以直接返回第一个数字
找到数组的中间元素
如果中间元素大于等于left指针指向的元素，此时数组的最小元素应该位于该中间元素的后面，把left指针指向该中间元素
如果中间元素小于等于right指针指向的元素，此时数组的最小元素应该位于该中间元素的前面，把right指针指向该中间元素
因为left指针总是指向前面递增数组的元素，right指针总是指向后面递减数组的元素。当left指针和right指针指向两个相邻元素时，right指针指向的就是数组中最小的元素。class Solution { public: int minArray(vector<int>& numbers) { int left = 0, right = numbers.size() - 1; // 如果把排序数组的0个元素搬到后面，当前数组仍是排序数组 if(numbers[left] < numbers[right]) return numbers[left]; // 当两个指针相邻，循环结束 while((right - left) > 1){ int mid = (left + right) / 2; // 中间和前后指针指向的数字相等时，无法移动指针来缩小查找范围，只能顺序查找 if(numbers[mid] == numbers[left] and numbers[mid] == numbers[right]){ return orderSearch(numbers); } // 二分查找 if(numbers[mid] >= numbers[left]){ left = mid; }else if(numbers[mid] <= numbers[right]){ right = mid; } } return numbers[right]; } // 顺序查找 int orderSearch(vector<int>& numbers){ int res = numbers[0]; for(int i = 1; i < numbers.size(); i++){ res = min(res, numbers[i]); } return res; } };矩阵中的路径（回溯法）
回溯法的三个问题：
路径：已经做出的选择
- 选择列表：当前可以做出的选择
- 结束条件
回溯函数的框架：
backtrack(路径，选择列表){
if 满足结束条件:
result.add(路径);
return;
for 选择 in 选择列表:
做选择;
backtrack(路径，选择列表);
撤销选择;
}
class Solution {
private:
vector<int> path;
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
// 标记是否访问过的数组
vector<vector<bool>> visited(m, vector<bool>(n, false));
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
bool res = false;
if(visited[i][j] == false){
res = backtrack(board, word, visited, i, j, m, n, 0);
}
if(res){
return true;
}
}
}
return false;
}
bool backtrack(vector<vector<char>>& board, string word, vector<vector<bool>>& visited, int i, int j, int m, int n, int start){
// 结束条件
if(i < 0 or j < 0 or i >= m or j >= n){
return false;
}
if(board[i][j] == word[start] and start == word.size() - 1 and visited[i][j] == false){
return true;
}
bool res = false;
// start标记当前匹配的位置
if(visited[i][j] == false and board[i][j] == word[start]){
// 做选择
visited[i][j] = true;
// 回溯
res = backtrack(board, word, visited, i, j - 1, m, n, start + 1)||
backtrack(board, word, visited, i, j + 1, m, n, start + 1)||
backtrack(board, word, visited, i - 1, j, m, n, start + 1)||
backtrack(board, word, visited, i + 1, j, m, n, start + 1);
if(res) return true;
// 撤销选择
visited[i][j] = false;
}
return false;
}
};
机器人的运动范围
机器人从坐标(0,0)开始移动，当它准备进入坐标为(i,j)的格子时，通过检查坐标的位数和来判断机器人是否能够进入。如果机器人能进入坐标为(i,j)的格子，机器人的运动范围+1，再判断它能否进入4个相邻的格子。
class Solution {
public:
int movingCount(int m, int n, int k) {
vector<vector<bool>>visited(m, vector<bool>(n, false));
return backtrack(visited, 0, 0, m, n, k);
}
int backtrack(vector<vector<bool>>& visited, int i, int j, int m, int n, int k){
// 结束条件
if(i < 0 or j < 0 or i >= m or j >= n or visited[i][j] == true){
return 0;
}
if((digitNum(i) + digitNum(j)) > k){
return 0;
}
// 标记被访问过
visited[i][j] = true;
// 访问的路径长度+1
int res = 1 + backtrack(visited, i - 1, j, m, n, k) + backtrack(visited, i + 1, j, m, n, k) + backtrack(visited, i, j - 1, m, n, k) + backtrack(visited, i, j + 1, m, n, k);
return res;
}
int digitNum(int m){
int res = 0;
while(m > 0){
res += m % 10;
m /= 10;
}
return res;
}
};
剪绳子
状态转移方程：
class Solution {
public:
int cuttingRope(int n) {
if(n == 2) return 1;
if(n == 3) return 2;
vector<int>dsp(n + 1, 0);
dsp[1] = 1;
dsp[2] = 2;
dsp[3] = 3;
for(int i = 4; i <= n; i++){
int temp = 0;
for(int j = 1; j <= i / 2; j++){
temp = max(temp, dsp[j] * dsp[i - j]);
}
dsp[i] = temp;
}
return dsp[n];
}
};
二进制中1的个数
在位运算中，把一个整数减去1再和原来的整数做位运算，得到的结果相当于把整数的二进制表示中最右边的1变成了0。
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while(n){
++count;
n = (n - 1) & n;
}
return count;
}
};
第三章
数值的整数次方（快速幂）
快速幂公式：
class Solution {
public:
double myPow(double x, int n) {
if(x == 0) return 0;
if(n == 0) return 1;
double res = getPower(x, abs(n));
if(n < 0) return double(1)/res;
return res;
}
// 快速幂函数
double getPower(double x, int n){
if(n == 0) return 1;
double p = getPower(x, n / 2);
p *= p;
// 若n是奇数
if(n & 0x1 == 1){
p *= x;
}
return p;
}
};
表示数值的字符串
删除多余的空格
根据e/E的位置将字符串划分为底数和指数两部分
分别判断底数和指数是否合法
class Solution {
public:
bool isNumber(string s) {
// 删除空格
int i = s.find_first_not_of(' ');
if(i == string :: npos) return false;
int j = s.find_last_not_of(' ');
if(j == string :: npos) return false;
s = s.substr(i, j - i + 1);
// 找到e的位置
int e = s.find('e');
if(e == (string :: npos)){
e = s.find('E');
}
// 根据e的位置划分底数和指数
if(e == string :: npos) return judgeBase(s);
return judgeBase(s.substr(0, e)) and judgeExp(s.substr(e + 1));
}
// 判断底数是否合法
bool judgeBase(string base){
bool result = false;
// 判断.出现的次数
bool dot = false;
for(int i = 0; i < base.size(); i++){
if(base[i] == '+' or base[i] == '-'){
if(i != 0){
return false;
}
}else if(base[i] == '.'){
if(dot){
return false;
}
dot = true;
}else if((base[i] < '0') or (base[i] > '9')){
return false;
}else{
result = true;
}
}
return result;
}
// 判断指数是否合法
bool judgeExp(string exp){
bool result = false;
for(int i = 0; i < exp.size(); i++){
if(exp[i] == '+' or exp[i] == '-'){
if(i != 0){
return false;
}
}else if(exp[i] < '0' or exp[i] > '9'){
return false;
}else{
result = true;
}
}
return result;
}
};
反转链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur != nullptr){
swap(cur->next, pre);
swap(pre, cur);
}
return pre;
}
};
合并两个排序的链表（递归）
比较两个头结点的值，将取值较小的头结点合并到新链表，运用递归函数完成合并的过程。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr){
return l2;
}
if(l2 == nullptr){
return l1;
}
ListNode* newHead = NULL;
if(l1->val <= l2->val){
newHead = l1;
newHead->next = mergeTwoLists(l1->next, l2);
}else{
newHead = l2;
newHead->next = mergeTwoLists(l1, l2->next);
}
return newHead;
}
};
数的子结构
同时判断：
- A为根节点的子树和树B是否具有相同的结构
- A的左孩子为根节点的子树和树B是否具有相同的结构
A的右孩子为根节点的子树和树B是否具有相同的结构
class Solution { public: bool isSubStructure(TreeNode* A, TreeNode* B) { // 同时判断A/A的左孩子/A的右孩子 和 B是否有相同的结构 return (A != NULL) and (B != NULL) ? recur(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B) : false; } // 以A为根节点的子树和以B为根节点的子树是否结构相同 bool recur(TreeNode* A, TreeNode* B){ if(B == NULL) return true; if((A == NULL) or (A->val != B->val)) return false; return recur(A->left, B->left) and recur(A->right, B->right); } };第四章
对称的二叉树
设置两个节点指针root1和root2，递归地判断root1->right是否等于root2->left and root1->left是否等于root2->right。
class Solution { public: bool isSymmetric(TreeNode* root) { return recur(root, root); } bool recur(TreeNode* root1, TreeNode* root2){ if(root1 == nullptr and root2 == nullptr) return true; if(root1 == nullptr or root2 == nullptr) return false; if(root1->val != root2->val) return false; return recur(root1->right, root2->left) and recur(root1->left, root2->right); } };顺时针打印矩阵
设置四个方向的边界：right，left，top and bottom。
按照顺时针方向，每次遍历完一行或一列，收缩边界。class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int> res; if(matrix.size() == 0 or matrix[0].size() == 0) return res; // 设置四个方向的边界 int l = 0, r = matrix[0].size() - 1, t = 0, b = matrix.size() - 1; while(true){ // 没遍历完一次 收缩边界 for(int i = l; i <= r; i++){ res.push_back(matrix[t][i]); } if((++t) > b) break; for(int i = t; i <= b; i++){ res.push_back(matrix[i][r]); } if((--r) < l) break; for(int i = r; i >= l; i--){ res.push_back(matrix[b][i]); } if((--b) < t) break; for(int i = b; i >= t; i--){ res.push_back(matrix[i][l]); } if((++l) > r) break; } return res; } };二叉搜索树的后序遍历序列
二叉树的后序遍历序列中，最后一个数字就是根节点的值。
根据二叉搜索树左子树的值都小于等于根节点的值的特性，找到划分左右子树的节点，把整颗树分为左子树对应的子序列和右子树对应的子序列。
判断右子树序列的值是否都大于等于根节点的值。
再递归地处理两个子序列。class Solution { public: bool verifyPostorder(vector<int>& postorder) { if(postorder.size() <= 1) return true; int root = postorder[postorder.size() - 1]; // 找到右子树开始的位置 int i = 0; while((i < postorder.size()- 1) and (postorder[i] <= root)){ i++; } // 判断右子树是不是都大于根节点 int j = i; while(j < postorder.size() - 1){ if(postorder[j++] < root) return false; } // 递归判断左右子树是否满足后序遍历序列 vector<int> left(postorder.begin(), postorder.begin() + i); vector<int> right(postorder.begin() + i, postorder.end() - 1); return verifyPostorder(left) and verifyPostorder(right); } };二叉树中和为某一值的路径
用path数组存储当前路径，用target变量标记当前路径下距离目标的差值。
终止条件：访问到叶节点，判断叶节点的值是否等于target
每次做选择：path.push_back(节点值)，target -= 节点值
访问左子树
访问右子树
撤销选择：path.pop_back()，target += 节点值class Solution { private: vector<int> path; public: vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector<int>> result; if(root == nullptr) return result; backtrack(root, result, sum); return result; } // 用一个变量target来标记当前距离目标的差值 void backtrack(TreeNode* root, vector<vector<int>>& result, int target){ // 叶子结点 if(root->left == nullptr and root->right == nullptr){ if(target == root->val){ path.push_back(root->val); result.push_back(path); path.pop_back(); } return; } // 做选择 path.push_back(root->val); target -= root->val; if(root->left != nullptr){ backtrack(root->left, result, target); } if(root->right != nullptr){ backtrack(root->right, result, target); } // 撤销选择 path.pop_back(); target += root->val; } };字符串的排列
回溯：保存已访问的路径path和未访问的路径unchoosen，注意string中erase和insert函数！！！
去重：先排序，如果相邻的unchoosen节点相等，只访问一个class Solution { public: vector<string> permutation(string s) { vector<string> result; if(s.empty()) return result; // 已访问的路径:path，未访问的路径:unchoosen string unchoosen = s; // 排序，为去重作准备 sort(unchoosen.begin(), unchoosen.end()); backtrack("", unchoosen, result); return result; } // 回溯 void backtrack(string path, string unchoosen, vector<string>& result){ if(unchoosen.empty()){ result.push_back(path); return; } for(int i = 0; i < unchoosen.size(); i++){ // 去重"aab" if(i > 0 and unchoosen[i] == unchoosen[i - 1]){ continue; } // 保存被删除的字符 char c = unchoosen[i]; path.push_back(c); // 注意string中erase和insert函数 unchoosen.erase(unchoosen.begin() + i); backtrack(path, unchoosen, result); unchoosen.insert(unchoosen.begin() + i, c); path.pop_back(); } } };第五章
数据流中的中位数
假设一共有n个数，用一个小顶堆存储最大的n/2个数，用一个大顶堆存储最小的n/2个数。数据流首先进入小顶堆，为了每轮数据在大顶堆和小顶堆中的数量是平衡的，移除小顶堆堆顶的数并插入大顶堆。如果小顶堆的数量小于大顶堆，再将大顶堆堆顶的数移除并插入小顶堆。
class MedianFinder { private: // 小顶堆存储最大的k/2个数字 priority_queue<int, vector<int>, greater<int>> greater_pq; // 大顶堆存储最小的k/2个数字 priority_queue<int, vector<int>, less<int>> less_pq; public: /** initialize your data structure here. */ MedianFinder() { } void addNum(int num) { // 先加到小顶堆 greater_pq.push(num); // 平衡 less_pq.push(greater_pq.top()); greater_pq.pop(); // 维护两个堆元素的个数 if(less_pq.size() > greater_pq.size()){ greater_pq.push(less_pq.top()); less_pq.pop(); } } double findMedian() { if(greater_pq.size() > less_pq.size()) return greater_pq.top(); return double(greater_pq.top() + less_pq.top()) / 2.0; } };把数组排成最小的数（自定义比较函数）
class Solution { public: string minNumber(vector<int>& nums) { vector<string>s; for(int num : nums){ s.push_back(to_string(num)); } sort(s.begin(), s.end(), compare); string result = ""; for(string ss : s){ result += ss; } return result; } // 自定义比较函数 static bool compare(string a, string b){ return a + b < b + a; } };最长不含重复字符的子字符串
如果第i个字符没出现过，dsp[i]=dsp[i-1]+1
如果第i个字符出现过：如果第i个字符到它上次出现在字符串中的位置的距离大于dsp[i-1]：dsp[i]=dsp[i-1]+1；
如果第i个字符到它上次出现在字符串中的位置的距离小于等于dsp[i-1]：dsp[i]=i-indexclass Solution { public: int lengthOfLongestSubstring(string s) { if(s.empty()) return 0; int result = 1; int n = s.size(); if(n == 1) return result; vector<int>dsp(s.size(), 1); for(int i = 1; i < s.size(); i++){ string str = s.substr(0, i); int index = str.find_last_of(s[i]); if(index == -1 or (i - index) > dsp[i - 1]){ dsp[i] = dsp[i - 1] + 1; }else{ dsp[i] = i - index; } result = max(dsp[i], result); } return result; } };数组中的逆序对（归并排序）
参考链接：链接
分解：待排序的区间为[left……right]，令mid = (left + right)/2，把[left……right]分为[left……mid]和[mid+1……right]两部分
解决：使用归并排序递归地排序两个子序列
合并：把两个已排好序的子序列[left……mid]和[mid+1……right]合并起来class Solution { public: int reversePairs(vector<int>& nums) { int len = nums.size(); if(len < 2) return 0; // 初始化一个长度为n的辅助数组 vector<int> temp(len); return reversePairs(nums, temp, 0, len - 1); } // nums[left……right]计算逆序对个数并排序 int reversePairs(vector<int>& nums, vector<int>& temp, int left, int right){ // 递归结束的条件 if(left == right) return 0; // 分解 int mid = (left + right) / 2; int leftPairs = reversePairs(nums, temp, left, mid); int rightPairs = reversePairs(nums, temp, mid + 1, right); // 如果已经有序 if(nums[mid] <= nums[mid + 1]){ return leftPairs + rightPairs; } // 两个数组之间的逆序对 int crossPairs = mergeAndCount(nums, temp, left, mid, right); return leftPairs + rightPairs + crossPairs; } // nums[left……mid]有序 nums[mid+1……right]有序 int mergeAndCount(vector<int>& nums, vector<int>& temp, int left, int mid, int right){ // 复制到nums[left……right]辅助数组 for(int i = left; i <= right; i++){ temp[i] = nums[i]; } int i = left, j = mid + 1; int count = 0; // 合并到原数组 for(int k = left; k <= right; k++){ if(i == mid + 1){ nums[k] = temp[j++]; }else if(j == right + 1){ nums[k] = temp[i++]; }else if(temp[i] <= temp[j]){ nums[k] = temp[i++]; }else{ nums[k] = temp[j++]; // 计算逆序对 count += (mid - i + 1); } } return count; } };两个链表的第一个公共节点
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode* node1 = headA; ListNode* node2 = headB; while(node1 != node2){ node1 = node1 != NULL ? node1->next : headB; node2 = node2 != NULL ? node2->next : headA; } return node1; } };在排序数组中查找数字（二分查找函数）
class Solution { public: int search(vector<int>& nums, int target) { // 返回nums中第一个值大于等于target的指针 auto left = lower_bound(nums.begin(), nums.end(), target); // 返回nums中第一个值大于target的指针 auto right = upper_bound(nums.begin(), nums.end(), target); return right - left; } };第六章
二叉树的深度
class Solution { public: int maxDepth(TreeNode* root) { int depth = 0; return maxDepth(root, depth); } int maxDepth(TreeNode* root, int depth){ if(root == nullptr) return 0; return 1 + max(maxDepth(root->left, depth), maxDepth(root->right, depth)); } };平衡二叉树
递归计算左右子树的深度，若当前节点的左右子树深度之差不小于2，直接返回-1
class Solution { public: bool isBalanced(TreeNode* root) { // 计算数的深度 return maxDepth(root) != -1; } int maxDepth(TreeNode* root){ if(root == nullptr) return 0; // 左子树的深度 int left = maxDepth(root->left); if(left == -1) return -1; // 右子树的深度 int right = maxDepth(root->right); if(right == -1) return -1; // 如果深度之差不小于2，直接返回-1 return abs(left - right) < 2 ? max(left, right) + 1 : -1; } };数组中数字出现的次数
从头到尾疑惑数组中的每个数字，得到的结果就是两个只出现一次的数字的异或结果。
- 在异或结果的数字中找到第一个为1的位置，记为index。
- 以index是否为1把原数组分成两个子数组，每个字数组都包含一个只出现一次的数字，而其他数字都出现了两次。
分别异或两个子数组，找到唯一一个只出现一次的数字
class Solution { public: vector<int> singleNumbers(vector<int>& nums) { int temp = 0; // 对所有的数取异或 for(int num : nums){ temp ^= num; } // 找到第一个位1的位的位置 int index = 1; while((index & temp) == 0){ index = index << 1; } // 以第index位是否为1把原数组分成两个子数组 vector<int> nums1; vector<int> nums2; for(int num : nums){ if((num & index) == 0){ nums1.push_back(num); }else{ nums2.push_back(num); } } // 在两个数组中找到唯一一个只出现一次的数字 int result1 = 0, result2 = 0; for(int num : nums1){ result1 ^= num; } for(int num : nums2){ result2 ^= num; } vector<int> result{{result1, result2}}; return result; } };和为s的连续正数序列Ⅱ（滑动窗口）
滑动窗口框架
int left = 0, right = 0;
while(right < s.size()){
//增大窗口
window.add(s[right]);
right++;
//缩小窗口
while(window needs shrink){
window.remove(s[left]);
left++;
}
}
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
vector<vector<int>>result;
// 滑动窗口边界
int left = 1, right = 1;
int window_value = 1;
vector<int> row{1};
while(left <= (target / 2)){
// 增大窗口
while(window_value < target){
++right;
row.push_back(right);
window_value += right;
}
// 减小窗口
while(window_value > target){
row.erase(row.begin());
window_value -= left;
left++;
}
if(window_value == target){
result.push_back(row);
right++;
row.push_back(right);
window_value += right;
}
}
return result;
}
};
滑动窗口的最大值
把有可能成为滑动窗口最大值的下标存入一个双端队列。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int>result;
if(nums.empty()) return result;
// 用一个双端队列保存最大值
deque<int>q;
// 保存第一个滑动窗口中的最大值的下标
for(int i = 0; i < k; i++){
while(!q.empty() and nums[i] >= nums[q.back()]){
q.pop_back();
}
q.push_back(i);
}
result.push_back(nums[q.front()]);
for(int i = k; i < nums.size(); i++){
// 如果当前的元素比队列的元素大，则队列的元素不可能再作为后面窗口的最大值
while(!q.empty() and nums[i] >= nums[q.back()]){
q.pop_back();
}
// 滑窗不再包括队首数字
if(!q.empty() and (i - q.front()) >= k){
q.pop_front();
}
q.push_back(i);
// 每次队列的第一个数字就是当前滑动窗口下的最大值下标
result.push_back(nums[q.front()]);
}
return result;
}
};
队列中的最大值
参考链接：链接
除了普通队列，我们还需要一个辅助的双端队列存储最大值出队后，队列里的下一个最大值：每次入队时，如果deque的队尾元素小于即将入队的元素value，则将小于value的元素全部出队，再将value入队；否则直接入队。
class MaxQueue {
public:
MaxQueue() {
}
int max_value() {
if(dq.empty()) return -1;
return dq.front();
}
void push_back(int value) {
q.push(value);
while(!dq.empty() and value >= dq.back()){
dq.pop_back();
}
dq.push_back(value);
}
int pop_front() {
if(q.empty()) return -1;
int result = q.front();
if(dq.front() == result){
dq.pop_front();
}
q.pop();
return result;
}
private:
queue<int>q;
deque<int>dq;
};
扑克牌中的顺子
首先把数组排序；其次统计数组中0的个数；最后统计排序之后的数组中相邻数字之间的空缺数。如果空缺总数小于等于0的个数，那么这个数组就是连续的；反之则不连续。
class Solution {
public:
bool isStraight(vector<int>& nums) {
// 对数组paix
sort(nums.begin(), nums.end());
// 数组中0的个数
int i = 0;
while(nums[i] == 0){
i++;
}
int space = 0;
for(int j = i; j < nums.size() - 1; j++){
int diff = nums[j + 1] - nums[j];
if(diff == 0) return false;
// 相邻数字间的空缺数
space += (diff - 1);
if(space > i) return false;
}
return space <= i;
}
};
股票的最大利润
当卖出价固定时，买入价越低获得的利润越大。也就是说，如果在扫描到数组中的第i个数字时，只要我们能够记住之前的(i-1)个数字中的最小值，就能算出在当前价位卖出时可能得到的最大利润。
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() <= 1) return 0;
// [0……i]区间的最小值
int min_price = prices[0];
// [0……i]区间的最大利润
int max_profit = 0;
for(int i = 1; i < prices.size(); i++){
min_price = min(min_price, prices[i]);
max_profit = max(max_profit, prices[i] - min_price);
}
return max_profit;
}
};
把字符串转换成整数
class Solution {
public:
int strToInt(string str) {
if(str.empty()) return 0;
// 找到第一个不是空格的位置
int i = 0;
while(str[i] == ' '){
i++;
}
// 删除之前的空格
str = str.substr(i);
// 如果字符全部由空格组成
if(str.empty()) return 0;
long long result = 0;
bool positive = true;
for(int i = 0; i < str.size(); i++){
// 处理‘+’和‘-’的情况
if(str[i] == '+'){
if(i != 0) return printResult(result, positive);
}else if(str[i] == '-'){
if(i != 0) return printResult(result, positive);
positive = false;
}else if(str[i] < '0' or str[i] > '9'){
return printResult(result, positive);
}else{
// long long 判断是否越界
long long temp = result * 10 + (str[i] - '0');
if(temp >= INT_MAX and positive){
return INT_MAX;
}else if(temp > INT_MAX and !positive){
return INT_MIN;
}else{
result = temp;
}
}
}
return printResult(result, positive);
}
int printResult(int result, bool positive){
if(!positive) return (-1) * result;
return result;
}
};
二叉搜索树的最近公共祖先
二叉搜索树是排序过的，位于左子树的节点都比父节点小，位于右子树的节点都比父节点大，因此我们只需要从数的根节点开始和两个输入的节点进行比较。
如果当前节点的值比两个节点的值都大，那么最低的公共父节点一定在当前节点的左子树中，于是下一步遍历当前节点的左子树节点。
如果当前节点的值比两个节点的值都小，那么最低的公共父节点一定在当前节点的右子树中，于是下一步遍历当前节点的右子树节点。
这样，在树中从上到下找到的第一个在两个输入节点的值之间的节点就是最低的公共祖先。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if((root->val > p->val) and (root->val > q->val)){
// 当前节点的值比两个节点的值都大，遍历左子树
return lowestCommonAncestor(root->left, p, q);
}else if((root->val < p->val) and (root->val < q->val)){
// 当前节点的值比两个节点的值都小，遍历右子树
return lowestCommonAncestor(root->right, p, q);
}
return root;
}
};
二叉树的最近公共祖先Ⅱ
参考链接：链接
递归解析：
- 终止条件：
- 当越过叶节点，返回null
- 等root等于p或q，返回root
- 递归工作：
- 开始递归左子节点，返回值记为left
- 开始递归右子节点，返回值记为right
返回值：根据left和right可以分为四种情况：
- 当left和right都为空，说明root的左右子树都不包括p和q，返回null
- 当left和right都不为空，说明p和q分别在root的异侧，因此root为最近公共祖先节点，返回root
- 当left为空，right不为空，说明p和q都不在root的左子树中，返回right
当right为空，left不为空，说明p和q都不在root的右子树中，返回left
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { // 递归终止条件 if(root == nullptr or root == p or root == q) return root; // 递归工作 TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); // 当left为空，right不为空，说明p和q都不在root的左子树中，返回right if(left == nullptr) return right; if(right == nullptr) return left; // 当left和right都不为空，说明p和q分别在root的异侧，因此root为最近公共祖先节点，返回root return root; } };
若有收获，就点个赞吧
0 人点赞
