用java编写剑指offer中的面试题.zip

### 面试题39 > #### 题目：数组中出现次数超过一半的数字 > #### 题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 > #### 思路：遍历数组，下一个数字与保存的数字相同则次数加一，否则减一。当最后次数为1时，则就是我们要找的结果 ```java public int MoreThanHalfNum(int[] numbers) { if(numbers == null) return -1; int result = numbers[0]; int times = 1; for(int i=1; i<numbers.length; i++) { if(times == 0) { result = numbers[i]; times = 1; } else if(numbers[i] == result) times++; else { times--; } } //验证出现次数最多的数是不是出现次数超过数组长度的一半 int sum = 0; for(int j=0; j<numbers.length; j++) { if(numbers[j] == result) sum++; } if(sum*2 > numbers.length) return result; else return -1; } ``` ### 面试题40 > #### 题目：最小的k个数 > #### 题目描述：输入n个整数，找出其中最小的k个数。 > #### 思路1：如果基于数组的k个数字来调整，则使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整后，位于数组中左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）。时间复杂度为n ```java private static int Partition(int[] arr, int start, int end) { int key = arr[start]; while(start < end) { while(arr[end] >= key && end > start) end--; arr[start] = arr[end]; while(arr[start] <= key && end > start) start++; arr[end] = arr[start]; } arr[start] = key; return start; } public static void GetLeastNumbers(int[] input, int k) { int len = input.length; if(input==null || k>len || len<=0 || k<=0) return; int start = 0; int end = len-1; int index = Partition(input, start, end); while(index != k-1) { if(index > k-1) { end = index-1; index = Partition(input, start, end); } else { start = index+1; index = Partition(input, start, end); } } } ``` > #### 思路2：先将前K个数放入数组，进行堆排序，若之后的数比它还小，将数组中的最大的数与之后比它小的数进行调整。时间复杂度nlogk，适合处理海量数据 ```java public ArrayList<Integer> GetLeastNumbers(int[] input, int k) { ArrayList<Integer> list = new ArrayList<Integer>(); if(input == null || k<=0 || k>input.length) return null; int[] kArray = Arrays.copyOfRange(input, 0, k); //创建大根堆 buildHeap(kArray); for(int i=k; i<input.length; i++) { if(input[i] < kArray[0]) { kArray[0] = input[i]; maxHeap(kArray, 0); } } for(int i=kArray.length-1; i>=0; i--) { list.add(kArray[i]); } return list; } public void buildHeap(int[] input) { for(int i=input.length/2-1; i>=0; i--) maxHeap(input, i); } public void maxHeap(int[] input, int i) { int left = 2*i+1; int right = left+1; int max = 0; if(left < input.length && input[left] > input[i]) max = left; else { max = i; } if(right < input.length && input[right] > input[max]) max = right; if(max != i) { int temp = input[i]; input[i] = input[max]; input[max] = temp; maxHeap(input, max); } } ``` ### 面试题41 > #### 题目：数据流中的中位数 > #### 题目描述：如何得到一个数据流中的中位数？如果从数据流中独处奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。 > #### 思路：创建优先级队列维护大顶堆和小顶堆两个堆，并且小顶堆的值都大于大顶堆的值，2个堆个数的差值小于等于1，所以当插入个数为奇数时：大顶堆个数就比小顶堆多1，中位数就是大顶堆堆头；当插入个数为偶数时，使大顶堆个数跟小顶堆个数一样，中位数就是 2个堆堆头平均数。也可使用集合类的排序方法。 ```java int count = 0; PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(16, new Comparator<Integer>() { public int compare(Integer o1, Integer o2){ return o2.compareTo(o1); } }); public void Insert(Integer num) { count++; //当数据的数目为奇数时，进入大根堆 if((count&1) == 1) { minHeap.offer(num); maxHeap.offer(minHeap.poll()); } else { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); } } public Double GetMedian() { if(count == 0) return null; if((count&1)==1) return Double.valueOf(maxHeap.peek()); else { return Double.valueOf((minHeap.peek()+maxHeap.peek()))/2; } } ``` ### 面试题42 > #### 题目：连续子数组的最大和 > #### 题目描述：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为n。 > #### 思路：如果加到一个负数，看是否加负数后的下一个的和比没有加负数前的和大，如果更大，则继续加。 ```java public int FindGreatestSumOfSubArray(int[] pData) { if(pData==null || pData.length<=0) return -9999; int cur = pData[0]; int greate = pData[0]; for(int i=1; i<pData.length; i++) { if(cur < 0) cur = pData[i]; else { cur += pData[i]; } if(cur > greate) greate = cur; } return greate; } ``` ### 面试题43 > #### 题目：1~n整数中1出现的次数 > #### 题目描述：输入一个整数n，求1到n这n个整数的十进制表示中1出现的次数 > #### 思路：考虑将n的十进制的每一位单独拿出讨论，每一位的值记为weight。从1到n，每增加1，weight就会加1，当weight加到9时，再加1又会回到0重新开始。 ```java public int NumberOf1Between1AndN(int n) { if(n <= 0) return 0; int count = 0; int base = 1; int round = n; while(round > 0) { int weight = round % 10; round /= 10; count += round * base; if(weight == 1) count += (n%base)+1; else if(weight > 1) count += base; base *= 10; } return count; } ``` ### 面试题44 > #### 题目：数字序列中某一位的数字 > #### 题目描述：数字以0123456789101112131415...的格式序列化到一个字符序列中。在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任何第n位对应的数字。 > #### 思路：序列的前10位是0到9这10个只有一位数的数字。接下来180位数字是90个10到99的两位数。接下来的2700位是900个100~999的三位数... ```java int digitAtIndex(int index) { if(index < 0) return -1; int digits = 1; while(true) { int numbers = countOfInteger(digits); if(index < numbers*digits) return digitAtIndex(index, digits); } } //例如输入2，则返回两位数（10~99）的个数90 int countOfInteger(int digits) { if(digits == 1) return 10; int count = (int)(Math.pow(10, digits-1)); return 9*count; } //当知道要找的那一位数字位于某m位数之中后，就可以使用如下函数找出那一位数字 int digitAtIndex(int index, int digits) { int number = beginNumber(digits) + index / digits; int indexFromRight = digits - index % digits; for(int i=1; i<indexFromRight; i++) { number /= 10; } return number%10; } int beginNumber(int digits) { if(digits == 1) return 0; return (int)(Math.pow(10, digits-1)); } ``` ### 面试题45 > #### 题目：把数组排成最小的数 > #### 题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如，输入数组{3,32,321}，则打印出这3个数字能拍成的最小数字321323 > #### 思路：先将整型数组