目录和为S的连续正数序列左旋转字符串翻转单词序列按之字形顺序打印二叉树二叉搜索树的第k个节点两数之和字母异位词分组最长连续序列移动零盛最多水的容器和为S的连续正数序列解法滑动窗口连续的一段递增非负区间之和容易想到使用滑动窗口解决进窗口统计结果出窗口class Solution { public: vectorvectorint FindContinuousSequence(int sum) { vectorvectorint ret; int tmp 0; for (int left 1, right 1; right sum; right) //[left,right] 保证和至少有两个永远在小于sum { //进窗口 tmp right; while (tmp sum) { //统计结果 if (tmp sum) { vectorint v; for (int i left; i right; i) v.push_back(i); ret.push_back(v); } //出窗口 tmp - left; left; } } return ret; } };左旋转字符串因为可能出现 n str.size() 所以 n%strsize()解法1模拟模拟一次的逆置逆置n次就只要循环n次解法2模拟把左旋的字符串s1 与不旋的字符串s2 分别截取出来后进行拼接 s2 s1 后返回解法3技巧在字符串后面再次拼接上相同字符串左旋几个就从左旋个数下标截取原字符串长度出来解法4模拟先局部逆置再整体逆置将左旋的区间的字符串逆置不左旋的区间的字符串逆置再总体逆置一遍后就得到答案class Solution { public: void Reverse(string str, int l, int r) { while (l r) { char tmp str[l]; str[l] str[r]; str[r] tmp; l; r--; } } string LeftRotateString(string str, int n) { // 一个一个进行左旋 // int lstr.size(); // if(l0) return ; // n%l; // while(n--) // { // char chstr[0]; // int j0; // for(;jl-1;j) str[j]str[j1]; // str[j]ch; // } // return str; // 截取待旋区间与不旋区间后进行合并 // if(str.size()0) return ; // string sstr.substr(0,n%str.size()); // strstr.substr(s.size()); // return strs; // 后面再连接一个完全相同的字符串在进行按需截取 // int lstr.size(); // if(l0) return; // strstr; // return str.substr(n%l,l); // 截取待旋区间与不旋区间后分别进行逆置,再整体逆置 if (str.size() 0) return ; n % str.size(); Reverse(str, 0, n - 1); Reverse(str, n, str.size() - 1); Reverse(str, 0, str.size() - 1); return str; } };翻转单词序列解法1双指针从后完前利用双指针将单词进行拼接有细节解法2模拟对一个一个单词进行逆置再整体逆置一遍就得答案上题思路class Solution { public: void Reverse(string str, int l, int r) { while (l r) { char tmp str[l]; str[l] str[r]; str[r] tmp; l; r--; } } string ReverseSentence(string str) { // 一个一个字符先局部逆置再整体逆置 if (str.size() 0) return ; int l 0, r 0, n str.size(); while (r n) { while (r n str[r] ! ) r; Reverse(str, l, r - 1); r; l r; } Reverse(str, 0, n - 1); return str; // 从后往前使用双指针进行拼接一个一个字符 // int nstr.size(); // int ln-1,rn-1; // string ret; // while(l0) // { // while(l-10str[l-1]! ) l--; // int tmpl-2; // while(lr) // { // retstr[l]; // } // lrtmp; // if(tmp0) ret ;//最后一个单词不加空格 // } // return ret; } };按之字形顺序打印二叉树解法1模拟使用队列进行遍历时如果遇到偶数层就要将收集到的值进行翻转解法2栈和队列使用栈和队列的特性进行模拟也要定义标记变量先将头节点放到栈中如果标记变量为1说明下一层的节点要从右向左所以就要先拿栈中节点的左节点放到队列中再拿右节点这个过程要收集栈中的节点值所有节点按照该顺序拿完后就把队列中的节点放到栈中把收集到的节点值保存起来同时更新标记变量也就是下一次要从左往右遍历class Solution { public: void Reverse(vectorint v) { int l 0, r v.size() - 1; while (l r) { int tmp v[l]; v[l] v[r]; v[r] tmp; l; r--; } } vectorvectorint Print(TreeNode *pRoot) { // Stack,Queue结合使用 if (pRoot nullptr) return {}; vectorvectorint ret; queueTreeNode * q; stackTreeNode * st; vectorint v; int t 1; // 标记 st.push(pRoot); while (!st.empty()) { while (!st.empty()) { TreeNode *tmp st.top(); st.pop(); v.push_back(tmp-val); // 下层节点要从右向左遍历就要先拿左节点再拿右节点 TreeNode *first t 1 ? tmp-left : tmp-right; TreeNode *second t 1 ? tmp-right : tmp-left; if (first) q.push(first); if (second) q.push(second); } ret.push_back(v); v.clear(); t t 1 ? 2 : 1; // 标记更新 // 把下一层的节点放到栈中 while (!q.empty()) { st.push(q.front()); q.pop(); } } return ret; // 偶次层进行逆置 // if(pRootnullptr) return {}; // vectorvectorint ret; // queueTreeNode* q; // int tmp1; // q.push(pRoot); // while(q.size()) // { // int szq.size(); // vectorint v; // while(sz--) // { // TreeNode* tmpq.front();q.pop(); // v.push_back(tmp-val); // if(tmp-left) q.push(tmp-left); // if(tmp-right) q.push(tmp-right); // } // if(tmp%20) Reverse(v); // ret.push_back(v); // tmp; // } // return ret; } };二叉搜索树的第k个节点解法递归因为二叉搜索树的中序遍历是有序的递归一次把值存到数组中合法下标返回解法模拟使用栈进行非递归的中序遍历细节较多需要结合代码理解特别是循环的结束条件~class Solution { public: // vectorint ret; // void dfs(TreeNode* proot) // { // if(prootnullptr) return; // dfs(proot-left); // ret.push_back(proot-val); // dfs(proot-right); // } int KthNode(TreeNode *proot, int k) { stackTreeNode * s; do { // 以proot为根节点:左子树入栈 while (proot) { //这里收集数据就是非递归的前序遍历写法 s.push(proot); proot proot-left; } // 从栈顶节点开始进行出栈如果有右子树务必要加入到栈中 if (!s.empty()) { TreeNode *tmp s.top(); s.pop(); // 栈顶节点依次出栈也是找第k小节点的过程 if (--k 0) return tmp-val; proot tmp-right; // 记录右节点如果右节点有左右子树,下次循环就将它们入栈 } } while (proot ! nullptr || !s.empty()); // 可能在子树中出现只有左子树或者右子树的情况 return -1; // dfs(proot); // if(ret.size()k || k0) return -1; // return ret[k-1]; } };补充一个非递归的后序遍历void BehindTree(TreeNode* proot) { stackTreeNode* s; while(proot) { s.push(proot); prootproot-left; } TreeNode*tmpnullptr;//标记根节点是否要访问 while(!s.empty()) { TreeNode*nodes.top();s.pop(); //根节点的右子树为空或者右子树被访问过了 if(node-rightnullptr || node-righttmp) { coutnode-valendl; tmpnode;//标记当前节点被访问了给上层的根节点做参考 } else { //根节点暂时还没访问到,还要再次入栈 s.push(node); //以右节点为根节点左子树入栈最开始循环逻辑 nodenode-right; while(node) { s.push(node); nodenode-left; } } } }两数之和解法哈希利用哈希表查询O(1)的时间找第二个数是否存在class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int hash; for (int i 0; i nums.size(); i) { int tmp target - nums[i]; if (hash.find(tmp) ! hash.end()) return {hash[tmp], i}; else hash[nums[i]] i; } return {-1, -1}; } };字母异位词分组解法哈希定义哈希表的类型为 string , vectorstring 以排序后的字符串作为第一个键值来收集以它为相同字母的所有异位字符串class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring hash; for (auto str : strs) { string s str; sort(s.begin(), s.end()); hash[s].push_back(str); } vectorvectorstring ret; for (auto [a, b] : hash) { ret.push_back(b); } return ret; } };最长连续序列解法哈希表先将所有数组存在哈希表中set或者unordered_set实现遍历哈希表中的每个数x贪心找起点不存在x-1从起点开始往后找连续序列从中找到最长连续序列找x-1x-2x-3... 和x1x2x3... 的两个数也就是连续序列的左端点与右端点进行相减就找到了一段连续序列从中筛选出最长连续序列class Solution { public: int longestConsecutive(vectorint nums) { setint hash(nums.begin(), nums.end()); // 省去写遍历数组 int ret 0; for (auto x : hash) { // if(hash.find(x-1)!hash.end()) continue; // 找x-1的数 if (hash.contains(x - 1)) continue; // 找x1的数 int y x 1; // while(hash.find(y)!hash.end()) y; while (hash.contains(y)) y; ret max(ret, y - x); } return ret; } };移动零解法双指针两个指针时根据指针划分区间后进行分情况进行移动class Solution { public: void moveZeroes(vectorint nums) { //[0,b]非0 [e,n-1]零 e找非0交换 int n nums.size(), b 0, e 0; while (e n) { while (e n - 1 nums[e] 0)// en-1保证e在最后一个位置停止 e; swap(nums[b], nums[e]); } } };盛最多水的容器解法双指针木桶效应盛最多水取决于最小的那块木板当然左右之间的距离也影响大小所以定义双指针时定义在左右两端计算结果去max后移动两个中较小的那个才有可能遇到比较大的木板让结果变大class Solution { public: int maxArea(vectorint height) { int n height.size(), b 0, e n - 1, ret 0; while (b e) { ret max(ret, (e - b) * min(height[b], height[e])); if (height[b] height[e]) b; else e--; } return ret; } };三数之和解法双指针先排序方便使用双指针寻找值并进行去重接着遍历时先固定最左(小)/右(大)数定义左右双指针向内聚拢进行三数之和为0的情况找到统计完要先去重后才接着往中间找避免漏掉class Solution { public: vectorvectorint threeSum(vectorint nums) { // 排序让相同数靠在一起/固定最小(大)值后进行遍历 sort(nums.begin(), nums.end()); vectorvectorint ret; int n nums.size(); for (int i 0; i n;) { if (nums[i] 0) break; // 小优化 int left i 1, right n - 1; while (left right) { int sum nums[left] nums[right] nums[i]; if (sum 0) left; else if (sum 0) right--; else { ret.push_back({nums[i], nums[left], nums[right]}); // 去重 left; right--; while (left right nums[left] nums[left - 1]) left; while (left right nums[right] nums[right 1]) right--; } } // 去重 i; while (i n nums[i] nums[i - 1]) i; } return ret; } };接雨水解法1双指针定义双指针指向左右两端通过指针向中间靠拢得到每层面积相加得到柱子与水的总面积class Solution { public: int trap(vectorint height) { // 一层一层计算得到总面积大小(水与柱子组成的面积)减去height中所有元素之和 int sum 0, h 1, n height.size(); for (int left 0, right n - 1; left right;) // leftright 把只有一个柱子的情况给统计到 { while (left right height[left] h) left; while (left right height[right] h) right--; sum right - left 1; h; } for (auto h : height) sum - h; return sum; } };解法2预处理 双指针遍历到当前位置时找到左边元素的最大值(包括自己)与右边元素的最大值后取最小值减去当前位置的值就得到当前位置接到的雨水的多少预处理出每个位置左边的最大值与右边的最大值class Solution { public: int trap(vectorint height) { int left_max[100001] {0}, right_max[100001] {0}, n height.size(); // 主要下标映射 for (int i 1; i n; i) { left_max[i] max(left_max[i - 1], height[i - 1]); } for (int i n; i 0; i--) { right_max[i] max(right_max[i 1], height[i - 1]); } int sum 0; for (int i 0; i n; i) { sum min(left_max[i 1], right_max[i 1]) - height[i]; } return sum; } };解法3单调栈上面的思路是按照竖着得到雨水面积我们也可以通过横着式计算出雨水大小数组【1,0,2,1,0,1,3】刚开始栈为空入栈此时栈内【1】一直是单调递减i 1时元素0小于栈顶元素入栈此时栈内【1,0】i 2时元素2大于栈顶元素使用变量tmp保存0出栈栈内【1】此时可以来统计1~2中雨水的面积宽1和2的距离下标之差(2-0)-1 1高min(1,2) - 0 1所以面积为1 * 1 1接下来 2 再与栈顶元素1进行比较大于栈顶元素出栈此时栈内为空结束计算把2入栈此时栈内【2】...遍历到当前位置找上一个比我小的元素在找的过程中填坑计算雨水面积class Solution { public: int trap(vectorint height) { int sum 0, n height.size(); stackint s; for (int i 0; i n; i) { int h height[i]; while (!s.empty() h height[s.top()]) //重复元素进循环 { int t height[s.top()]; s.pop(); if (s.empty()) break; int height min(height[s.top()], h) - t; sum height * (i - s.top() - 1); } s.push(i); } return sum; } };每日温度单调栈解法单调栈正向遍历找大温度找到后对栈中存着的升序的小温度进行初始化方向遍历找待初始化的温度用栈中存着降序的大温度来初始化class Solution { public: vectorint dailyTemperatures(vectorint temperatures) { int ntemperatures.size(); vectorint ret(n); stackint s; //正向遍历 // for(int i0;in;i) // { // int ttemperatures[i]; // while(!s.empty()ttemperatures[s.top()]) //找到了未来的温度 // { // int poss.top(); // ret[pos]i-pos; // s.pop(); // } // s.push(i); // } //反向遍历 for(int in-1;i0;i--) { int ttemperatures[i]; while(!s.empty() ttemperatures[s.top()]) s.pop();//栈顶小就说明未来的这天温度不是我要找的 if(!s.empty()) ret[i]s.top()-i; s.push(i); } return ret; } };以上便是全部内容有问题欢迎在评论区指正感谢观看