欢迎大家加QQ群：623375442，可以方便群里面交流。
100310. Special Array I
如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。
Aging 有一个整数数组 nums。如果 nums 是一个 特殊数组 ，返回 true，否则返回 false。
测试样例：
输入：nums = [1]
输出：true
解释：只有一个元素，所以答案为 true。
解答：暴力扫描一下
class Solution {
public boolean isArraySpecial(int[] nums) {
for (int i = 1; i < nums.length; ++i) {
if (nums[i] % 2 == nums[i - 1] % 2) {
return false;
}
}
return true;
}
}100308. Special Array II
如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。
周洋哥有一个整数数组 nums 和一个二维整数矩阵 queries，对于 queries[i] = [fromi, toi]，请你帮助周洋哥检查子数组 nums[fromi..toi] 是不是一个 特殊数组 。
返回布尔数组 answer，如果 nums[fromi..toi] 是特殊数组，则 answer[i] 为 true ，否则，answer[i] 为 false 。
测试样例：
输入：nums = [4,3,1,6], queries = [[0,2],[2,3]]
输出：[false,true]
解释：子数组是 [4,3,1]。3 和 1 都是奇数。因此这个查询的答案是 false。子数组是 [1,6]。只有一对：(1,6)，且包含了奇偶性不同的数字。因此这个查询的答案是 true。
解答：首先计算符合要求的区间，并存在一颗红黑树中。扫描query，查看每次query是否落在复合要求的区间中。
class Solution {
public boolean[] isArraySpecial(int[] nums, int[][] queries) {
int st = 0;
TreeSet<int[]> set = new TreeSet<>((a, b) -> (Integer.compare(a[0], b[0])));
for (int i = 1; i <= nums.length; ++i) {
if (i == nums.length || nums[i] % 2 == nums[i - 1] % 2) {
set.add(new int[]{st, i - 1});
st = i;
}
}
boolean[] res = new boolean[queries.length];
for (int i = 0; i < queries.length; ++i) {
int[] first = set.floor(queries[i]);
if (first != null && first[1] >= queries[i][1]) {
res[i] = true;
}
}
return res;
}
}100300. Sum of Digit Differences of All Pairs
车尔尼有一个数组 nums ，它只包含 正 整数，所有正整数的数位长度都 相同 。
两个整数的 数位不同 指的是两个整数 相同 位置上不同数字的数目。
请车尔尼返回 nums 中 所有 整数对里，数位不同之和。
测试样例：
输入：nums = [13,23,12]
输出：4
解释：计算过程如下：
- 13 和 23 的数位不同为 1 。
- 13 和 12 的数位不同为 1 。
- 23 和 12 的数位不同为 2 。
所以所有整数数对的数位不同之和为 1 + 1 + 2 = 4 。
解答：手速场，没仔细看，只需要计算不同的数目。先把每一位的数字分布情况记录下来，然后枚举一下不同的个数。
class Solution {
public long sumDigitDifferences(int[] nums) {
long res = 0, mod = 10;
for (int i = 0; i < 30; ++i) {
long div = mod / 10;
int[] count = new int[10];
// 记录当前数位的数字分布情况
for (int n : nums) {
count[(int) (n % mod / div)] += 1;
}
res += calDiff(count);
mod *= 10;
}
return res;
}
private long calDiff(int[] count) {
long total = 0;
for (int n : count) {
total += n;
}
long res = 0;
// 累和不同的个数
for (int n : count) {
total -= n;
res += total * n;
}
return res;
}
}100298. Find Number of Ways to Reach the K-th Stair
给你有一个 非负 整数 k 。有一个无限长度的台阶，最低 一层编号为 0 。
虎老师有一个整数 jump ，一开始值为 0 。虎老师从台阶 1 开始，虎老师可以使用 任意 次操作，目标是到达第 k 级台阶。假设虎老师位于台阶 i ，一次 操作 中，虎老师可以：
- 向下走一级到 i - 1 ，但该操作 不能 连续使用，如果在台阶第 0 级也不能使用。
- 向上走到台阶 i + 2jump 处，然后 jump 变为 jump + 1 。
请你返回虎老师到达台阶 k 处的总方案数。
注意 ，虎老师可能到达台阶 k 处后，通过一些操作重新回到台阶 k 处，这视为不同的方案。
测试样例：
输入：k = 0
输出：2
解释：2 种到达台阶 0 的方案为：
- 虎老师从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 虎老师从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 执行第二种操作，向上走 20 级台阶到台阶 1 。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
解答：这题还是挺简单的，BFS暴力枚举就行了。
class Solution {
public int waysToReachStair(int k) {
HashMap<Long, Integer> total = initialMap(), cur = initialMap();
int jump = 0;
while (!cur.isEmpty()) {
HashMap<Long, Integer> next = new HashMap<>();
for (Map.Entry<Long, Integer> kv : cur.entrySet()) {
long tmp = kv.getKey() + (1L << jump);
// BFS 暴力下一种情况
// 大于K的就直接扔掉。因为下一次必然还是Type 2
if (tmp <= k) {
next.put(tmp, next.getOrDefault(tmp, 0) + kv.getValue());
total.put(tmp, total.getOrDefault(tmp, 0) + kv.getValue());
}
// Type 1在BFS已经计算，下一次必然是Type 2
if (tmp - 1 <= k) {
next.put(tmp - 1, next.getOrDefault(tmp - 1, 0) + kv.getValue());
total.put(tmp - 1, total.getOrDefault(tmp - 1, 0) + kv.getValue());
}
}
++jump;
cur = next;
}
return total.getOrDefault((long) k, 0);
}
private HashMap<Long, Integer> initialMap() {
HashMap<Long, Integer> map = new HashMap<>();
map.put(1L, 1);
map.put(0L, 1);
return map;
}
}