Leetcode Test
2454 下一个更大元素Ⅳ(12.12)
给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。
如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：
j > inums[j] > nums[i]恰好存在 一个 k 满足 i < k < j 且 nums[k] > nums[i] 。
如果不存在 nums[j] ，那么第二大整数为 -1 。
比方说，数组 [1, 2, 4, 3] 中，1 的第二大整数是 4 ，2 的第二大整数是 3 ，3 和 4 的第二大整数是 -1 。
请你返回一个整数数组 answer ，其中 answer[i]是 nums[i] 的第二大整数。
提示：
1 <= nums.length <= 1050 <= nums[i] <= 109
【2个单调栈】2454. 下一个更大元素 IV - 力扣（LeetCode）
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* secondGreaterElement(int* nums, int numsSize, int* returnSize) {
int n = numsSize;
int st1[n], st2[n];
int st1Size = 0, st2Size = 0;
int *res = (int *)malloc(sizeof(int) * n);
memset(res, 0xff, sizeof(int) * n);
for (int i = 0; i < n; i++) {
int v = nums[i];
while (st2Size > 0 && nums[st2[st2Size - 1]] < v) {
res[st2[st2Size - 1]] = v;
st2Size--;
}
int pos = st1Size - 1;
while (pos >= 0 && nums[st1[pos]] < v) {
pos--;
}
memcpy(st2 + st2Size, st1 + pos + 1, sizeof(int) * (st1Size - pos - 1));
st2Size += st1Size - pos - 1;
st1Size = pos + 1;
st1[st1Size++] = i;
}
*returnSize = n;
return res;
}
算法：
初始化 ans 数组，长度和 nums 相同，初始值均为 -1。初始化两个空栈 s 和 t。从左到右遍历 nums。设 x=nums[i]。如果 x 比 t 的栈顶大，则栈顶元素对应的答案为 x，并弹出 t 的栈顶。如果 x 比 s 的栈顶大，则弹出 s 的栈顶，并移入 t 的栈顶。由于要保证 t 也是一个递减的单调栈，我们可以直接把一整段从 s 中弹出的元素插入到 t 的末尾。把 x 加到 s 的栈顶。代码实现时，为方便记录答案，改为把 x 的下标 i 加到栈顶。
2697 字典序最小回文串(12.13)
给你一个由 小写英文字母 组成的字符串 s ，你可以对其执行一些操作。在一步操作中，你可以用其他小写英文字母 替换 s 中的一个字符。
请你执行 尽可能少的操作 ，使 s 变成一个 回文串 。如果执行 最少 操作次数的方案不止一种，则只需选取 字典序最小 的方案。
对于两个长度相同的字符串 a 和 b ，在 a 和 b 出现不同的第一个位置，如果该位置上 a 中对应字母比 b 中对应字母在字母表中出现顺序更早，则认为 a 的字典序比 b 的字典序要小。
返回最终的回文字符串。
提示：
1 <= s.length <= 1000s 仅由小写英文字母组成
【双指针】
char * makeSmallestPalindrome(char * s){
int len=strlen(s);
int left=0,right=len-1;
while(left if(s[left]!=s[right]){ int gap=s[left]-s[right]; if(gap<0){ s[right]=s[left]; } else{ s[left]=s[right]; } } left++; right--; } return s; } 2132 用邮票贴满网格图(12.14) 给你一个 m x n 的二进制矩阵 grid ，每个格子要么为 0 （空）要么为 1 （被占据）。 给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中，且满足以下 限制 和 要求 ： 覆盖所有 空 格子。不覆盖任何 被占据 的格子。我们可以放入任意数目的邮票。邮票可以相互有 重叠 部分。邮票不允许 旋转 。邮票必须完全在矩阵 内 。 如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false 。 提示： m == grid.lengthn == grid[r].length1 <= m, n <= 1051 <= m * n <= 2 * 105grid[r][c] 要么是 0 ，要么是 1 。1 <= stampHeight, stampWidth <= 105 【二维差分】 class Solution { public: bool possibleToStamp(vector int m = grid.size(), n = grid[0].size(); // 1. 计算 grid 的二维前缀和 vector for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + grid[i][j]; } } // 2. 计算二维差分 // 为方便第 3 步的计算，在 d 数组的最上面和最左边各加了一行（列），所以下标要 +1 vector for (int i2 = stampHeight; i2 <= m; i2++) { for (int j2 = stampWidth; j2 <= n; j2++) { int i1 = i2 - stampHeight + 1; int j1 = j2 - stampWidth + 1; if (s[i2][j2] - s[i2][j1 - 1] - s[i1 - 1][j2] + s[i1 - 1][j1 - 1] == 0) { d[i1][j1]++; d[i1][j2 + 1]--; d[i2 + 1][j1]--; d[i2 + 1][j2 + 1]++; } } } // 3. 还原二维差分矩阵对应的计数矩阵（原地计算） for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { d[i + 1][j + 1] += d[i + 1][j] + d[i][j + 1] - d[i][j]; if (grid[i][j] == 0 && d[i + 1][j + 1] == 0) { return false; } } } return true; } }; 2415 反转二叉树的奇数层(12.15) 给你一棵 完美 二叉树的根节点 root ，请你反转这棵树中每个 奇数 层的节点值。 例如，假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] ，那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。 反转后，返回树的根节点。 完美 二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。 节点的 层数 等于该节点到根节点之间的边数。 提示： 树中的节点数目在范围 [1, 214] 内0 <= Node.val <= 105root 是一棵 完美 二叉树 【dfs】 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* reverseOddLevels(TreeNode* root) { dfs(root->left, root->right, true); return root; } void dfs(TreeNode *root1, TreeNode *root2, bool isOdd) { if (root1 == nullptr) { return; } if (isOdd) { swap(root1->val, root2->val); } dfs(root1->left, root2->right, !isOdd); dfs(root1->right, root2->left, !isOdd); } }; 2276 统计区间中的整数数目(12.16) 给你区间的 空 集，请你设计并实现满足要求的数据结构： **新增：**添加一个区间到这个区间集合中。**统计：**计算出现在 至少一个 区间中的整数个数。 实现 CountIntervals 类： CountIntervals() 使用区间的空集初始化对象void add(int left, int right) 添加区间 [left, right] 到区间集合之中。int count() 返回出现在 至少一个 区间中的整数个数。 **注意：**区间 [left, right] 表示满足 left <= x <= right 的所有整数 x 。 提示： 1 <= left <= right <= 109最多调用 add 和 count 方法 总计 105 次调用 count 方法至少一次 【平衡树】2276. 统计区间中的整数数目 - 力扣（LeetCode） class CountIntervals { map int cnt=0; public: CountIntervals() {} void add(int left, int right) { for(auto it=m.lower_bound(left);it!=m.end()&&it->second<=right;m.erase(it++)){ int l=it->second,r=it->first; left=min(left,l); right=max(right,r); cnt-=r-l+1; } cnt+=right-left+1; m[right]=left; } int count() { return cnt; } }; /** * Your CountIntervals object will be instantiated and called as such: * CountIntervals* obj = new CountIntervals(); * obj->add(left,right); * int param_2 = obj->count(); */ 746 使用最小花费爬楼梯(12.17) 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。 提示： 2 <= cost.length <= 10000 <= cost[i] <= 999 【dp】 int minCostClimbingStairs(int* cost, int costSize) { int *pay=malloc(sizeof(int)*(costSize+1)); for(int i=0;i<=costSize;i++){ pay[i]=0; } for(int i=2;i<=costSize;i++){ pay[i]=fmin(pay[i-1]+cost[i-1],pay[i-2]+cost[i-2]); } return pay[costSize]; } 162 寻找峰值(12.18) 峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞ 。 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。 提示： 1 <= nums.length <= 1000-231 <= nums[i] <= 231 - 1对于所有有效的 i 都有 nums[i] != nums[i + 1] 【寻找max】 int findPeakElement(int* nums, int numsSize) { int n=numsSize,maxid=0,max=nums[0]; for(int i=1;i if(max max=nums[i]; maxid=i; } } return maxid; } 【二分】 class Solution { public: int findPeakElement(vector int n = nums.size(); // 辅助函数，输入下标 i，返回一个二元组 (0/1, nums[i]) // 方便处理 nums[-1] 以及 nums[n] 的边界情况 auto get = [&](int i) -> pair if (i == -1 || i == n) { return {0, 0}; } return {1, nums[i]}; }; int left = 0, right = n - 1, ans = -1; while (left <= right) { int mid = (left + right) / 2; if (get(mid - 1) < get(mid) && get(mid) > get(mid + 1)) { ans = mid; break; } if (get(mid) < get(mid + 1)) { left = mid + 1; } else { right = mid - 1; } } return ans; } }; 精彩文章
发表评论