黑车面试 permutation 变形

黑车面试， 一小时一道题。permutation 的变形体。题目描述：there is a set of {p1 d

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

fore p2.
想一想
后面会post solution。

感谢楼主！ 一个小建议：面试中尽量避免global variable，很可能会被面试官各种挑刺。

post一个我的写法

1.     public List<List<String>> permutation(List<String> input) {
   
2.         int len = input.size();
   
3.         List<List<String>> res = new ArrayList<>();
   
4.         boolean[] visited = new boolean[len];
   
5.         dfs(input, visited, new ArrayList<>(), res);
   
6. 
   
7.         return res;
   
8.     }
   
9. 
   
10.     private void dfs(List<String> input, boolean[] visited, List<String> cur, List<List<String>> res) {
    
11.         if (cur.size() == input.size()) {
    
12.             res.add(new ArrayList<>(cur));
    
13.             return;
    
14.         }
    
15. 
    
16.         for (int i = 0; i < input.size(); ++i) {
    
17.             if (i % 2 == 0 && visited[i] || i % 2 == 1 && (!visited[i - 1] || visited[i]))
    
18.                 continue;
    
19. 
    
20.             visited[i] = true;
    
21.             cur.add(input.get(i));
    
22.             dfs(input, visited, cur, res);
    
23.             cur.remove(cur.size() - 1);
    
24.             visited[i] = false;
    
25.         }
    
26.     }

复制代码

抛个砖 这个应该跟lc那个有重复的permutation类似的思路吧

yayafuture 发表于 2019-7-27 14:09
抛个砖 这个应该跟lc那个有重复的permutation类似的思路吧

对的， 就是那个思路， 不过在backtrack 判断条件时要保证constranit. 有些变形， 所以背住permutation的答案肯定不行。 还是要理解。

下面是我的答案， 欢迎交流。solution (n!)

1. import java.util.ArrayList;
   
2. import java.util.List;
   
3. 
   
4. public class uberInterview {
   
5.     static List res;
   
6.     static int[] arr;
   
7. 
   
8.     public static void main(String[] args) {
   
9.         int n = 3;
   
10.         res = new ArrayList<>();
    
11.         List list = new ArrayList<>();
    
12.         arr = new int[2 * n];
    
13.         //p1d1p2d2
    
14.         //2*n
    
15.         for (int i = 0; i < n; i++) {
    
16.             list.add("p" + i);
    
17.             list.add("d" + i);
    
18.         }
    
19.         //
    
20.         recur(list, arr, 2 * n, "");
    
21.         System.out.println("res.size()");
    
22.         System.out.println(res.size());
    
23.         for (int i = 0; i < res.size(); i++) {
    
24.             System.out.println(res.get(i));
    
25.         }
    
26. 
    
27.     }
    
28. 
    
29.     static void recur(List list, int[] arr, int len, String curString) {
    
30.         if (curString.length() == 2* len) {
    
31. 
    
32.             String tempString = curString;
    
33.             res.add(tempString);
    
34.             return;
    
35.         }
    
36.         for (int i = 0; i < list.size(); i++) {
    
37.             if(i==0){
    
38.                 if(arr==0){
    
39.                     arr = 1;
    
40.                 recur(list, arr, len, curString + list.get(i));
    
41.                 arr = 0;
    
42.                 }
    
43.             }//pi not visited and di is visited
    
44.             else if (arr[i-1] == 0 && list.get(i).charAt(0) == 'd') {
    
45. 
    
46.             } else if (arr == 0) {
    
47.                 arr = 1;
    
48.                 recur(list, arr, len, curString + list.get(i));
    
49.                 arr = 0;
    
50.             }
    
51.         }
    
52.     }
    
53. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

我还是不会做....
哭哭啼啼

akdhfikbk 发表于 2020-2-22 18:37
我还是不会做....
哭哭啼啼

面试考了吗？