Ligh0x74's Blog

2023-11-20发表2023-11-20更新算法 / LeetCode3 分钟读完 (大约429个字)

使三个字符串相等

等价于求字符串的最长公共前缀。

class Solution {
    public int findMinimumOperations(String s1, String s2, String s3) {
        int n = Math.min(s1.length(), Math.min(s2.length(), s3.length()));
        int i = 0;
        while (i < n && s1.charAt(i) == s2.charAt(i) && s2.charAt(i) == s3.charAt(i)) {
            i++;
        }
        return i == 0 ? -1 : s1.length() + s2.length() + s3.length() - 3 * i;
    }
}

区分黑球与白球

将每个 \(1\) 右边 \(0\) 的个数累加就是需要交换的次数，或者累加每个 \(0\) 左边 \(1\) 的个数也行。

class Solution {
    public long minimumSteps(String s) {
        long ans = 0L;
        int n = s.length(), cnt = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') cnt++;
            else ans += cnt;
        }
        return ans;
    }
}

要求 \(\max((a\oplus x)\times(b\oplus x))\)，可以得出异或只会在两者都为 \(0\) 的位上补 \(1\)，或者交换两者某位上的 \(0\) 和 \(1\)。此时 \((a\oplus x)+(b\oplus x)=c\)，\(c\) 为某个定值，从而问题可以转化为求函数 \(y=x(c-x)\) 的最大值，可以知道当 \(x=\frac{c}{2}\) 时取到最大值，即我们需要让 \((a\oplus x)\) 和 \((b\oplus x)\) 尽可能相等。

class Solution {
    private static final int MOD = (int) 1e9 + 7;
    
    public int maximumXorProduct(long a, long b, int n) {
        long p = a >> n << n, q = b >> n << n;
        for (int i = n - 1; i >= 0; i--) {
            if ((a >> i & 1) == (b >> i & 1)) {
                p |= 1L << i;
                q |= 1L << i;
            } else if (p < q) {
                p |= 1L << i;
            } else {
                q |= 1L << i;
            }
        }
        return (int) (p % MOD * (q % MOD) % MOD);
    }
}

找到 Alice 和 Bob 可以相遇的建筑

离线查询，可以预处理查询序列，然后使用单调栈 + 二分，或者使用最小堆；在线查询，可以使用线段树（暂时不学）。

2023-11-14发表2023-11-14更新算法 / LeetCode1 分钟读完 (大约219个字)

第 371 场力扣周赛

找出强数对的最大异或值 I

暴力。

高访问员工

模拟。

最大化数组末位元素的最少操作次数

两种情况，分类讨论。

找出强数对的最大异或值 II

要找满足 \(\mid x-y\mid\leq\min(x,y)\) 的数对，可以排序化简公式，得到 \(x\leq y\leq2x\)。然后我们可以使用双指针，枚举 \(y\) 或者 \(x\) 都行，基本上就是把满足条件的数添加到 0-1 trie 树中，把不满足条件的从树中删除，一边枚举一边计算最大异或值。还可以使用哈希表做，参考灵茶山艾府的题解。

2023-11-07发表2023-11-07更新算法 / LeetCode5 分钟读完 (大约709个字)

第 370 场力扣周赛

找到冠军 I

如果某一列全为 \(0\)，则该列表示的队伍会成为冠军。

class Solution {
    public int findChampion(int[][] grid) {
        int n = grid.length;
        for (int j = 0; j < n; j++) {
            int cnt = 0;
            for (int i = 0; i < n && cnt == 0; i++) {
                cnt += grid[i][j];
            }
            if (cnt == 0) {
                return j;
            }
        }
        return -1;
    }
}

找到冠军 II

相当于判断入度为 \(0\) 的节点是否只有一个。

class Solution {
    public int findChampion(int n, int[][] edges) {
        int[] in = new int[n];
        for (var e : edges) {
            in[e[1]]++;
        }
        int ans = -1;
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) {
                if (ans == -1) ans = i;
                else return -1;
            }
        }
        return ans;
    }
}

在树上执行操作以后得到的最大分数

树形 DP，要求最大分数，可以先求损失的最小分数，然后使用总分减去该分数即可。

class Solution {
    public long maximumScoreAfterOperations(int[][] edges, int[] values) {
        int n = values.length;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : edges) {
            int u = e[0], v = e[1];
            g[u].add(v);
            g[v].add(u);
        }
        long ans = 0L;
        for (int x : values) {
            ans += x;
        }
        return ans - dfs(0, -1, g, values);
    }
    
    private long dfs(int x, int fa, List<Integer>[] g, int[] values) {
        if (g[x].size() == 1 && g[x].get(0) == fa) {
            return values[x];
        }
        long res = 0L;
        for (int y : g[x]) {
            if (y != fa) {
                res += dfs(y, x, g, values);
            }
        }
        return Math.min(res, values[x]);
    }
}

也可以直接正向做，对于每个节点有两种情况：选择当前节点，要求该节点的每个子树都是健康的；不选当前节点，该节点的所有子节点都可以选。

class Solution {
    public long maximumScoreAfterOperations(int[][] edges, int[] values) {
        int n = values.length;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : edges) {
            int u = e[0], v = e[1];
            g[u].add(v);
            g[v].add(u);
        }
        long[] sum = new long[n];
        return dfs(0, -1, g, values, sum);
    }
    
    private long dfs(int x, int fa, List<Integer>[] g, int[] values, long[] sum) {
        sum[x] = values[x];
        if (g[x].size() == 1 && g[x].get(0) == fa) {
            return 0;
        }
        long dp0 = values[x], dp1 = 0;
        for (int y : g[x]) {
            if (y != fa) {
                dp0 += dfs(y, x, g, values, sum);
                dp1 += sum[y];
            }
        }
        sum[x] += dp1;
        return Math.max(dp0, dp1);
    }
}

平衡子序列的最大和

离散化 + 树状数组优化 DP，直接看灵神代码吧。

// 作者：灵茶山艾府
// 链接：https://leetcode.cn/problems/maximum-balanced-subsequence-sum/solutions/2513121/shu-zhuang-shu-zu-you-hua-dp-by-endlessc-3zf4/
class Solution {
    public long maxBalancedSubsequenceSum(int[] nums) {
        int n = nums.length;
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = nums[i] - i;
        }
        Arrays.sort(b);
 
        BIT t = new BIT(b.length + 1);
        for (int i = 0; i < n; i++) {
            // j 为 nums[i]-i 离散化后的值（从 1 开始）
            int j = Arrays.binarySearch(b, nums[i] - i) + 1;
            long f = Math.max(t.preMax(j), 0) + nums[i];
            t.update(j, f);
        }
        return t.preMax(b.length);
    }
}

// 树状数组模板（维护前缀最大值）
class BIT {
    private long[] tree;

    public BIT(int n) {
        tree = new long[n];
        Arrays.fill(tree, Long.MIN_VALUE);
    }

    public void update(int i, long val) {
        while (i < tree.length) {
            tree[i] = Math.max(tree[i], val);
            i += i & -i;
        }
    }

    public long preMax(int i) {
        long res = Long.MIN_VALUE;
        while (i > 0) {
            res = Math.max(res, tree[i]);
            i &= i - 1;
        }
        return res;
    }
}