😺 第 75 场力扣夜喵双周赛

虽然是手速场，但没有Wrong就很开心。

2220. 转换数字的最少位翻转次数

一次 位翻转 定义为将数字 x 二进制中的一个位进行 翻转 操作，即将 0 变成 1 ，或者将 1 变成 0 。

• 比方说，x = 7 ，二进制表示为 111 ，我们可以选择任意一个位（包含没有显示的前导 0 ）并进行翻转。比方说我们可以翻转最右边一位得到 110 ，或者翻转右边起第二位得到 101 ，或者翻转右边起第五位（这一位是前导 0 ）得到 10111 等等。

给你两个整数 start 和 goal ，请你返回将 start 转变成 goal 的 最少位翻转 次数。

示例 1：
输入：start = 10, goal = 7 输出：3 解释：10 和 7 的二进制表示分别为 1010 和 0111 。我们可以通过 3 步将 10 转变成 7 ： - 翻转右边起第一位得到：1010 -> 1011 。 - 翻转右边起第三位：1011 -> 1111 。 - 翻转右边起第四位：1111 -> 0111 。 我们无法在 3 步内将 10 转变成 7 。所以我们返回 3 。
示例 2：
输入：start = 3, goal = 4 输出：3 解释：3 和 4 的二进制表示分别为 011 和 100 。我们可以通过 3 步将 3 转变成 4 ： - 翻转右边起第一位：011 -> 010 。 - 翻转右边起第二位：010 -> 000 。 - 翻转右边起第三位：000 -> 100 。 我们无法在 3 步内将 3 变成 4 。所以我们返回 3 。

提示：

• 0 <= start, goal <= 109

思路：
模拟

class Solution {
    public int minBitFlips(int s, int p) {
        int cnt = 0;
        for (int i = 0; i < 31; i++) {
            int x = s >> i & 1, y = p >> i & 1;
            if (x != y)
                cnt++;
        }
        return cnt;
    }
}

2221. 数组的三角和

显示英文描述
我的提交返回竞赛

• 通过的用户数3074
• 尝试过的用户数3152
• 用户总通过次数3112
• 用户总提交次数3945
• 题目难度Medium

给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 0 到 9 之间（两者都包含）的一个数字。
nums 的 三角和 是执行以下操作以后最后剩下元素的值：

1. nums 初始包含 n 个元素。如果 n == 1 ，终止 操作。否则，创建 一个新的下标从 0 开始的长度为 n - 1 的整数数组 newNums 。
2. 对于满足 0 <= i < n - 1 的下标 i ，newNums[i] 赋值 为 (nums[i] + nums[i+1]) % 10 ，% 表示取余运算。
3. 将 newNums 替换 数组 nums 。
4. 从步骤 1 开始 重复 整个过程。

请你返回 nums 的三角和。

示例 1：

输入：nums = [1,2,3,4,5] 输出：8 解释： 上图展示了得到数组三角和的过程。
示例 2：
输入：nums = [5] 输出：5 解释： 由于 nums 中只有一个元素，数组的三角和为这个元素自己。

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 9

思路：
模拟递推过程

class Solution {
    public int triangularSum(int[] nums) {
        // int res = 0;
        int n = nums.length;
        if (n == 1) return nums[0];
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                nums[j] = (nums[j] + nums[j + 1]) % 10;
            }
        }
        return nums[0];
    }
}

6035. 选择建筑的方案数

给你一个下标从 0 开始的二进制字符串 s ，它表示一条街沿途的建筑类型，其中：

• s[i] = ‘0’ 表示第 i 栋建筑是一栋办公楼，
• s[i] = ‘1’ 表示第 i 栋建筑是一间餐厅。

作为市政厅的官员，你需要随机 选择 3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑 相邻 的两栋不能是同一类型。

• 比方说，给你 s = “00_1101“ ，我们不能选择第 1 ，3 和 5 栋建筑，因为得到的子序列是 “011_” ，有相邻两栋建筑是同一类型，所以 不合 题意。

请你返回可以选择 3 栋建筑的 有效方案数 。

示例 1：
输入：s = “001101” 输出：6 解释： 以下下标集合是合法的： - [0,2,4] ，从 “0_01101” 得到 “010” - [0,3,4] ，从 “001101” 得到 “010” - [1,2,4] ，从 “001101” 得到 “010” - [1,3,4] ，从 “001101” 得到 “010” - [2,4,5] ，从 “001101“ 得到 “101” - [3,4,5] ，从 “001101_” 得到 “101” 没有别的合法选择，所以总共有 6 种方法。
示例 2：
输入：s = “11100” 输出：0 解释：没有任何符合题意的选择。

提示：

• 3 <= s.length <= 105
• s[i] 要么是 ‘0’ ，要么是 ‘1’ 。

思路：
只能选101或者010
枚举即可

class Solution {
    public long numberOfWays(String s) {
        int n = s.length();
        int[] l0 = new int[n], r0 = new int[n];
        int[] l1 = new int[n], r1 = new int[n];
        int c0 = 0, c1 = 0;
        for (int i = 0; i < n; i++) {
            l0[i] = c0;
            l1[i] = c1;
            if (s.charAt(i) == '1')
                c1++;
            else
                c0++;
        }
        c0 = 0;
        c1 = 0;
        for (int i = n - 1; i >= 0; i--) {
            r0[i] = c0;
            r1[i] = c1;
            if (s.charAt(i) == '1')
                c1++;
            else
                c0++;
        }
        long res = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') {
                res += 1L * l1[i] * r1[i];
            } else {
                res += 1L * l0[i] * r0[i];
            }
        }
        return res;
    }
}

2223. 构造字符串的总得分和

你需要从空字符串开始 构造 一个长度为 n 的字符串 s ，构造的过程为每次给当前字符串 前面 添加 一个 字符。构造过程中得到的所有字符串编号为 1 到 n ，其中长度为 i 的字符串编号为 si 。

• 比方说，s = “abaca” ，s1 == “a” ，s2 == “ca” ，s3 == “aca” 依次类推。

si 的 得分 为 si 和 sn 的 最长公共前缀 的长度（注意 s == sn ）。
给你最终的字符串 s ，请你返回每一个_ _si 的 得分之和 。

示例 1：
输入：s = “babab” 输出：9 解释： s1 == “b” ，最长公共前缀是 “b” ，得分为 1 。 s2 == “ab” ，没有公共前缀，得分为 0 。 s3 == “bab” ，最长公共前缀为 “bab” ，得分为 3 。 s4 == “abab” ，没有公共前缀，得分为 0 。 s5 == “babab” ，最长公共前缀为 “babab” ，得分为 5 。 得分和为 1 + 0 + 3 + 0 + 5 = 9 ，所以我们返回 9 。
示例 2 ：
输入：s = “azbazbzaz” 输出：14 解释： s2 == “az” ，最长公共前缀为 “az” ，得分为 2 。 s6 == “azbzaz” ，最长公共前缀为 “azb” ，得分为 3 。 s9 == “azbazbzaz” ，最长公共前缀为 “azbazbzaz” ，得分为 9 。 其他 si 得分均为 0 。 得分和为 2 + 3 + 9 = 14 ，所以我们返回 14 。

提示：

• 1 <= s.length <= 105
• s 只包含小写英文字母。

思路：
方法1：哈希 + 二分
方法2：扩展KMP(Z函数)板子题

class Solution {
    int N = 100010, P = 13331;
    long[] h = new long[N], p = new long[N];
    public long sumScores(String s) {
        int n = s.length();
        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i-1] * P;
            h[i] = h[i-1] * P + s.charAt(i - 1);
        }
        long res = n;
        for (int i = 2; i <= n; i++) {
            if (s.charAt(i - 1) != s.charAt(0))
                continue;
            int l = i, r = n;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (get(i, mid) != get(1, mid - i + 1))
                    r = mid - 1;
                else
                    l = mid;
            }
            res += l - i + 1;
        }
        return res;
    }
    long get(int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
}

class Solution {
    public long sumScores(String s) {
        int[] z = z_func(s);
        long res = s.length();
        for (int x : z)
            res += x;
        return res;
    }
    int[] z_func(String s) {
        int n = s.length(), l = 0, r = 0;
        int[] z = new int[n];
        for (int i = 1; i < n; i++) {
            if (i <= r && z[i - l] < r - i + 1)
                z[i] = z[i - l];
            else {
                z[i] = Math.max(0, r - i + 1);
                while (i + z[i] < n && s.charAt(i + z[i]) == s.charAt(z[i]))
                    z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }
}