欢迎大家加QQ群：623375442，可以方便群里面交流。今天去China Joy了，现在China Joy是越来越无聊了。
100377. Find if Digit Game Can Be Won
给你一个 正整数 数组 nums。
小红和小明正在玩游戏。在游戏中，小红可以从 nums 中选择所有个位数 或 所有两位数，剩余的数字归小明所有。如果小红所选数字之和 严格大于 小明的数字之和，则小红获胜。
如果小红能赢得这场游戏，返回 true；否则，返回 false。
测试样例：
输入：nums = [1,2,3,4,10]
输出：false
解释：
小红不管选个位数还是两位数都无法赢得比赛。
解答：暴力运算两位和一位数之和。只要和不同，就是true。
class Solution {
public boolean canAliceWin(int[] nums) {
int s1 = 0, s2 = 0;
for (int n : nums) {
if (n < 10) {
s1 += n;
} else {
s2 += n;
}
}
return s1 != s2;
}
}100371. Find the Count of Numbers Which Are Not Special
给你两个 正整数 l 和 r。对于任何数字 x，x 的所有正因数（除了 x 本身）被称为 x 的 真因数。
如果一个数字恰好仅有两个 真因数，则称该数字为 特殊数字。例如：
- 数字 4 是 特殊数字，因为它的真因数为 1 和 2。
- 数字 6 不是 特殊数字，因为它的真因数为 1、2 和 3。
返回区间 [l, r] 内 不是 特殊数字 的数字数量。
测试样例：
输入：l = 5, r = 7
输出：3
解释：区间 [5, 7] 内不存在特殊数字。
解答：这题脑筋急转弯。被2个数整除，且当中一个数字还是1，且不能是自己本身。那么这个数一定是某个质数的平方。暴力运算一下l到r之间，质数平方的情况。
class Solution {
public int nonSpecialCount(int l, int r) {
int res = 0;
for (int i = 2; i * i <= r; ++i) {
if (i * i < l) {
continue;
} else {
boolean isValid = true;
for (int j = 2; j * j <= i; ++j) {
if (i % j == 0) {
isValid = false;
break;
}
}
if (isValid) {
++res;
}
}
}
return r - l + 1 - res;
}
}100348. Count the Number of Substrings With Dominant Ones
给你一个二进制字符串 s。
请你统计并返回其中 1 显著 的 子字符串 的数量。
如果字符串中 1 的数量 大于或等于 0 的数量的 平方，则认为该字符串是一个 1 显著 的字符串 。
测试样例：
输入：s = "00011"
输出：5
解释：1 显著的子字符串如下表所示。
i j s[i..j] 0 的数量 1 的数量 3 3 1 0 1 4 4 1 0 1 2 3 01 1 1 3 4 11 0 2 2 4 011 1 2
解答：注意一个重点，是0的数量平方。那么利用0出现的次数，暴力计算每个区间就是可能的。
class Solution {
public int numberOfSubstrings(String s) {
List<Integer> zeroPos= new ArrayList<>();
// 堆积0出现的位置
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '0') {
zeroPos.add(i);
}
}
int res = 0;
// 不存在0的子字符串
{
int last = -1;
for (int n : zeroPos) {
int diff = n - last - 1;
res += (diff + 1) * diff / 2;
last = n;
}
int diff = s.length() - last - 1;
res += (diff + 1) * diff / 2;
}
// 暴力枚举所有0出现次数的子字符串
for (int i = 1; i * i <= s.length(); ++i) {
int st = 0, ed = st + i - 1;
while (ed < zeroPos.size()) {
int left = st == 0 ? -1 : zeroPos.get(st - 1);
int right = ed == zeroPos.size() - 1 ? s.length() : zeroPos.get(ed + 1);
int internalOne = zeroPos.get(ed) - zeroPos.get(st) - i + 1;
int leftOne = zeroPos.get(st) - left - 1, rightOne = right - zeroPos.get(ed) - 1;
if (i * i <= internalOne + leftOne + rightOne) {
if (internalOne >= i * i) {
res += (leftOne + 1) * (rightOne + 1);
} else {
// 利用等差数列快速计算结果
res += cal(i * i, internalOne, Math.max(leftOne, rightOne), Math.min(leftOne, rightOne));
}
}
++st;
++ed;
}
}
return res;
}
private int cal(int require, int internalOne, int leftOne, int rightOne) {
int res = 0;
if (leftOne + internalOne >= require) {
res += (leftOne - require + internalOne + 1) * (rightOne + 1);
}
if (rightOne > 0) {
int atLeastOneRight = Math.min(require - internalOne - 1, leftOne);
int max = rightOne;
if (require - internalOne - 1 > leftOne) {
max = rightOne - (require - internalOne - 1 - leftOne);
}
int needAllRight = Math.max(require - internalOne - rightOne, 0);
int diff = atLeastOneRight - needAllRight + 1;
res += (max + max - diff + 1) * (diff) / 2;
}
return res;
}
}100347. Check if the Rectangle Corner Is Reachable
给你两个正整数 X 和 Y 和一个二维整数数组 circles ，其中 circles[i] = [xi, yi, ri] 表示一个圆心在 (xi, yi) 半径为 ri 的圆。
坐标平面内有一个左下角在原点，右上角在 (X, Y) 的矩形。你需要判断是否存在一条从左下角到右上角的路径满足：路径 完全 在矩形内部，不会 触碰或者经过 任何 圆的内部和边界，同时 只 在起点和终点接触到矩形。
如果存在这样的路径，请你返回 true ，否则返回 false 。
测试样例：
输入：X = 3, Y = 4, circles = [[2,1,1]]
输出：true
解释：黑色曲线表示一条从 (0, 0) 到 (3, 4) 的路径。
解答：第三题花了太多时间了。这题按照现在的测试集和数量其实非常好做。利用并查集计算所有相交的圆，然后判断一下所有聚合相交的圆是否和拆开矩阵。
class Solution {
public boolean canReachCorner(int X, int Y, int[][] circles) {
int n = circles.length;
int[] parent = new int[n];
int[] top = new int[n];
int[] bottom = new int[n];
int[] left = new int[n];
int[] right = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
int x = circles[i][0], y = circles[i][1], t = circles[i][2];
top[i] = y + t;
bottom[i] = y - t;
left[i] = x - t;
right[i] = x + t;
}
for (int i = 0; i < n; i++) {
long x = circles[i][0], y = circles[i][1], t = circles[i][2];
for (int j = i + 1; j < n; j++) {
long a = circles[j][0], b = circles[j][1], s = circles[j][2];
// 利用并查集计算相交的圆集合
if ((x - a) * (x - a) + (y - b) * (y - b) <= (t + s) * (t + s)) {
int f1 = find(i, parent), f2 = find(j, parent);
parent[f1] = f2;
top[f2] = Math.max(top[f2], top[f1]);
bottom[f2] = Math.min(bottom[f2], bottom[f1]);
left[f2] = Math.min(left[f2], left[f1]);
right[f2] = Math.max(right[f2], right[f1]);
}
}
}
for (int i = 0; i < n; i++) {
// 判断圆能把矩阵断开
if (parent[i] == i) {
if (top[i] >= Y && bottom[i] <= 0) {
return false;
}
if (top[i] >= Y && right[i] >= X) {
return false;
}
if (left[i] <= 0 && right[i] >= X) {
return false;
}
if (left[i] <= 0 && bottom[i] <= 0) {
return false;
}
}
}
return true;
}
int find(int v, int[] parent) {
return parent[v] == v ? v : (parent[v] = find(parent[v], parent));
}
}