分而治之：把复杂的算法问题按一定的”分解”方法分为等价的规模较小的若干部分，然后逐个解决，分别找出个部分的解，把各部分的解组成整个问题的解。
根据算法图解
D&C策略：
（1）找出基线条件，这种条件必须尽可能简单。
（2）不断将问题分解（或者说缩小规模），直到符合基线条件。
从数组中选择一个元素，这个元素被称为 基准值（pivot）
快排的独特之处在于，其速度取决于选择的基准值。
LeetCode题目：
至少有 K 个重复字符的最长子串
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
示例 1：
输入：s = “aaabb”, k = 3
输出：3
解释：最长子串为 “aaa” ，其中 ‘a’ 重复了 3 次。
示例 2：
输入：s = “ababbc”, k = 2
输出：5
解释：最长子串为 “ababb” ，其中 ‘a’ 重复了 2 次， ‘b’ 重复了 3 次。
运用分治法：
class Solution {
public int longestSubstring(String s, int k) {
int n = s.length();
return dfs(s, 0, n - 1, k);
}
public int dfs(String s, int l, int r, int k) {
int[] cnt = new int[26];
for (int i = l; i r; i++) {
cnt[s.charAt(i) - 'a']++;
}
char split = 0;
for (int i = 0; i < 26; i++) {
if (cnt[i] > 0 && cnt[i] < k) {
split = (char) (i + 'a');
break;
}
}
if (split == 0) {
return r - l + 1;
}
int i = l;
int ret = 0;
while (i r) {
while (i r && s.charAt(i) == split) {
i++;
}
if (i > r) {
break;
}
int start = i;
while (i r && s.charAt(i) != split) {
i++;
}
int length = dfs(s, start, i - 1, k);
ret = Math.max(ret, length);
}
return ret;
}
}
优美的排列 II
给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：
假设该列表是 answer = [a1, a2, a3, … , an] ，那么列表 [|a1 – a2|, |a2 – a3|, |a3 – a4|, … , |an-1 – an|] 中应该有且仅有 k 个不同整数。
返回列表 answer 。如果存在多种答案，只需返回其中 任意一种 。
示例 1：
输入：n = 3, k = 1
输出：[1, 2, 3]
解释：[1, 2, 3] 包含 3 个范围在 1-3 的不同整数，并且 [1, 1] 中有且仅有 1 个不同整数：1
示例 2：
输入：n = 3, k = 2
输出：[1, 3, 2]
解释：[1, 3, 2] 包含 3 个范围在 1-3 的不同整数，并且 [2, 1] 中有且仅有 2 个不同整数：1 和 2
构造法：
class Solution {
public int[] constructArray(int n, int k) {
int[] res = new int[n];
for (int i = 0; i < n - k - 1; i++) {
res[i] = i + 1;
}
int j = 0;
int left = n - k;
int right = n;
for (int i = n - k - 1; i < n; i++) {
if (j % 2 == 0) {
res[i] = left;
left++;
} else {
res[i] = right;
right--;
}
j++;
}
return res;
}
}
Original: https://www.cnblogs.com/GeniusWang/p/15644213.html
Author: Genius_Wang
Title: 分而治之-快排
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583140/
转载文章受原作者版权保护。转载请注明原作者出处！