欢迎大家加QQ群：623375442，可以方便群里面交流。
100299. Check if Grid Satisfies Conditions
给你一个大小为 m x n 的二维矩阵 grid 。你需要判断每一个格子 grid[i][j] 是否满足：
- 如果它下面的格子存在，那么它需要等于它下面的格子，也就是 grid[i][j] == grid[i + 1][j] 。
- 如果它右边的格子存在，那么它需要不等于它右边的格子，也就是 grid[i][j] != grid[i][j + 1] 。
如果 所有 格子都满足以上条件，那么返回 true ，否则返回 false 。
测试样例：
输入：grid = [[1,0,2],[1,0,2]]
输出：true
解释：网格图中所有格子都符合条件。
解答：暴力。
class Solution {
public boolean satisfiesConditions(int[][] grid) {
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i + 1 < m && grid[i][j] != grid[i + 1][j]) {
return false;
}
if (j + 1 < n && grid[i][j] == grid[i][j + 1]) {
return false;
}
}
}
return true;
}
}100302. Maximum Points Inside the Square
给你一个二维数组 points 和一个字符串 s ，其中 points[i] 表示第 i 个点的坐标，s[i] 表示第 i 个点的 标签 。
如果一个正方形的中心在 (0, 0) ，所有边都平行于坐标轴，且正方形内 不 存在标签相同的两个点，那么我们称这个正方形是 合法 的。
请你返回 合法 正方形中可以包含的 最多 点数。
注意：
- 如果一个点位于正方形的边上或者在边以内，则认为该点位于正方形内。
- 正方形的边长可以为零。
测试样例：
输入：points = [[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]], s = "abdca"
输出：2
解释：边长为 4 的正方形包含两个点 points[0] 和 points[1] 。
解答：首先寻找满足要求的最大正方形。由于不能同时存在两个相同标签的节点，寻找所有标签的最小两个节点的位置，并取第二大节点的最小值就是正方形大小。
class Solution {
public int maxPointsInsideSquare(int[][] points, String s) {
int[][] min = new int[26][2];
for (int i = 0; i < 26; ++i) {
min[i][0] = Integer.MAX_VALUE;
min[i][1] = Integer.MAX_VALUE;
}
for (int i = 0; i < s.length(); ++i) {
int offset = s.charAt(i) - 'a';
// 距离由加大的绝对值决定
int max = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));
// 寻找每个字母的最小两个位置
if (max < min[offset][0]) {
min[offset][1] = min[offset][0];
min[offset][0] = max;
} else if (max < min[offset][1]) {
min[offset][1] = max;
}
}
int maxDia = Integer.MAX_VALUE;
for (int[] m : min) {
maxDia = Math.min(m[1] - 1, maxDia);
}
// 计算满足要求的节点数
int res = 0;
for (int i = 0; i < s.length(); ++i) {
int max = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));
if (max <= maxDia) {
++res;
}
}
return res;
}
}100289. Minimum Substring Partition of Equal Character Frequency
给你一个字符串 s ，你需要将它分割成一个或者更多的 平衡 子字符串。比方说，s == "ababcc" 那么 ("abab", "c", "c") ，("ab", "abc", "c") 和 ("ababcc") 都是合法分割，但是 ("a", "bab", "cc") ，("aba", "bc", "c") 和 ("ab", "abcc") 不是，不平衡的子字符串用粗体表示。
请你返回 s 最少 能分割成多少个平衡子字符串。
注意：一个 平衡 字符串指的是字符串中所有字符出现的次数都相同。
测试样例：
输入：s = "fabccddg"
输出：3
解释：我们可以将 s 分割成 3 个子字符串：("fab, "ccdd", "g") 或者 ("fabc", "cd", "dg") 。
解答：这题范围不大，1 <= s.length <= 1000。直接利用动态规划解决问题。
class Solution {
public int minimumSubstringsInPartition(String s) {
int[] dp = new int[s.length() + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i < s.length(); ++i) {
int[] count = new int[26];
for (int j = i; j >= 0; --j) {
count[s.charAt(j) - 'a'] += 1;
if (dp[j] != Integer.MAX_VALUE && isValid(count)) {
dp[i + 1] = Math.min(dp[j] + 1, dp[i + 1]);
}
}
}
return dp[s.length()];
}
private boolean isValid(int[] count) {
int last = -1;
for (int n : count) {
if (n != 0) {
if (last == -1) {
last = n;
} else if (last != n) {
return false;
}
}
}
return true;
}
}100295. Find Products of Elements of Big Array
一个整数 x 的 强数组 指的是满足和为 x 的二的幂的最短有序数组。比方说，11 的强数组为 [1, 2, 8] 。
我们将每一个正整数 i （即1，2，3等等）的 强数组 连接得到数组 big_nums ，big_nums 开始部分为 [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...] 。
给你一个二维整数数组 queries ，其中 queries[i] = [fromi, toi, modi] ，你需要计算 (big_nums[fromi] big_nums[fromi + 1] ... * big_nums[toi]) % modi 。
请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。
测试样例：
输入：queries = [[1,3,7]]
输出：[[4]]
解释：只有一个查询。big_nums[1..3] = [2,1,2] 。它们的乘积为 4 ，4 对 7 取余数得到 4 。
解答：这题真的阅读理解，工作日出这么难的题目是真的有点恶心了。重点是要利用折半搜索。因为数组所有成员都是二的幂，我们可以利用big_num的前缀和，而前缀和稍微有点trick，重点是寻找到2的N次幂中的N。寻找分为2部：第一步寻找到big_nums[i], 第i位对应的原始数字。第二步将不够的位数补足。
countDigitOneFromN这个函数的逻辑可以参考233. Number of Digit One，灵神有很详细的题解。
class Solution {
public int[] findProductsOfElements(long[][] queries) {
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; ++i) {
// 寻找二次N的前缀和之差
long diff = findQueryPower(queries[i][1] + 1) - findQueryPower(queries[i][0]);
res[i] = (int) mul(diff, queries[i][2]);
}
return res;
}
private long findQueryPower(long q) {
if (q <= 0) {
return 0L;
}
long st = 0, ed = q + 1;
while (st < ed) {
long mid = (st + ed + 1) / 2;
// 折半搜索，寻找到原始数字
if (countDigitOneFromN(mid) > q) {
ed = mid - 1;
} else {
st = mid;
}
}
// 计算2的N次幂中的N
long res = countPowerFromN(st);
long next = st + 1, total = countDigitOneFromN(st);
// 补足不够的部分
for (int i = 0; i < 60 && total < q; ++i) {
long tmp = (next >> i) & 1;
if (tmp == 1) {
res += i;
++total;
}
}
return res;
}
private long countDigitOneFromN(long n) {
long res = 0, mul = 1, div = 2;
while (div / 2 <= n) {
long re = n / div;
long tmp = (n - re * div) / (div / 2);
res += re * mul;
if (tmp == 1) {
res += n - re * div - mul + 1;
} else if (tmp > 1) {
res += mul;
}
div *= 2;
mul *= 2;
}
return res;
}
private long countPowerFromN(long n) {
long res = 0, mul = 1, div = 2, resMul = 0;
while (div / 2 <= n) {
long re = n / div;
long tmp = (n - re * div) / (div / 2);
res += re * mul * resMul;
if (tmp == 1) {
res += (n - re * div - mul + 1) * resMul;
} else if (tmp > 1) {
res += mul * resMul;
}
div *= 2;
mul *= 2;
++resMul;
}
return res;
}
private long mul(long count, long mod) {
if (count == 0) {
return 1 % mod;
} else {
long tmp = mul(count / 2, mod);
tmp = tmp * tmp % mod;
if (count % 2 == 1) {
tmp = (tmp * 2) % mod;
}
return tmp;
}
}
}