月薪从1.5万降到3千，我接受了。。。
P
Web前端专栏约 4 分钟
Web前端专栏约 4 分钟
我们一直说今年行情差，不好找工作，但能有多差，是比较模糊的。而我在网上看到一网友的帖子算是给了我一个概念，“有谁会接受月薪从1.5万降到三千吗？我接受了。”15k到3k？我都怀疑我看错了。但这还不是个例，更恐怖的也有。
下面分享一道大厂的算法题
算法题目
给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
1
虽然只是个例，但管中 窥豹，这搁以前，肯定都以为在开玩笑。就算到了现在，都觉得不可思议。那么大家怎么看呢？专属福利 👉点击领取：最全Python资料合集
下面分享一道大厂的算法题
今年的环境就这样，不管是大厂还是小厂，笔面试都会问算法，所以要内卷，算法是必不可少的。这是 今日算法题，来自LeetC ode的第46题： 全排列 ，很多 大厂都考过，下面是我的算法思路及实现，让我 们来看看吧。
全排列
算法题目
给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
引言
全排列是一个经典的算法问题，在很多场景下都有广泛的应用，比如解决一些组合问题、优化问题等。它要求我们找到给定集合的所有排列方式，即不同的元素排列组合的方式。这个问题可以通过递归来解决，也就是我们常说的回溯算法。算法思路
解决全排列问题的关键是理解递归的过程及如何通过回溯遍历所有可能的排列。基本步骤如下：- 路径：记录在 path 中，表示当前的排列情况。
- 选择列表：nums 中不存在于 path 的那些元素。
- 结束条件：nums 中的元素全都在 path 中出现。
- 从左至右遍历数组 nums，将当前元素加入到路径 path 中，并将其从选择列表中移除。
- 进入下一层决策树。
- 通过递归完成所有路径的探索。
- 回溯阶段：将当前元素从路径 path 中移除，恢复选择列表，继续探索其他路径。
代码实现
Java Scrip t实现
Java实现function permute(nums) {let res = [];let path = [];function backtrack(path) {if (path.length === nums.length) {res.push(Array.from(path));return;}for (let i = 0; i < nums.length; i++) {if (path.includes(nums[i])) continue;path.push(nums[i]);backtrack(path);path.pop();}}backtrack(path);return res;}
Go实现import java.util.ArrayList;import java.util.List;public class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();boolean[] used = new boolean[nums.length];backtrack(nums, used, path, res);return res;}private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {if (path.size() == nums.length) {res.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (used[i]) continue;path.add(nums[i]);used[i] = true;backtrack(nums, used, path, res);used[i] = false;path.remove(path.size() - 1);}}}
package mainfunc permute(nums []int) [][]int {var res [][]intvar path []intused := make([]bool, len(nums))var backtrack func(int)backtrack = func(n int) {if n == len(nums) {res = append(res, append([]int(nil), path...))return}for i, v := range nums {if used[i] {continue}path = append(path, v)used[i] = truebacktrack(n + 1)path = path[:len(path)-1]used[i] = false}}backtrack(0)return res}
算法解析
此算法的时间复杂度为O(n×n!)，这是因为对于 n 个不同元素，每个元素都有 n-1 种排列方式，因此总的时间复杂度为排列数乘以生成每个排列的时间（即n!）。空间复杂度主要由递归深度O(n)）和存储结果的列表（O(n!)）决定。示例和测试
以 nums = [1,2,3] 为例，按照上述算法步骤执行，可以得到结果 [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]。 测试代码可以根据上述实现直接运行，以验证算法的正确性。总结
全排列问题是回溯算法的经典应用之一，通过深入理解和实践这类问题，可以帮助我们更好地掌握回溯算法的设计思想和编码技巧，进而解决更多复杂的组合、排列问题。
热门推荐