字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

解题思路

参考的别人的思路完成的(http://www.cnblogs.com/pmars/archive/2013/12/04/3458289.html) //这一段就是回溯法，这里以"abc"为例

//递归的思想与栈的入栈和出栈是一样的,某一个状态遇到return结束了之后，会回到被调用的地方继续执行 //1.第一次进到这里是ch=['a','b','c'],list=[],i=0，我称为 状态A ，即初始状态 //那么j=0，swap(ch,0,0)，就是['a','b','c']，进入递归，自己调自己，只是i为1，交换(0,0)位置之后的状态我称为 状态B //i不等于2，来到这里，j=1，执行第一个swap(ch,1,1)，这个状态我称为 状态C1 ,再进入fun函数，此时标记为T1，i为2，那么这时就进入上一个if，将"abc"放进list中 /-------》此时结果集为["abc"] //2.执行完list.add之后，遇到return，回退到T1处，接下来执行第二个swap(ch,1,1)，状态C1又恢复为状态B //恢复完之后，继续执行for循环，此时j=2,那么swap(ch,1,2),得到"acb"，这个状态我称为C2,然后执行fun，此时标记为T2,发现i+1=2,所以也被添加进结果集，此时return回退到T2处往下执行 /-------》此时结果集为["abc","acb"] //然后执行第二个swap(ch,1,2)，状态C2回归状态B,然后状态B的for循环退出回到状态A // a|b|c(状态A) // | // |swap(0,0) // | // a|b|c(状态B) // / \ // swap(1,1)/ \swap(1,2) (状态C1和状态C2) // / \ // a|b|c a|c|b //3.回到状态A之后，继续for循环，j=1,即swap(ch,0,1)，即"bac",这个状态可以再次叫做状态A,下面的步骤同上 /-------》此时结果集为["abc","acb","bac","bca"] // a|b|c(状态A) // | // |swap(0,1) // | // b|a|c(状态B) // / \ // swap(1,1)/ \swap(1,2) (状态C1和状态C2) // / \ // b|a|c b|c|a //4.再继续for循环，j=2,即swap(ch,0,2)，即"cab",这个状态可以再次叫做状态A，下面的步骤同上 /-------》此时结果集为["abc","acb","bac","bca","cab","cba"] // a|b|c(状态A) // | // |swap(0,2) // | // c|b|a(状态B) // / \ // swap(1,1)/ \swap(1,2) (状态C1和状态C2) // / \ // c|b|a c|a|b //5.最后退出for循环，结束。

代码

import java.util.ArrayList; import java.util.Collections; import java.util.List; /** * 剑指offer一刷：字符串的排列 * * @author User * @create 2019-05-23-20:49 */ public class jzo27 { public ArrayList<String> Permutation(String str) { List<String> resultList = new ArrayList<>(); if(str.length() == 0) return (ArrayList)resultList; //递归的初始值为（str数组，空的list，初始下标0） fun(str.toCharArray(),resultList,0); Collections.sort(resultList); return (ArrayList)resultList; } private void fun(char[] ch,List<String> list,int i){ //这是递归的终止条件，就是i下标已经移到char数组的末尾的时候，考虑添加这一组字符串进入结果集中 if(i == ch.length-1){ //判断一下是否重复 if(!list.contains(new String(ch))){ list.add(new String(ch)); return; } }else{ for(int j=i;j<ch.length;j++){ swap(ch,i,j); fun(ch,list,i+1); swap(ch,i,j); } } } //交换数组的两个下标的元素 private void swap(char[] str, int i, int j) { if (i != j) { char t = str[i]; str[i] = str[j]; str[j] = t; } } public static void main(String[] args){ String a="123"; jzo27 so=new jzo27(); System.out.println(so.Permutation(a)); } }

数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解题思路

一次再删除在数组中删除不同的数，不停的删除，直到剩下一种，如果这个数出现的次数大于一半，这个数最后一定会剩下来。

代码

/** * 剑指offer一刷：数组中出现次数超过一半的数字 * * @author User * @create 2019-05-23-21:57 */ public class jzo28 { public int MoreThanHalfNum_Solution(int [] array) { int cand=0; int times=0; for(int i=0;i<array.length;i++){ //没有候选 if(times==0){ cand=array[i]; times++; }else if(array[i]==cand){ //当前array[i]与cand相同 times++; //times++ }else { times--; //times-- } } times=0; for (int i=0;i<array.length;i++){ if (array[i]==cand){ times++; } } int num=0; if (times>array.length/2){ num=cand; } return num; } public static void main(String[] args){ int[] arr={1,2,3,2,2,5,4,2}; jzo28 so=new jzo28(); System.out.println(so.MoreThanHalfNum_Solution(arr)); } }