【综合笔试题】难度 3/5，近期小厂面试原题-六虎

标题描绘

这是 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 < = a r r . l e n g t h < = 16$
$1 < = a r r [i] . l e n g t h < = 26$
arr[i]中只含有小写英文字母

根本剖析

依据题意，能够将本题看做一类特别的「数独问题」：在给定的 arr 字符数组中挑选，尽或许多的掩盖一个 $\times 26$ 的矩阵。

关于此类「准确掩盖」问题，换个角度也能够看做「组合问题」。

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

其间一头一尾解法过于简略和困难，有爱好的同学自行了解与完成。

剪枝 DFS

依据题意，能够有如下的剪枝战略：

预处理掉「自身具有重复字符」的无效字符串，并去重；
因为只关怀某个字符是否出现，而不关怀某个字符在原字符串的位置，因此能够将字符串运用 int 进行表明；
因为运用 int 进行表明，因此能够运用「位运算」来判断某个字符是否能够被追加到当时状况中；
DFS 过程中维护一个 total，代表后续未经处理的字符串所剩余的“最大价值”是多少，然后完成剪枝；
运用 lowbit 核算某个状况对应的字符长度是多少；
运用「全局哈希表」记载某个状况对应的字符长度是多少（运用 static 润饰，确保某个状况在一切测试数据中只会被核算一次）；
【未应用】因为存在第 $4$ 点这样的「更优性剪枝」，理论上咱们能够依据「字符串所包括字符数量」进行从大到小排序，然后再进行 DFS 这样作用理论上会更好。想象一下假设存在一个包括一切字母的字符串，先挑选该字符串，后续一切字符串将不能被增加，那么由它动身的分支数量为 $0$ ；而假设一个字符串只包括单个字母，先决议计划挑选该字符串，那么由它动身的分支数量必定大于 $0$ 。但该战略实测作用不好，没有增加到代码中。

代码：

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}$ 代表挑选前两个字符串， $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,...] 均称为「最优前缀序列」。

不难发现，答案与最优前缀序列是一对多联系，这指导咱们能够将「参数」调得宽松一些。

具有「一对多」联系的问题十分合适运用「模拟退火」，运用「模拟退火」能够轻松将本题 arr.length 数据范围上升到 $60$ 乃至以上。

调整成比较宽松的参数能够跑赢「二进制枚举」，但为了以后增加数据不容易被 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 shuffle(int[] nums) {
        for (int i = n; i > 0; i--) {
            int idx = random.nextInt(i);
            swap(nums, idx, i - 1);
        }
    }
    void swap(int[] nums, int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
    void sa() {
        shuffle(ws);
        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 = cur - prev;
            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 原题链接和其他优选题解。

更多更全更抢手的「书面考试/面试」相关材料可拜访排版精巧的合集新基地

【综合笔试题】难度 3/5，近期小厂面试原题

标题描绘

根本剖析

剪枝 DFS

二进制枚举

模拟退火

最后

作者信息

推广

【综合笔试题】难度 3/5，近期小厂面试原题

标题描绘

根本剖析

剪枝 DFS

二进制枚举

模拟退火

最后

相关文章

一个简单的小demo：实时时钟显示

git push时如果遇到问题，来试试这几种方式

每日记录自己的Android项目（一）——UI界面

Swift 周报 第二十六期

作者信息

推广

Swift 周报第二十六期