215. 数组中的第K KK个最大元素
给定整数数组nums 和整数k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第k 个不同的元素。
你必须设计并实现时间复杂度为O(n) 的算法解决此问题。
class Solution { public: int quick_selection(vector<int>& nums,int l,int r,int k){ if (l==r) return nums[k]; int x=nums[l]; int i=l-1,j=r+1; while(i<j){ do i++;while(nums[i]<x); do j--;while(nums[j]>x); if (i<j) swap(nums[i],nums[j]); } if (k<=j) return quick_selection(nums,l,j,k); else return quick_selection(nums,j+1,r,k); } int findKthLargest(vector<int>& nums, int k) { return quick_selection(nums,0,nums.size()-1,nums.size()-k); } };
221. 最大正方形
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
class Solution { public: int maximalSquare(vector<vector<char>>& matrix) { int n=matrix.size(); int m=matrix[0].size(); int res=0; vector<vector<int>> f(n,vector<int>(m,0)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if (i==j&&i==0) f[i][j]=matrix[i][j]-'0'; else if (i==0||j==0) f[i][j]=matrix[i][j]-'0'; else if (matrix[i][j]=='1') f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1; res=max(res,f[i][j]); } } return res*res; } };
226. 翻转二叉树
class Solution { public: TreeNode* invertTree(TreeNode* root) { if (root==NULL) return root; if (root->left!=NULL) invertTree(root->left); if (root->right!=NULL) invertTree(root->right); swap(root->left,root->right); return root; } };
234. 回文链表
class Solution { public: bool isPalindrome(ListNode* head) { stack<int> stk; ListNode *p=head; while(p!=NULL){ stk.push(p->val); p=p->next; } p=head; while(!stk.empty()){ int t=stk.top(); stk.pop(); if (t!=p->val){ return false; } p=p->next; } return true; } };
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树T TT的两个节点 q，最近公共祖先表示为一个节点x，满足x是q的祖先且x xx的深度尽可能大（一个节点也可以是它自己的祖先）。”
class Solution { public: unordered_map<TreeNode *,int> l; unordered_map<TreeNode *,TreeNode *>f; void dfs(TreeNode *root){ if (root->left){ f[root->left]=root; l[root->left]=l[root]+1; dfs(root->left); } if (root->right){ f[root->right]=root; l[root->right]=l[root]+1; dfs(root->right); } return; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { f[root]=NULL; l[root]=0; dfs(root); int lp=l[p]; int lq=l[q]; while(lp>lq){ p=f[p]; lp=l[p]; } while(lq>lp){ q=f[q]; lq=l[q]; } while(p!=q){ p=f[p]; q=f[q]; } return p; } };
238. 除自身以外数组的乘积
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n=nums.size(); vector<int> l(n,1);//左缀 vector<int> r(n,1);//右缀 for(int i=1;i<n;i++) l[i]=l[i-1]*nums[i-1]; for(int i=n-2;i>=0;i--) r[i]=r[i+1]*nums[i+1]; vector<int> res(n,1); for(int i=0;i<n;i++) res[i]=l[i]*r[i]; return res; } };
239. 滑动窗口最大值
给你一个整数数组snums，有一个大小为k kk的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; int n=nums.size(); vector<int> ans; for (int i = 0; i < n; i++) { if (!dq.empty() && i - k + 1 > dq.front()) dq.pop_front(); while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back(); dq.push_back(i); if (i >= k - 1) ans.push_back(nums[dq.front()]); } return ans; } };
240. 搜索二维矩阵 II
编写一个高效的算法来搜索mxn矩阵matrix中的一个目标值target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty()||matrix[0].empty()) return false; int n=matrix.size(); int m=matrix[0].size(); int i=0,j=m-1; while(i<n&&j>=0){ int t=matrix[i][j]; if (t==target) return true; else if (t>target) j--; else i++; } return false; } };
279. 完全平方数
给你一个整数n，返回和为n的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
class Solution { public: int numSquares(int n) { vector<int> f(n+1,0x3f3f3f3f); f[0]=0; f[1]=1; for(int i=2;i<=n;i++){ for(int j=1;j*j<=i;j++) f[i]=min(f[i],f[i-j*j]+1); } return f[n]; } };
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
class Solution { public: void moveZeroes(vector<int>& nums) { int n=nums.size(); int i=0,j=0; for(;i<n;i++){ if (nums[i]!=0){ nums[j]=nums[i]; j++; } } for(;j<n;j++) nums[j]=0; } };
287. 寻找重复数
给定一个包含n+1个整数的数组snums，其数字都在[1,n] 范围内（包括1和n），可知至少存在一个重复的整数。
假设nums只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组snums且只用常量级O(1)的额外空间。
class Solution { public: int findDuplicate(vector<int>& nums) { int slow=0,fast=0; do{ slow=nums[slow]; fast=nums[nums[fast]]; }while(slow!=fast); slow=0; while(slow!=fast){ slow=nums[slow]; fast=nums[fast]; } return slow; } };
297. 二叉树的序列化与反序列化
class Codec { public: string path; // Encodes a tree to a single string. string serialize(TreeNode* root) { dfs_s(root); return path; } void dfs_s(TreeNode* root) { if (!root) path += "#,"; else { path += to_string(root->val) + ','; dfs_s(root->left); dfs_s(root->right); } } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { int u = 0; return dfs_d(data, u); } TreeNode* dfs_d(string& data, int& u) { if (data[u] == '#') { u += 2; return NULL; } else { int k = u; while (data[u] != ',') u ++ ; auto root = new TreeNode(stoi(data.substr(k, u - k))); u ++ ; root->left = dfs_d(data, u); root->right = dfs_d(data, u); return root; } } };
301. 删除无效的括号
给你一个由若干括号和字母组成的字符串s，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
class Solution { public: vector<string> ans; vector<string> removeInvalidParentheses(string s) { int l = 0, r = 0; for (auto x: s) if (x == '(') l ++ ; else if (x == ')') { if (l == 0) r ++ ; else l -- ; } dfs(s, 0, "", 0, l, r); return ans; } void dfs(string& s, int u, string path, int cnt, int l, int r) { if (u == s.size()) { if (!cnt) ans.push_back(path); return; } if (s[u] != '(' && s[u] != ')') dfs(s, u + 1, path + s[u], cnt, l, r); else if (s[u] == '(') { int k = u; while (k < s.size() && s[k] == '(') k ++ ; l -= k - u; for (int i = k - u; i >= 0; i -- ) { if (l >= 0) dfs(s, k, path, cnt, l, r); path += '('; cnt ++, l ++ ; } } else if (s[u] == ')') { int k = u; while (k < s.size() && s[k] == ')') k ++ ; r -= k - u; for (int i = k - u; i >= 0; i -- ) { if (cnt >= 0 && r >= 0) dfs(s, k, path, cnt, l, r); path += ')'; cnt --, r ++ ; } } } };
309. 最佳买卖股票时机含冷冻期
给定一个整数数组prices，其中prices[i]表示第i ii天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
class Solution { public: int maxProfit(vector<int>& prices) { int n=prices.size(); vector<vector<int>> f(n,vector<int>(3,0)); f[0][1]=-prices[0]; int res=0; for(int i=1;i<n;i++){ f[i][0]=max(f[i-1][0],f[i-1][2]); f[i][1]=max(f[i-1][0]-prices[i],f[i-1][1]); f[i][2]=f[i-1][1]+prices[i]; } return max(f[n-1][0],f[n-1][2]); } };
312. 戳气球
有n个气球，编号为n−1，每个气球上都标有一个数字，这些数字存在数组nums中。
现在要求你戳破所有的气球。戳破第i ii个气球，你可以获得nums[i+1]枚硬币。 这里的i+1代表和i ii相邻的两个气球的序号。如果i−1或i+1超出了数组的边界，那么就当它是一个数字为1的气球。
求所能获得硬币的最大数量。
class Solution { public: int maxCoins(vector<int>& nums) { int n=nums.size(); vector<int> a(n+2,1); for(int i=0;i<n;i++) a[i+1]=nums[i]; vector<vector<int>> f(n+2,vector<int>(n+2,0)); for(int len=3;len<=n+2;len++){ for(int i=0;i+len-1<=n+1;i++){ int j=i+len-1; for(int k=i+1;k<j;k++){ f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]); } } } return f[0][n+1]; } };
322. 零钱兑换
给你一个整数数组coins，表示不同面额的硬币；以及一个整数amount，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 −1。
你可以认为每种硬币的数量是无限的。
class Solution { public: int coinChange(vector<int>& coins, int amount) { sort(coins.begin(),coins.end()); vector<int> f(amount+1,0x3f3f3f3f); f[0]=0; for(int i=1;i<=amount;i++){ for(int coin:coins){ if (i>=coin) f[i]=min(f[i],f[i-coin]+1); } } if (f[amount]==0x3f3f3f3f) return -1; else return f[amount]; } };
337. 打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
class Solution { public: vector<int> dfs(TreeNode *root){ if (root==NULL) return {0,0}; vector<int> f(2); auto l=dfs(root->left); auto r=dfs(root->right); f[0]=max(l[0],l[1])+max(r[0],r[1]); f[1]=l[0]+r[0]+root->val; return f; } int rob(TreeNode* root) { auto f=dfs(root); return max(f[0],f[1]); } };
338. 比特位计数
给你一个整数n ，对于i<=n中的每个i，计算其二进制表示中 1 的个数 ，返回一个长度为n+1的数组ans作为答案。
class Solution { public: vector<int> countBits(int n) { vector<int> f(n+1); for(int i=1;i<=n;i++){ f[i]=f[i>>1]+(i&1); } return f; } };
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> cnt; for (auto x: nums) cnt[x] ++ ; int n = nums.size(); vector<int> s(n + 1); for (auto [x, c]: cnt) s[c] ++ ; int i = n, t = 0; while (t < k) t += s[i -- ]; vector<int> res; for (auto [x, c]: cnt) if (c > i) res.push_back(x); return res; } };
394. 字符串解码
class Solution { public: string decodeString(string s) { int u = 0; return dfs(s, u); } string dfs(string& s, int& u) { string res; while (u < s.size() && s[u] != ']') { if (s[u] >= 'a' && s[u] <= 'z' || s[u] >= 'A' && s[u] <= 'Z') res += s[u ++ ]; else if (s[u] >= '0' && s[u] <= '9') { int k = u; while (s[k] >= '0' && s[k] <= '9') k ++ ; int x = stoi(s.substr(u, k - u)); u = k + 1; string y = dfs(s, u); u ++ ; // 过滤掉右括号 while (x -- ) res += y; } } return res; } };
399. 除法求值
给你一个变量对数equations和一个实数值数组values作为已知条件，其中equationsi=Ai,Bi和ivaluesi共同表示等式iAi/Bi=valuesi。每个Ai或iBi是一个表示单个变量的字符串。
另有一些以数组queries表示的问题，其中jqueriesj=Cj,Dj表示第j jj个问题，请你根据已知条件找出j=Cj/Dj=? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
class Solution { public: vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) { unordered_set<string> vers; unordered_map<string, unordered_map<string, double>> d; for (int i = 0; i < equations.size(); i ++ ) { auto a = equations[i][0], b = equations[i][1]; auto c = values[i]; d[a][b] = c, d[b][a] = 1 / c; vers.insert(a), vers.insert(b); } for (auto k: vers) for (auto i: vers) for (auto j: vers) if (d[i][k] && d[j][k]) d[i][j] = d[i][k] * d[k][j]; vector<double> res; for (auto q: queries) { auto a = q[0], b = q[1]; if (d[a][b]) res.push_back(d[a][b]); else res.push_back(-1); } return res; } };
402. 移掉K位数字
class Solution { public: string removeKdigits(string num, int k) { k = min(k, (int)num.size()); string res; for (auto c: num) { while (k && res.size() && res.back() > c) { k -- ; res.pop_back(); } res += c; } while (k -- ) res.pop_back(); k = 0; while (k < res.size() && res[k] == '0') k ++ ; if (k == res.size()) res += '0'; return res.substr(k); } };
406. 根据身高重建队列
假设有打乱顺序的一群人站成一个队列，数组people表示队列中一些人的属性（不一定按顺序）。每个peoplei=hi,ki表示第i ii个人的身高为ihi，前面正好有ki个身高大于或等于hi的人。
请你重新构造并返回输入数组eople所表示的队列。返回的队列应该格式化为数组queue ，其中queuej=hj,kj是队列中第个人的属性（queue0是排在队列前面的人）。
class Solution { public: int n; vector<int> tr; int lowbit(int x) { return x & -x; } void add(int x, int v) { for (int i = x; i <= n; i += lowbit(i)) tr[i] += v; } int query(int x) { int res = 0; for (int i = x; i; i -= lowbit(i)) res += tr[i]; return res; } vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { n = people.size(); tr.resize(n + 1); sort(people.begin(), people.end(), [](vector<int>a, vector<int>b) { if (a[0] != b[0]) return a[0] < b[0]; return a[1] > b[1]; }); vector<vector<int>> res(n); for (auto p: people) { int h = p[0], k = p[1]; int l = 1, r = n; while (l < r) { int mid = l + r >> 1; if (mid - query(mid) >= k + 1) r = mid; else l = mid + 1; } res[r - 1] = p; add(r, 1); } return res; } }; /* class Solution { public: vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { auto cmp = [](const vector<int>& a, const vector<int>& b) { if(a[0] != b[0]) return a[0] < b[0]; return a[1] > b[1]; }; sort(people.begin(), people.end(), cmp); int n = people.size(); vector<vector<int>> res(n); for(auto &p: people) { int k = p[1] + 1; for(auto &seg: res) if(seg.empty()) { k --; if(!k) { seg = p; break; } } } return res; } }; */
416. 分割等和子集
给你一个 只包含正整数的非空数组nums请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
class Solution { public: bool canPartition(vector<int>& nums) { bitset<10001> f; f[0] = 1; int sum = 0; for (auto x: nums) { f |= f << x; sum += x; } if (sum % 2) return false; return f[sum / 2]; } };
437. 路径总和 III
给定一个二叉树的根节点root，和一个整数targetSum，求该二叉树里节点值之和等于 targetSum的路径的数目。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
class Solution { public: unordered_map<int, int> cnt; int res = 0; int pathSum(TreeNode* root, int sum) { cnt[0] ++ ; dfs(root, sum, 0); return res; } void dfs(TreeNode* root, int sum, int cur) { if (!root) return; cur += root->val; res += cnt[cur - sum]; cnt[cur] ++ ; dfs(root->left, sum, cur), dfs(root->right, sum, cur); cnt[cur] -- ; } };
438. 找到字符串中所有字母异位词
给定两个字符串s和p，找到s中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
class Solution { public: vector<int> findAnagrams(string s, string p) { unordered_map<char, int> cnt; for (auto c: p) cnt[c] ++ ; vector<int> res; int tot = cnt.size(); for (int i = 0, j = 0, satisfy = 0; i < s.size(); i ++ ) { if ( -- cnt[s[i]] == 0) satisfy ++ ; while (i - j + 1 > p.size()) { if (cnt[s[j]] == 0) satisfy -- ; cnt[s[j ++ ]] ++ ; } if (satisfy == tot) res.push_back(j); } return res; } };
448. 找到所有数组中消失的数字
给你一个含n个整数的数组nums，其中numsi在区间[1,n]内。请你找出所有在[1,n]范围内但没有出现在nums中的数字，并以数组的形式返回结果。
class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { for (auto x: nums) { x = abs(x); if (nums[x - 1] > 0) nums[x - 1] *= -1; } vector<int> res; for (int i = 0; i < nums.size(); i ++ ) if (nums[i] > 0) res.push_back(i + 1); return res; } };
461. 汉明距离
class Solution { public: int hammingDistance(int x, int y) { int res = 0; while (x || y) { res += (x & 1) ^ (y & 1); x >>= 1, y >>= 1; } return res; } };
494. 目标和
给你一个整数数组nums和一个整数target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums=[2,1]，可以在2之前添加 ‘+’ ，在1之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等target的不同表达式的数目。
class Solution { public: int findTargetSumWays(vector<int>& a, int S) { if (S < -1000 || S > 1000) return 0; int n = a.size(), Offset = 1000; vector<vector<int>> f(n + 1, vector<int>(2001)); f[0][Offset] = 1; for (int i = 1; i <= n; i ++ ) for (int j = -1000; j <= 1000; j ++ ) { if (j - a[i - 1] >= -1000) f[i][j + Offset] += f[i - 1][j - a[i - 1] + Offset]; if (j + a[i - 1] <= 1000) f[i][j + Offset] += f[i - 1][j + a[i - 1] + Offset]; } return f[n][S + Offset]; } };
538. 把二叉搜索树转换为累加树
class Solution { public: int sum = 0; TreeNode* convertBST(TreeNode* root) { dfs(root); return root; } void dfs(TreeNode* root) { if (!root) return; dfs(root->right); int x = root->val; root->val += sum; sum += x; dfs(root->left); } };
543. 二叉树的直径
class Solution { public: int ans = 0; int diameterOfBinaryTree(TreeNode* root) { dfs(root); return ans; } int dfs(TreeNode* root) { if (!root) return 0; int left = dfs(root->left), right = dfs(root->right); ans = max(ans, left + right); return max(left, right) + 1; } };
560. 和为K KK的子数组
给你一个整数数组nums和一个整数k，请你统计并返回该数组中和为k的连续子数组的个数 。
class Solution { public: int subarraySum(vector<int>& nums, int k) { int n = nums.size(); vector<int> s(n + 1); for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + nums[i - 1]; unordered_map<int, int> hash; hash[0] = 1; int res = 0; for (int i = 1; i <= n; i ++ ) { res += hash[s[i] - k]; hash[s[i]] ++ ; } return res; } };
581. 最短无序连续子数组
给你一个整数数组nums，你需要找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的最短子数组，并输出它的长度。
class Solution { public: int findUnsortedSubarray(vector<int>& nums) { int l = 0, r = nums.size() - 1; while (l + 1 < nums.size() && nums[l + 1] >= nums[l]) l ++ ; if (l == r) return 0; while (r - 1 >= 0 && nums[r - 1] <= nums[r]) r -- ; for (int i = l + 1; i < nums.size(); i ++ ) while (l >= 0 && nums[l] > nums[i]) l -- ; for (int i = r - 1; i >= 0; i -- ) while (r < nums.size() && nums[r] < nums[i]) r ++ ; return r - l - 1; } };
617. 合并二叉树
class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (t2) swap(t1, t2); // 可以保证t1一定不为空 if (!t1) return NULL; if (t2) t1->val += t2->val; t1->left = mergeTrees(t1->left, t2 ? t2->left : NULL); t1->right = mergeTrees(t1->right, t2 ? t2->right : NULL); return t1; } };
621. 任务调度器
给你一个用字符数组tasks表示的CPU需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在1个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个相同种类的任务之间必须有长度为整数n的冷却时间，因此至少有连续n个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
class Solution { public: int leastInterval(vector<char>& tasks, int n) { unordered_map<char, int> hash; for (auto c: tasks) hash[c] ++ ; int maxc = 0, cnt = 0; for (auto [k, v]: hash) maxc = max(maxc, v); for (auto [k, v]: hash) if (maxc == v) cnt ++ ; return max((int)tasks.size(), (maxc - 1) * (n + 1) + cnt); } };
647. 回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
class Solution { public: int countSubstrings(string s) { int res = 0; for (int i = 0; i < s.size(); i ++ ) { // 枚举长度为奇数的情况 for (int j = i, k = i; j >= 0 && k < s.size(); j --, k ++ ) { if (s[j] != s[k]) break; res ++ ; } // 偶数情况 for (int j = i, k = i + 1; j >= 0 && k < s.size(); j --, k ++ ) { if (s[j] != s[k]) break; res ++ ; } } return res; } };
739. 每日温度
给定一个整数数组temperatures，表示每天的温度，返回一个数组nswer，其中answeri是指对于第i ii天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
class Solution { public: vector<int> dailyTemperatures(vector<int>& T) { stack<int> stk; vector<int> res(T.size()); for (int i = T.size() - 1; i >= 0; i -- ) { while (stk.size() && T[i] >= T[stk.top()]) stk.pop(); if (stk.size()) res[i] = stk.top() - i; stk.push(i); } return res; } };
