关于后端:698-划分为k个相等的子集-搜索-剪枝模拟退火

44次阅读

共计 5104 个字符,预计需要花费 13 分钟才能阅读完成。

题目形容

这是 LeetCode 上的 698. 划分为 k 个相等的子集 ,难度为 中等

Tag :「搜寻」、「爆搜」、「剪枝」、「模拟退火」、「启发式搜寻」、「回溯算法」、「贪婪」

给定一个整数数组  nums 和一个正整数 k,找出是否有可能把这个数组分成 k 个非空子集,其总和都相等。

示例 1:

输出:nums = [4, 3, 2, 3, 5, 2, 1], k = 4

输入:True

阐明:有可能将其分成 4 个子集(5),(1,4),(2,3),(2,3)等于总和。

示例 2:

输出: nums = [1,2,3,4], k = 3

输入: false

提醒:

  • $1 <= k <= len(nums) <= 16$
  • $0 < nums[i] < 10000$
  • 每个元素的频率在 $[1,4]$ 范畴内

搜寻 + 剪枝(贪婪策略)

将 $n$ 个数均分成 $k$ 份,且 $n$ 与 $k$ 数据范畴为 $16$,容易想到搜寻剪枝。

先对一些显然的无解状况进行剖析:记 $tot = \sum_{i = 0}^{n – 1}nums[i]$,若 $tot$ 不为 $k$ 的倍数,必然是无奈实现均分,间接返回 false(可行性剪枝)。同时可知单个汇合的总和为 $t = \frac{tot}{k}$。

设计搜寻函数为 boolean dfs(int idx, int cur, int cnt, boolean[] vis),各项参数含意如下:

  • cur 为以后汇合的元素和(初始值为 $0$);
  • cnt 是已凑成多少个总和为 $t$ 的汇合(初始值为 $0$,当 $cnt = k$ 时,咱们搜寻到了非法计划,返回 true,否则对 cnt 进行加一操作,并将 cur 置零,搜寻下个汇合);
  • vis 用于记录哪些 $nums[i]$ 已被应用;
  • idx 是搜寻要害,其含意为搜寻空间的宰割点。即对于以后正在搜寻的汇合,咱们不会每次都扫描整个 nums 来找增加到该汇合的下一个元素,而是可能明确下一个元素必然在 $idx$ 的右边或左边。
    具体的,咱们晓得若最终存在非法计划,必然每个 $nums[i]$ 都均棣属于某个具体汇合。咱们思考搜寻某个汇合的组成元素时,依照「从大到小」的形式进行搜寻(起始先对 nums 进行排序),这样可能 确保若上一个被退出该汇合的元素为 $nums[i]$,则下一个被增加的元素 $nums[j]$ 必然位于 $nums[i]$ 的右边,即从下标 $i – 1$ 开始往前搜寻(程序性剪枝)
    同时,也正是咱们依照「从大到小」的形式进行搜寻,确保了以后汇合的搜寻,毋庸对已搜寻到的汇合进行调整
    也就是说咱们搜寻的第一个汇合是所有 $nums[i]$ 中的最大值所在的那个汇合;二次搜寻是所有 $nums[i]$ 减去第一个汇合后残余元素中最大值所在的汇合 …
    这疏导咱们,如果以后汇合如果连第一个值都无奈搜到(即残余元素的最大值不能作为以后汇合的元素),必然无解(可行性剪枝)

这样的「搜寻 + 剪枝」的解法实质是利用了「贪婪」来做策略:咱们每个回合的搜寻总是在搜寻「残余未应用元素的最大值」所在的那个汇合,并且依照「优先应用大数值」的准则来结构。

可证实该做法的正确性:因为搜寻的是「残余未应用元素的最大值」所在的那个汇合,因而残余未应用元素必然在汇合内,若被搜寻到的其余元素参加汇合结构导致有解变无解(即须要将其余元素进行替换能力确保有解),依据咱们「从大到小」搜寻下一个元素准则,替换过程必然不会使汇合元素个数变少,即总是会拿不少于 $K$ 个的元素来替换以后汇合的 $K$ 个元素(总和雷同),从而可推断该替换并非必须。

Java 代码:

class Solution {int[] nums;
    int n, t, k;
    public boolean canPartitionKSubsets(int[] _nums, int _k) {
        nums = _nums; k = _k;
        int tot = 0;
        for (int x : nums) tot += x;
        if (tot % k != 0) return false; // 可行性剪枝
        Arrays.sort(nums);
        n = nums.length; t = tot / k;
        return dfs(n - 1, 0, 0, new boolean[n]);
    }
    boolean dfs(int idx, int cur, int cnt, boolean[] vis) {if (cnt == k) return true;
        if (cur == t) return dfs(n - 1, 0, cnt + 1, vis);
        for (int i = idx; i >= 0; i--) {  // 程序性剪枝
            if (vis[i] || cur + nums[i] > t) continue;  // 可行性剪枝
            vis[i] = true;
            if (dfs(i - 1, cur + nums[i], cnt, vis)) return true;
            vis[i] = false;
            if (cur == 0) return false; // 可行性剪枝
        }
        return false;
    }
}

TypeScript 代码:

let nums: number[];
let n: number, t: number, k: number;
function canPartitionKSubsets(_nums: number[], _k: number): boolean {
    nums = _nums; k = _k;
    let tot = 0
    for (let x of nums) tot += x
    if (tot % k != 0) return false
    nums.sort((a,b)=>a-b)
    n = nums.length; t = tot / k
    return dfs(n - 1, 0, 0, new Array<boolean>(n).fill(false))
};
function dfs(idx: number, cur: number, cnt: number, vis: boolean[]): boolean {if (cnt == k) return true
    if (cur == t) return dfs(n - 1, 0, cnt + 1, vis)
    for (let i = idx; i >= 0; i--) {if (vis[i] || cur + nums[i] > t) continue
        vis[i] = true
        if (dfs(idx - 1, cur + nums[i], cnt, vis)) return true
        vis[i] = false
        if (cur == 0) return false
    }
    return false
}
  • 工夫复杂度:爆搜剪枝不剖析时空复杂度
  • 空间复杂度:爆搜剪枝不剖析时空复杂度

模拟退火

数据范畴为 $16$ 天然也是很好的调参使用题。

因为将 $n$ 个数划分为 $k$ 份,等效于用 $n$ 个数结构出一个「特定排列」,而后对「特定排列」进行固定模式的结构逻辑,就能实现「答案」与「指标排列」的对应关系。

基于此,咱们能够应用「模拟退火」进行求解。

单次迭代的根本流程:

  1. 随机抉择两个下标,计算「替换下标元素前对应序列的得分」&「替换下标元素后对应序列的得分」
  2. 如果温度降落(替换后的序列更优),进入下一次迭代
  3. 如果温度回升(替换前的序列更优),以「肯定的概率」复原现场(再替换回来)

咱们能够制订如下规定来掂量以后排列与非法排列的差别水平:将以后的 nums 从前往后划分成总和不超过 $t$ 的 $k$ 份,并将 $k$ 份与 $t$ 的差值之和,作为对以后排列的差别水平评级 diff,当呈现 diff = 0 阐明找到了非法排列,可完结搜寻。

该计算规定可确保排列变动的间断性能无效体现在 diff 数值上。

Java 代码(2022/09/20 可通过):

class Solution {int[] nums;
    int n, tval, k;
    Random random = new Random(20220920);
    double hi = 1e9, lo = 1e-4, fa = 0.95;
    int N = 600;
    boolean ans;
    int calc() {
        int diff = tval * k;
        for (int i = 0, j = 0; i < n && j < k; j++) {
            int cur = 0;
            while (i < n && cur + nums[i] <= tval) cur += nums[i++];
            diff -= cur;
        }
        if (diff == 0) ans = true;
        return diff;
    }
    void sa() {shuffle(nums);
        for (double t = hi; t > lo && !ans; t *= fa) {int a = random.nextInt(n), b = random.nextInt(n);
            if (a == b) continue;
            int prev = calc();
            swap(nums, a, b);
            int cur = calc();
            int diff = cur - prev;
            if (Math.log(diff / t) > random.nextDouble()) swap(nums, a, b);
        }
    }
    public boolean canPartitionKSubsets(int[] _nums, int _k) {
        nums = _nums; k = _k;
        int tot = 0;
        for (int x : nums) tot += x;
        if (tot % k != 0) return false;
        n = nums.length; tval = tot / k;
        while (!ans && N-- > 0) sa();
        return ans;
    }
    void shuffle(int[] nums) {for (int i = n; i > 0; i--) swap(nums, random.nextInt(i), i - 1);
    }
    void swap(int[] nums, int a, int b) {int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
}

TypeScript 代码(2022/09/20 可通过):

let nums: number[];
let n: number, tval: number, k: number
let ans: boolean
let hi: number, lo: number, fa: number, N: number
function getRandom(max: number): number {return Math.floor(Math.random() * (max + 1))
}
function calc(): number {
    let diff = tval * k
    for (let i = 0, j = 0; i < n && j < k; j++) {
        let cur = 0
        while (i < n && cur + nums[i] <= tval) cur += nums[i++]
        diff -= cur
    }
    if (diff == 0) ans = true
    return diff
}
function sa(): void {shuffle(nums)
    for (let t = hi; t > lo && !ans; t *= fa) {const a = getRandom(n - 1), b = getRandom(n - 1)
        if (a == b) continue
        const prev = calc()
        swap(nums, a, b)
        const cur = calc()
        const diff = cur - prev
        if (Math.log(diff / t) > Math.random()) swap(nums, a, b)
    }
}
function canPartitionKSubsets(_nums: number[], _k: number): boolean {
    nums = _nums; k = _k
    let tot = 0
    for (let x of nums) tot += x
    if (tot % k != 0) return false
    n = nums.length; tval = tot / k
    hi = 1e9; lo = 1e-4; fa = 0.98; N = 700
    ans = false
    while (!ans && N-- > 0) sa()
    return ans
}
function shuffle(nums: number[]): void {for (let i = n; i > 0; i--) swap(nums, getRandom(i), i - 1)
}
function swap(nums: number[], a: number, b: number): void {const c = nums[a]
    nums[a] = nums[b]
    nums[b] = c
}
  • 工夫复杂度:启发式搜寻不剖析时空复杂度
  • 空间复杂度:启发式搜寻不剖析时空复杂度

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.698 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。

在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。

在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

正文完
 0