今天没啥前言,分治很难,主要难在如何拆分后比较好治理合并,这比二分这些只要拆了就结束要难上一个 level,所以这里属于出入 分治
这种想法的思维,后续会尽可能的锻炼这样的做法;做一道分治,如果能用其他方法代替的时候,一般分治不算是最优解,起码很伤脑子;
分治即分而治之
,所以要分成两部分
分支和 dp 有很深联系,且与二分法也有关联,本质上,二分就是一直只有分没有治的分治,因为二分的结果只需要找到那个较小的相同问题的解,不需要再合并起来;
分析 -- 分治法
参考视频:传送门
var maxSubArray = function (nums) {
const recursion = (l,r) => {
if(l === r) {
return {
totalSum: nums[l],
leftSum: nums[l],
rightSum: nums[l],
maxSum: nums[l]
}
}
const mid = ((r-l)>>2)+l
const left = recursion(l,mid)
const right = recursion(mid+1,r)
return {
totalSum:left.totalSum+right.totalSum, // 区间内值的总和
leftSum:Math.max(left.leftSum,left.totalSum+right.leftSum), // 左边界开始的最大连续子列和
rightSum: Math.max(right.rightSum,right.totalSum+left.rightSum), // 区间哟偶边界结束的最大连续子列和
maxSum:Math.max(left.maxSum,right.maxSum,left.rightSum+right.leftSum)
}
}
return recursion(0,nums.length-1).maxSum
}
分析 -- 贪心
连续子数组
var maxSubArray = function (nums) {
let max = -Infinity;
let sum = 0
for(let i = 0 ;i<nums.length;i++){
sum+=nums[i]
max = Math.max(sum,max)
if(sum<=0){
sum=0
}
}
return max
};
分析 -- 分治
var numTrees = function (n) {
const map = new Map();
const recursion = (n) => {
if (n <= 1) return 1; //没有节点也算一种分配
let temp = 0;
for (let i = 1; i <= n; i++) {
let l, r;
if (map.has(i - 1)) {
l = map.get(i - 1);
} else {
l = recursion(i - 1);
map.set(i - 1, l);
}
if (map.has(n - i)) {
r = map.get(n - i);
} else {
r = recursion(n - i);
map.set(n - i, r);
}
temp += l * r;
}
return temp;
};
return recursion(n);
};
分析 -- dp + 分治
var numTrees = function (n) {
const dp = new Array(n+1)
dp[0] = 1
for(let i =1;i<=n;i++){
dp[i] = 0
for(let j = 1;j<=i;j++){
dp[i] +=dp[j-1]*dp[i-j]
}
}
return dp[n]
}
分析 -- 分治
var majorityElement = function(nums) {
const recursion = (l,r) => {
if(l === r) return nums[l]
const mid = ((r-l)>>1)+l
const lMax = recursion(l,mid)
const rMax = recursion(mid+1,r)
if(lMax === rMax) return lMax // 如果相等,则就是众数了
let lMaxtCount = 0
let rMaxtCount = 0
for(let i=l;i<=r;i++){
if(nums[i] === lMax) lMaxtCount++
if(nums[i] === rMax) rMaxtCount++
}
return lMaxtCount>rMaxtCount ? lMax:rMax
}
return recursion(0,nums.length-1)
}
分析 -- 摩尔投票法
var majorityElement = function(nums) {
let target;
let count = 0
for(let num of nums){
if(count === 0 && target !== num) {
// 如果 count 为 0, 证明上一个 target 已经无效了
target = num
}
if(target === num){
count++
}else{
count--
}
}
return target
};
分析 -- 直接迭代合并链表
var mergeKLists = function (lists) {
if (!lists.length) return new ListNode().next;
return lists.reduce((prev, cur) => mergeTwoList(prev, cur));
};
// 合并两个有序链表
const mergeTwoList = (l1, l2) => {
let temp1 = l1,
temp2 = l2;
let emptyNode = (current = new ListNode());
while (temp1 && temp2) {
if (temp1.val > temp2.val) {
current.next = temp2;
temp2 = temp2.next;
} else {
current.next = temp1;
temp1 = temp1.next;
}
current = current.next;
}
while (temp1) {
current.next = temp1;
current = current.next;
temp1 = temp1.next;
}
while (temp2) {
current.next = temp2;
current = current.next;
temp2 = temp2.next;
}
return emptyNode.next;
};
分析 -- 分治
var mergeKLists = function (lists) {
const len = lists.length;
if (!len) return null
if (len === 1) return lists[0];
if(len === 2) return mergeTwoList(lists[0],lists[1])
const mid = len >> 1;
return mergeTwoList(
mergeKLists(lists.slice(0, mid)),
mergeKLists(lists.slice(mid))
);
};
分析 -- 分治
奇数+偶数 !== 奇数
,所以如果取值的时候左侧都是奇数,右侧都是偶数,那么肯定符合要求这里最需要考虑的就是当取到三个值是同奇偶的时候,如何保证漂亮; 我们知道对于同奇偶的值而言,它是由下一层的漂亮数组递归回来,然后通过 2k+b 的方式转换而来的,也就是说同奇偶的值是符合第二个公式的,进而可以确定他们也是漂亮的 这里其实还隐藏了一个等式,那就是对于 1,2,...,2n 而言,它是由[1,2,...n.map(i=>i2-1) , 1,2,...n.map(i=>i2-1)] 组成的,这样也同时将奇数放在左边,偶数放在了右边,这是治的一部分;
var beautifulArray = function (n) {
const map = new Map();
map.set(1, [1]); // 初始化,也是截止条件
const recursion = (n) => {
if (map.has(n)) return map.get(n); // 递归的终止条件
// 奇数放在左侧 -- 按照数组长度排列好漂亮数组后,然后再通过 2N-1 的方式转成当前层的奇数
const left = recursion((n + 1) >> 1).map((item) => item * 2 - 1);
const right = recursion(n >> 1).map((item) => item * 2);
const ret = [...left, ...right];
map.set(n, ret);
return ret;
};
return recursion(n);
};
分治 -- 快速搜索
var findKthLargest = function (nums, k) {
const select = (left, right) => {
if (left === right) return nums[left];
let mid = ((right - left) >> 1) + left;
// pivotIndex 表示 mid 在整理后数组所在 index
const pivotIndex = dfs(left, right, mid);
if (pivotIndex === nums.length-k) return nums[pivotIndex];
if (pivotIndex > nums.length-k) {
return select(left, pivotIndex - 1);
} else {
return select(pivotIndex + 1, right);
}
};
const dfs = (left, right, pivot) => {
let l = left,
r = right;
const target = nums[pivot];
//先放在最左边,然后[l+1,r] 的位置进行处理,最后在 l,r 的交界处,再把 target 交换回来
// 这里是先将 target 放在了左边,所以要找到的是交界处小于 target 的那个点,也就是 r,然后让 r 和 原始的left 进行值交换即可
[nums[l], nums[pivot]] = [nums[pivot], nums[l]];
while (l <= r) {
while (nums[l] <= target && l <= r) {
l++;
}
while (nums[r] >= target && r >= l) {
r--;
}
if (l > r) break;
[nums[l], nums[r]] = [nums[r], nums[l]];
}
[nums[left], nums[r]] = [nums[r], nums[left]];
return r;
};
return select(0, nums.length - 1);
};
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。