Leetcode - 周赛423

目录

一，3349. 检测相邻递增子数组 I

二，3350. 检测相邻递增子数组 II

三，3351. 好子序列的元素之和

四，3352. 统计小于 N 的 K 可约简整数

一，3349. 检测相邻递增子数组 I

本题有两种做法：

1. 先求出递增子数组 f （以 i 结尾的最长子数组长度），然后枚举前一个数组的末尾下标i，判断 f[i] 和 f[i+k] 是否都大于 k
2. 求数组的两个子数组都是严格递增且相邻，有两种情况，要么它一直递增，那么最长可能满足条件的就是 cnt/2，要么它是相邻的两段递增（这两段数组长度求最小），画个图理解一下：

代码如下：

//方法一
class Solution {
    public boolean hasIncreasingSubarrays(List<Integer> nums, int k) {
        int n = nums.size();
        int[] f = new int[n];
        f[0] = 1;
        for(int i=1; i<n; i++){
            if(nums.get(i) > nums.get(i-1)){
                f[i] = f[i-1] + 1;
            }else{
                f[i] = 1;
            }
        }
        for(int i=k-1; i<n-k; i++){
            if(f[i]>=k && f[i+k]>=k)
                return true;
        }
        return false;
    }
}
//方法二
class Solution {
    public boolean hasIncreasingSubarrays(List<Integer> nums, int k) {
        int ans = 1, cnt = 0, pre = 0;
        for(int i=0; i<nums.size(); i++){
            cnt++;
            if(i == nums.size()-1 || nums.get(i) >= nums.get(i+1)){
                ans = Math.max(ans, Math.max(cnt/2, Math.min(cnt, pre)));
                pre = cnt;
                cnt = 0;
            }
        }
        return ans >= k;
    }
}

二，3350. 检测相邻递增子数组 II

本题和T1有一点不同，它是求满足条件的最长子数组的长度，那么就是T1的方法二，直接返回ans就行，当然如果T1是用方法一写的，那么这题肯定会想到二分。

代码如下：

class Solution {
    public int maxIncreasingSubarrays(List<Integer> nums) {
        int ans = 1, cnt = 0, pre = 0;
        for(int i=0; i<nums.size(); i++){
            cnt++;
            if(i == nums.size()-1 || nums.get(i) >= nums.get(i+1)){
                ans = Math.max(ans, Math.max(cnt/2, Math.min(cnt, pre)));
                pre = cnt;
                cnt = 0;
            }
        }
        return ans;
    }
}
//二分写法
class Solution {
    public int maxIncreasingSubarrays(List<Integer> nums) {
        int n = nums.size();
        int[] f = new int[n];
        f[0] = 1;
        for(int i=1; i<n; i++){
            if(nums.get(i) > nums.get(i-1)){
                f[i] = f[i-1] + 1;
            }else{
                f[i] = 1;
            }
        }
        int l = 1, r = n;
        while(l <= r){
            int k = (l + r) / 2;
            if(check(k, nums, f)){
                l = k + 1;
            }else{
                r = k - 1;
            }
        }
        return l - 1;
    }
    boolean check(int k, List<Integer> nums, int[] f){
        int n = nums.size();
        for(int i=k-1; i<n-k; i++){
            if(f[i]>=k && f[i+k]>=k)
                return true;
        }
        return false;
    }
}

三，3351. 好子序列的元素之和

定义 cnt[x]：以 x 结尾的子序列的个数，f[x]：所有以 x 结尾的子序列的和。枚举 nums 数组，对于当前元素 x 来说：

• cnt[x] = cnt[x] + cnt[x-1] + cnt[x+1] + 1
• f[x] = f[x] + f[x-1] + f[x+1] + (cnt[x-1] + cnt[x+1] + 1) * x
• 答案就是 sum(f)

代码如下：

class Solution {
    public int sumOfGoodSubsequences(int[] nums) {
        final int MOD = 1_000_000_007;
        Map<Integer, Integer> f = new HashMap<>();
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            long c = cnt.getOrDefault(x - 1, 0) + cnt.getOrDefault(x + 1, 0) + 1;
            f.put(x, (int)((x * c + f.getOrDefault(x, 0) + f.getOrDefault(x - 1, 0) + f.getOrDefault(x + 1, 0)) % MOD));
            cnt.put(x, (int)((cnt.getOrDefault(x, 0) + c) % MOD));
        }
        long ans = 0;
        for (int s : f.values()) {
            ans += s;
        }
        return (int) (ans % MOD);
    }
}

四，3352. 统计小于 N 的 K 可约简整数

定义 f[x]：表示 x 二进制中 1 的个数，f*[x]：将 x 通过 f[x] 不断的迭代，将 x 迭代成 1 需要的操作次数。可以得到：f*[x] = f*[f(x)] + 1

通过上述公式可以算出二进制中有 x 个 1 的数需要操作 f*[x] 次才能转换成 1，本题问的是有多少个整数，可以使用数位DP进行计算，通过枚举每一个二进制位为 0 / 1，计算出总共有多少满足条件的整数，注：题目要求所有整数小于给的二进制数 s。

代码如下：

class Solution {
    private static final int MOD = 1_000_000_007;
    public int countKReducibleNumbers(String s, int k) {
        int n = s.length();
        int ans = 0;
        int[] f = new int[n];
        memo = new int[n][n];
        for(int[] r : memo) Arrays.fill(r, -1);
        List<Integer> v = new ArrayList<>();
        for(int i=1; i<n; i++){
            f[i] = f[Integer.bitCount(i)] + 1;
            if(f[i] <= k){ 
                //原本f[1]=0,f[i] < k, 但是这里f[1]=1,相当于所有f[i]+1,所以<=k
                ans = (ans + dfs(0, i, true, s.toCharArray())) % MOD;
            }
        }
        return ans;
    }
    int[][] memo;
    int dfs(int i, int j, boolean islimit, char[] s){
        if(i == s.length) return !islimit&&j==0?1:0;//1.防止与s全部相同。2.使用了j个1
        if(!islimit && memo[i][j] != -1) return memo[i][j];
        int up = islimit ? s[i] - '0' : 1;
        int res = 0;
        for(int d=0; d<=Math.min(j, up); d++){
            res = (res + dfs(i+1, j-d, islimit && d==up, s)) % MOD;
        }
        if(!islimit) memo[i][j] = res;
        return res;
    }
}