🦴狗新鲜面经

queensberry 发表于 2020-2-15 03:16
第一题followup

[mw_shl_code=java,true]public String mnse(String s) {

能解释一下思路吗

edging1218 发表于 2020-2-15 01:55
第一题follow up greedy O(n)

请问greedy怎么做

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

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

queensberry 发表于 2020-2-16 11:31
first of all, what it means to be the shortest non subsequence of a string?
it means that if we  ...

那AABAA怎么办，最短是BB

krystal1115 发表于 2020/02/16 12:44:24
那AABAA怎么办，最短是BB

根据我的算法跑下来是BB，因为碰到中间的B对应的是答案里第一个B，算法会检测到下一个字符是A从而append B到答案，你可以跑下代码

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

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

lyronly 发表于 2020-2-14 11:18
第四题建立 建立每个word 和其他所有word相同字符的maping 比如 相同字符6个的有3个word  相同字符5个的有2 ...

你这样做的理由是什么呢？为啥选最平均的？

lyronly 发表于 2020-2-14 11:18
第四题建立 建立每个word 和其他所有word相同字符的maping 比如 相同字符6个的有3个word  相同字符5个的有2 ...

什么是最平均？为什么选最平均？

第四题

1. public void findSecretWord(String[] wordlist, Master master) {
   
2.         List<String> words = Arrays.asList(wordlist);
   
3.         while(true) {
   
4.             String current = getMostOverlapWord(words);
   
5.             int same_count = master.guess(current);
   
6.             if (same_count == 6) break;
   
7.             words = get_match_list(words, current, same_count);
   
8.         }
   
9.     }
   
10.    
    
11.     public List<String> get_match_list(List<String> words, String current, int count) {
    
12.         List<String> res = new ArrayList<String>();
    
13.         for (String word : words) {
    
14.             if (word.equals(current)) continue;
    
15.             int same = 0;
    
16.             for (int j = 0; j < 6; j++) {
    
17.                 if (current.charAt(j) == word.charAt(j)) same += 1;
    
18.             }   
    
19.             if (same == count) res.add(word);
    
20.         }
    
21.         return res;
    
22.     }
    
23.    
    
24.     private String getMostOverlapWord(List<String> wordlist) {
    
25.         int[] count = new int[26];        
    
26.         for (String w : wordlist) {
    
27.             for (char ch : w.toCharArray()) count[ch - 'a']++;
    
28.         }
    
29.         int maxScore = 0;
    
30.         String bestWord = "";
    
31.         // 所有words 里面 寻找最多字母重合的 word
    
32.         for (String w : wordlist) {
    
33.             int score = 0;
    
34.             for (int i = 0; i < w.length(); i++) {
    
35.                 score += count[w.charAt(i) - 'a'];
    
36.             }
    
37.             if (score >= maxScore) {
    
38.                 maxScore = score;
    
39.                 bestWord = w;
    
40.             }
    
41.         }
    
42.         return bestWord;
    
43.     }

复制代码