本文主要是介绍今日刷三题（day13）：变态跳台阶+包含不超过两种字符的最长字串+字符串的排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目一：变态跳台阶
题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
输入输出描述：
输入：3 输出：4
输入：1 输出：1
题目解析：
动态规划思想。
① 跳上n级台阶，可以站在n-1级跳1级上去，站在n-2级跳2级上去，站在n-3及跳3级上去.....站在第1级跳n-1级上去，站在平台上跳n级上去,一共跳的方法有：
f(n)=f(n-1)+f(n-2)+f(n-3)+f(n-4)+......+f(2)+f(1)+f(0)
② 跳上n-1级台阶，站在n-2级跳1级上去，站在n-3及跳2级上去.....站在第1级跳n-2级上去，站在平台上跳n-1级上去,一共跳的方法有：
f(n-1)=f(n-2)+f(n-3)+f(n-4)+......+f(2)+f(1)+f(0)
③ 联立式子①②可得：
f(n)=f(n-1)*2
作答情况：
正确，注意理解思路题目不难。
代码：
public static void main(String[] args) {Scanner in=new Scanner(System.in);int n=in.nextInt();int[] dp=new int[n+1];//dp[i]代表跳到第i个台阶上有多少种办法for(int i=1;i<dp.length;i++){if(i==1) dp[i]=1;else if(i==2) dp[i]=2;else dp[i]=2*dp[i-1];}System.out.print(dp[n]);}题目二：包含不超过两种字符的最长字串
题目描述：
给定一个长度为 n 的字符串，找出最多包含两种字符的最长子串 t ，返回这个最长的长度。
数据范围：1≤n≤105 ，字符串种仅包含小写英文字母
输入输出描述：
输入：nowcoder 输出：2
输入：nooooow 输出：6
题目解析：
滑动窗口的思想。
准备：两个指针，left和right，right负责进窗口动作，left负责出窗口动作。
step1：（进窗口）用count来统计窗口内有多少种字符，当某个字符的个数从0变为1，说明多了一种字符，进窗口。
step2：（判断）当count>2时，就要准备出窗口。
step3：（出窗口）当left所指向字符的个数为1时，出窗口，将left原本指向的字符的个数变为0，并且left自增，count自减。
其他情况：right--，并更新ret长度。
作答情况：
没有想到滑动窗口，用的暴力解法。
hash[s[right]-'a']++==0表示：hash[s[right]-'a']在自增之前值为0；
hash[s[left++]-'a']--==1表示：hash[s[left++]-'a']在自减之前值为1；
import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);char[] s=in.next().toCharArray();int left=0;int right=0;int n=s.length;int count=0;//统计窗口中有多少种字符int[] hash=new int[26];int ret=0;while(right<n){if(hash[s[right]-'a']++==0){//没出现过，新增的字符//在++之前他的值为0count++;}if(count>2){if(hash[s[left++]-'a']--==1){//在--之前它的值为1count--;}}ret=Math.max(ret,right-left+1);right++; }System.out.print(ret);}}题目三：字符串的排列
题目描述：
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
输入输出描述：
输入："abc" 输出："abc","acb","bac","bca","cab","cba"
输入："aab" 输出："aab","aba","baa"
题目解析：
字符串+递归 思想，由题目可知将返回值设置为集合ArrayList<String>类型。
step1:首先将字符串转化为字符数组，调用s.toCharArray()方法。
step2：开始进行对字符数组全排列，排列之前写一个Set集合来进行去重。
step3：全排列过程：第一个不动，从不动的开始遍历整个数组，分别都开辟新空间放在首位。
第二个不动，从不动的开始遍历整个数组，分别放在第一位后面。
以此类推。
step4：终止条件： 临时数组中选取了n个元素（start==end），已经形成了一种排列情况了，可以将其加入输出数组中。
作答情况：
结果是这样的，最后找到了问题所在，未按字典序升序排列.
解决方案：添加Collection.sort(result),ArrayList<String> result 里面存的是String的数组，String类型的数据不需要我们重新去写这个比较条件的。
代码：
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);String s = in.nextLine();ArrayList<String> result = new ArrayList<>();//将字符串转化为字符数组char[] ch = s.toCharArray();Allsort(ch, 0, ch.length - 1, result);Collections.sort(result);System.out.print(result);}public static void Allsort(char[] ch, int start, int end,ArrayList<String> result) {Set<Character> set = new HashSet<>();for (int i = start; i <= end; i++) {if (i == start || !set.contains(ch[i])) {set.add(ch[i]);swap(ch, i, start);Allsort(ch, start + 1, end, result);swap(ch, i, start);}}if (start == end) {result.add(String.valueOf(ch)) ;}}public static void swap(char[] ch, int a, int b) {char temp = ch[a];ch[a] = ch[b];ch[b] = temp;}
}收获：
①常见的如一些基本数据类型的包装类（如 Integer、Double 等）以及一些标准库中自带的类都实现了 Comparable 接口并具有默认的比较规则。当被排序的元素所属的类已经实现了 Comparable 接口并定义了合理的自然排序规则时，使用 Collections.sort() 通常就不需要再重写比较条件。
②Arrays.sort()和Collections.sort()区别：
Arrays.sort 针对任意对象，排序的类型就为传入的对象类 。 如：Arrays.sort(a)，这里a为数组，可以是 int/String /类 数组。
Collections.sort 针对集合（List）,排序类型为List对应的类型。
如：Collections.sort (l)，这里l为List 对象，可以为List< Integer>或List< String>或List<类> 。
③ArrayList<ArrayList<Integer>>嵌套集合类时，就要重写比较规则：
ArrayList<ArrayList<Integer>> result = new ArrayList<>();if (num.length <= 0) return result;AllSort(num, 0, num.length - 1, result);Collections.sort(result,new Comparator<ArrayList<Integer>>(){public int compare(ArrayList<Integer> list1,ArrayList<Integer> list2){for(int i=0;i<list1.size();i++){if(list1.get(i)!=list2.get(i)){return list1.get(i)-list2.get(i);}}return 0;}});这篇关于今日刷三题（day13）：变态跳台阶+包含不超过两种字符的最长字串+字符串的排列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
