6461. Check if The Number is Fascinating
给你一个三位数整数 n 。
如果经过以下修改得到的数字 恰好 包含数字 1 到 9 各一次且不包含任何 0 ，那么我们称数字 n 是 迷人的 ：
- 将 n 与数字 2 n 和 3 n 连接 。
如果 n 是迷人的，返回 true，否则返回 false 。
连接 两个数字表示把它们首尾相接连在一起。比方说 121 和 371 连接得到 121371 。
测试样例
输入：n = 192
输出：true
解释：我们将数字 n = 192 ，2 n = 384 和 3 n = 576 连接，得到 192384576 。这个数字包含 1 到 9 恰好各一次。
解答：按照题意，拼接数字并且统计一下各个数位0-9出现情况。
class Solution {
public boolean isFascinating(int n) {
boolean[] isVisit = new boolean[10];
for (int i = 1; i <= 3; ++i) {
if (!refresh(n * i, isVisit)) return false;
}
for (int i = 1; i <= 9; ++i) {
if (!isVisit[i]) {
return false;
}
}
return true;
}
private boolean refresh(int n, boolean[] isVisit) {
while (n != 0) {
int m = n % 10;
if (m == 0 || isVisit[m]) {
return false;
}
isVisit[m] = true;
n /= 10;
}
return true;
}
}6425. Find the Longest Semi-Repetitive Substring
给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。
如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串是半重复的 。
请你返回 s 中最长半重复子字符串的长度。
一个子字符串是一个字符串中一段连续 非空 的字符。
测试样例：
输入：s = "52233"
输出：4
解释：
最长半重复子字符串是 "5223" ，子字符串从 i = 0 开始，在 j = 3 处结束。
解答: 这道题目也能暴力通过。反正提示：1 <= s.length <= 50。直接两重循环寻找最长半重复字符串就行了
class Solution {
public int longestSemiRepetitiveSubstring(String s) {
int max = 0;
for (int i = 0; i < s.length(); ++i) {
for (int j = i; j < s.length(); ++j) {
if (isValid(s, i, j)) {
max = Math.max(max, j - i + 1);
}
}
}
return max;
}
private boolean isValid(String s, int st, int ed) {
int count = 0;
for (int i = st + 1; i <= ed; ++i) {
if (s.charAt(i) == s.charAt(i - 1)) {
++count;
if (count == 2) return false;
}
}
return true;
}
}6426. Movement of Robots
有一些机器人分布在一条无限长的数轴上，他们初始坐标用一个下标从 0 开始的整数数组 nums 表示。当你给机器人下达命令时，它们以每秒钟一单位的速度开始移动。
给你一个字符串 s ，每个字符按顺序分别表示每个机器人移动的方向。'L' 表示机器人往左或者数轴的负方向移动，'R' 表示机器人往右或者数轴的正方向移动。
当两个机器人相撞时，它们开始沿着原本相反的方向移动。
请你返回指令重复执行 d 秒后，所有机器人之间两两距离之和。由于答案可能很大，请你将答案对 109 + 7 取余后返回。
注意：
- 对于坐标在 i 和 j 的两个机器人，(i,j) 和 (j,i) 视为相同的坐标对。也就是说，机器人视为无差别的。
- 当机器人相撞时，它们 立即改变 它们的前进时间，这个过程不消耗任何时间。
- 当两个机器人在同一时刻占据相同的位置时，就会相撞。
- 例如，如果一个机器人位于位置 0 并往右移动，另一个机器人位于位置 2 并往左移动，下一秒，它们都将占据位置 1，并改变方向。再下一秒钟后，第一个机器人位于位置 0 并往左移动，而另一个机器人位于位置 2 并往右移动。
- 例如，如果一个机器人位于位置 0 并往右移动，另一个机器人位于位置 1 并往左移动，下一秒，第一个机器人位于位置 0 并往左行驶，而另一个机器人位于位置 1 并往右移动。
测试样例：
输入：nums = [-2,0,2], s = "RLL", d = 3
8
解释：
- 1 秒后，机器人的位置为 [-1,-1,1] 。现在下标为 0 的机器人开始往左移动，下标为 1 的机器人开始往右移动。
- 2 秒后，机器人的位置为 [-2,0,0] 。现在下标为 1 的机器人开始往左移动，下标为 2 的机器人开始往右移动。
- 3 秒后，机器人的位置为 [-3,-1,1] 。
下标为 0 和 1 的机器人之间距离为 abs(-3 - (-1)) = 2 。下标为 0 和 2 的机器人之间的距离为 abs(-3 - 1) = 4 。下标为 1 和 2 的机器人之间的距离为 abs(-1 - 1) = 2 。
所有机器人对之间的总距离为 2 + 4 + 2 = 8 。
解答: 这道题目需要一点脑筋急转弯。按照题意2个机器人相撞之后会改变方向，但是实际上你可以认为他们没有改变方向，继续前进了（不影响最终机器的位置统计）。
如果这个脑筋急转弯没问题的话，那么接下来就是后缀和计算距离。
class Solution {
private static final int mod = 1_000_000_007;
public int sumDistance(int[] nums, String s, int d) {
long ld = d;
int len = nums.length;
long[] pos = new long[len];
for (int i = 0; i < len; ++i) {
if (s.charAt(i) == 'R') {
pos[i] = nums[i] + ld;
} else {
pos[i] = nums[i] - ld;
}
}
Arrays.sort(pos);
long rightSum = 0;
for (long n : pos) {
rightSum += n;
}
long res = 0;
int right = nums.length;
for (long p : pos) {
res += rightSum - right * p;
res %= mod;
right -= 1;
rightSum -= p;
}
return (int) res;
}
}6463. Find a Good Subset of the Matrix
给你一个下标从 0 开始大小为 m x n 的二进制矩阵 grid 。
从原矩阵中选出若干行构成一个行的 非空 子集，如果子集中任何一列的和至多为子集大小的一半，那么我们称这个子集是 好子集。
更正式的，如果选出来的行子集大小（即行的数量）为 k，那么每一列的和至多为 floor(k / 2) 。
请你返回一个整数数组，它包含好子集的行下标，请你将子集中的元素 升序 返回。
如果有多个好子集，你可以返回任意一个。如果没有好子集，请你返回一个空数组。
一个矩阵 grid 的行 子集 ，是删除 grid 中某些（也可能不删除）行后，剩余行构成的元素集合。
测试样例：
输入：grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]]
输出：[0,1]
解释
我们可以选择第 0 和第 1 行构成一个好子集。选出来的子集大小为 2 。
解答: 这题有个重要的提示：1 <= n <= 5。所以会很容易想到存在状态压缩。题目只要求返回一个符合要求的好子集即可。
那么如果存在一行，所有元素都是0，那么它自己就是一个好子集。否则必然会存在一个子集对，它们俩求与会是0。
抄一个大佬证明：
假设任意两个都交。
- 不存在0个1的行：证明：如果存在，随便找另一个都是不交的
- 不存在1个1的行：如果存在，由于任意两个都交，所以这一列全都是1，显然无解
- 不存在2个1的行：证明: 假设这一行长这样：11000, 那别的行要么是10xxx，要么是01xxx，要么是 11xxx，容易看出不管怎么选，前两列都是不能满足要求的。于是所有行都有至少3个1。由于题目条件，每一列最多只有m/2个1，所以所有列加起来最多只有2.5m个 1，但是我们推导出了一共有3m个1，矛盾。
class Solution {
public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
int[] first = new int[32];
Arrays.fill(first, -1);
for (int i = 0; i < grid.length; ++i) {
int[] r = grid[i];
int key = 0;
for (int p = 0; p < r.length; ++p) {
key += (r[p] << p);
}
if (key == 0) {
return Arrays.asList(i);
}
for (int k = 1; k < 32; ++k) {
if (first[k] != -1 && (k & key) == 0) {
return Arrays.asList(first[k], i);
}
}
first[key] = i;
}
return new ArrayList<>();
}
}emm，感觉这周有挺多脑筋急转弯了。我不是认同这周题目出得不错。