29、兩數相除

思路：不斷相減就是求解的最直接方法，我這樣計算時間復雜度有點高

// 時間復雜度O(count*divisor)
// 空間復雜度O(1)class Solution {int res = 0;public int divide(int dividend, int divisor) {// dividend 是被除數if(dividend == 0)   return 0;if(divisor == 1)    return dividend;if(divisor == -1){if(dividend == Integer.MAX_VALUE)return -dividend;else if(dividend == Integer.MIN_VALUE)return Integer.MAX_VALUE;   // 怕的是特殊情況Integer.MIN_VALUE 除以 -1，那么就超過結果的范圍了}// 不斷相減就是求解的最直接方法int count = 0;long bc = (long)dividend;long c = (long)divisor;if(bc<0 && c<0){while(bc - c <= 0){bc -= c;count++;}return count;}else if(bc<0 && c>0){while(bc + c <= 0){bc += c;count++;}return -count;}else if(bc>0 && c<0){while(bc + c >= 0){bc += c;count++;}return -count;}else{while(bc - c >= 0){bc -= c;count++;}return count;}}
}

?31、下一個排列

// 時間復雜度[ O(nlogn),O(n^2) ) 
// 空間復雜度O(1)class Solution {public void nextPermutation(int[] nums) {/* 總體思路分成4步1、從后向前遍歷，找到第一次出現遞增的兩個數，i-1與i是遞增的2、其次找[i,nums.length-1]位置中最接近且比nums[i]大的元素，并與nums[i]交換3、交換完成后，對于[i,nums.length-1]進行遞增的排序4、輸出答案*/// 分割點就是出現序列變化的地方，因為需要一個更大的序列，所以分割點的位置就是讓大的元素向前移動一位的關鍵位置int split = -1;int n = nums.length;for(int i=n-1; i>0; i--){if(nums[i-1] < nums[i]){// 找到了一次遞減的地方// i-1位置就是分割點int j = i;  int min = i;              while(j<n){// 出現了第一個小于的，說明可以碰到僅次于分割點位置的較大元素了，則交換if(nums[j] > nums[i-1] && nums[j] < nums[min]){min = j;}j++;}int temp = nums[min];nums[min] = nums[i-1];nums[i-1] = temp;split = i-1;break;}}// 如果整個數組都是遞減的，那么整個數組重新排序就可以，split為-1quickSort(nums, split+1, n-1);}public int[] quickSort(int[] a, int i, int j) {//   doQuickSort(a, n, 0, n - 1);doQuickSort(a, j - i + 1, i, j);return a;}// 快速排序public void doQuickSort(int[] a, int n, int start, int end) {if (n > 1) {int current = a[end];int minLen = 0;// 小于區間的長度int i = start;for (; i < end; i++) {if (a[i] < current) {//發現比當前數小的數，擴充小于區間int temp = a[start + minLen];a[start + minLen] = a[i];a[i] = temp;minLen++;}}a[end] = a[start + minLen];a[start + minLen] = current;//當前位置已經確定，排左右序列doQuickSort(a, minLen, start, start + minLen - 1);doQuickSort(a, n - minLen - 1, start + minLen + 1, end);}}
}