《剑指Offer》java 2.4 算法和数据操作

2019-11-06 09:04:30

字体：大中小

来源：转载

供稿：网友

No.8 旋转数组的最小数字翻转的数组，总有一边是有序的 eg[2,3,4,5,6,1]；采用二分查找，注意{1,0,1,1,1,1,1}，则不能缩小问题规模，需要依次遍历

//特例{1,0,1,1,1,1,1} public int minOrder(int[] array, int left, int right){ int min = array[left]; for(int i = left + 1; i <= right; i++){ min = Math.min(min, array[i]); } return min; } public int minNumberInRotateArray(int [] array) { int len = array.length; if(len == 0) return 0; int low = 0, high = len - 1, mid; //结束条件：若该段数组是有序的，则返回第一个值 while(array[low] >= array[high]){ //防止大数相加溢出 mid = low + (high - low) / 2; if(mid == low) return Math.min(array[low], array[high]); if(array[low] == array[mid] && array[mid] == array[high]) return minOrder(array, low, high); if(array[low] > array[mid]){ high = mid; }else{ low = mid; } } return array[low]; }

No.9 斐波那契数列思路：递归（简洁，耗时）、循环（高效）

public int Fibonacci(int n){ if(n == 0 || n == 1) return n; return Fibonacci(n - 1) + Fibonacci(n - 2); } public int Fibonacci(int n){ if(n == 0 || n == 1) return n; int low = 0, high = 1, sum = 1; for(int i = 2; i < n; i++){ sum = low + high; low = high; high = sum; } return sum; }

No.10 跳台阶（类似于）

这里写代码片

上一篇：java之解析DNS的SRV记录

下一篇：JAVA经典算法