一题三解 : 「剪枝 DFS」&「二进制枚举」&「模拟退火」

简介: 一题三解 : 「剪枝 DFS」&「二进制枚举」&「模拟退火」

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 1239. 串联字符串的最大长度 ,难度为 中等


Tag : 「DFS」、「二进制枚举」、「模拟退火」


给定一个字符串数组 arr,字符串 s 是将 arr 某一子序列字符串连接所得的字符串,如果 s 中的每一个字符都只出现过一次,那么它就是一个可行解。


请返回所有可行解 s 中最长长度。


示例 1:


输入:arr = ["un","iq","ue"]
输出:4
解释:所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique",最大长度为 4。
复制代码


示例 2:


输入:arr = ["cha","r","act","ers"]
输出:6
解释:可能的解答有 "chaers" 和 "acters"。
复制代码


示例 3:


输入:arr = ["abcdefghijklmnopqrstuvwxyz"]
输出:26
复制代码


提示:


  • 1 <= arr.length <= 16
  • 1 <= arr[i].length <= 26
  • arr[i] 中只含有小写英文字母


基本分析



根据题意,可以将本题看做一类特殊的「数独问题」:在给定的 arr 字符数组中选择,尽可能多的覆盖一个 1 * 26126 的矩阵。


对于此类「精确覆盖」问题,换个角度也可以看做「组合问题」。


通常有几种做法:DFS、剪枝 DFS、二进制枚举、模拟退火、DLX


其中一头一尾解法过于简单和困难,有兴趣的同学自行了解与实现。


基本分析



根据题意,可以将本题看做一类特殊的「数独问题」:在给定的 arr 字符数组中选择,尽可能多的覆盖一个 1 * 26126 的矩阵。


对于此类「精确覆盖」问题,换个角度也可以看做「组合问题」。


通常有几种做法:DFS、剪枝 DFS、二进制枚举、模拟退火、DLX


其中一头一尾解法过于简单和困难,有兴趣的同学自行了解与实现。


剪枝 DFS



根据题意,可以有如下的剪枝策略:


  1. 预处理掉「本身具有重复字符」的无效字符串,并去重;
  2. 由于只关心某个字符是否出现,而不关心某个字符在原字符串的位置,因此可以将字符串使用 int 进行表示;
  3. 由于使用 int 进行表示,因而可以使用「位运算」来判断某个字符是否可以被追加到当前状态中;
  4. DFS 过程中维护一个 total,代表后续未经处理的字符串所剩余的“最大价值”是多少,从而实现剪枝;
  5. 使用 lowbit 计算某个状态对应的字符长度是多少;
  6. 使用「全局哈希表」记录某个状态对应的字符长度是多少(使用 static 修饰,确保某个状态在所有测试数据中只会被计算一次);
  7. 【未应用】由于存在第 44 点这样的「更优性剪枝」,理论上我们可以根据「字符串所包含字符数量」进行从大到小排序,然后再进行 DFS 这样效果理论上会更好。想象一下如果存在一个包含所有字母的字符串,先选择该字符串,后续所有字符串将不能被添加,那么由它出发的分支数量为 00;而如果一个字符串只包含单个字母,先决策选择该字符串,那么由它出发的分支数量必然大于 00。但该策略实测效果不好,没有添加到代码中。

网络异常,图片无法展示
|


代码:


class Solution {
    // 本来想使用如下逻辑将「所有可能用到的状态」打表,实现 O(1) 查询某个状态有多少个字符,但是被卡了
    // static int N = 26, M = (1 << N);
    // static int[] cnt = new int[M];
    // static {
    //     for (int i = 0; i < M; i++) {
    //         for (int j = 0; j < 26; j++) {
    //             if (((i >> j) & 1) == 1) cnt[i]++;
    //         }
    //     }
    // }
    static Map<Integer, Integer> map = new HashMap<>();
    int get(int cur) {
        if (map.containsKey(cur)) {
            return map.get(cur);
        }
        int ans = 0;
        for (int i = cur; i > 0; i -= lowbit(i)) ans++;
        map.put(cur, ans);
        return ans;
    }
    int lowbit(int x) {
        return x & -x;
    }
    int n;
    int ans = Integer.MIN_VALUE;
    int[] hash;
    public int maxLength(List<String> _ws) {
        n = _ws.size();
        HashSet<Integer> set = new HashSet<>();
        for (String s : _ws) {
            int val = 0;
            for (char c : s.toCharArray()) {
                int t = (int)(c - 'a');
                if (((val >> t) & 1) != 0) {
                    val = -1;
                    break;
                } 
                val |= (1 << t);
            }
            if (val != -1) set.add(val);
        }
        n = set.size();
        if (n == 0) return 0;
        hash = new int[n];
        int idx = 0;
        int total = 0;
        for (Integer i : set) {
            hash[idx++] = i;
            total |= i;
        }
        dfs(0, 0, total);
        return ans;
    }
    void dfs(int u, int cur, int total) {
        if (get(cur | total) <= ans) return;
        if (u == n) {
            ans = Math.max(ans, get(cur));
            return;
        }
        // 在原有基础上,选择该数字(如果可以)
        if ((hash[u] & cur) == 0) {
            dfs(u + 1, hash[u] | cur, total - (total & hash[u]));
        }
        // 不选择该数字
        dfs(u + 1, cur, total);
    }
}
复制代码


二进制枚举



首先还是对所有字符串进行预处理。


然后使用「二进制枚举」的方式,枚举某个字符串是否被选择。


举个🌰,(110)_{2}(110)2 代表选择前两个字符串,(011)_{2}(011)2 代表选择后两个字符串,这样我们便可以枚举出所有组合方案。


网络异常,图片无法展示
|


代码:


class Solution {
    static Map<Integer, Integer> map = new HashMap<>();
    int get(int cur) {
        if (map.containsKey(cur)) {
            return map.get(cur);
        }
        int ans = 0;
        for (int i = cur; i > 0; i -= lowbit(i)) ans++;
        map.put(cur, ans);
        return ans;
    }
    int lowbit(int x) {
        return x & -x;
    }
    int n;
    int ans = Integer.MIN_VALUE;
    Integer[] hash;
    public int maxLength(List<String> _ws) {
        n = _ws.size();
        HashSet<Integer> set = new HashSet<>();
        for (String s : _ws) {
            int val = 0;
            for (char c : s.toCharArray()) {
                int t = (int)(c - 'a');
                if (((val >> t) & 1) != 0) {
                    val = -1;
                    break;
                } 
                val |= (1 << t);
            }
            if (val != -1) set.add(val);
        }
        n = set.size();
        if (n == 0) return 0;
        hash = new Integer[n];
        int idx = 0;
        for (Integer i : set) hash[idx++] = i;
        for (int i = 0; i < (1 << n); i++) {
            int cur = 0, val = 0;
            for (int j = 0; j < n; j++) {
                if (((i >> j) & 1) == 1) {
                    if ((cur & hash[j]) == 0) {
                        cur |= hash[j];
                        val += get(hash[j]);
                    } else {
                        cur = -1;
                        break;
                    }
                }
            }
            if (cur != -1) ans = Math.max(ans, val);
        }
        return ans;
    }
}
复制代码


模拟退火



事实上,可以将原问题看作求「最优前缀序列」问题,从而使用「模拟退火」进行求解。

具体的,我们可以定义「最优前缀序列」为 组成最优解所用到的字符串均出现在排列的前面。


举个🌰,假如构成最优解使用到的字符串集合为 [a,b,c],那么对应 [a,b,c,...][a,c,b,...] 均称为「最优前缀序列」。


不难发现,答案与最优前缀序列是一对多关系,这指导我们可以将「参数」调得宽松一些。


调整成比较宽松的参数可以跑赢「二进制枚举」,但为了以后增加数据不容易被 hack,还是使用 N=400 & fa=0.90 的搭配。


「模拟退火」的几个参数的作用在 这里 说过了,不再赘述。


网络异常,图片无法展示
|


代码:


class Solution {
    static Map<Integer, Integer> map = new HashMap<>();
    int get(int cur) {
        if (map.containsKey(cur)) {
            return map.get(cur);
        }
        int ans = 0;
        for (int i = cur; i > 0; i -= lowbit(i)) ans++;
        map.put(cur, ans);
        return ans;
    }
    int lowbit(int x) {
        return x & -x;
    }
    int n;
    int ans = Integer.MIN_VALUE;    
    Random random = new Random(20210619);
    double hi = 1e4, lo = 1e-4, fa = 0.90; 
    int N = 400; 
    int calc() {
        int mix = 0, cur = 0;
        for (int i = 0; i < n; i++) {
            int hash = ws[i];
            if ((mix & hash) == 0) {
                mix |= hash;
                cur += get(hash);
            } else {
                break;
            }
        }
        ans = Math.max(ans, cur);
        return cur;
    }
    void swap(int[] arr, int i, int j) {
        int c = arr[i];
        arr[i] = arr[j];
        arr[j] = c;
    }
    void sa() {
        for (double t = hi; t > lo; t *= fa) {
            int a = random.nextInt(n), b = random.nextInt(n);
            int prev = calc(); 
            swap(ws, a, b);
            int cur = calc(); 
            int diff = prev - cur;
            if (Math.log(diff / t) >= random.nextDouble()) { 
                swap(ws, a, b);
            }
        }
    }
    int[] ws;
    public int maxLength(List<String> _ws) {
        // 预处理字符串:去重,剔除无效字符
        // 结果这一步后:N 可以下降到 100;fa 可以下降到 0.70,耗时约为 78 ms
        // 为了预留将来添加测试数据,题解还是保持 N = 400 & fa = 0.90 的配置
        n = _ws.size();
        HashSet<Integer> set = new HashSet<>();
        for (String s : _ws) {
            int val = 0;
            for (char c : s.toCharArray()) {
                int t = (int)(c - 'a');
                if (((val >> t) & 1) != 0) {
                    val = -1;
                    break;
                } 
                val |= (1 << t);
            }
            if (val != -1) set.add(val);
        }
        n = set.size();
        if (n == 0) return 0;
        ws = new int[n];
        int idx = 0;
        for (Integer i : set) ws[idx++] = i;
        while (N-- > 0) sa();
        return ans;
    }
}
复制代码


最后



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


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


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


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

相关文章
|
7月前
|
设计模式 网络协议 Java
04.里式替换原则介绍
里式替换原则(LSP)是面向对象设计的重要原则之一,确保子类可以无缝替换父类而不破坏程序功能。本文详细介绍了LSP的定义、背景、理解方法及应用场景,通过电商支付和鸟类飞行案例展示了如何遵循LSP,并分析了其优缺点。LSP强调子类应保持父类的行为一致性,有助于提高代码的可扩展性、可维护性和可重用性,但也可能导致过度设计。最后,对比了LSP与多态的区别,明确了LSP作为设计原则的重要性。
230 4
|
前端开发 Java 测试技术
综合案例【商品管理系统-Java基础版】(附完整源码)
综合案例【商品管理系统-Java基础版】(附完整源码)
484 9
|
存储 计算机视觉 Python
NumPy 在图像处理中的应用
【8月更文第30天】NumPy 是 Python 中用于科学计算的核心库之一,它提供了高效的数组操作功能。在图像处理领域,NumPy 的数组结构非常适合存储和操作图像数据。本文将详细介绍如何使用 NumPy 进行图像处理,包括加载图像、显示图像、像素操作、颜色空间转换和简单的滤波器应用等。
510 0
|
存储 Prometheus 监控
SLS时序监控实战: Spring Boot应用监控最佳实践
当今随着云原生和微服务的盛行, 我们的应用的运行环境也变得越来越复杂, 也使得我们越来越难以掌握它的运行状态, 也因此诞生了一批开源软件来帮助我们提升应用的可观察性, 例如prometheus, grafana, open tracing, open telementry等, 这些多半是比较通用的技术, 在实际的场景下, 我们需要怎么从各个层面来做监控和数据的分析呢, 我们就以大家使用最多的技术栈: Java + Spring Boot为例, 来详细阐述应用监控的最佳实践
8038 0
SLS时序监控实战: Spring Boot应用监控最佳实践
|
前端开发 JavaScript NoSQL
"从零到一:全方位解析现代Web开发技术栈
【7月更文挑战第9天】在当今快速发展的互联网时代,Web开发技术日新月异,为开发者提供了前所未有的创新空间。本文将从基础到高级,全面解析现代Web开发技术栈,帮助初学者或希望升级技能树的开发者构建稳固的知识体系。我们将探讨前端、后端以及全栈开发的关键技术,并通过一个简单的项目示例来演示这些技术的实际应用。
1608 1
|
数据安全/隐私保护
给虚拟机配置网络 Xshell 使用
给虚拟机配置网络 Xshell 使用
|
编解码 对象存储 UED
[Halcon&标定] 单相机标定
[Halcon&标定] 单相机标定
1353 1
|
C++ 容器
【C++STL基础入门】stack栈的增删查等操作的使用
【C++STL基础入门】stack栈的增删查等操作的使用
555 0
|
机器学习/深度学习 Python Windows
基于Python之邻接矩阵沿对角线拼接操作简单方法
基于Python之邻接矩阵沿对角线拼接操作简单方法
557 0
基于Python之邻接矩阵沿对角线拼接操作简单方法
|
算法 Java 决策智能
0-1背包问题:动态规划的经典应用
0-1背包问题:动态规划的经典应用
601 0