shelterofly

目标

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

示例 2:

输入: nums = [1,2,3,4], k = 3
输出: false

说明：

• 1 <= k <= len(nums) <= 16
• 0 < nums[i] < 10000
• 每个元素的频率在 [1,4] 范围内

思路

给定一个数组 nums，判断能否将其划分为 k 个非空子集，要求每个子集的和都相等。

与数组中元素顺序无关可以排序。数组元素的和是可以枚举的，它一定大于等于数组中的最大元素。和确定了之后就可以从后向前判断能否组成这个和，如果不能则立即返回。

// todo

代码

性能

目标

给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ，对于所有 0 <= i < n - 1 ，满足 nums[i + 1] 大于 nums[i] ，并且数组 nums 中所有元素的按位 AND 运算结果为 x 。

返回 nums[n - 1] 可能的 最小 值。

示例 1：

输入：n = 3, x = 4
输出：6
解释：
数组 nums 可以是 [4,5,6] ，最后一个元素为 6 。

示例 2：

输入：n = 2, x = 7
输出：15
解释：
数组 nums 可以是 [7,15] ，最后一个元素为 15 。

说明：

• 1 <= n, x <= 10^8

思路

构造一个长度为 n 的单调递增数组 nums，要求数组所有元素按位与的结果为正整数 x，返回 nums[n - 1] 的最小值。

要使元素按位与的结果为 x，那么 x 中bit位为1的位置在元素中也必须为1。我们可以找到 x 中bit位为0的位置，从最低位开始置1，如果还不凑不够数组个数就将最高位置1，重新从最低位开始置1。

刚开始是按照上面的思路模拟着写的，非常容易出错。调试了半天发现，其实就是将 n - 1 的二进制表示填入 x 的二进制表示中的bit位为0的位置，如果不够就借用高位的0。之所以是 n -1 是因为 x 本身也算一个元素，0 ~ n - 1 共 n 个元素。

官网题解也正是这个思路，不过实现简洁多了。主要是刚开始没有想清楚，其实根本不用讨论低位/高位，直接填就行了。

代码

/**
 * @date 2024-08-22 10:12
 */
public class MinEnd3133 {

    public long minEnd(int n, int x) {
        List<Integer> zeroIndex = new ArrayList<>(63);
        int i = 0;
        int tmp = x;
        // 记录0的位置
        while (tmp > 0) {
            if ((tmp & 1) == 0) {
                zeroIndex.add(i);
            }
            tmp >>= 1;
            i++;
        }
        long res = x;
        int zeroCnt = zeroIndex.size();
        long highBitsCnt;
        // 如果不含0，那么只能填高位
        if (zeroCnt == 0) {
            // 这个不应该全填1，应填n-1的二进制表示
            highBitsCnt = n - 1;
            while (highBitsCnt > 0) {
                if ((highBitsCnt & 1) == 1) {
                    res |= 1L << i;
                }
                i++;
                highBitsCnt >>= 1;
            }
            return res;
        }
        // 如果含0则计算其能表示的数字个数，下面是快速幂
        long oneLoopElementCnt = 1;
        tmp = zeroCnt;
        int base = 2;
        while (tmp > 0) {
            if ((tmp & 1) == 1) {
                oneLoopElementCnt = oneLoopElementCnt * base;
            }
            base *= base;
            tmp >>= 1;
        }
        // 低位需要填的个数
        long lowBitsCnt = n % oneLoopElementCnt - 1;
        if (lowBitsCnt == -1) {
            // 如果为-1，表示能够整除，将低位的0全置为1
            for (Integer index : zeroIndex) {
                res |= 1L << index;
            }
            // 如果低位能够填满数组则无需填高位
            if (n <= oneLoopElementCnt) {
                highBitsCnt = 0;
            } else {
                // 高位的计数需减1，是因为将低位全填1，这时已经完成了一个loop，例如n=4，x=2，oneLoopElementCnt 为2，n / oneLoopElementCnt = 2， (10 11) 110 111，我们只需要填充一个高位
                highBitsCnt = n / oneLoopElementCnt - 1;
            }
        } else {
            // 否则将需要填在低位的个数填入低位的0
            int j = 0;
            while (lowBitsCnt > 0) {
                if ((lowBitsCnt & 1) == 1) {
                    res |= 1L << zeroIndex.get(j);
                }
                j++;
                lowBitsCnt >>= 1;
            }
            // 如果低位能够填满数组则无需填高位
            if (n <= oneLoopElementCnt) {
                highBitsCnt = 0;
            } else {
                // 这里不需要减1，是因为n不能整除oneLoopElementCnt，多余位已经被舍去了，例如n=3，x=2，n / oneLoopElementCnt = 1
                highBitsCnt = n / oneLoopElementCnt;
            }
        }

        // 填充高位个数
        while (highBitsCnt > 0) {
            if ((highBitsCnt & 1) == 1) {
                // 出错点：如果写成1，会溢出，必须加上L
                res |= 1L << i;
            }
            i++;
            highBitsCnt >>= 1;
        }

        return res;
    }

}

性能

目标

给你一个长度为 n 的字符串 word 和一个整数 k ，其中 k 是 n 的因数。

在一次操作中，你可以选择任意两个下标 i 和 j，其中 0 <= i, j < n ，且这两个下标都可以被 k 整除，然后用从 j 开始的长度为 k 的子串替换从 i 开始的长度为 k 的子串。也就是说，将子串 word[i..i + k - 1] 替换为子串 word[j..j + k - 1] 。

返回使 word 成为 K 周期字符串 所需的 最少 操作次数。

如果存在某个长度为 k 的字符串 s，使得 word 可以表示为任意次数连接 s ，则称字符串 word 是 K 周期字符串 。例如，如果 word == "ababab"，那么 word 就是 s = "ab" 时的 2 周期字符串 。

示例 1：

输入：word = "leetcodeleet", k = 4
输出：1
解释：可以选择 i = 4 和 j = 0 获得一个 4 周期字符串。这次操作后，word 变为 "leetleetleet" 。

示例 2：

输入：word = "leetcoleet", k = 2
输出：3
解释：可以执行以下操作获得一个 2 周期字符串。

i j word
0 2 etetcoleet
4 0 etetetleet
6 0 etetetetet

说明：

• 1 <= n == word.length <= 10^5
• 1 <= k <= word.length
• k 能整除 word.length 。
• word 仅由小写英文字母组成。

思路

给定字符串 word 以及周期 k（k 为 word 长度的因数，即可以被 word 长度整除），将字符串分为 word.length()/k 份，每次操作可以将其中一份替换为其它份字符串。问最少需要多少次操作，可以使每份字符串都相等。

用份数减去出现次数最多的子串即可。

代码

/**
 * @date 2024-08-17 20:44
 */
public class MinimumOperationsToMakeKPeriodic3137 {

    /**
     * 使用substring效率更高
     * 循环步长为k
     */
    public int minimumOperationsToMakeKPeriodic(String word, int k) {
        int n = word.length();
        int max = 0;
        int parties = n / k;
        // 优化点：指定初始容量
        Map<String, Integer> map = new HashMap<>(parties);
        // 出错点，这里循环条件使 <= n，而非小于n，因为我们使用的使substring，不包括结束index
        for (int i = k; i <= n; i += k) {
            String period = word.substring(i - k, i);
            // 优化点：这里可以直接拿到cnt，不用后面再从map里get
            int cnt = map.merge(period, 1, Integer::sum);
            max = Math.max(cnt, max);
        }
        return parties - max;
    }

}

性能