Ligh0x74's Blog

2023-10-29发表2023-10-29更新算法 / LeetCode6 分钟读完 (大约834个字)

找出数组中的 K-or 值

模拟。

class Solution {
    public int findKOr(int[] nums, int k) {
        int ans = 0;
        for (int i = 0; i < 31; i++) {
            int cnt = 0;
            for (int x : nums) {
                cnt += x >> i & 1;
            }
            if (cnt >= k) {
                ans |= 1 << i;
            }
        }
        return ans;
    }
}

数组的最小相等和

分类讨论。所有 $0$ 都必须被替换为正整数，那么首先将所有 $0$ 替换为 $1$。如果两个数组中都有 $0$，则此时得到的最大的数组和就应该是答案，因为较小的一方总是可以使用更大的正整数替换 $0$，使得两个数组的元素和相等。如果某个数组的和不等于最大和，并且数组中不包含 $0$，那么就无法使两个数组的元素和相等。

class Solution {
    public long minSum(int[] nums1, int[] nums2) {
        int cnt1 = 0, cnt2 = 0;
        long sum1 = 0L, sum2 = 0L;
        for (int x : nums1) {
            if (x == 0) cnt1++;
            sum1 += x;
        }
        for (int x : nums2) {
            if (x == 0) cnt2++;
            sum2 += x;
        }
        long max = Math.max(sum1 + cnt1, sum2 + cnt2);
        if (sum1 != max && cnt1 == 0) return -1;
        if (sum2 != max && cnt2 == 0) return -1;
        return max;
    }
}

使数组变美的最小增量运算数

按照灵神的题解，每个位置的状态就是它右边有多少个数小于 $k$，加上这个维度就可以做记忆化搜索，然后转递推真的很妙。题解区还有其他的状态定义方式，可以看看。代码就贴灵神的。（这题感觉很不错，没有见过的类型）

class Solution {
    public long minIncrementOperations(int[] nums, int k) {
        long f0 = 0, f1 = 0, f2 = 0;
        for (int x : nums) {
            long inc = f0 + Math.max(k - x, 0);
            f0 = Math.min(inc, f1);
            f1 = Math.min(inc, f2);
            f2 = inc;
        }
        return f0;
    }
}

收集所有金币可获得的最大积分

当我们遍历到某个节点时，它的状态就是需要除以多少次 $2$，由数据范围可知每个节点最多有 $15$ 个状态。我们可以从子问题的最优解推出原问题的最优解，并且子问题可以独立求解，符合最优子结构；如果当前节点处于某个状态，它可能是由不同的路径转移得到的，即存在重叠子问题。所以我们可以使用树型 DP 求解该问题，列出如下状态转移方程：

$$ dp[x][i]=\max(\sum_{y}{dp[y][i]}+(coins[x]>>i)-k,\sum_{y}{dp[y][i + 1]}+(coins[x]>>(i+1))) $$

其中 $dp[i][j]$ 表示到达节点 $i$，需要除以 $2^{j}$，该状态下以节点 $i$ 为根的子树能够得到的最大积分。

class Solution {
    public int maximumPoints(int[][] edges, int[] coins, int k) {
        int n = coins.length;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, t -> new ArrayList<>());
        for (var e : edges) {
            int u = e[0], v = e[1];
            g[u].add(v);
            g[v].add(u);
        }
        return dfs(0, -1, g, coins, k)[0];
    }
    
    private int[] dfs(int x, int fa, List<Integer>[] g, int[] coins, int k) {
        int[] sum1 = new int[15];
        int[] sum2 = new int[15];

        for (int y : g[x]) {
            if (y == fa) continue;
            int[] t = dfs(y, x, g, coins, k);
            for (int i = 0; i < 14; i++) {
                sum1[i] += t[i];
                sum2[i] += t[i + 1];
            }
        }

        for (int i = 0; i < 14; i++) {
            sum1[i] = Math.max(sum1[i] + (coins[x] >> i) - k, sum2[i] + (coins[x] >> (i + 1)));
        }
        return sum1;
    }
}

2023-10-29发表2023-10-29更新算法 / LeetCode5 分钟读完 (大约813个字)

第 116 场力扣夜喵双周赛

使二进制字符串变美丽的最少修改次数

长度为偶数的字符串要满足条件，那么将数组分为长度为 $2$ 的各个小段，使各个子数组满足条件一定是最优的。

class Solution {
    public int minChanges(String s) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < n; i += 2) {
            ans += (s.charAt(i) ^ s.charAt(i + 1)) & 1;
        }
        return ans;
    }
}

和为目标值的最长子序列的长度

0-1 背包，转移方程为 $dp[i][j]=\max(dp[i-1][j],dp[i-1][j-nums[i]]+1)$，注意初始化为 $-1$，并在转移时判断有效性。

class Solution {
    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
        int n = nums.size();
        int[] dp = new int[target + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int x : nums) {
            for (int j = target; j >= x; j--) {
                if (dp[j - x] != -1) {
                    dp[j] = Math.max(dp[j], dp[j - x] + 1);
                }
            }
        }
        return dp[target];
    }
}

子数组不同元素数目的平方和 II

动态规划 + 线段树，刚学的线段树就用上了，但是不太熟练，忘记我的线段树板子是从下标一开始操作，并且没有特判，如果操作的右端点比左端点小，那么就会导致数组越界，之后得修改一下板子。假设以 $i$ 为右端点的所有子数组的不同计数的平方和为 $dp[i]$，考虑如何转移到 $dp[i+1]$。

如果在 $[0,i]$ 中和 $nums[i+1]$ 相等的数为 $nums[j]$，则添加 $nums[i+1]$ 会使左端点在 $[j+1,i]$ 范围内的子数组的不同计数加 $1$，而左端点在 $[0,j]$ 范围内子数组的不同计数不变，最后不要忘记加上左端点在 $i+1$ 的子数组的不同计数的平方。我们可以得到如下转移方程，其中 $x_{i,j}$ 表示子数组 $nums[i,j]$ 的不同计数。

$$ \begin{align} dp[i] &=x_{0,i}^{2}+x_{1,i}^{2}+\cdots+x_{i,i}^{2} \\ dp[i+1] &=x_{0,i}^{2}+\cdots+x_{j,i}^{2}+(x_{j+1,i}+1)^{2}+\cdots+(x_{i,i}+1)^{2}+x_{i+1,i+1}^{2} \end{align} $$

然后我们将 $dp[i]$ 代入到 $dp[i+1]$ 中，得到：

$$ dp[i+1]=dp[i]+2\sum_{k=j+1}^{i}x_{k,i}+(i-j)+x_{i+1,i+1}^{2} $$

首先我们需要得到每个数，它左边第一个相同的数的位置，这可以在遍历的过程中使用哈希表得到。然后我们需要维护以当前位置为右端点，所有左端点表示的子数组的不同计数（区间修改），并且需要快速的求区间和，那么就可以使用线段树，这样我们只需要花费 $O(\log{n})$ 的时间进行转移。转移之后，不要忘记更新左端点在 $[j+1,i+1]$ 范围内的子数组的不同计数。

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int sumCounts(int[] nums) {
        int n = nums.length;
        long ans = 0L, sum = 0L;
        var st = new SegmentTree(n);
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 1; i <= n; i++) {
            int j = map.getOrDefault(nums[i - 1], 0);
            map.put(nums[i - 1], i);
            sum = (sum + 2 * st.get(j + 1, i) + i - j) % MOD;
            ans = (ans + sum) % MOD;
            st.add(j + 1, i, 1);
        }
        return (int) ans;
    }
}

2023-10-24发表2023-10-24更新算法 / LeetCode3 分钟读完 (大约523个字)

第 368 场力扣周赛

元素和最小的山形三元组 I

同下。

元素和最小的山形三元组 II

前后缀分解。

class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n + 1], suf = new int[n + 1];
        pre[0] = suf[n] = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            pre[i + 1] = Math.min(pre[i], nums[i]);
        }
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = Math.min(suf[i + 1], nums[i]);
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > pre[i] && nums[i] > suf[i + 1]) {
                ans = Math.min(ans, pre[i] + nums[i] + suf[i + 1]);
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

合法分组的最少组数

贪心，不太会，直接看题解。

class Solution {
    public int minGroupsForValidAssignment(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }
        int k = nums.length;
        for (int x : cnt.values()) {
            k = Math.min(k, x);
        }
        
        for (; ; k--) {
            int ans = 0;
            for (int x : cnt.values()) {
                if (x / k < x % k) {
                    ans = 0;
                    break;
                }
                ans += (x + k) / (k + 1);
            }
            if (ans > 0) {
                return ans;
            }
        }
    }
}

得到 K 个半回文串的最少修改次数

直接记忆化搜索就能搞定，特别注意子字符串的长度要求至少为 $2$。当然还可以预处理出所有因子，也可以将记忆化搜索转化为自底向上的动态规划。

class Solution {
    public int minimumChanges(String s, int k) {
        int n = s.length();

        int[][] change = new int[n][n];
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                change[i][j] = calc(s.substring(i, j + 1));
            }
        }

        int[][] dp = new int[n][k];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        return dfs(0, s, n, k - 1, change, dp);
    }

    private int calc(String s) {
        int n = s.length(), res = n;
        for (int d = 1; d < n; d++) {
            if (n % d == 0) {
                int cnt = 0;
                for (int k = 0; k < d; k++) {
                    for (int i = k, j = n - d + k; i < j; i += d, j -= d) {
                        if (s.charAt(i) != s.charAt(j)) {
                            cnt++;
                        }
                    }
                }
                res = Math.min(res, cnt);
            }
        }
        return res;
    }

    private int dfs(int i, String s, int n, int k, int[][] change, int[][] dp) {
        if (k == 0) {
            return change[i][n - 1];
        }

        if (dp[i][k] != -1) {
            return dp[i][k];
        }

        int res = n;
        for (int j = i + 1; j < n - 2 * k; j++) {
            res = Math.min(res, dfs(j + 1, s, n, k - 1, change, dp) + change[i][j]);
        }
        return dp[i][k] = res;
    }
}