目录

一，3151. 特殊数组 I

二，3152. 特殊数组 II

三，3153. 所有数对中数位不同之和

四，3154. 到达第 K 级台阶的方案数

---

一，3151. 特殊数组 I

本题就是判断一个数组是否是奇偶相间的，如果是，返回true；否则，返回false，直接暴力

代码如下： 

class Solution {public boolean isArraySpecial(int[] nums) {int n = nums.length;for(int i=1; i<n; i++){if(nums[i]%2 == nums[i-1]%2)return false;}return true;}
}

二，3152. 特殊数组 II

本题就是判断nums数组在 [from，to] 的区间是否满足奇偶相间。由于数据范围太大，无法暴力。其实我们可以预处理一下，先统计出数组pre[i]：表示以 i 为右端点的满足条件的最小左端点。再遍历queries数组，判断这里的左端点是否>=pre[queries[i][1]]，如果大于等于，ans[i] = true；如果小于，ans[i] = false;

class Solution {public boolean[] isArraySpecial(int[] nums, int[][] queries) {int n = nums.length;int[] pre = new int[n];for(int r=1; r<n; r++){if(nums[r]%2 != nums[r-1]%2){pre[r] = pre[r-1];}else{pre[r] = r;}}boolean[] ans = new boolean[queries.length];for(int i=0; i<queries.length; i++){ans[i] = pre[queries[i][1]] <= queries[i][0];}return ans;}
}

前缀和做法：

我们定义一个a[i]:表示nums[i] 和 nums[i+1]是否是奇偶相间的，a[i] = 0，表示两个数一奇一偶；a[i] = 1，表示两个数同奇同偶。如果想要得知【from，to】区间是否是特殊数组，就是判断数组a在【from，to-1】区间是否出现过1（即区间和是否>0），这就变成了一个求前缀和的问题。

代码如下：

class Solution {public boolean[] isArraySpecial(int[] nums, int[][] queries) {int[] s = new int[nums.length];//a数组的前缀和数组for(int i=1; i<nums.length; i++){s[i] = s[i-1] + (nums[i-1]%2==nums[i]%2?1:0);}boolean[] ans = new boolean[queries.length];for(int i=0; i<queries.length; i++){ans[i] = s[queries[i][0]] == s[queries[i][1]];}return ans;}
}

三，3153. 所有数对中数位不同之和

本题可以从个位，十位，百位.....依次进行计算，而单个位上的计算，就变成了这个问题——给你一个长为 n 的数组 a，只包含数字 0 到 9，其中有多少个不同的数对？我们可以遍历数组a，使用一个数组或哈希表记录<出现过的数字，出现次数>，如果当前数字 d 没有出现过，ans += k，表示d能与前面出现的所有数字组成数对（k表示之前出现了k个数字），如果d出现过，ans += k - cnt[d]，表示d能与k - cnt[d] 个数组成数对。

代码如下：

class Solution {public long sumDigitDifferences(int[] nums) {int n = String.valueOf(nums[0]).length();long[][] cnt = new long[n][10];long ans = 0;for(int i=0; i<nums.length; i++){int x = nums[i];int j = 0;while(x > 0){if(cnt[j][x%10]==0){ans += i;}else{ans += i-cnt[j][x%10];}cnt[j][x%10]++;j++;x /= 10;}}return ans;}
}

四，3154. 到达第 K 级台阶的方案数

dfs(i，j，flg)：在该状态下，到达台阶k的总方案数

• i：表示当前所处的位置
• j：表示使用操作二的次数
• flg：表示前一次操作是否使用操作一，这个参数是为了判断当前能否使用操作一，因为题目中规定不能连续使用操作一

它的转移来源：

• 使用操作一：前提 flg == false && i > 0，接下来要解决的子问题就是 dfs(i-1，j，true)，加入返回值中
• 使用操作二：随时都能使用，接下来要解决的子问题就是 dfs(i+(1<<j)，j+1，false)，加入返回值中
• 因为题目可以在它到达台阶k处继续操作，所以该条件不能作为结束条件，但是它也是一个正确的方案，所以当 i == k 时，返回值+1

结束条件：我们发现操作一最多只能回退一个台阶，而操作二除了第一次上1个台阶，其余都>1，所以可以发现如果 i > k + 1，那么就再也回不到台阶 k 了，因此结束条件是 i > k + 1，返回 0.

代码如下：

class Solution {public int waysToReachStair(int k) {return dfs(1, 0, k, false);}Map<String, Integer> map = new HashMap<>();int dfs(int i, int j, int k, boolean flg){if(i > k+1) return 0;String key = i + " " + j + " " + flg;if(map.containsKey(key)) return map.get(key);int res = i==k?1:0;if(flg == false)res += dfs(i-1, j, k, true);res += dfs(i+(1<<j), j+1, k, false);map.put(key, res);return res;}
}