分治
概述
分治思想
- 将大问题划分为两个到多个子问题；
- 子问题可以继续拆分为跟小的子问题，直到能够简单求解；
- 如有必要，将子问题的解进行合并，得到原始问题的解；
经典分而治之的例子
- 二分查找
- 快速排序
- 归并排序
- 合并k个排序链表-Leetcode23
二分查找
public static int recursion(int[] nums, int target, int i, int j) {if (i > j) {return -1;}int m = (i + j) >>> 1;if (target < nums[m]) {return recursion(nums, target, i, m - 1);} else if (target > nums[m]) {return recursion(nums, target, m + 1, j);} else {return m;}
}
快速排序
归并排序
合并K个有序链表
快速选择算法
public class QuickSelect{public int quick(int nums[], int left, int right, int i) {int p = partition(nums, left, right);if (p == i) {return nums[i];}if (i < p) {return partition(nums, left, p - 1);} else {return partition(nums, p + 1, right);}}// 双边快排public int partition(int[] nums, int left, int right) {// int pv = nums[left]; // 左侧第一个元素作为基准点int pv = ThreadLocalRandom.current().nextInt(right - left + 1) + left; // 随机算法选择基准点；int i = left; // i找比基准点大的元素int j = right; // j找比基准点小的元素while(i < j) {while (i < j && nums[j] > pv) {j--;}while (i < j && nums[i] <= pv) {i++;}swap(nums, i, j);}swap(nums, i, left);return i;}public void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}
Leetcode215
数据组第K大的元素
public class Leetcode215{public int findKthLargest(int[] nums, int k) {// 使用快速选择算法上的函数进行调用return QuickSelect.quick(nums, 0, nums.length - 1, nums.length - k);}}
数据中位数
public class FindMedian{public static double findMedian(int[] nums) {if (nums.length % 2 == 1) {// 奇数return QuickSelect.quick(nums, 0, nums.length - 1, nums.length / 2);} else {// 偶数return (QuickSelect.quick(nums, 0, nums.length - 1, nums.length / 2) +QuickSelect.quick(nums, 0, nums.length - 1, nums.length / 2 - 1)) / 2.0;}}}
快速幂
public class QuickPowLeetcode50{public double myPow(double x, int n) {long m = n > 0 ? n : -n; // 若n为最小int数，需要longdouble y = myPowPositive(x, m);return n > 0 ? y : 1 / y;}public double myPowPositive(double x, int n) {if (n == 0) {return 1.0;}if (n == 1) {return x;}double y = myPow(x, n / 2);if ((n & 1) == 0) {return y * y;} else {return x * y * y;} }
}
Leetcode69
public class Leetcode69{public static int mySqrt(int n) {int i = 0;int j = n;int p = 0;while (i <= j) {int m = (i + j) >>> 1;if (m < n / m) {i = m + 1;p = m;} else if (m > n / m) {j = m - 1;} else {return m;}}return p;}
}
public class Leetcode69{public static int mySqrt(int n) {int i = 0;int j = n;int p = 0;while (i <= j) {int m = (i + j) >>> 1;if (m <= n / m) {i = m + 1;p = m;} else if (m > n / m) {j = m - 1;} }return p;}
}
Leetcode395
public class Leetcode395{public int longestSubstring(String s, int k) {if (s.length() < k) {retu}int[] counts = new int[26];char chars = s.toCharArray();for(int ch : chars) {counts[ch - 'a']++;}for(int i = 0; i < chars.length; i++) {int count = counts[chars[i] - 'a'];if (count > 0 && count < k) {int j = i + 1;while (j < chars.length && counts[chars[j] - 'a'] < k) {j++;}return Math.max(longestSubstring(s.substring(0, i), k), longestSubstring(s.substring(j), k))}}return s.length();}
}