面试快结尾了突然来个手写算法题，结果没写出来。

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 572 天前的主题，其中的信息可能已经有所发展或是发生改变。

昨天，远程视频面试。

感觉前面的问题回答得挺好的，突然发了个网址，让我在线写代码。

一个全排列的算法，事后我查了是 leetcode 第 46 道原题，中等难度。

https://leetcode.cn/problems/permutations/

拿到题，最开始想直接数组遍历，逐步迭代，当前全排列基于上一个排列插入新数字的生成新的结果。

结果磕磕绊绊，没写出完整。面试官最后让我说下思路。。。

唉，郁闷了一晚上没睡着。

排列

面试

算法

组遍历

41 条回复 • 2023-04-20 09:10:39 +08:00

CQdake

2023-04-18 09:29:01 +08:00

1 、思路讲明白大概就可以了，说不定其他面试者连面试的问题都回答不上呢，到时候工作还是你的。

exmario

2023-04-18 09:43:37 +08:00

+1 ，本来就是考思路，谁还能直接手写代码一遍过啊

aLazarus

2023-04-18 09:45:30 +08:00

如果没思路的话，可以试一下申请换题

Exsole

2023-04-18 09:47:41 +08:00

@aLazarus #3 还可以这么要求。。第一次听说。

poemcorner

2023-04-18 09:50:02 +08:00

不想再郁闷一晚上就把 hot100 刷五六遍

leon0918

2023-04-18 09:56:35 +08:00

如果前面回答的挺好的，这种情况也有机会过

dogfight

2023-04-18 09:58:05 +08:00

chatgpt

Exsole

2023-04-18 10:02:41 +08:00

@dogfight #7
chatGPT 回答面试八股文，解算法题，都比人类强。
面试的时候，遇到一些问题，我真想直接回答：“ 这种问题问下 chatGPT ，它的答案更好 ”。

Nazz

2023-04-18 10:11:18 +08:00

DFS 可解, 虽然效率不高, 但 leetcode 不卡时间

Erroad

2023-04-18 10:14:58 +08:00

说考思路的认真的？这种 hot100 还是回溯模板题，我面的几家答不出都是挂啊

Biggoldfish

2023-04-18 10:18:57 +08:00 via Android

考思路的认真的+1

这种常见题不准备也该一遍秒啊，再说有思路写成代码才多久

emSaVya

2023-04-18 10:25:07 +08:00

出这种题说明是真的想要你的。没 ac 可惜了。

bigxianyu

2023-04-18 10:35:05 +08:00

backing , 不过有一些公司思路更重要，实现不是全部

northbrunv

2023-04-18 10:36:44 +08:00

楼主郁闷的应该是"简单题"没写出来，有相当大的机会然而没把握住。换成难题你就不会郁闷了。

iOCZ

2023-04-18 10:41:30 +08:00

一般就 DFS 啥的

dswyzx

2023-04-18 10:47:22 +08:00 via iPhone

这题还真得 dfs ，还有个变种是数组有相同数字哎，只能说面试官有点找事吧

Litccc

2023-04-18 11:12:49 +08:00

回溯模板题，现在面试基本都要考算法题的，楼主多刷刷吧

Nazz

2023-04-18 11:14:27 +08:00

DFS 也能写得非常高效, 0ms AC
https://leetcode.cn/submissions/detail/425576450/

SeaTac

2023-04-18 11:21:46 +08:00

这种题只要求讲思路过分了吧
至少要写出能过基本 test case 的代码

chenshun00

2023-04-18 11:28:32 +08:00

@emSaVya 这么说的话，不来两数之和嘛

optional

2023-04-18 11:29:52 +08:00 via iPhone

感觉是放水题

coyoteer

2023-04-18 11:41:46 +08:00

全排列 dfs 最简单啦

hankai17

2023-04-18 12:01:17 +08:00

不刷题的话应该不好想
如果前面答得好也没什么

baislsl

2023-04-18 12:42:50 +08:00

@Nazz DFS 不重不漏, 已经是最优解法了

k9982874

2023-04-18 12:50:51 +08:00

直接递归完事

dudubaba

2023-04-18 12:52:27 +08:00

不刷题在面试这种几分钟的紧张氛围里没几人写的出来。

ccagml

2023-04-18 13:33:49 +08:00 via Android

可惜了，不是出 hard 感觉就是要你了

JasonLaw

2023-04-18 14:11:20 +08:00

```python
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def gen_permutations(nums) -> List[List[int]]:
if len(nums) == 1:
return [nums]
permutations = []
for i in range(len(nums)):
for p in gen_permutations(nums[0:i] + nums[i + 1:]):
permutations.append([nums[i]] + p)
return permutations

res = gen_permutations(nums)
return res
```

JasonLaw

2023-04-18 14:11:58 +08:00

@JasonLaw #28 https://leetcode.com/problems/permutations/submissions/935632864/

laowudxf

2023-04-18 14:19:28 +08:00

没刷过力扣，想了三分钟有了思路，感觉不是很难。

Tompes

2023-04-18 14:27:02 +08:00

全排列属于很常规的题了，出这题应该也是想让你过的

reducm

2023-04-18 14:49:21 +08:00

LeetCode 46 题的题目描述为：给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

解题思路：

该题可以使用回溯算法来解决，回溯算法解决的问题都可以抽象成树结构，每个节点表示一个状态，每个节点的子节点表示在该状态下可以转移到的所有状态。

在本题中，我们可以将每个元素看作一个节点，然后每个节点的子节点是剩下的元素，表示选择了该元素后可以继续选择哪些元素。因此，我们可以使用回溯算法来遍历这棵树，找到所有的解。

具体实现时，我们可以使用一个数组来保存当前选择的元素，使用一个布尔数组来标记每个元素是否已经被选择过，然后按照如下步骤进行回溯：

如果选择的元素数量等于原始数组的长度，说明已经选择了所有元素，将当前选择的元素列表加入最终结果中。

遍历原始数组，对于每个未被选择过的元素，将其加入选择列表中，并将其标记为已选择，然后递归进入下一层。

回溯时，将选择列表中最后一个元素删除，并将其标记为未选择。

重复上述步骤，直到遍历完所有状态。

Java 代码实现：

class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, new ArrayList<>(), used, res);
return res;
}

private void backtrack(int[] nums, List<Integer> temp, boolean[] used, List<List<Integer>> res) {
if (temp.size() == nums.length) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (!used[i]) {
temp.add(nums[i]);
used[i] = true;
backtrack(nums, temp, used, res);
used[i] = false;
temp.remove(temp.size() - 1);
}
}
}
}

时间复杂度：O(n×n!)，其中 n 表示数组的长度，n! 表示全排列的总数，因为每个全排列包含 n 个元素，因此总共需要枚举 n×n! 个状态。

空间复杂度：O(n)，其中 n 表示数组的长度，空间复杂度取决于递归调用栈的深度和存储当前选择的元素的列表。在最坏情况下，递归调用栈的深度为 n ，因此空间复杂度为 O(n)。

mqtdut1

2023-04-18 16:01:26 +08:00

一看就是递归
再看一下，数组长度 1-6 ，那就换总写法吧
写 6 个 if ，2 写 2 层 for ，3 写 3 层 for
https://leetcode.cn/submissions/detail/425663532/

Nazz

2023-04-18 16:22:20 +08:00

@mqtdut1 简单粗暴 👍🏻

gitignore

2023-04-18 16:31:54 +08:00

递归咯，每个数插在前一个全排列的缝隙里

[0, 1] => [ [ 0, 1 ], [ 1, 0 ] ]

[0 , 1, 2] 相当于在上面每个数组的每个缝隙插入 2:

[0, 1] 插入 2 得到 [2, 0, 1], [0, 2, 1], [0, 1, 2]
[1, 0] 插入 2 得到 [2, 1, 0], [1, 2, 0], [1, 0, 2]

Exsole

2023-04-18 16:34:14 +08:00

@gitignore #35
我就是这么思考的。结果写着写着卡壳了。