剑指offer面试题 java解答31-35

面试题31:连续子数组的最大和

public class Test31 { public int FindGreatestSunOfSubArray(int[] data) throws Exception{ if (data==null||data.length==0) { throw new Exception("invalid input"); } int sum=data[0]; int greatSum=Integer.MIN_VALUE; for (int i = 1; i < data.length; i++) { if(sum<=0){ sum=data[i]; }else { sum+=data[i]; } if (sum>greatSum) { greatSum=sum; } } return greatSum; } public static void main(String[] args) throws Exception { int[] data={1,-2,3,10,-4,7,2,-5}; Test31 t=new Test31(); int max=t.FindGreatestSunOfSubArray(data); System.out.println(max); } }

面试题32:从1到n整数中1出现的次数

public class Test32 { public static int NumberOf1Between1AndN(int n) { if (n <= 0) { return 0; } int count = 0; int factor = 1; while(n / factor != 0) { int lowerNum = n - n / factor * factor; int currentNum = (n / factor) % 10; int higherNum = n / (factor * 10); if (currentNum == 0) { // 如果为0,出现1的次数由高位决定 count += higherNum * factor; } else if (currentNum == 1) { // 如果为1,出现1的次数由高位和低位决定 count += higherNum * factor + lowerNum + 1; } else { // 如果大于1,出现1的次数由高位决定 count += (higherNum + 1) * factor; } factor *= 10; } return count; } public static void main(String[] args) { Test32 t=new Test32(); int num=t.NumberOf1Between1AndN(12); System.out.println(num); } }

面试题33:把数组排成最小的数

public class Test33 { //新的比较规则 private static <T> int compare(T a,T tmp){ String str1=""+a+tmp; String str2=""+tmp+a; return str1.compareTo(str2); } private static <T extends Comparable<? super T>> int getMiddle(T[] a,int left,int right) { T tmp=a[left]; while (left<right) { while (left<right&&compare(a[right],tmp)>=0) { right--; } a[left]=a[right]; while (left<right&&compare(a[left],tmp)<=0) { left++; } a[right]=a[left]; a[left]=tmp; } return left; } private static <T extends Comparable<? super T>> void qSort(T[] a,int left,int right) { if (left<right) { int middle=getMiddle(a,left,right); qSort(a, left, middle-1); qSort(a, middle+1,right); } } public static <T extends Comparable<? super T>> void quickSort(T[] a) { if (a.length>0) { qSort(a, 0, a.length-1); } } public void PrintMinNumber(Integer[] numbers){ if (numbers==null||numbers.length<=0) { return; } quickSort(numbers); String result=""; for (int i = 0; i < numbers.length; i++) { result+=numbers[i]; } System.out.println(result); } public static void main(String[] args) { Integer[] a={3,32,321}; Test33 t=new Test33(); t.PrintMinNumber(a); } }

面试题34:丑数

public class Test34 { public int GetUglyNumber_Solution2(int index){ int[] uglyNumbers=new int[index]; uglyNumbers[0]=1; int nextUglyIndex=1; int lastMultiply2=0; int lastMultiply3=0; int lastMultiply5=0; while (nextUglyIndex<index) { int tmp=Math.min(uglyNumbers[lastMultiply2]*2, uglyNumbers[lastMultiply3]*3); int min=Math.min(tmp, uglyNumbers[lastMultiply5]*5); uglyNumbers[nextUglyIndex]=min; while (uglyNumbers[lastMultiply2]*2<=uglyNumbers[nextUglyIndex]) { lastMultiply2++; } while (uglyNumbers[lastMultiply3]*3<=uglyNumbers[nextUglyIndex]) { lastMultiply3++; } while (uglyNumbers[lastMultiply5]*5<=uglyNumbers[nextUglyIndex]) { lastMultiply5++; } nextUglyIndex++; } return uglyNumbers[nextUglyIndex-1]; } public static void main(String[] args) { Test34 t=new Test34(); int result=t.GetUglyNumber_Solution2(1500); System.out.println(result); } }

面试题35:第一个只出现一次的字符

import java.util.HashMap; import java.util.Iterator; public class Test35 { private class Value{ int num=1; public void selfIncrease(){ this.num++; } } public char FirstNotRepeatingChar(String str) throws Exception{ if (str==null) { throw new Exception("invalid input"); } char[] chars=str.toCharArray(); HashMap<Character,Value> map=new HashMap<Character,Value>(chars.length); for (int i = 0; i < chars.length; i++) { char key=chars[i]; if (map.containsKey(key)) { map.get(key).selfIncrease(); }else { map.put(key, new Value()); } } Iterator<Character> iterator=map.keySet().iterator(); while (iterator.hasNext()) { char key=iterator.next(); if (map.get(key).num==1) { return key; } } return (Character) null; } public static void main(String[] args) throws Exception { Test35 t=new Test35(); char c=t.FirstNotRepeatingChar("abaccdeff"); System.out.println(c); } }