LeetCode周记 EP2

2024-08-18

字数统计: 2.2k字 | 阅读时长: 9分

前言

这周周赛菜了…赶紧记一下。

本周主题：差分数组、动态规划

题目：

240615每日一题—Maximum Beauty of an Array After Applying Operation
240616周赛第三题—Maximum Total Damage With Spell Casting
LC198打家劫舍—House Robber

差分数组（Difference Array）

作用：开辟一块空间用于压缩对原数组上连续子数组的操作。

引出

考虑数组 $a=[1,3,3,5,8]$，对其中的相邻元素两两作差（右边减左边），得到数组 $[2,0,2,3]$。然后在开头补上 $a[0]$，得到差分数组：$d=[1,2,0,2,3]$

这有什么用呢？如果从左到右累加 ddd 中的元素，我们就「还原」回了 $a$ 数组 $[1,3,3,5,8]$。这类似求导与积分的概念。

这又有什么用呢？现在把连续子数组 $a[1],a[2],a[3]$ 都加上 $10$，得到 $a’=[1,13,13,15,8]$。再次两两作差，并在开头补上 $a’[0]$，得到差分数组：$d’=[1,12,0,2,−7]$

对比 $d$ 和 $d’$，可以发现只有 $d[1]$ 和 $d[4]$ 变化了，这意味着对 $a$ 中连续子数组的操作，可以转变成对差分数组 $d$ 中两个数的操作。

定义和性质

对于数组 $a$，定义其差分数组（difference array）为

$d[i] = \begin{cases} a[0],&i=0\\ a[i]-a[i-1],&i\ge 1 \end{cases} $

性质 1：从左到右累加 $d$ 中的元素，可以得到数组 $a$。

性质 2：如下两个操作是等价的。

把 $a$ 的子数组 $a[i],a[i+1],\cdots,a[j]$ 都加上 $x$。
把 $d[i]$ 增加 $x$，把 $d[j+1]$ 减少 $x$。

利用性质 2，我们只需要 $O(1)$ 的时间就可以完成对 $a$ 的子数组的操作。最后利用性质 1 从差分数组复原出数组 $a$。

注：也可以这样理解，$d[i]$ 表示把下标 $≥i$ 的数都加上 $d[i]$。

例题：Maximum Beauty of an Array After Applying Operation

Maximum Beauty of an Array After Applying Operation

You are given a 0-indexed array nums and a non-negative integer k.

In one operation, you can do the following:

Choose an index i that hasn’t been chosen before from the range [0, nums.length - 1].
Replace nums[i] with any integer from the range [nums[i] - k, nums[i] + k].
The beauty of the array is the length of the longest subsequence consisting of equal elements.

Return the maximum possible beauty of the array nums after applying the operation any number of times.

Note that you can apply the operation to each index only once.

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the order of the remaining elements.

Constraints:

1 <= nums.length <= 1e5

0 <= nums[i], k <= 1e5

自然想到的思路是把每个元素看作是一个可换空间，将所有可换空间在一个足够大的空间中进行叠加，被最多可换空间覆盖到的地方即为所求结果。或者，把每个元素考虑为对其对应可换空间中的每一个位置投一票，最终票数最多的位置为所求结果。

从数据范围上分析，区间大小应该为[-1e5, 2e5]。将区间为负数的部分用offset来表示，则可以写出以下解法：

// author: SilenceZheng66
class Solution {
    public int maximumBeauty(int[] nums, int k) {
        int res = 0, n = nums.length;
        // 多开3个空间，为了存0、存差分数组上限和匹配下标
        int[] diffArr = new int[(int)3e5+3];
        int ofst = (int)1e5+1; // diffArr[ofst]为0所在位置

        for(int x:nums){
            diffArr[x-k+ofst]++;
            diffArr[x+k+ofst+1]--;
        }
        
        for(int i=1;i<diffArr.length;i++){
            diffArr[i] += diffArr[i-1];
            res = Math.max(res, diffArr[i]);
        }

        return res;
    }
}

打家劫舍

周赛第三题属于值域上的打家劫舍，因此先来了解一下打家劫舍类型题目，其特点是对某一元素的选择会对其相邻区域造成影响。此类问题通常可以通过动态规划求解。

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。

如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 $k(k>2)$ 间房屋，有两个选项:

偷窃第 $k$ 间房屋，那么就不能偷窃第 $k-1$ 间房屋，偷窃总金额为前 $k-2$ 间房屋的最高总金额与第 $k$ 间房屋的金额之和。
不偷窃第 $k$ 间房屋，偷窃总金额为前 $k-1$ 间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 $k$ 间房屋能偷窃到的最高总金额。

用 $d p[i]$ 表示前 $i$ 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：

$d p[i]=\max (d p[i-2]+\operatorname{nums}[i], d p[i-1])$

边界条件为：

$\begin{cases}d p[0]=\operatorname{nums}[0] & \text { 只有一间房屋，则偷窃该房屋 } \\ d p[1]=\max (n u m s[0], n u m s[1]) & \text { 只有两间房屋，选择其中金额较高的房屋进行偷窃 }\end{cases}$

最终的答案即为 $d p[n-1]$, 其中 $n$ 是数组的长度。

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}

同时，可以考虑使用滚动数组优化空间使用。上述方法使用了数组存储结果，考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。得到优化解法如下：

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}

例题：Maximum Total Damage With Spell Casting

Maximum Total Damage With Spell Casting

A magician has various spells.

You are given an array power, where each element represents the damage of a spell. Multiple spells can have the same damage value.

It is a known fact that if a magician decides to cast a spell with a damage of power[i], they cannot cast any spell with a damage of power[i] - 2, power[i] - 1, power[i] + 1, or power[i] + 2.

Each spell can be cast only once.

Return the maximum possible total damage that a magician can cast.

这道题不是从空间上限制选取，而是从值域上限制，因此我们可以考虑对原数组进行排序，使元素选取与空域产生一定相关性，方便状态记录。排序后，考虑聚合相等值的元素，每一步选取实际上都是选取了一组元素。

用$nums$表示聚合后的排序数组，$total(nums[k])$表示元素$nums[k]$的值总和，用 $dp[i]$ 表示前 $i$ 个元素能造成的最高总伤害，那么对于$nums[k]$选或不选：

不选，$dp[i] = dp[i-1]$;
选，则值在$[nums[k]-2, nums[k]-1]$的元素不能选，令$j$为最小满足$nums[j]>=nums[k]-2$的元素，则$dp[i] = dp[j-1] + total(nums[k])$。

对两种情况取最大值，有如下的状态转移方程：

$dp[i] = max(dp[i-1], dp[j-1] + total(nums[i]))$

假设一种最坏的情况，$nums$中所有的元素都是连续的，那么在遇到元素$nums[i]$时，我们至少要保存三个状态才能够完成状态转移，即$dp[i-1], dp[i-2], dp[i-3]$，此时他们的末尾值分别对应$nums[i]-1,nums[i]-2,nums[i]-3$，则$j = i-2$，状态可能从$dp[i-3]$转移。也就是说，$dp[j-1]$的取值范围是$dp[i-1], dp[i-2], dp[i-3]$。

边界条件为：

$\begin{cases}d p[0]=total(\operatorname{nums}[0]) \\ d p[1]= \begin{cases} \max (total(\operatorname{nums}[0]), total(\operatorname{nums}[1])),&nums[0]-2<=nums[1]<nums[0] \\ dp[0]+total(\operatorname{nums}[1]), &nums[0]<nums[1]-2 \end{cases}\end{cases}$

此时发现问题：面对下标为$2$的元素，并不存在状态$dp[-1]$供其转移（$dp[j-1]$的下界）。于是如果从$nums[2]$开始遍历则应该添加此状态（置0），或从$nums[3]$开始遍历。

注意到当前状态仅与前三个状态有关，则可以用长度为$3$的滚动数组进行优化，代码如下：

// author: SilenceZheng66
class Solution {
    public long maximumTotalDamage(int[] power) {
        Map<Integer, Long> map = new TreeMap<>();
        for (int x : power) {
            map.merge(x, (long) x, Long::sum);
        }
        Integer[] nums = map.keySet().toArray(new Integer[0]);
        // 三个状态
        long[] dp = new long[3];
        dp[1] = map.get(nums[0]);
        if(nums.length==1) return dp[1]; 
        dp[2] = nums[0]<nums[1]-2?dp[1]+map.get(nums[1]):Math.max(dp[1], map.get(nums[1]));

        // j放到外面，可以避免每次都从0开始查
        int j=0;
        for(int i=2;i<nums.length;i++){
            // 定位j
            while (nums[j] < nums[i]-2) {
                j++;
            }
            int pos = j==i?2:(j==i-1?1:0);
            long tmp = dp[2];
            dp[2] = Math.max(dp[2], dp[pos]+map.get(nums[i]));
            dp[0] = dp[1];
            dp[1] = tmp;
        }

        return dp[2];
    }
}

思考：如果把2换为k呢？一样的，多增加几个状态就行了，滚动数组法只需要k+1个状态。

参考文献

[1] https://leetcode.cn/problems/house-robber/solutions/263856/da-jia-jie-she-by-leetcode-solution/
[2] https://leetcode.cn/problems/maximum-total-damage-with-spell-casting/solutions/2812389/tao-lu-da-jia-jie-she-pythonjavacgo-by-e-p9b5/

后记

首发于 silencezheng.top，转载请注明出处。