LeetCode周记 EP9

2024-08-25

字数统计: 3.9k字 | 阅读时长: 18分

前言

周赛依然没空打，面笔太多辽，感觉这周数位题比较多，写周六的hard题用了两个小时还是没能全A，不过思路没问题，表扬一下自己。

本周主题：三维动态规划（三个限制）、组合数学、位运、状态压缩DP

题目：

240819每日一题—Student Attendance Record II
240820每日一题—Find Number of Ways to Reach the K-th Stair
240822每日一题—Minimum Array End
240823每日一题—Find Products of Elements of Big Array
240824每日一题—Partition to K Equal Sum Subsets

PS：腾子音乐的笔也忒难了

Student Attendance Record II （HARD）

Student Attendance Record II

An attendance record for a student can be represented as a string where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters:

‘A’: Absent.

‘L’: Late.

‘P’: Present.

Any student is eligible for an attendance award if they meet both of the following criteria:

The student was absent (‘A’) for strictly fewer than 2 days total.

The student was never late (‘L’) for 3 or more consecutive days.

Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 109 + 7.

初次分析时，可得到如下限制：

最多只能有两个A
L可能被A或P隔开
L只能出现单独的一个或连续的两个
L的最大数量为n/3*2 + n-(n/3*2)，即把出勤分为若干个三元组与一个末尾，三元组中均存在两个L，末尾均为L

动态规划

可以使用动态规划计算可奖励的出勤记录的数量。

由于可奖励的出勤记录要求缺勤次数少于 2 和连续迟到次数少于 3，因此动态规划的状态由总天数、缺勤次数和结尾连续迟到次数决定（由于不会记录连续迟到次数等于或多于 3 的情况，因此非结尾的连续迟到次数一定少于 3，只需要记录结尾连续迟到次数即可）。

定义 $d p[i][j][k]$ 表示前 $i$ 天有 $j$ 个 ‘$\mathrm{A}$’ 且结尾有连续 $k$ 个 ‘ L ‘ 的可奖励的出勤记录的数量, 其中 $0 \leq i \leq$ $n, 0 \leq j \leq 1,0 \leq k \leq 2$ 。

当 $i=0$ 时，没有任何出勤记录，此时 ‘ $A$ ‘的数量和结尾连续 ‘ $L$ ‘ 的数量一定是 0 ，因此动态规划的边界情况是 $d p[0][0][0]=1$ 。

当 $1 \leq i \leq n$ 时， $d p[i][][]$ 的值从 $d p[i-1][][]$ 的值转移得到，计算每个状态的值需要考虑第 $i$ 天的出勤记录:

如果第 $i$ 天的出勤记录是 ‘ P ‘，则前 $i$ 天和前 $i-1$ 天的出勤记录相比， ‘ $A$ ‘的数量不变，结尾连续 ${ }^{\prime} \mathrm{L}$ ‘ 的数量清零，因此对 $0 \leq j \leq 1$ ，有

$d p[i][j][0]:=d p[i][j][0]+\sum_{k=0}^2 d p[i-1][j][k]$

如果第 $i$ 天的出勤记录是 ‘ $A$ ‘，则前 $i$ 天和前 $i-1$ 天的出勤记录相比， ‘ $A$ ‘的数量加 1 ，结尾连续 ‘ $L$ ‘ 的数量清零，此时要求前 $i-1$ 天的出勤记录记录中的 ‘ $A$ ‘的数量必须为 0 ，否则前 $i$ 天的出勤记录至少有 2 个 ‘ $A$ ‘，不满足可奖励的条件，因此有

$d p[i][1][0]:=d p[i][1][0]+\sum_{k=0}^2 d p[i-1][0][k]$

如果第 $i$ 天的出勤记录是 ‘ L ‘，则前 $i$ 天和前 $i-1$ 天的出勤记录相比， ‘A’ 的数量不变，结尾连续 ${ }^{\prime} L$ ‘ 的数量加 1 , 此时要求前 $i-1$ 天的出勤记录记录中的结尾连续 ‘ $L$ ‘ 的数量不超过 1 ，否则前 $i$天的出勤记录的结尾至少有 3 个 ‘ $L$ ‘，不满足可奖励的条件，因此对 $0 \leq j \leq 1$ 和 $1 \leq k \leq 2$ ，有

$d p[i][j][k]:=d p[i][j][k]+d p[i-1][j][k-1]$

上述状态转移方程对于i=1也适用。计算长度为 n 的所有可奖励的出勤记录的数量，即为计算 dp[n][][] 的所有元素之和。计算过程中需要将结果对10^9+7取模。

class Solution {
    public int checkRecord(int n) {
        final int MOD = 1000000007;
        int[][][] dp = new int[n + 1][2][3]; // 长度，A 的数量，结尾连续 L 的数量
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            // 以 P 结尾的数量
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD;
                }
            }
            // 以 A 结尾的数量
            for (int k = 0; k <= 2; k++) {
                dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD;
            }
            // 以 L 结尾的数量
            for (int j = 0; j <= 1; j++) {
                for (int k = 1; k <= 2; k++) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD;
                }
            }
        }
        int sum = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                sum = (sum + dp[n][j][k]) % MOD;
            }
        }
        return sum;
    }
}

根据状态转移，发现可以利用滚动数组优化：

class Solution {
    public int checkRecord(int n) {
        final int MOD = 1000000007;
        int[][] dp = new int[2][3]; // A 的数量，结尾连续 L 的数量
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int[][] dpNew = new int[2][3];
            // 以 P 结尾的数量
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    dpNew[j][0] = (dpNew[j][0] + dp[j][k]) % MOD;
                }
            }
            // 以 A 结尾的数量
            for (int k = 0; k <= 2; k++) {
                dpNew[1][0] = (dpNew[1][0] + dp[0][k]) % MOD;
            }
            // 以 L 结尾的数量
            for (int j = 0; j <= 1; j++) {
                for (int k = 1; k <= 2; k++) {
                    dpNew[j][k] = (dpNew[j][k] + dp[j][k - 1]) % MOD;
                }
            }
            dp = dpNew;
        }
        int sum = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                sum = (sum + dp[j][k]) % MOD;
            }
        }
        return sum;
    }
}

PS：逐渐理解DP似乎就是一种限制条件枚举的解法，列出限制，逐条件枚举，例如01背包就是在枚举背包容量。

Find Number of Ways to Reach the K-th Stair （HARD）

Find Number of Ways to Reach the K-th Stair

You are given a non-negative integer k. There exists a staircase with an infinite number of stairs, with the lowest stair numbered 0.

Alice has an integer jump, with an initial value of 0. She starts on stair 1 and wants to reach stair k using any number of operations. If she is on stair i, in one operation she can:

Go down to stair i - 1. This operation cannot be used consecutively or on stair 0.

Go up to stair i + 2jump. And then, jump becomes jump + 1.
Return the total number of ways Alice can reach stair k.
Note that it is possible that Alice reaches the stair k, and performs some operations to reach the stair k again.

容易想到递归方式穷举所有可能性，代码如下：

// author: SilenceZheng66
class Solution {
    int res = 0;
    int ks;
    
    public void moveMachine(int i, int jump, boolean canDown, int ops){
        if(i<0||i>ks+1||ops>61) return;
        if(i==ks){
            res++;
        }
        moveMachine(i+(int)Math.pow(2, jump), jump+1, true, ops+1);
        if(canDown) moveMachine(i-1, jump, false, ops+1);
    }

    public int waysToReachStair(int k) {
        ks = k;
        moveMachine(1, 0, true, 0);
        return k==1?4:res;
    }
}

暴力穷举用例只能通过50%，组合数学法见官解。

位运算

两道题都是组合+位运算的类型，例题一必须完全掌握，第二题以目前水平能写个七八十就可以了。

例题一：Minimum Array End

Minimum Array End

You are given two integers n and x. You have to construct an array of positive integers nums of size n where for every 0 <= i < n - 1, nums[i + 1] is greater than nums[i], and the result of the bitwise AND operation between all elements of nums is x.

Return the minimum possible value of nums[n - 1].

题目还是很好理解的，仔细分析一下就知道是要从x开始逐步往0位上填1，直到填出第n-1个数，填充过程保持数组递增。我的第一次解法如下，会OOM：

// author: SilenceZheng66
class Solution {
    public long minEnd(int n, int x) {
        long last = 1;
        // 存储低位到高位的0位置，后续按顺序拼mask就行了
        List<Long> masks = new ArrayList<>();
        while(last<=Long.MAX_VALUE&&masks.size()<n-1){
            if((last&x)==0){
                masks.add(last);
                int len = masks.size();
                // 存储组合
                for(int i=0;i<len-1;i++){
                    masks.add(last^masks.get(i));
                }
            }
            last<<=1;
        }
        return n==1?x:(x^masks.get(n-2));
    }
}

遇到的卡点是计算目标值需要存储前序值，需要压缩空间。可以用另一种视角来看填0位的过程，即把x上的1位都提出来，剩下的位置上按1、2、...、n-1的值去填即可，例如对于x = 100010, n = 4，可以看作是向0000上依次填0001, 0010, 0011，则可得出答案100111。因此，可以确定目标值为把n-1的二进制插入到x的0位中，解法如下。

class Solution {
    public long minEnd(int n, int x) {
        // 返回值可能的最大位数，即两个long的长度减去各自的前导0，当x全是1时出现。
        int bitCount = 128 - Long.numberOfLeadingZeros(n) - Long.numberOfLeadingZeros(x);
        long res = x;
        long m = n - 1; // 要填到0位的所有bit
        int j = 0; // 记录x中已经填过的bit
        for (int i = 0; i < bitCount; ++i) {
            // 逐位查看是否是0
            if (((res >> i) & 1) == 0) {
                // 对于是0的位置，如果n-1也为0则不处理，如果为1则用异或填入
                if (((m >> j) & 1) == 1) {
                    res |= (1L << i);
                }
                j++;
            }
        }
        return res;
    }
}

例题二：Find Products of Elements of Big Array （HARD）

Find Products of Elements of Big Array

The powerful array of a non-negative integer x is defined as the shortest sorted array of powers of two that sum up to x. The table below illustrates examples of how the powerful array is determined. It can be proven that the powerful array of x is unique.

The array big_nums is created by concatenating the powerful arrays for every positive integer i in ascending order: 1, 2, 3, and so on. Thus, big_nums begins as [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, …].

You are given a 2D integer matrix queries, where for queries[i] = [fromi, toi, modi] you should calculate (big_nums[fromi] big_nums[fromi + 1] … * big_nums[toi]) % modi.

Return an integer array answer such that answer[i] is the answer to the ith query.

思路：首先看如何定位bignums[i]的值，从数位的角度考虑，对于01000来说，其之前的元素个数其实就是1、2、3个1在3个格子中有多少种排列，然后再乘元素数C31*1+C32*2+C33*3 = 12，可以应用组合数的加权求和公式。用b(x)表示b(x)位为1，其余为0的二进制数，x从0开始，则b(x)的下标为n*2^(n-1)。对于任意一个下标y，考虑遍历i，找到首个小于y的i*2^(i-1)，然后模拟遍历数位找到bignums[from]的值，继续模拟遍历，找到bignums[to]之间的若干值，求解。

// author: SilenceZheng66
class Solution {
    public int[] findProductsOfElements(long[][] queries) {
        int n = queries.length;
        int[] ans = new int[n];
        for(int k=0;k<n;k++){
            long from = queries[k][0];
            long to = queries[k][1];
            long mod = queries[k][2];

            int lastSmallInd = 0;
            int lastPower = 0;
            for(int i=0;i<32;i++){
                if((int)Math.pow(2, i-1) * i<=from){
                    lastSmallInd = (int)Math.pow(2, i-1) * i;
                    lastPower = i;
                }
                else break;
            }
            int startOuterVal = (int)Math.pow(2, lastPower);
            int startVal = startOuterVal;

            if(lastSmallInd<from){
                // 模拟
                int startInd = lastSmallInd;
                while(startInd<from){
                    startOuterVal++;
                    int tmp = Integer.bitCount(startOuterVal); // 减去最大的1
                    if(startInd+tmp<from) startInd+=tmp;
                    else{
                        // 逐位右移寻找
                        int sov = startOuterVal;
                        int cnt = 0; // 元素计数
                        int bitCnt = -1; // 位数计数
                        while (startInd+cnt<from) {
                            // 判断末位是否为1
                            if((sov&1)==1) cnt++;
                            sov>>=1;
                            bitCnt++;
                        }
                        startVal = (int) Math.pow(2, bitCnt);
                        startInd+=cnt;
                    }
                }
            }
            // 开始计算结果
            long mul = startVal;
            long remain = to-from; // to-from个元素还没计算

            while(remain>0){
                while(startVal<startOuterVal){
                    startVal<<=1;
                    if(remain<=0) break;
                    // 有重合的1
                    if((startVal&startOuterVal)!=0){
                        remain--;
                        mul*=startVal;
                    }
                }
                startOuterVal++;
                startVal = 1;
                if((startVal&startOuterVal)!=0) remain--;
            }
           

            ans[k] = (int) (mul%mod);
        }
        return ans;
    }
}

这种解法可以通过95%的用例，全通的解法可以参考官解。

Partition to K Equal Sum Subsets

Partition to K Equal Sum Subsets

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

1 <= k <= nums.length <= 16
1 <= nums[i] <= 10^4
The frequency of each element is in the range [1, 4].

状态压缩DP

状态压缩就是使用某种方法，简明扼要地以最小代价来表示某种状态，通常是用一串01数字（二进制数）来表示各个点的状态。这就要求使用状态压缩的对象的点的状态必须只有两种，0 或 1；当然如果有三种状态用三进制来表示也未尝不可。

状态压缩的目的一方面是缩小了数据存储的空间，另一方面是在状态对比和状态整体处理时能够提高效率。这样就要求状态数据中的单元个数不能太大，比如用int来表示一个状态的时候，状态的单元个数不能超过32（32位的机器），所以题目一般都是至少有一维的数据范围很小。

状压DP就是使用状态压缩的动态规划。动态规划问题通常有两种，一种是对递归问题的记忆化求解，另一种是把大问题看作是多阶段的决策求解。这里用的便是后一种，这带来一个需求，即存储之前的状态，再由状态及状态对应的值推演出状态转移方程最终得到最优解。

回到本题，题目给定长度为 $n$ 的数组 $nums$，和整数 $k$，我们需要判断是否能将数组分成 $k$ 个总和相等的非空子集。首先计算数组的和 $all$，如果 $all$ 不是 $k$ 的倍数，那么不可能能有合法方案，此时直接返回 $False$。否则我们需要得到 $k$ 个和为 $per= all/k$的集合。

数组长度在16以内，则可以用一个整数 $S$ 来表示当前可用的数字集合：从低位到高位, 第 $i$ 位为 0 则表示数字 nums $[i]$ 可以使用, 否则表示 nums [i] 已被使用。然后我们用 $d p[S]$ 来表示在可用的数字状态为 $S$ 的情况下是否可能可行, 初始全部状态为记录为不可行状态 False, 只记 $d p[0]=$ True 为可行状态。

我们每次对于当前状态下从可用的数字中选择一个数字, 若此时选择全部数字取模后小于等于 per。则说明选择该数字后的状态再继续往下添加数字是可能能满足题意的，并且此时标记状为可能可行状态，否则就一定不能达到满足。最终返回 $d p[U]$即可, 其中 $U$ 表示全部数字使用的集合状态。

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int all = Arrays.stream(nums).sum();
        if (all % k != 0) {
            return false;
        }
        int per = all / k;
        Arrays.sort(nums);
        int n = nums.length;
        if (nums[n - 1] > per) {
            return false;
        }
        // 开始DP
        boolean[] dp = new boolean[1 << n]; // 所有可能的状态
        int[] curSum = new int[1 << n]; // 状态对应的总和？
        dp[0] = true;
        for (int i = 0; i < 1 << n; i++) {
            if (!dp[i]) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                if (curSum[i] + nums[j] > per) {
                    break;
                }
                // 状态i中j物品可用
                if (((i >> j) & 1) == 0) {
                    // 定位下一个状态，即选了j物品后的状态
                    int next = i | (1 << j);
                    // 如果是不可用状态，说明还没更新过
                    if (!dp[next]) {
                        // 对per取余表示删除已存满的子集
                        curSum[next] = (curSum[i] + nums[j]) % per;
                        dp[next] = true;
                    }
                }
            }
        }
        // 全为1的状态下是否可用，即取走全部元素后是否可行
        return dp[(1 << n) - 1];
    }
}

参考文献

[1] https://algo.itcharge.cn/10.Dynamic-Programming/07.State-DP/01.State-DP/
[2] https://blog.nowcoder.net/n/fcc30eadb2b44395862194814e819315?from=nowcoder_improve

后记

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