第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 <= 105

1 <= 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 <= 1000

1 <= 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
❞