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){ScannerinnewScanner(System.in);intnin.nextInt();System.out.println(1(n-1));}}是 Java 中的左移运算符。1 (n - 1)表示把数字1的二进制向左移动n - 1位。每向左移动一位数值就乘以2因此[ 1 (n-1)2^{n-1} ]例如n 31 的二进制 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){ScannerinnewScanner(System.in);char[]sin.next().toCharArray();intret0;int[]hashnewint[26];intkind0;for(intl0,r0;rs.length;r){hash[s[r]-a];if(hash[s[r]-a]1)kind;if(kind2){retMath.max(ret,r-l1);}while(kind2){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;privateArrayListStringret;publicArrayListStringPermutation(Stringstr){sstr.toCharArray();Arrays.sort(s);ns.length;checknewboolean[n];pathnewStringBuilder();retnewArrayList();dfs(0);returnret;}// depth 表示递归层数privatevoiddfs(intdepth){if(path.length()n){ret.add(path.toString());return;}for(inti0;in;i){// 该字符已经被使用过if(check[i]){continue;}// 同一层中相同字符只选择一次// !check[i - 1] 用于处理 aa 字符的排序情况// 相同字符必须按照下标顺序使用先用前面的 a再用后面的 a这样既不会漏掉排列也不会产生重复排列。if(i0s[i]s[i-1]!check[i-1]){continue;}path.append(s[i]);check[i]true;dfs(depth1);check[i]false;path.deleteCharAt(path.length()-1);}}}
)
