乐趣区

关于后端:473-火柴拼正方形

题目形容

这是 LeetCode 上的 473. 火柴拼正方形 ,难度为 中等

Tag :「剪枝」、「DFS」、「爆搜」、「模拟退火」、「启发式搜寻」

你将失去一个整数数组 matchsticks,其中 $matchsticks[i]$ 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。

你 不能折断 任何一根火柴棒,但你能够把它们连在一起,而且每根火柴棒必须 应用一次。

如果你能使这个正方形,则返回 true,否则返回 false

示例 1:

输出: matchsticks = [1,1,2,2,2]

输入: true

解释: 能拼成一个边长为 2 的正方形,每边两根火柴。

示例 2:

输出: matchsticks = [3,3,3,3,4]

输入: false

解释: 不能用所有火柴拼成一个正方形。

提醒:

  • $1 <= matchsticks.length <= 15$
  • $1 <= matchsticks[i] <= 10^8$

祝大家儿童节高兴,永葆童心,始终凶恶 😊 ~

DFS 剪枝

为了不便,咱们称 matchsticksms

数据范畴为 $n = 15$,奢侈的 DFS 爆搜(搜寻过程中保护一个大小为 $4$ 的数组 cur,数组中的每一位代表正方形一条边长所应用到的火柴总长度,若最终数组中每一位均等于 $t = \frac{\sum_{i = 0}^{n – 1}ms[i]}{4}$,代表存在非法计划)复杂度为 $4^n$,会 TLE

咱们思考如何进行「剪枝」。

首先一个较为显著的剪枝操作是进行「可行性剪枝」:咱们在决策 $ms[idx]$ 时,如果将其累加到某个 $cur[i]$ 之后,会导致 $cur[i] > t$,则阐明必然不会是非法计划,该分支不再往后搜寻。

另外一个较为 trick 的剪枝是通过调整搜寻程序来进行「重复性剪枝」:咱们能够先对 ms 排倒序,进行「从大到小」的爆搜。实质上,咱们是将一些小火柴反复放到某几个桶的搜寻门路(其实对应的是雷同的调配计划),放到了最初解决。

代码:

class Solution {int[] ms;
    int t;
    public boolean makesquare(int[] _ms) {
        ms = _ms;
        int sum = 0;
        for (int i : ms) sum += i;
        t = sum / 4;
        if (t * 4 != sum) return false;
        Arrays.sort(ms);
        return dfs(ms.length - 1, new int[4]);
    }
    boolean dfs(int idx, int[] cur) {if (idx == -1) {
            boolean ok = true;
            for (int i : cur) {if (i != t) ok = false;
            }
            return ok;
        }
        for (int i = 0; i < 4; i++) {int u = ms[idx];
            if (cur[i] + u > t) continue;
            cur[i] += u;
            if (dfs(idx - 1, cur)) return true;
            cur[i] -= u;
        }
        return false;
    }
}
  • 工夫复杂度:$O(4^n)$
  • 空间复杂度:排序的复杂度为 $O(\log{n})$,疏忽递归带来的额定空间开销,复杂度为 $O(\log{n})$

模拟退火

事实上,这道题还能应用「模拟退火」进行求解。

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

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

单次迭代的根本流程:

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

值得一提的是,这道题造数据的人非常有程度,在最初一个样例中放了个卡 SA 的数据:

[403,636,824,973,815,318,881,506,863,21,834,211,316,772,803]

但我不晓得为什么 LC 的提交后果会这么奇怪,已通过 184/183 样例?是总样例数哪个中央更新漏了,还是缓存没刷新:

这个数据点优良在于起始排序能够导致咱们固定的 calc 逻辑最终落入部分最优。针对这种状况,也很好解决,只须要在执行 SA 之前,先对原数组进行一次随机化打乱即可。

代码(2022/06/01 可通过):

class Solution {int ms[];
    int n, k;
    Random random = new Random(20220601);
    boolean ans = false;
    double hi = 1e4, lo = 1e-4, fa = 0.98; 
    int N = 400;
    int calc() {
        int diff = 0;
        for (int i = 0, j = 0; i < 4; i++) {
            int cnt = 0;
            while (j < n && cnt < k) cnt += ms[j++];
            diff += Math.abs(cnt - k);
        }
        if (diff == 0) ans = true;
        return diff;
    }
    void sa() {for (double t = hi; t > lo && !ans; t *= fa) {int a = random.nextInt(n), b = random.nextInt(n);
            int prev = calc();
            swap(ms, a, b);
            int cur = calc();
            int diff = prev - cur;
            if (Math.log(diff / t) > random.nextDouble()) swap(ms, a, b);
        }
    }
    public boolean makesquare(int[] _ms) {
        ms = _ms;
        n = ms.length;
        int sum = 0;
        for (int i : ms) sum += i;
        k = sum / 4;
        if (k * 4 != sum) return false;
        shuffle(ms);
        while (N-- > 0) sa();
        return ans;
    }
    void shuffle(int[] arr) {
        int n = arr.length;
        for (int i = n; i > 0; i--) {int idx = random.nextInt(i);
            swap(arr, idx, i - 1);
        }
    }
    void swap(int[] arr, int i, int j) {int c = arr[i];
        arr[i] = arr[j];
        arr[j] = c;
    }
}

我猜你问

Q0. 模拟退火有何危险?
随机算法,会面临 WATLE 危险。

Q1. 模拟退火中的参数如何敲定的?
依据教训猜的,而后提交。依据后果是 WA 还是 TLE 来决定之后的调参方向。如果是 WA 阐明局部数据落到了「部分最优」或者尚未达到「全局最优」。

Q2. 参数如何调整?
如果是 WA 了,个别我是优先调大 fa 参数,使降温变慢,来变相减少迭代次数;如果是 TLE 了,个别是优先调小 fa 参数,使降温变快,减小迭代次数。总迭代参数 N 也是同理。

能够简略了解调大 fa 代表将「大步」改为「baby step」,避免越过全局最优,同时减少总执行步数。

Q3. 对于「模拟退火」正确性?

随机种子不变,测试数据不变,迭代参数不变,那么退火的过程就是恒定的,必然都能找到这些测试样例的「全局最优」。

最初

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

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

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

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

本文由 mdnice 多平台公布

退出移动版