石神
2023/03/08阅读：16主题：全栈蓝
【leetcode周赛】第二期
第98场双周赛
本文只是节选公众号的中的一篇，我的公众号每日都会更新，欢迎参观 公众号算法每日一更
2566. 替换一个数字后的最大差值
❝力扣链接：https://leetcode.cn/problems/maximum-difference-by-remapping-a-digit/
题目描述：
给你一个整数 num 。你知道 Danny Mittal 会偷偷将 0 到 9 中的一个数字 替换 成另一个数字。
请你返回将 num 中 恰好一个 数字进行替换后，得到的最大值和最小值的差位多少。
注意：
当 Danny 将一个数字 d1 替换成另一个数字 d2 时，Danny 需要将 nums 中所有 d1 都替换成 d2 。 Danny 可以将一个数字替换成它自己，也就是说 num 可以不变。 Danny 可以将数字分别替换成两个不同的数字分别得到最大值和最小值。 替换后得到的数字可以包含前导 0 。
//示例 1：
输入：num = 11891
输出：99009
解释：
为了得到最大值，我们将数字 1 替换成数字 9 ，得到 99899 。
为了得到最小值，我们将数字 1 替换成数字 0 ，得到 890 。
两个数字的差值为 99009 。
//示例 2：
输入：num = 90
输出：99
解释：
可以得到的最大值是 99（将 0 替换成 9），最小值是 0（将 9 替换成 0）。
所以我们得到 99 。提示：
❞
1 <= num <= 108
-
比赛解法：模拟
long long power(int a, int x){
int res = a;
for(int i = 0; i < x; i++)
res *= 10;
return res;
}
int minMaxDifference(int num){
long long res = 0, min = 0, max = 0;
int tmp = num;
int x = 0;
// x是num的位数
while(tmp > 0){
x++;
tmp /= 10;
}
tmp = num;
int arr[x];
// num存在数组中，如num=12，则num[0]=2,num[1]=1
for(int i = 0; i < x; i++){
arr[i] = tmp % 10;
tmp /= 10;
}
// num的最高位
int c = arr[x - 1];
// min num的最高位替换为0
for(int i = 0; i < x; i++){
// 剪枝/替换为0
if(arr[i] == c)
continue;
int tmp = arr[i];
min += power(tmp, i);
}
int i;
// max num的第一个非9高位替换成9
for(i = x - 1; i >= 0; i--){
// 找到替换位b
if(arr[i] < 9){
int b = arr[i];
for(int j = 0; j < x; j++){
int tmp = arr[j];
// 和替换位数字相同，替换为9
if(arr[j] == b){
max += power(9, j);
}// 否则不替换
else
max += power(tmp, j);
}
break;
}
}
// num全是由9组成的特判
if(i == -1 && max == 0)
max = num;
return max - min;
}
解法优化
❝这里的优化是从代码量以及复杂度上的优化，是针对打比赛的，之后不在赘述
❞
/* 数字转字符串也可以优化，只不过c语言没有这种库函数，如果用c打比赛，建议将此做成函数
*/
// 求最值：power函数=>每次乘10
for(int i = x - 1; i >= 0; i--){
// 剪枝/替换为0
int e = (c == arr[i]) ? 0 : arr[i];
min = min * 10 + e;
}
// min同理
for(int i = x - 1; i >= 0; i--){
int e = (arr[i] == b) ? 9 : arr[i];
max = max * 10 + e;
}
-
优化后的答案
int minMaxDifference(int num){
long long res = 0, min = 0, max = 0;
int tmp = num;
int x = 0;
// x是num的位数
while(tmp > 0){
x++;
tmp /= 10;
}
tmp = num;
int arr[x];
// num存在数组中，如num=12，则num[0]=2,num[1]=1
for(int i = 0; i < x; i++){
arr[i] = tmp % 10;
tmp /= 10;
}
// num的最高位
int c = arr[x - 1];
// min - num的最高位替换为0
for(int i = x - 1; i >= 0; i--){
// 剪枝/替换为0
int e = (c == arr[i]) ? 0 : arr[i];
min = min * 10 + e;
}
int b = 0;
// max - num的第一个非9高位替换成9
for(int i = x - 1; i >= 0; i--){
// 找到替换位b
if(arr[i] < 9){
b = arr[i];
break;
}
}
for(int i = x - 1; i >= 0; i--){
int e = (arr[i] == b) ? 9 : arr[i];
max = max * 10 + e;
}
return max - min;
}
-
大佬解法：即优化后的答案
class Solution {
public int minMaxDifference(int num) {
char[] ch = String.valueOf(num).toCharArray();
// 找要更换的数字
char max_num = '9', min_num = ch[0];
for (char c: ch) {
if (c != max_num) {
max_num = c;
break;
}
}
// mx: 最大值 mn: 最小值
int mx = 0, mn = 0;
for (char c: ch) {
mx = mx * 10 + (c != max_num? (c - '0'): 9);
mn = mn * 10 + (c != min_num? (c - '0'): 0);
}
return mx - mn;
}
}
2567. 修改两个元素的最小分数
❝力扣链接：https://leetcode.cn/problems/minimum-score-by-changing-two-elements/
题目描述：
给你一个下标从 0 开始的整数数组 nums 。
nums 的 最小 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最小值。 nums的 最大 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最大值。 nums 的分数是 最大 得分与 最小 得分的和。 我们的目标是最小化 nums 的分数。你 最多 可以修改 nums 中 2 个元素的值。
请你返回修改 nums 中 至多两个 元素的值后，可以得到的 最小分数 。
|x| 表示 x 的绝对值。
// 示例 1：
输入：nums = [1,4,3]
输出：0
解释：将 nums[1] 和 nums[2] 的值改为 1 ，nums 变为 [1,1,1] 。|nums[i] - nums[j]| 的值永远为 0 ，所以我们返回 0 + 0 = 0 。
// 示例 2：
输入：nums = [1,4,7,8,5]
输出：3
解释：
将 nums[0] 和 nums[1] 的值变为 6 ，nums 变为 [6,6,7,8,5] 。
最小得分是 i = 0 且 j = 1 时得到的 |nums[i] - nums[j]| = |6 - 6| = 0 。
最大得分是 i = 3 且 j = 4 时得到的 |nums[i] - nums[j]| = |8 - 5| = 3 。
最大得分与最小得分之和为 3 。这是最优答案。提示：
3 <= nums.length <= 105 1 <= nums[i] <= 109
❞
-
比赛解法：没做出来
说下当时思路：至少三个数，改两个数，最小值必然是0，问题变成了求最大值，最大值就是返回值。把最大值max，次次大值max1，最小值min，次次小值min1求出来，答案就是max - min1和max1 - min里面的最小值。
这个解法显然把中间的数理想化了，如[58,42,8,75,28]，return 30，而上面那个算法只能得到33。
解法优化
//其中cmp函数应写为：
int cmp(const void *a, const void *b)
{
return *(int*)a - *(int*)b; //由小到大排序
//return *(int *)b - *(int *)a; 由大到小排序
}
int minimizeSum(int* nums, int numsSize){
if(numsSize == 3) return 0;
qsort(nums, numsSize, sizeof(int), cmp);
int min = INT_MAX;
// 因为只能改两个数，因此结果在以下三种情况中取最小值
for(int i = 0; i < 3; i++){
if(nums[numsSize - 3 + i] - nums[i] < min)
min = nums[numsSize - 3 + i] - nums[i];
}
return min;
}
-
大佬解法：同上
2568. 最小无法得到的或值
❝题目链接：https://leetcode.cn/problems/minimum-impossible-or/
题目描述：
给你一个下标从 「0」 开始的整数数组
nums。如果存在一些整数满足
0 <= index1 < index2 < ... < indexk < nums.length，得到nums[index1] | nums[index2] | ... | nums[indexk] = x，那么我们说x是 「可表达的」 。换言之，如果一个整数能由nums的某个子序列的或运算得到，那么它就是可表达的。请你返回
nums不可表达的 「最小非零整数」 。「示例 1：」
输入：nums = [2,1]
输出：4
解释：1 和 2 已经在数组中，因为 nums[0] | nums[1] = 2 | 1 = 3 ，所以 3 是可表达的。由于 4 是不可表达的，所以我们返回 4 。「示例 2：」
输入：nums = [5,3,2]
输出：1
解释：1 是最小不可表达的数字。「提示：」
❞
1 <= nums.length <= 1051 <= nums[i] <= 109
-
目前想法：位操作模拟
❝
未出现的最高位即为答案
❞
//其中cmp函数应写为：
int cmp(const void *a, const void *b)
{
return *(int*)a - *(int*)b; //由小到大排序
//return *(int *)b - *(int *)a; 由大到小排序
}
int minImpossibleOR(int* nums, int numsSize){
qsort(nums, numsSize, sizeof(int), cmp);
int x = 1;
for(int i = 0; i < numsSize; i++){
if(x == nums[i])
x *= 2;
}
return x;
}
-
大佬解法
class Solution {
public:
int minImpossibleOR(vector<int> &nums) {
int mask = 0;
for (int x : nums)
if ((x & (x - 1)) == 0) // x 是 2 的幂次
mask |= x;
mask = ~mask;
return mask & -mask; // lowbit
}
};
2569. 更新数组后处理求和查询
之前说过，hard放，贴个链接：https://leetcode.cn/problems/handling-sum-queries-after-update/
第333场周赛
2570. 合并两个二维数组
❝力扣链接：https://leetcode.cn/problems/merge-two-2d-arrays-by-summing-values/
题目描述：
给你两个 二维 整数数组 nums1 和 nums2.
nums1[i] = [idi, vali] 表示编号为 idi 的数字对应的值等于 vali 。 nums2[i] = [idi, vali] 表示编号为 idi 的数字对应的值等于 vali 。 每个数组都包含 互不相同 的 id ，并按 id 以 递增 顺序排列。
请你将两个数组合并为一个按 id 以递增顺序排列的数组，并符合下述条件：
只有在两个数组中至少出现过一次的 id 才能包含在结果数组内。 每个 id 在结果数组中 只能出现一次 ，并且其对应的值等于两个数组中该 id 所对应的值求和。如果某个数组中不存在该 id ，则认为其对应的值等于 0 。 返回结果数组。返回的数组需要按 id 以递增顺序排列。
//示例 1：
输入：nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
输出：[[1,6],[2,3],[3,2],[4,6]]
解释：结果数组中包含以下元素：
- id = 1 ，对应的值等于 2 + 4 = 6 。
- id = 2 ，对应的值等于 3 。
- id = 3 ，对应的值等于 2 。
- id = 4 ，对应的值等于5 + 1 = 6 。
// 示例 2：
输入：nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
输出：[[1,3],[2,4],[3,6],[4,3],[5,5]]
解释：不存在共同 id ，在结果数组中只需要包含每个 id 和其对应的值。提示：
❞
1 <= nums1.length, nums2.length <= 200 nums1[i].length == nums2[j].length == 2 1 <= idi, vali <= 1000 数组中的 id 互不相同 数据均按 id 以严格递增顺序排列
-
比赛解法：模拟即可
❝当时c的参数没搞对，最后只能用Java写（第一次用Java写程序:)
❞
class Solution {
public int[][] mergeArrays(int[][] nums1, int[][] nums2) {
int[][] tmp = new int[400][2];
int a = 0;
int i = 0, j = 0;
while(i < nums1.length && j < nums2.length){
if(nums1[i][0] < nums2[j][0]){
tmp[a][0] = nums1[i][0];
tmp[a++][1] = nums1[i++][1];
}
else if(nums1[i][0] > nums2[j][0]){
tmp[a][0] = nums2[j][0];
tmp[a++][1] = nums2[j++][1];
}
else{
tmp[a][0] = nums1[i][0];
tmp[a++][1] = nums1[i++][1] + nums2[j++][1];
}
}
while(i < nums1.length){
tmp[a][0] = nums1[i][0];
tmp[a++][1] = nums1[i++][1];
}
while(j < nums2.length){
tmp[a][0] = nums2[j][0];
tmp[a++][1] = nums2[j++][1];
}
int[][] res = new int [a][2];
for(int k = 0; k < a; k++){
res[k][0] = tmp[k][0];
res[k][1] = tmp[k][1];
}
return res;
}
}
补个c的：
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** mergeArrays(int** nums1, int nums1Size, int* nums1ColSize, int** nums2, int nums2Size, int* nums2ColSize, int* returnSize, int** returnColumnSizes){
int tmp[400][2];
*returnSize = 0;
int ** res = (int**)malloc(sizeof(int*) * 400);
*returnColumnSizes = (int*)malloc(sizeof(int) * 400);
for(int k = 0; k < 400; k++){
res[k] = (int*)malloc(sizeof(int) * 2);
(*returnColumnSizes)[k] = 2;
}
int i = 0, j = 0;
while(i < nums1Size && j < nums2Size){
if(nums1[i][0] < nums2[j][0]){
res[*returnSize][0] = nums1[i][0];
res[(*returnSize)++][1] = nums1[i++][1];
}
else if(nums1[i][0] > nums2[j][0]){
res[*returnSize][0] = nums2[j][0];
res[(*returnSize)++][1] = nums2[j++][1];
}
else{
res[*returnSize][0] = nums1[i][0];
res[(*returnSize)++][1] = nums1[i++][1] + nums2[j++][1];
}
}
while(i < nums1Size){
res[*returnSize][0] = nums1[i][0];
res[(*returnSize)++][1] = nums1[i++][1];
}
while(j < nums2Size){
res[*returnSize][0] = nums2[j][0];
res[(*returnSize)++][1] = nums2[j++][1];
}
return res;
}
当时returnColumnSizes没申请空间，结果这个题足足花了51min，害。
-
大佬解法：归并
class Solution:
def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
n1, n2 = len(nums1), len(nums2)
res = []
i, j = 0, 0
while i < n1 and j < n2:
id1, id2 = nums1[i][0], nums2[j][0]
if id1 < id2:
res.append(nums1[i])
i += 1
elif id1 == id2:
res.append([id1, nums1[i][1] + nums2[j][1]])
i += 1
j += 1
else:
res.append(nums2[j])
j += 1
while i < n1:
res.append(nums1[i])
i += 1
while j < n2:
res.append(nums2[j])
j += 1
return res
append()
// 向
fruits = ['apple', 'banana', 'cherry']
fruits.append("orange")
2571. 将整数减到零需要的最少操作数
❝力扣链接：https://leetcode.cn/problems/minimum-operations-to-reduce-an-integer-to-0/
题目描述：
给你一个正整数 n ，你可以执行下述操作 任意 次：
n 加上或减去 2 的某个 幂 返回使 n 等于 0 需要执行的 最少 操作数。
如果 x == 2i 且其中 i >= 0 ，则数字 x 是 2 的幂。
// 示例 1：
输入：n = 39
输出：3
解释：我们可以执行下述操作：
- n 加上 20 = 1 ，得到 n = 40 。
- n 减去 23 = 8 ，得到 n = 32 。
- n 减去 25 = 32 ，得到 n = 0 。
可以证明使 n 等于 0 需要执行的最少操作数是 3 。
// 示例 2：
输入：n = 54
输出：3
解释：我们可以执行下述操作：
- n 加上 21 = 2 ，得到 n = 56 。
- n 加上 23 = 8 ，得到 n = 64 。
- n 减去 26 = 64 ，得到 n = 0 。
使 n 等于 0 需要执行的最少操作数是 3 。提示：
1 <= n <= 105
❞
-
比赛解法：二进制模拟
❝9 = 1001
需要2次，一个二进制的1需要一次
39 = 100111
需要3次，出现连续的1，则记作两次
❞
int minOperations(int n){
int res = 0;
int arr[100];
int tmp = n;
int k = 0;
while(tmp){
arr[k++] = tmp % 2;
tmp /= 2;
}
int tag = 0;
int i;
for(i = 0; i <= k; i++){
if(i + 1 <= k && arr[i] == arr[i + 1] && arr[i] == 1){
tag = 1;
}
// 若是两个及以上连续的1，按两个处理
else if(tag == 1){
tag = 0;
arr[i + 1] = 1;
res++;
}
else if(arr[i] == 1)
res++;
}
// 高位溢出的特判
if(arr[i] == 1 && n != 1)
res++;
return res;
}
解法优化
-
大佬解法：贪心+位运算
❝看不懂，贴个链接：https://leetcode.cn/problems/minimum-operations-to-reduce-an-integer-to-0/solution/ji-yi-hua-sou-suo-by-endlesscheng-cm6l/
❞
class Solution {
public int minOperations(int n) {
return Integer.bitCount(3 * n ^ n);
}
}
2572. 无平方子集计数
❝力扣链接：https://leetcode.cn/problems/count-the-number-of-square-free-subsets/
题目描述：
给你一个正整数数组
nums。如果数组
nums的子集中的元素乘积是一个 「无平方因子数」 ，则认为该子集是一个 「无平方」 子集。「无平方因子数」 是无法被除
1之外任何平方数整除的数字。返回数组
nums中 「无平方」 且 「非空」 的子集数目。因为答案可能很大，返回对109 + 7取余的结果。
nums的 「非空子集」 是可以由删除nums中一些元素（可以不删除，但不能全部删除）得到的一个数组。如果构成两个子集时选择删除的下标不同，则认为这两个子集不同。「示例 1：」
输入：nums = [3,4,4,5]
输出：3
解释：示例中有 3 个无平方子集：
- 由第 0 个元素 [3] 组成的子集。其元素的乘积是 3 ，这是一个无平方因子数。
- 由第 3 个元素 [5] 组成的子集。其元素的乘积是 5 ，这是一个无平方因子数。
- 由第 0 个和第 3 个元素 [3,5] 组成的子集。其元素的乘积是 15 ，这是一个无平方因子数。
可以证明给定数组中不存在超过 3 个无平方子集。「示例 2：」
输入：nums = [1]
输出：1
解释：示例中有 1 个无平方子集：
- 由第 0 个元素 [1] 组成的子集。其元素的乘积是 1 ，这是一个无平方因子数。
可以证明给定数组中不存在超过 1 个无平方子集。「提示：」
❞
1 <= nums.length <= 10001 <= nums[i] <= 30
-
目前解法：宕机了
-
大佬解法：动态规划+二进制枚举
// 这个题我放弃思考了，不过下面有动态规划的一点点内容
class Solution {
public int squareFreeSubsets(int[] nums) {
int MOD = (int)(1e9 + 7);
int [] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int pn = 10;
List<Integer> a = new ArrayList<>();
for (int x: nums){
boolean ok = true;
for (int y = 2; y < 6; y ++){
if (x % (y * y) == 0){
ok = false;
break;
}
}
if (ok == true){
a.add(x);
}
}
int n = a.size();
int [][] dp = new int[n + 1][1 << pn];
dp[0][0] = 1;
for (int i = 0; i < n; i ++){
int x = a.get(i);
for (int state = 0; state < (1 << pn); state ++){
dp[i + 1][state] = dp[i][state];
}
int mask = 0;
for (int pi = 0; pi < pn; pi ++){
if (x % primes[pi] == 0){
mask |= (1 << pi);
}
}
for (int state = 0; state < (1 << pn); state ++){
if ((state & mask) == 0){
int nxt_state = state | mask;
dp[i + 1][nxt_state] += dp[i][state];
dp[i + 1][nxt_state] %= MOD;
}
}
}
int res = 0;
for (int state = 0; state < (1 << pn); state ++){
res += dp[n][state];
res %= MOD;
}
res = (res - 1 + MOD) % MOD;
return res;
}
}
动态规划（Dynamic Programming）
❝用于处理重叠子问题，每一个状态都是由上一个状态推导出来的。感觉类似于解决递归问题
❞
用迭代求斐波那契数就是dp问题
❝力扣链接：https://leetcode.cn/problems/fibonacci-number/
题目描述：
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。
// 示例 1：
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
// 示例 2：
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
// 示例 3：
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3提示：
0 <= n <= 30
❞
-
解法：动态规划
❝❞
搞清数组下标含义 确定递推公式 数组赋初值 确定循环边界
int fib(int n){
// 数组下标即参数
int arr[31];
// 数组初值
arr[0] = 0;
arr[1] = 1;
// 根据下标及初值，得到循环上界和下界
for(int i = 2; i <= n; i++){
// 递推公式
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
2573. 找出对应 LCP 矩阵的字符串
❝https://leetcode.cn/problems/find-the-string-with-lcp
❞
作者介绍