Python技术迷

为什么还有人用VIM?

虎哥2024年08月10日约 4 分钟

为什么还有人用 Vim？

很多人喜欢用 Vim，是因为Vim 大概是世界上扩展能力最强的编辑器。

它的扩展能力无敌，各种插件、配置文件和脚本都能让你把 Vim 变成你想要的样子。

Vim 的操作效率特别高。虽然一开始可能会觉得命令和模式有点复杂，但习惯了之后，工作效率真的是飞跃式的提升。

用 Vim，不需要离开键盘，所有操作都能用快捷键完成，这对于编程来说简直太方便了。

另外，Vim 很轻量，启动快，占用资源少，不会轻易崩溃。这对老旧系统或者资源有限的环境来说特别友好。而且，Vim 在各种平台上都能用，无论是 Linux、Mac 还是 Windows，只要有个终端，就能实现编程。

这也是为什么那么多人仍然钟情于 Vim 的原因。

今天刚好看到一个大厂的算法题，我们一起来看看怎么做。

面试题目

一个数组表示面值，一个数组表示对应的数量，求所有可能的价格总和

这道题听起来像是个组合问题，但实际上更像是个变种的背包问题。咱们一步一步来解。

题目拆解

首先，我们需要明确一下题目要求：

一个数组 values 表示不同面值，比如 [1, 2, 3]。
另一个数组 counts 表示对应面值的数量，比如 [2, 1, 3]。

这两个数组的长度是一样的，分别代表面值和对应的数量。我们要做的是，计算所有可能的价格总和。

思路分析

这个问题本质上是一个多重背包问题，只不过我们不需要考虑容量限制，只需要计算所有可能的组合。

我们可以使用深度优先搜索（DFS）来解决这个问题。DFS 的思想是，从第一个面值开始，逐个尝试每种可能的数量，然后递归处理剩下的面值。我们用一个集合来记录所有可能的价格总和，避免重复计算。

算法步骤

定义一个集合 results 用来存储所有可能的价格总和。
从第一个面值开始，使用 DFS 遍历所有可能的数量组合。
每次遍历到一个面值，尝试从 0 到该面值的最大数量（由 counts 决定）。
递归处理剩下的面值。
当遍历完成时，将总和加入 results。

代码实现

JavaScript：

<!DOCTYPE html><html lang="en"><head>    <meta charset="UTF-8">    <meta name="viewport" content="width=device-width, initial-scale=1.0">    <title>面值组合总和</title></head><body>    <h1>面值组合总和</h1>    <p>打开控制台查看结果</p>    <script>        function allPossibleSums(values, counts) {            let results = new Set();
            function dfs(index, currentSum) {                if (index === values.length) {                    results.add(currentSum);                    return;                }
                for (let i = 0; i <= counts[index]; i++) {                    dfs(index + 1, currentSum + values[index] * i);                }            }
            dfs(0, 0);
            return Array.from(results).sort((a, b) => a - b);        }
        // 示例数据        const values = [1, 2, 3];        const counts = [2, 1, 3];
        // 调用函数并打印结果        const result = allPossibleSums(values, counts);        console.log(result);</script></body></html>

结果说明

这个前端代码实现和之前的 Python 代码逻辑是一样的，最终会输出所有可能的价格总和，例如 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11]。

python：

def all_possible_sums(values, counts):    results = set()    def dfs(index, current_sum):        # 如果遍历完所有面值，添加当前总和到结果集        if index == len(values):            results.add(current_sum)            return        # 遍历当前面值的所有可能数量        for i in range(counts[index] + 1):            dfs(index + 1, current_sum + values[index] * i)    # 从第一个面值开始    dfs(0, 0)    return sorted(results)
# 示例数据values = [1, 2, 3]counts = [2, 1, 3]
# 调用函数并打印结果result = all_possible_sums(values, counts)print(result)

代码解析

results 是一个集合，用来存储所有可能的总和。使用集合可以自动去重。
dfs 函数是核心递归函数，index 表示当前处理到的面值下标，current_sum 表示当前累计的总和。
在 dfs 函数中，先检查是否遍历完所有面值，如果是，就把当前总和加入结果集。
如果没有遍历完，就遍历当前面值的所有可能数量（从 0 到最大数量），递归处理下一个面值。
最后，通过调用 dfs(0, 0) 从第一个面值开始计算，返回结果集合并排序。

结果说明

这个代码会输出所有可能的价格总和，排序后的结果更直观易读。举个例子，对于 values = [1, 2, 3] 和 counts = [2, 1, 3]，程序会输出 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11]。

这样，所有可能的价格总和就求出来了。这个方法比较直接，利用 DFS 的回溯思想，虽然在数据规模较大时可能效率不高，但对于面试或者小规模问题绝对够用。如果数据规模特别大，可以考虑动态规划等优化手段。

好了，这就是这个算法题的解法，希望对你有帮助。如果有其他问题或者更好的解法，欢迎讨论！虎哥在这里等着你们！

目前，对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。

🔥虎哥私藏精品热门推荐🔥

虎哥作为一名老码农，整理了全网最全 《python高级架构师资料合集》。

资料包含了《IDEA视频教程》、《最全python面试题库》、《最全项目实战源码及视频》及《毕业设计系统源码》，总量高达 650GB。全部 免费领取！全面满足各个阶段程序员的学习需求。