狗家 昂赛面经

看面经的门槛越来越高了啊。。。

LZ, 第三轮的考点是什么，谢谢

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

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

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

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

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

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

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

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

分享一个DFS解法，大家讨论一下

1.     public List<String> getPattern(int n) {
   
2.         List<String> res = new ArrayList<>();
   
3.         List<Character> exist = new ArrayList<>();
   
4.         exist.add('1');
   
5.         dfs(exist, res, "1", n);
   
6.         return res;
   
7.     }
   
8. 
   
9.     private void dfs(List<Character> exist, List<String> res, String str, int n) {
   
10.         if (str.length() == n) {
    
11.             res.add(str);
    
12.             return;
    
13.         }
    
14.         char end = exist.get(exist.size()-1);
    
15.         for (char c = '1'; c <= end+1; c++){
    
16. 
    
17.             if (!exist.contains(c)) {
    
18.                 List<Character> newexist = new ArrayList<>(exist);
    
19.                 newexist.add(c);
    
20.                 dfs(newexist, res, str+c, n);
    
21.             } else {
    
22.                 dfs(exist, res, str+c, n);
    
23.             }
    
24. 
    
25.         }
    
26. 
    
27.     }

复制代码

分享一个第一题的一个DFS的解法 大家可以讨论下

1.     public List<String> findAllPatterns(int n) {
   
2.         List<String> results = new ArrayList();
   
3.         if (n <= 0) {
   
4.             return results;
   
5.         }
   
6. 
   
7.         Map<Character, Integer> existingMap = new HashMap();
   
8.         findAllPatternHelper(n, results, existingMap, new StringBuilder());
   
9.         return results;
   
10.     }
    
11. 
    
12.     private void findAllPatternHelper(int n, List<String> results, Map<Character, Integer> existingMap, StringBuilder sb) {
    
13.         if (sb.length() == n) {
    
14.             results.add(sb.toString());
    
15.             System.out.println("sb is: " + sb.toString());
    
16.             return;
    
17.         }
    
18. 
    
19.         Set<Character> set = new HashSet(existingMap.keySet());
    
20.         for (Character ch : set) {
    
21.             sb.append(ch);
    
22.             // update exisingMap
    
23.             existingMap.put(ch, existingMap.get(ch) + 1);
    
24.             findAllPatternHelper(n, results, existingMap, sb);
    
25.             sb.deleteCharAt(sb.length() - 1);
    
26.             // update exisingMap
    
27.             existingMap.put(ch, existingMap.get(ch) - 1);
    
28.         }
    
29. 
    
30.         // add new character
    
31.         char newChar = (char) ('A' +  sb.length());
    
32.         existingMap.put(newChar, 1);
    
33.         sb.append(newChar);
    
34.         findAllPatternHelper(n, results, existingMap, sb);
    
35.         sb.deleteCharAt(sb.length() - 1);
    
36.         if (existingMap.get(newChar) == 1) {
    
37.             existingMap.remove(newChar);
    
38.         } else {
    
39.             existingMap.put(newChar, existingMap.get(newChar) - 1);
    
40.         }
    
41.     }

复制代码

第三轮最直接的想法就是把词典里的词全都放到hashset里，词的长度存到一个treeset里，然后扫给定的文件，用treeset里的所有长度看是不是在hashset里，是就在初始为0的孪生数组中标记为1，然后每一次cursor往后移动1。 这样的时间复杂度是O(文件的长度* 字典长度的种类)。 接下来的想法是感觉可以用carbin-karp优化，因为不同长度的验证感觉有重复计算。

jdlimiao 发表于 2019-4-15 12:27
在扩展AA的时候，我只会加A（原string里自带的），以及一个新letter也就是B，不会再加C的，所以没有重复 ...

准确的说是紧接着当前string已有letter之后的一个新letter