【Leetcode Sheet】Weekly Practice 21

Leetcode Test

1901 寻找峰值Ⅱ(12.19)

一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。

给你一个 从 0 开始编号 的 m x n 矩阵 mat ，其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值 mat[i][j] 并 返回其位置 [i,j] 。

你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。

要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 500
• 1 <= mat[i][j] <= 105
• 任意两个相邻元素均不相等.

【二分】

只考虑每一行的最大值，判断第i行的最大元素mat（i，j）

如果mat（i，j）大于上一行的元素mat（i-1，j）和下一行的元素mat（i+1，j），则符合题目的条件

/*** Note: The returned array must be malloced, assume caller calls free().*///找第i行的最大值
int Max(int *row,int n){int id=0;for(int i=0;i<n;i++){if(row[id]<row[i]){id=i;}}return id;
}int* findPeakGrid(int** mat, int matSize, int* matColSize, int* returnSize) {int m=matSize,n=matColSize[0];int low=0,high=m-1;//二分起始是第0行和第m-1行while(low<=high){int i=(low+high)/2;int j=Max(mat[i],n);if(i>=1 && mat[i][j]<mat[i-1][j]){//如果当前行 小于 上一行，说明峰值在上面，更新highhigh=i-1;continue;}if(i<m-1 && mat[i][j]<mat[i+1][j]){//如果当前行 小于 下一行，说明峰值在下面，更新lowlow=i+1;continue;}int *ret=malloc(sizeof(int)*2);ret[0]=i;ret[1]=j;*returnSize=2;return ret;}*returnSize=0;return NULL;
}

2828 判别首字母缩略词(12.20)

给你一个字符串数组 words 和一个字符串 s ，请你判断 s 是不是 words 的 首字母缩略词 。

如果可以按顺序串联 words 中每个字符串的第一个字符形成字符串 s ，则认为 s 是 words 的首字母缩略词。例如，"ab" 可以由 ["apple", "banana"] 形成，但是无法从 ["bear", "aardvark"] 形成。

如果 s 是 words 的首字母缩略词，返回 true ；否则，返回 false 。

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 10
• 1 <= s.length <= 100
• words[i] 和 s 由小写英文字母组成

【模拟】

bool isAcronym(char ** words, int wordsSize, char * s){int n=wordsSize,sn=strlen(s);if(n!=sn){return 0;}bool flag=1;for(int i=0;i<n;i++){if(s[i]!=words[i][0]){flag=0;break;}}return flag;
}

2866 美丽塔Ⅱ(12.21)

给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。

你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。

如果以下条件满足，我们称这些塔是 美丽 的：

1. 1 <= heights[i] <= maxHeights[i]
2. heights 是一个 山脉 数组。

如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山脉 数组：

• 对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]
• 对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]

请你返回满足 美丽塔 要求的方案中，高度和的最大值 。

提示：

• 1 <= n == maxHeights <= 105
• 1 <= maxHeights[i] <= 109

【单调栈】

2866. 美丽塔 II - 力扣（LeetCode）

long long maximumSumOfHeights(int* maxHeights, int maxHeightsSize) {int n = maxHeightsSize;long long res = 0;long long prefix[n], suffix[n];int stack1[n], stack2[n];int top1 = 0, top2 = 0;for (int i = 0; i < n; i++) {while (top1 > 0 && maxHeights[i] < maxHeights[stack1[top1 - 1]]) {top1--;}if (top1 == 0) {prefix[i] = (long long)(i + 1) * maxHeights[i];} else {prefix[i] = prefix[stack1[top1 - 1]] + (long long)(i - stack1[top1 - 1]) * maxHeights[i];}stack1[top1++] = i;}for (int i = n - 1; i >= 0; i--) {while (top2 > 0 && maxHeights[i] < maxHeights[stack2[top2 - 1]]) {top2--;}if (top2 == 0) {suffix[i] = (long long)(n - i) * maxHeights[i];} else {suffix[i] = suffix[stack2[top2 - 1]] + (long long)(stack2[top2 - 1] - i) * maxHeights[i];}stack2[top2++] = i;res = fmax(res, prefix[i] + suffix[i] - maxHeights[i]);}return res;
}

左侧单调栈解析：maxHeights = [6, 5, 3, 9, 2, 7]

初始状态

• maxHeights = [6, 5, 3, 9, 2, 7]
• stack1 = [] (空栈)
• prefix = [0, 0, 0, 0, 0, 0]

步骤 1: i = 0 (maxHeights[0] = 6)

• 栈空，直接入栈。
• prefix[0] = (0 + 1) * 6 = 6
• stack1 = [0]
• prefix = [6, 0, 0, 0, 0, 0]

步骤 2: i = 1 (maxHeights[1] = 5)

• maxHeights[1] 小于 maxHeights[stack1[top1 - 1]] (即 maxHeights[0]), 弹出栈顶元素，栈变为空。
• prefix[1] = (1 + 1) * 5 = 10 (因为栈为空)
• stack1 = [1]
• prefix = [6, 10, 0, 0, 0, 0]

步骤 3: i = 2 (maxHeights[2] = 3)

• 同样，maxHeights[2] 小于 maxHeights[stack1[top1 - 1]] (即 maxHeights[1]), 弹出栈顶元素，栈变为空。
• prefix[2] = (2 + 1) * 3 = 9 (因为栈为空)
• stack1 = [2]
• prefix = [6, 10, 9, 0, 0, 0]

步骤 4: i = 3 (maxHeights[3] = 9)

• maxHeights[3] 大于 maxHeights[stack1[top1 - 1]] (即 maxHeights[2]), 所以直接入栈。
• prefix[3] = prefix[stack1[top1 - 1]] + (3 - stack1[top1 - 1]) * maxHeights[3] = 9 + (3 - 2) * 9 = 18
• stack1 = [2, 3]
• prefix = [6, 10, 9, 18, 0, 0]

步骤 5: i = 4 (maxHeights[4] = 2)

• maxHeights[4] 小于 maxHeights[stack1[top1 - 1]] (即 maxHeights[3]), 弹出栈顶元素。重复此过程，直到栈为空。
• prefix[4] = (4 + 1) * 2 = 10 (因为栈为空)
• stack1 = [4]
• prefix = [6, 10, 9, 18, 10, 0]

步骤 6: i = 5 (maxHeights[5] = 7)

• maxHeights[5] 大于 maxHeights[stack1[top1 - 1]] (即 maxHeights[4]), 所以直接入栈。
• prefix[5] = prefix[stack1[top1 - 1]] + (5 - stack1[top1 - 1]) * maxHeights[5] = 10 + (5 - 4) * 7 = 17
• stack1 = [4, 5]
• prefix = [6, 10, 9, 18, 10, 17]

1671 得到山形数组的最少删除次数(12.22)

我们定义 arr 是 山形数组 当且仅当它满足：

• arr.length >= 3

• 存在某个下标

  i
  

  （

  从 0 开始

  ） 满足

  0 < i < arr.length - 1
  

  且：

  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给你整数数组 nums ，请你返回将 nums 变成 山形状数组 的 最少 删除次数。

提示：

• 3 <= nums.length <= 1000
• 1 <= nums[i] <= 109
• 题目保证 nums 删除一些元素后一定能得到山形数组。

【二分 + dp】

class Solution {
public:int minimumMountainRemovals(vector<int> &nums) {int n = nums.size();vector<int> suf(n), g;for (int i = n - 1; i; i--) {int x = nums[i];auto it = lower_bound(g.begin(), g.end(), x);suf[i] = it - g.begin() + 1; // 从 nums[i] 开始的最长严格递减子序列的长度if (it == g.end()) {g.push_back(x);} else {*it = x;}}int mx = 0;g.clear();for (int i = 0; i < n - 1; i++) {int x = nums[i];auto it = lower_bound(g.begin(), g.end(), x);int pre = it - g.begin() + 1; // 在 nums[i] 结束的最长严格递增子序列的长度if (it == g.end()) {g.push_back(x);} else {*it = x;}if (pre >= 2 && suf[i] >= 2) {mx = max(mx, pre + suf[i] - 1); // 减去重复的 nums[i]}}return n - mx;}
};

1962 移除石子使总数最小(12.23)

给你一个整数数组 piles ，数组 下标从 0 开始 ，其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ，请你执行下述操作 恰好 k 次：

• 选出任一石子堆 piles[i] ，并从中 移除 floor(piles[i] / 2) 颗石子。

**注意：**你可以对 同一堆 石子多次执行此操作。

返回执行 k 次操作后，剩下石子的 最小 总数。

floor(x) 为 小于 或 等于 x 的 最大 整数。（即，对 x 向下取整）。

提示：

• 1 <= piles.length <= 105
• 1 <= piles[i] <= 104
• 1 <= k <= 105

【贪心 + 优先队列】

class Solution {
public:int minStoneSum(vector<int>& piles, int k) {priority_queue<int> pq(piles.begin(), piles.end());for (int i = 0; i < k; i++) {int pile = pq.top();pq.pop();pile -= pile / 2;pq.push(pile);}int sum = 0;while (!pq.empty()) {sum += pq.top();pq.pop();}return sum;}
};

【原地堆化】

class Solution {
public:int minStoneSum(vector<int> &piles, int k) {make_heap(piles.begin(), piles.end()); // 原地堆化（最大堆）while (k-- && piles[0] != 1) {pop_heap(piles.begin(), piles.end()); // 弹出堆顶并移到末尾piles.back() -= piles.back() / 2;push_heap(piles.begin(), piles.end()); // 把末尾元素入堆}return accumulate(piles.begin(), piles.end(), 0);}
};

1954 收集足够苹果的最小花园周长(12.24)

给你一个用无限二维网格表示的花园，每一个 整数坐标处都有一棵苹果树。整数坐标 (i, j) 处的苹果树有 |i| + |j| 个苹果。

你将会买下正中心坐标是 (0, 0) 的一块 正方形土地 ，且每条边都与两条坐标轴之一平行。

给你一个整数 neededApples ，请你返回土地的 最小周长 ，使得 至少 有 neededApples 个苹果在土地 里面或者边缘上。

|x| 的值定义为：

• 如果 x >= 0 ，那么值为 x
• 如果 x < 0 ，那么值为 -x

提示：

• 1 <= neededApples <= 1015

【枚举】

long long minimumPerimeter(long long neededApples) {long long n=1;while(2*n*(n+1)*(2*n+1)<neededApples){n++;}return 4*(n*2);
}

【二分】

long long minimumPerimeter(long long neededApples) {long long left = 1, right = 100000, ans = 0;while (left <= right) {long long mid = (left + right) / 2;if (2 * mid * (mid + 1) * (mid * 2 + 1) >= neededApples) {ans = mid;right = mid - 1;} else {left = mid + 1;}}return ans * 8;
}

1276 不浪费原料的汉堡制作方案(12.25)

圣诞活动预热开始啦，汉堡店推出了全新的汉堡套餐。为了避免浪费原料，请你帮他们制定合适的制作计划。

给你两个整数 tomatoSlices 和 cheeseSlices，分别表示番茄片和奶酪片的数目。不同汉堡的原料搭配如下：

• **巨无霸汉堡：**4 片番茄和 1 片奶酪
• **小皇堡：**2 片番茄和 1 片奶酪

请你以 [total_jumbo, total_small]（[巨无霸汉堡总数，小皇堡总数]）的格式返回恰当的制作方案，使得剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量都是 0。

如果无法使剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量为 0，就请返回 []。

提示：

• 0 <= tomatoSlices <= 10^7
• 0 <= cheeseSlices <= 10^7

【数学：二元一次方程组】

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* numOfBurgers(int tomatoSlices, int cheeseSlices, int* returnSize) {
if (tomatoSlices % 2 != 0 || tomatoSlices < cheeseSlices * 2 || cheeseSlices * 4 < tomatoSlices) {*returnSize = 0;return NULL;}int *ans = (int *)malloc(sizeof(int) * 2);ans[0] = tomatoSlices / 2 - cheeseSlices;ans[1] = cheeseSlices * 2 - tomatoSlices / 2;*returnSize = 2;return ans;
}/*
方程组
4x+2y=tomatoSlices
x+y=cheeseSlicesx= 1/2 tomatoSlices−cheeseSlices
y=2 cheeseSlices - 1/2 tomatoSlices
*/