昨天,远程视频面试。
感觉前面的问题回答得挺好的,突然发了个网址,让我在线写代码。
一个全排列的算法,事后我查了是 leetcode 第 46 道原题,中等难度。
https://leetcode.cn/problems/permutations/
拿到题,最开始想直接数组遍历,逐步迭代,当前全排列基于上一个排列插入新数字的生成新的结果。
结果磕磕绊绊,没写出完整。面试官最后让我说下思路。。。
唉,郁闷了一晚上没睡着。
1
CQdake 2023-04-18 09:29:01 +08:00
1 、思路讲明白大概就可以了,说不定其他面试者连面试的问题都回答不上呢,到时候工作还是你的。
|
2
exmario 2023-04-18 09:43:37 +08:00
+1 ,本来就是考思路,谁还能直接手写代码一遍过啊
|
3
aLazarus 2023-04-18 09:45:30 +08:00
如果没思路的话,可以试一下申请换题
|
5
poemcorner 2023-04-18 09:50:02 +08:00
不想再郁闷一晚上就把 hot100 刷五六遍
|
6
leon0918 2023-04-18 09:56:35 +08:00
如果前面回答的挺好的,这种情况也有机会过
|
7
dogfight 2023-04-18 09:58:05 +08:00
chatgpt
|
8
Exsole OP |
9
Nazz 2023-04-18 10:11:18 +08:00
DFS 可解, 虽然效率不高, 但 leetcode 不卡时间
|
10
Erroad 2023-04-18 10:14:58 +08:00
说考思路的认真的?这种 hot100 还是回溯模板题,我面的几家答不出都是挂啊
|
11
Biggoldfish 2023-04-18 10:18:57 +08:00 via Android
考思路的认真的+1
这种常见题不准备也该一遍秒啊,再说有思路写成代码才多久 |
12
emSaVya 2023-04-18 10:25:07 +08:00
出这种题说明是真的想要你的。没 ac 可惜了。
|
13
bigxianyu 2023-04-18 10:35:05 +08:00
backing , 不过有一些公司思路更重要,实现不是全部
|
14
northbrunv 2023-04-18 10:36:44 +08:00
楼主郁闷的应该是"简单题"没写出来,有相当大的机会然而没把握住。换成难题你就不会郁闷了。
|
15
iOCZ 2023-04-18 10:41:30 +08:00
一般就 DFS 啥的
|
16
dswyzx 2023-04-18 10:47:22 +08:00 via iPhone
这题还真得 dfs ,还有个变种是数组有相同数字哎,只能说面试官有点找事吧
|
17
Litccc 2023-04-18 11:12:49 +08:00
回溯模板题,现在面试基本都要考算法题的,楼主多刷刷吧
|
18
Nazz 2023-04-18 11:14:27 +08:00
DFS 也能写得非常高效, 0ms AC
https://leetcode.cn/submissions/detail/425576450/ |
19
SeaTac 2023-04-18 11:21:46 +08:00
这种题只要求讲思路过分了吧
至少要写出能过基本 test case 的代码 |
20
chenshun00 2023-04-18 11:28:32 +08:00
@emSaVya 这么说的话,不来两数之和嘛
|
21
optional 2023-04-18 11:29:52 +08:00 via iPhone
感觉是放水题
|
22
coyoteer 2023-04-18 11:41:46 +08:00
全排列 dfs 最简单啦
|
23
hankai17 2023-04-18 12:01:17 +08:00
不刷题的话 应该不好想
如果前面答得好 也没什么 |
25
k9982874 2023-04-18 12:50:51 +08:00
直接递归完事
|
26
dudubaba 2023-04-18 12:52:27 +08:00
不刷题在面试这种几分钟的紧张氛围里没几人写的出来。
|
27
ccagml 2023-04-18 13:33:49 +08:00 via Android
可惜了,不是出 hard 感觉就是要你了
|
28
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 ``` |
29
JasonLaw 2023-04-18 14:11:58 +08:00
|
30
laowudxf 2023-04-18 14:19:28 +08:00
没刷过力扣,想了三分钟有了思路,感觉不是很难。
|
31
Tompes 2023-04-18 14:27:02 +08:00
全排列属于很常规的题了,出这题应该也是想让你过的
|
32
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)。 |
33
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/ |
35
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] |
37
kjstart 2023-04-18 21:38:40 +08:00
全排列一般用回溯, 找几个经典的题解把常见算法看看就可以了. 从第一位开始全试一遍, 下一层去掉正在使用的数字, 重复上面的步骤.
|
38
littleBink 2023-04-19 01:09:46 +08:00
我最后面试官给了一道签到题:tom is a cat 倒序输出 cat is a tom 。一看题目以为面试官这是送我 offer ,结果折腾了五分钟,差点没写出来,总是有小细节遗漏了😂
|
39
WashFreshFresh 2023-04-19 09:37:02 +08:00
@grahamsa0503 好久没刷题确实不熟练,像这个就是有好几种解法。
|
40
JasonLaw 2023-04-20 09:04:24 +08:00
@grahamsa0503 #38 LeetCode 地址 - https://leetcode.com/problems/reverse-words-in-a-string/description/
|
41
littleBink 2023-04-20 09:10:39 +08:00 via iPhone
@JasonLaw 谢谢。面试官不让用 api ,需要全部自己实现。我思路基本上是清楚的,就是实现的时候有些细节总是疏忽😂
|