Day 33
跳台阶扩展问题
解题思路：可以把跳跃过程先看成连续的n个“1级台阶”。
以n = 3为例：
1 1 1这 3 个1之间有n - 1 = 2个间隙：
1 | 1 | 1每个间隙有两种选择：
- 断开：表示前后两段是两次跳跃
- 不断开：表示前后两段合并为同一次跳跃
所有情况如下：
不分隔： 3 -> 跳 3 级 第1处分隔：1 + 2 第2处分隔：2 + 1 两处分隔：1 + 1 + 1表示有 n 个阶梯, n-1 个阶梯间隙，每个间隙有断开，不断开两种情况，所以总选择数是：
[ \underbrace{2 \times 2 \times \cdots \times 2}_{n-1\text{个间隙}} =2^{n-1} ]
所以共有：
2^(n-1) = 2^2 = 4代码实现：
importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intn=in.nextInt();System.out.println(1<<(n-1));}}<<是 Java 中的左移运算符。
1 << (n - 1)表示把数字1的二进制向左移动n - 1位。每向左移动一位，数值就乘以2，因此：
[ 1 << (n-1)=2^{n-1} ]
例如n = 3：
1 的二进制： 0001 向左移动 2 位： 0100 十进制结果： 4对应代码：
int result = 1 << (n - 1); System.out.println(result);也可以使用数学函数：
int result = (int) Math.pow(2, n - 1);不过这道题使用位运算更直接，而且n <= 20，结果不会超出int的范围。
包含不超过两种字符的最长子串
解题思路：
- 滑动窗口，kind <=2 更新长度
代码实现：
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);char[]s=in.next().toCharArray();intret=0;int[]hash=newint[26];intkind=0;for(intl=0,r=0;r<s.length;r++){hash[s[r]-'a']++;if(hash[s[r]-'a']==1)kind++;if(kind<=2){ret=Math.max(ret,r-l+1);}while(kind>2){hash[s[l]-'a']--;if(hash[s[l]-'a']==0)kind--;l++;}}System.out.println(ret);}}字符串的排列
解题思路：
- 递归层数，实现重排序；
- 注意相同字符必须按照下标顺序使用，先用前面的
a，再用后面的a，这样既不会漏掉排列，也不会产生重复排列。
代码实现：
importjava.util.*;publicclassSolution{privatechar[]s;privateboolean[]check;privateintn;privateStringBuilderpath;privateArrayList<String>ret;publicArrayList<String>Permutation(Stringstr){s=str.toCharArray();Arrays.sort(s);n=s.length;check=newboolean[n];path=newStringBuilder();ret=newArrayList<>();dfs(0);returnret;}// depth 表示递归层数privatevoiddfs(intdepth){if(path.length()==n){ret.add(path.toString());return;}for(inti=0;i<n;i++){// 该字符已经被使用过if(check[i]){continue;}// 同一层中，相同字符只选择一次// !check[i - 1] 用于处理 aa 字符的排序情况// 相同字符必须按照下标顺序使用，先用前面的 a，再用后面的 a，这样既不会漏掉排列，也不会产生重复排列。if(i>0&&s[i]==s[i-1]&&!check[i-1]){continue;}path.append(s[i]);check[i]=true;dfs(depth+1);check[i]=false;path.deleteCharAt(path.length()-1);}}}
