特殊数组Ⅰ
如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。
Aging 有一个整数数组 nums。如果 nums 是一个 特殊数组 ，返回 true，否则返回 false。
示例 1：
输入：nums = [1]
输出：true
解释：
只有一个元素，所以答案为 true。
示例 2：
输入：nums = [2,1,4]
输出：true
解释：
只有两对相邻元素： (2,1) 和 (1,4)，它们都包含了奇偶性不同的数字，因此答案为 true。
示例 3：
输入：nums = [4,3,1,6]
输出：false
解释：
nums[1] 和 nums[2] 都是奇数。因此答案为 false。
提示：
1 <= nums.length <= 1001 <= nums[i] <= 100
比较暴力，可以直接判断相邻的元素的奇偶性，如果相同返回False，如果检查没有的话，返回True。
代码如下：
class Solution:
def isArraySpecial(self, nums: List[int]) -> bool:
for x,y in pairwise(nums):
if x%2 == y%2:
return False
return True特殊数组Ⅱ
如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。
周洋哥有一个整数数组 nums 和一个二维整数矩阵 queries，对于 queries[i] = [fromi, toi]，请你帮助周洋哥检查子数组 nums[fromi..toi] 是不是一个 特殊数组 。
返回布尔数组 answer，如果 nums[fromi..toi] 是特殊数组，则 answer[i] 为 true ，否则，answer[i] 为 false 。
示例 1：
输入：nums = [3,4,1,2,6], queries = [[0,4]]
输出：[false]
解释：
子数组是 [3,4,1,2,6]。2 和 6 都是偶数。
示例 2：
输入：nums = [4,3,1,6], queries = [[0,2],[2,3]]
输出：[false,true]
解释：
- 子数组是
[4,3,1]。3 和 1 都是奇数。因此这个查询的答案是false。 - 子数组是
[1,6]。只有一对：(1,6)，且包含了奇偶性不同的数字。因此这个查询的答案是true。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= queries.length <= 105queries[i].length == 20 <= queries[i][0] <= queries[i][1] <= nums.length - 1
直接暴力去解决会超时，因为暴力的解法是O(n^2)，而数据范围是1e5。
换一种考虑的方法，既然是要考虑相邻的元素之间的奇偶性，不妨直接考虑他们之间的“逗号”。
比如说例子——
4， 3， 1， 6
我们去考虑每个逗号两侧的数字的奇偶性的相同，如果是相同的话，记为0，不同的话记为1.
那么就是这样——
0， 1， 0
做个图：
但是我们是需要去查询一段区间内是否有这种特殊的数组，不难想到使用前缀和的方法。
查询的时候发现需要加一个前导0.
原理就是只要这个区间的两端的端点的前缀和不相等就是False，反之就是True。
代码如下：
class Solution:
def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
s = [0]
for x,y in pairwise(nums):
s.append(s[-1]+(x%2==y%2))
return [s[f] == s[t] for f,t in queries]所有数对中数位不同之和
车尔尼有一个数组 nums ，它只包含 正 整数，所有正整数的数位长度都 相同 。
两个整数的 数位不同 指的是两个整数 相同 位置上不同数字的数目。
请车尔尼返回 nums 中 所有 整数对里，数位不同之和。
示例 1：
输入：nums = [13,23,12]
输出：4
解释：
计算过程如下：
- 13 和 23 的数位不同为 1 。
- 13 和 12 的数位不同为 1 。
- 23 和 12 的数位不同为 2 。
所以所有整数数对的数位不同之和为 1 + 1 + 2 = 4 。
示例 2：
输入：nums = [10,10,10,10]
输出：0
解释：
数组中所有整数都相同，所以所有整数数对的数位不同之和为 0 。
提示：
2 <= nums.length <= 1051 <= nums[i] < 109nums中的整数都有相同的数位长度。
题目中说明，只包含有正整数，并且正整数的数位长度是相同的，需要我们返回的是所有正数中不同数位之和。
把所有的数位分开来考虑，举个例子——
假如说现在已经考虑到了第1个数（下标为1）的各位，不妨把所有的各位抽出来看看如何计算。
箭头所指向的3，就是我们当前考虑到的地方，那么是如何进行考虑的呢？
因为我们是要统计每个数字的每一位的不同的数量，下标刚好就是在我们当前这个位置一共有多少个数字，我们可以搞一个哈希表，来统计在我们这个位置之前的，这个位置的值出现的次数。
又因为这个值只会是【0，9】，所以完全可以使用数组来模拟。
class Solution:
def sumDigitDifferences(self, nums: List[int]) -> int:
ans = 0
cnt = [[0]*10 for _ in str(nums[0])]
for k,x in enumerate(nums):
for i,v in enumerate(map(int,str(x))):
ans += k - cnt[i][v]
cnt[i][v]+=1
return ans
到达第 K 级台阶的方案数
给你有一个 非负 整数 k 。有一个无限长度的台阶，最低 一层编号为 0 。
虎老师有一个整数 jump ，一开始值为 0 。虎老师从台阶 1 开始，虎老师可以使用 任意 次操作，目标是到达第 k 级台阶。假设虎老师位于台阶 i ，一次 操作 中，虎老师可以：
- 向下走一级到
i - 1，但该操作 不能 连续使用，如果在台阶第 0 级也不能使用。 - 向上走到台阶
i + 2jump处，然后jump变为jump + 1。
请你返回虎老师到达台阶 k 处的总方案数。
注意 ，虎老师可能到达台阶 k 处后，通过一些操作重新回到台阶 k 处，这视为不同的方案。
示例 1：
输入：k = 0
输出：2
解释：
2 种到达台阶 0 的方案为：
- 虎老师从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 虎老师从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 执行第二种操作，向上走 20 级台阶到台阶 1 。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
示例 2：
输入：k = 1
输出：4
解释：
4 种到达台阶 1 的方案为：
- 虎老师从台阶 1 开始，已经到达台阶 1 。
- 虎老师从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 执行第二种操作，向上走 20 级台阶到台阶 1 。
- 虎老师从台阶 1 开始。
- 执行第二种操作，向上走 20 级台阶到台阶 2 。
- 执行第一种操作，向下走 1 级台阶到台阶 1 。
- 虎老师从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 执行第二种操作，向上走 20 级台阶到台阶 1 。
- 执行第一种操作，向下走 1 级台阶到台阶 0 。
- 执行第二种操作，向上走 21 级台阶到台阶 2 。
- 执行第一种操作，向下走 1 级台阶到台阶 1 。
提示：
0 <= k <= 10^9
先来解释一下这个题目的意思，说是最小的阶梯是0，从1阶梯开始，要求我们走到k阶梯，有两种操作，但是是有条件的。
操作一：向下走一级
操作二：向上走 2^jump 级
那么很容易想到使用暴力搜索改成记忆化的方法来求解。
画一个图来帮助我们理解一下——
那么递归的出口又在哪里呢？
这需要我们在来分析一下了——
首先，分析出一个原理，在递归的过程中，数字 i 是逐渐变大的。
当 i 已经等于 k 的时候我们不能结束，因为他继续搜下去可能会再有一个答案。
当 i 等于 k + 1 的时候我们还不能结束，因为这个时候只要执行了操作一就可以给结果再加上一个一，变成 i 等于 k，回到第一点。
当 i 等于 k+2的时候，我们就可以结束了，因为这个时候无论如何 i 都不可能能等于 k 了，直接返回0即可。
还有一点值得注意的就是我们需要再参数中加上一个bool类型的变量，用来说明喔当前这种情况是否是两个操作都可以做。
最后代码如下：
class Solution:
def waysToReachStair(self, k: int) -> int:
@cache
def dfs(i:int,j:int,p:bool)->int:
if i >= k+2:
return 0
ans = 1 if i==k else 0
ans += dfs(i+(1<<j),j+1,True)
if p:
ans += dfs(i-1,j,False)
return ans
return dfs(1,0,True)
