1、有0,1,2,3...n n+1个序列，有n个数，找出没在序列中出现的数。
如 输入3 3 0 1 输出2 第一个数表示有n个数，301表示要查的数
思路：【1】将这个数组排序，判断a[i]=i是否成立，不成立的即输出i
【2】在数组存储的时候，a[sc.nextInt()]=1，然后在0-n判断a[i]是否为1 不为1的即为没出现的。
1 package zhenti; 2 /** 3 * @author zlz099 4 * @date 创建时间：4月10日 下午5:19:04 5 */ 6 import java.util.*; 7 public class Main { 8 9public static void main(String[] args) {10 // TODO Auto-generated method stub11 // Scanner scanner = new Scanner(System.in);12 // int n = scanner.nextInt();13 // int[] a = new int[n];14 // int[] b = new int[n];15 // ArrayList<Integer> arrayList = new ArrayList<>();16 // TreeSet<Integer> t = new TreeSet<>();17 // for(int i = 0; i < n;i++){18 // a[i] = scanner.nextInt();19 // t.add(a[i]);20 // }21 // Iterator<Integer> iterator = t.iterator();22 // while(iterator.hasNext()){23 // arrayList.add(iterator.next());24 // }25 // for(int i = 0; i < arrayList.size();i++){26 // //System.out.println(arrayList.get(i));27 // if(arrayList.get(i)!=i){28 //System.out.println(i);29 // }30 // }31 // }32 Scanner sc = new Scanner(System.in);33 int n = sc.nextInt();34 int[] a = new int[n+1];35 for(int i = 0; i < n; i++){36 a[sc.nextInt()]=1;37 }38 for(int i = 0; i < n; i++){39 if(a[i]!=1){40 System.out.println(i);41 }42 }43}44 }
2、小猫跳数轴，有三种走法，
（1）正向走一步记为n+1
（2）负向走一步记为n-1
（3）跳当前的2倍记为n*2
输入x,输出跳到x需要的最小步数
思路：可用动态规划，跟跳台阶是一个思路
边界判断，0为0步 1为1步
n是偶数，则为f(n/2)+1
n为奇数，则为f(n-1)+1
n为负数，则为f(Math.abs(n))
1 package zhenti; 2 /** 3 * @author zlz099 4 * @date 创建时间：4月10日 下午7:47:06 5 */ 6 import java.util.*; 7 8 import edu.princeton.cs.algs4.In; 9 public class Jump {10 11public static void main(String[] args) {12 // TODO Auto-generated method stub13 Scanner scanner = new Scanner(System.in);14 int n = scanner.nextInt();15 System.out.println(jump(n));16}17public static int jump(int n){18 if(n == 0) return 0;19 else if(n == 1 || n == -1) return 1;20 if(n<0){return jump(Math.abs(n));}21 if(n%2==0){return jump(n/2)+1;}22 else {23 return jump(n-1)+1;24 } 25}26 }
3、剑指offer上的原题，丑数
质因子为2,3,5的数
第一种方法时间复杂度超时了，过了80%
package zhenti;/** * @author zlz099* @date 创建时间：4月10日 下午8:02:02 */import java.util.*;public class Choushu {public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);int n = sc.nextInt();System.out.println(choushu(n));}// public static boolean choushu(int n){// while(n%2==0)// n/=2;// while(n%3==0)// n/=3;// while(n%5==0)// n/=5;// return(n == 1)? true:false;// }// public static int getChoushu(int index){// if(index<0){return 0;}// int num = 0;// int uglyfound = 0;// while(uglyfound<index){// num++;// if(choushu(num)){//++uglyfound;// }// }// return num;// }public static int choushu(int index){if(index<0){return 0;}int[] uglyarray = new int[index];uglyarray[0] = 1;int m2 = 0;int m3 = 0;int m5 = 0;for(int i = 1; i < index;i++){int min = min(uglyarray[m2]*2,uglyarray[m3]*3,uglyarray[m5]*5);uglyarray[i] = min;while(uglyarray[m2]*2 == uglyarray[i])m2++;while(uglyarray[m3]*3 == uglyarray[i])m3++;while(uglyarray[m5]*5 == uglyarray[i])m5++;}return uglyarray[index-1];}public static int min(int n1,int n2,int n3){int min = (n1<n2)?n1:n2;return min<n3?min:n3;}}
