剑指offer hot100 第三周
目录
和为S的连续正数序列
左旋转字符串
翻转单词序列
按之字形顺序打印二叉树
二叉搜索树的第k个节点
两数之和
字母异位词分组
最长连续序列
移动零
盛最多水的容器
和为S的连续正数序列
解法：滑动窗口
连续的一段递增非负区间之和，容易想到使用滑动窗口解决：进窗口，统计结果，出窗口
class Solution { public: vector<vector<int>> FindContinuousSequence(int sum) { vector<vector<int>> ret; int tmp = 0; for (int left = 1, right = 1; right < sum; right++) //[left,right] 保证和至少有两个永远在小于sum { //进窗口 tmp += right; while (tmp >= sum) { //统计结果 if (tmp == sum) { vector<int> 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 l=str.size(); // if(l==0) return ""; // n%=l; // while(n--) // { // char ch=str[0]; // int j=0; // for(;j<l-1;j++) str[j]=str[j+1]; // str[j]=ch; // } // return str; // 截取待旋区间与不旋区间后进行合并 // if(str.size()==0) return ""; // string s=str.substr(0,n%str.size()); // str=str.substr(s.size()); // return str+s; // 后面再连接一个完全相同的字符串在进行按需截取 // int l=str.size(); // if(l==0) return""; // str+=str; // 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 n=str.size(); // int l=n-1,r=n-1; // string ret; // while(l>=0) // { // while(l-1>=0&&str[l-1]!=' ') l--; // int tmp=l-2; // while(l<=r) // { // ret+=str[l++]; // } // l=r=tmp; // if(tmp>=0) ret+=' ';//最后一个单词不加空格 // } // return ret; } };按之字形顺序打印二叉树
解法1：模拟
使用队列进行遍历时，如果遇到偶数层就要将收集到的值进行翻转；
解法2：栈和队列
使用栈和队列的特性进行模拟（也要定义标记变量）：先将头节点放到栈中：如果标记变量为1说明下一层的节点要从右向左，所以就要先拿栈中节点的左节点放到队列中，再拿右节点（这个过程要收集栈中的节点值）；所有节点按照该顺序拿完后就把队列中的节点放到栈中，把收集到的节点值保存起来，同时更新标记变量（也就是下一次要从左往右遍历）
class Solution { public: void Reverse(vector<int> &v) { int l = 0, r = v.size() - 1; while (l < r) { int tmp = v[l]; v[l] = v[r]; v[r] = tmp; l++; r--; } } vector<vector<int>> Print(TreeNode *pRoot) { // Stack,Queue结合使用 if (pRoot == nullptr) return {}; vector<vector<int>> ret; queue<TreeNode *> q; stack<TreeNode *> st; vector<int> 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(pRoot==nullptr) return {}; // vector<vector<int>> ret; // queue<TreeNode*> q; // int tmp=1; // q.push(pRoot); // while(q.size()) // { // int sz=q.size(); // vector<int> v; // while(sz--) // { // TreeNode* tmp=q.front();q.pop(); // v.push_back(tmp->val); // if(tmp->left) q.push(tmp->left); // if(tmp->right) q.push(tmp->right); // } // if(tmp%2==0) Reverse(v); // ret.push_back(v); // tmp++; // } // return ret; } };二叉搜索树的第k个节点
解法：递归
因为二叉搜索树的中序遍历是有序的，递归一次把值存到数组中，合法下标返回；
解法：模拟
使用栈进行非递归的中序遍历，细节较多需要结合代码理解，特别是循环的结束条件~
class Solution { public: // vector<int> ret; // void dfs(TreeNode* proot) // { // if(proot==nullptr) return; // dfs(proot->left); // ret.push_back(proot->val); // dfs(proot->right); // } int KthNode(TreeNode *proot, int k) { stack<TreeNode *> 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 || k==0) return -1; // return ret[k-1]; } };补充一个非递归的后序遍历
void BehindTree(TreeNode* proot) { stack<TreeNode*> s; while(proot) { s.push(proot); proot=proot->left; } TreeNode*tmp=nullptr;//标记根节点是否要访问 while(!s.empty()) { TreeNode*node=s.top();s.pop(); //根节点的右子树为空或者右子树被访问过了 if(node->right==nullptr || node->right==tmp) { cout<<node->val<<endl; tmp=node;//标记当前节点被访问了，给上层的根节点做参考 } else { //根节点暂时还没访问到,还要再次入栈 s.push(node); //以右节点为根节点：左子树入栈（最开始循环逻辑） node=node->right; while(node) { s.push(node); node=node->left; } } } }两数之和
解法：哈希
利用哈希表查询O(1)的时间找第二个数是否存在
class Solution { public: vector<int> twoSum(vector<int> &nums, int target) { unordered_map<int, 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 , vector<string>> ：以排序后的字符串作为第一个键值来收集以它为相同字母的所有异位字符串
class Solution { public: vector<vector<string>> groupAnagrams(vector<string> &strs) { unordered_map<string, vector<string>> hash; for (auto &str : strs) { string s = str; sort(s.begin(), s.end()); hash[s].push_back(str); } vector<vector<string>> ret; for (auto &[a, b] : hash) { ret.push_back(b); } return ret; } };最长连续序列
解法：哈希表
先将所有数组存在哈希表中（set或者unordered_set实现）
遍历哈希表中的每个数x：（贪心）找起点（不存在x-1），从起点开始往后找连续序列，从中找到最长连续序列
找x-1，x-2，x-3... 和x+1，x+2，x+3... 的两个数，也就是连续序列的左端点与右端点，进行相减就找到了一段连续序列，从中筛选出最长连续序列
class Solution { public: int longestConsecutive(vector<int> &nums) { set<int> 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; // 找x+1的数 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(vector<int> &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)// e<n-1保证e在最后一个位置停止 e++; swap(nums[b++], nums[e++]); } } };盛最多水的容器
解法：双指针
木桶效应：盛最多水取决于最小的那块木板；当然左右之间的距离也影响大小
所以定义双指针时定义在左右两端，计算结果去max后移动两个中较小的那个，才有可能遇到比较大的木板让结果变大
class Solution { public: int maxArea(vector<int> &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: vector<vector<int>> threeSum(vector<int> &nums) { // 排序让相同数靠在一起/固定最小(大)值后进行遍历 sort(nums.begin(), nums.end()); vector<vector<int>> 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(vector<int> &height) { // 一层一层计算得到总面积大小(水与柱子组成的面积)减去height中所有元素之和 int sum = 0, h = 1, n = height.size(); for (int left = 0, right = n - 1; left <= right;) // left<=right 把只有一个柱子的情况给统计到 { 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(vector<int> &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(vector<int> &height) { int sum = 0, n = height.size(); stack<int> 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: vector<int> dailyTemperatures(vector<int>& temperatures) { int n=temperatures.size(); vector<int> ret(n); stack<int> s; //正向遍历 // for(int i=0;i<n;i++) // { // int t=temperatures[i]; // while(!s.empty()&&t>temperatures[s.top()]) //找到了未来的温度 // { // int pos=s.top(); // ret[pos]=i-pos; // s.pop(); // } // s.push(i); // } //反向遍历 for(int i=n-1;i>=0;i--) { int t=temperatures[i]; while(!s.empty() && t>=temperatures[s.top()]) s.pop();//栈顶小就说明未来的这天温度不是我要找的 if(!s.empty()) ret[i]=s.top()-i; s.push(i); } return ret; } };以上便是全部内容，有问题欢迎在评论区指正，感谢观看！