狗家VO 大概率挂经

匿名用户 发表于 2022-05-18 09:09:05
请问第三轮follow up 猜的顺序是给定的还是需要自己找一个可能valid的顺序？

给定的szszsz

jijismile 发表于 2022-05-18 09:45:25
第二题 是不是可以这样做 先算出来end time
然后 把start time 和-1 * endtime 放进一个sorted set 里面
还要把被测试的那个时间也放进去

是可以的，和用有效对接感觉差不多，jobs数量比较多的时候感觉时间会很长，面的L3没有sd

yuxudong199 发表于 2022-05-18 11:10:02
感谢分享， 第二题follow up感觉可以这么搞：
TreeMap 存当前已有的job key = start Time, value = endTime + cpu needed for thi

感觉是可以的，python没有这个数据结构，就想到这个

lihe14569 发表于 2022-05-18 14:34:34
第三轮的follow up肯否讲一下思路，是要求G的位置字母都包含，Y的位置上的字母要和前一个guess word一样吗？？

要求G位置字母都相同，Y位置字母都包含，这样的话先check G的位置，然后Y的话就计数看是不是超过就行了

感谢楼主！请问第三轮follow up 能举个例子么？实在没明白啥意思

匿名用户 发表于 2022-05-19 19:38:48
感谢楼主！请问第三轮follow up 能举个例子么？实在没明白啥意思

比如说我的target是ABCDE
我有一个guess word的序列，是AGHBD，那么第一步得到的结果就是GRRYY，下一步的话valid的guess就可以是比如ACBDG（G的位置必须index和值都还是原来的，所以第一个位置必须是A，Y的地方必需至少包含，所以必须包含BD），像AGHYU或者BDAHG就不行，给一个guess word的list，判断是不是每次猜测都是基于前一步的guess的valid guess

匿名者 发表于 2022-5-19 22:58
比如说我的target是ABCDE
我有一个guess word的序列，是AGHBD，那么第一步得到的结果就是GRRYY，下一步的 ...

谢谢楼主解答！

这道题的解法是one pass O(n) 么？ 只想到了two pass 的方法，不知道这道题应该怎么优化

follow up 感觉也是跟第一问没什么关系，问的是什么算法知识呢？

匿名用户 发表于 2022-05-20 15:54:59
谢谢楼主解答！

这道题的解法是one pass O(n) 么？ 只想到了two pass 的方法，不知道这道题应该怎么优化

我的做法是two pass O(n)
第二次pass的时候因为最多只需要check英文字母所以是常数时间。
感觉没考啥难的算法……一个ordered set一个hash map就解决，主要是沟通理解题意和考虑corner cases？

匿名者 发表于 2022-5-20 18:11
我的做法是two pass O(n)
第二次pass的时候因为最多只需要check英文字母所以是常数时间。
感觉没考啥难的 ...

为啥需要2遍啊？遍历一次，相邻的比较就可以了啊 ，时间O(m * n) ，其实还是遍历2次……

1. public boolean[] getHint(String secret, String guesses[]) {
   
2.         Map<Character, Integer> h = new HashMap<>();
   
3.         for (char s : secret.toCharArray()) {
   
4.             h.put(s, h.getOrDefault(s, 0) + 1);
   
5.         }
   
6. 
   
7.         int m = guesses[0].length();
   
8.         boolean[] res = new boolean[guesses.length];
   
9.         for (int i = 1; i < guesses.length; i++) {
   
10.             Set<Character> Y = new HashSet<>();
    
11.             TreeSet<Integer> G = new TreeSet<>();
    
12.             for (int idx = 0; idx < m; ++idx) {
    
13.                 char ch = guesses[i - 1].charAt(idx);
    
14.                 if (h.containsKey(ch)) {
    
15.                     // corresponding characters match
    
16.                     if (ch == secret.charAt(idx)) {
    
17.                         G.add(idx);
    
18.                         // corresponding characters don't match
    
19.                     } else if (h.get(ch) > 0) {
    
20.                         Y.add(ch);
    
21.                     }
    
22.                     // ch character was used
    
23.                     h.put(ch, h.get(ch) - 1);
    
24.                 }
    
25.             }
    
26. 
    
27.             Set<Character> curY = new HashSet<>();
    
28.             String cur = guesses[i];
    
29.             boolean isValidG = true;
    
30.             for (int j: G) {
    
31.                 if (cur.charAt(j) != secret.charAt(j)) {
    
32.                     res[i] = false;
    
33.                     isValidG = false;
    
34.                     break;
    
35.                 }
    
36.             }
    
37. 
    
38.             if (!isValidG) {
    
39.                 continue;
    
40.             }
    
41.             for (int j = 0; j < n; j++) {
    
42.                 if (G.contains(j)) {
    
43.                     continue;
    
44.                 }
    
45.                 char c = cur.charAt(j);
    
46.                 if (Y.contains(c)) {
    
47.                     curY.add(c);
    
48.                 }
    
49.             }
    
50.             if (curY.size() == Y.size()) {
    
51.                 res[i] = true;
    
52.             } else {
    
53.                 res[i] = false;
    
54.             }
    
55.         }
    
56.         res[0] = true;
    
57.         return res;
    
58.     }

复制代码

dwl1222 发表于 2022-5-18 15:18
只check floor 和ceil可能不够。因为和新加入的ovelap的可以有很多。甚至所有当前的都可以与之overlap。  ...

最坏情况要都遍历，可以用tailSet找出所有endTime > new job's startTime，之后看是否overlap