LeetCode Biweekly Contest 111

6954. Count Pairs Whose Sum is Less than Target

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。

测试样例

输入：nums = [-1,1,2,3,1], target = 2

输出：3

解释：总共有 3 个下标对满足题目描述：

• (0, 1) ，0 < 1 且 nums[0] + nums[1] = 0 < target
• (0, 2) ，0 < 2 且 nums[0] + nums[2] = 1 < target
• (0, 4) ，0 < 4 且 nums[0] + nums[4] = 0 < target

注意 (0, 3) 不计入答案因为 nums[0] + nums[3] 不是严格小于 target 。

解答：暴力两重循环计算。

class Solution {
    public int countPairs(List<Integer> nums, int target) {
        int[] arr = new int[nums.size()];
        int p = 0;
        for (int n : nums) {
            arr[p++] = n;
        }

        int res = 0;
        for (int i = 0; i < arr.length; ++i) {
            for (int j = i + 1; j < arr.length; ++j) {
                if (arr[i] + arr[j] < target) {
                    ++res;
                }
            }
        }
        return res;
    }
}

8014. Make String a Subsequence Using Cyclic Increments

给你一个下标从 0 开始的字符串 str1 和 str2 。

一次操作中，你选择 str1 中的若干下标。对于选中的每一个下标 i ，你将 str1[i] 循环 递增，变成下一个字符。也就是说 'a' 变成 'b' ，'b' 变成 'c' ，以此类推，'z' 变成 'a' 。

如果执行以上操作 至多一次 ，可以让 str2 成为 str1 的子序列，请你返回 true ，否则返回 false 。

注意：一个字符串的子序列指的是从原字符串中删除一些（可以一个字符也不删）字符后，剩下字符按照原本先后顺序组成的新字符串。

测试样例：

输入：str1 = "abc", str2 = "ad"

输出：true

解释：

选择 str1 中的下标 2 。将 str1[2] 循环递增，得到 'd' 。因此，str1 变成 "abd" 且 str2 现在是一个子序列。所以返回 true 。

解答: 稍微有点脑筋急转弯，其实就是遍历str1，然后str2从0开始计数。如果当前的字符可以和str2计数中的位置匹配上（相等或者加一相等），那么str2的计数加一。如果计数完毕，就是true，否则是false。

class Solution {
    public boolean canMakeSubsequence(String str1, String str2) {
        int p = 0;
        for (int i = 0; i < str1.length(); ++i) {
            if (str1.charAt(i) == str2.charAt(p) || str1.charAt(i) + 1 == str2.charAt(p)
                || (str1.charAt(i) == 'z' && str2.charAt(p) == 'a')) {
                ++p;
                if (p == str2.length()) return true;
            }
        }
        return false;
    }
}

6941. Sorting Three Groups

给你一个下标从 0 开始长度为 n 的整数数组 nums 。

从 0 到 n - 1 的数字被分为编号从 1 到 3 的三个组，数字 i 属于组 nums[i] 。注意，有的组可能是 空的 。

你可以执行以下操作任意次：

• 选择数字 x 并改变它的组。更正式的，你可以将 nums[x] 改为数字 1 到 3 中的任意一个。

你将按照以下过程构建一个新的数组 res ：

• 将每个组中的数字分别排序。
• 将组 1 ，2 和 3 中的元素 依次 连接以得到 res 。

如果得到的 res 是 非递减顺序的，那么我们称数组 nums 是 美丽数组 。

请你返回将 nums 变为 美丽数组 需要的最少步数。

测试样例：

输入：nums = [2,2,2,2,3,3]

输出：0

解释：

组 1 为空，组 2 为 [0,1,2,3] ，组 3 为 [4,5] 。所以 res 等于 [0,1,2,3,4,5] ，它是非递减顺序的。

解答: 其实这道题目也是暴力。枚举所以切割的位置，然后计算当前切割时，需要移动的次数。保存最小值。

class Solution {
    public int minimumOperations(List<Integer> nums) {
        int[] arr = new int[nums.size()];
        int p = 0;
        for (int n : nums) {
            arr[p++] = n - 1;
        }

        int res = Integer.MAX_VALUE;
        for (int i = 0; i <= arr.length; ++i) {
            for (int j = i; j <= arr.length; ++j) {
                int cur = 0;
                for (int k = 0; k < arr.length; ++k) {
                    if (k < i) {
                        if (arr[k] != 0) ++cur;
                    } else if (k < j) {
                        if (arr[k] != 1) ++cur;
                    } else {
                        if (arr[k] != 2) ++cur;
                    }
                }
                res = Math.min(res, cur);
            }
        }
        return res;
    }
}

8013. Number of Beautiful Integers in the Range

给你正整数 low ，high 和 k 。

如果一个数满足以下两个条件，那么它是 美丽的 ：

• 偶数数位的数目与奇数数位的数目相同。
• 这个整数可以被 k 整除。

请你返回范围 [low, high] 中美丽整数的数目。

测试样例：

输入：low = 5, high = 5, k = 2

输出：0

解释：

5 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。

解答: 这道题目想复杂了，原来暴力也能过。。。枚举所有小于high的，偶数数位的数目与奇数数位的数目相同的数字。然后计算一下多少大于等于low，且能被k整除。

class Solution {
    private static final int[][] markMatrix = {{1,2},{3,5,9,6,10,12},{7,11,19,35,13,21,37,25,41,49,14,22,38,26,42,50,28,44,52,56},{15,23,39,71,135,27,43,75,139,51,83,147,99,163,195,29,45,77,141,53,85,149,101,165,197,57,89,153,105,169,201,113,177,209,225,30,46,78,142,54,86,150,102,166,198,58,90,154,106,170,202,114,178,210,226,60,92,156,108,172,204,116,180,212,228,120,184,216,232,240}};
    private int high, low;

    public int numberOfBeautifulIntegers(int low, int high, int k) {
        this.high = high;
        this.low = low;
        return curNum(k);
    }

    private int curNum(int k) {
        String str = String.valueOf(high);
        int len = str.length(), res = 0;
        for (int i = 2; i <= Math.min(len, 8); i += 2) {
            res += generateCombine(markMatrix[i / 2 - 1], i, k);
        }
        return res;
    }

    private int generateCombine(int[] marks, int len, int k) {
        int res = 0;
        for (int mark : marks) {
            res += dfs(mark, len, k, 0, 0);
        }
        return res;
    }

    private int dfs(int mark, int len, int k, int pos, int num) {
        if (pos == len) {
            if (num % k == 0 && num >= low && num <= high) {
                return 1;
            } else {
                return 0;
            }
        } else {
            int mask = (mark >> (len - 1 - pos)) & 1;
            int res = 0;
            if (mask == 1) {
                for (int i = 1; i <= 9; i += 2) {
                    res += dfs(mark, len, k, pos + 1, num * 10 + i);
                }
            } else {
                for (int i = (pos == 0 ? 2 : 0); i <= 9; i += 2) {
                    res += dfs(mark, len, k, pos + 1, num * 10 + i);
                }
            }
            return res;
        }
    }
}