比赛review帖

vtiaocao 发表于 2018-6-10 10:40
我也来跟lz打个卡。。

利口最后一题日常被爆。。已经决定放弃了

佛了, 刚才打的被审核了.
最后一道确实有点难度.. 然后在我写第二题的时候就发现别人4道都写完了.. 感觉慌了. 后来第三题其实也没写出来, 就跑出去喝酒了.
848

1.     public String shiftingLetters(String S, int[] shifts) {
   
2.         for(int i = shifts.length - 2; i >= 0; i--)
   
3.         {
   
4.             shifts[i] += shifts[i + 1] % 26;
   
5.         }
   
6.         char[] c = S.toCharArray();
   
7.         for(int i = 0; i < c.length; i++)
   
8.         {
   
9.             shifts[i] %= 26;
   
10.             c[i] = (char)(c[i] + shifts[i]);
    
11.             if(c[i] > 'z') c[i] = (char)(c[i] - 26);
    
12.         }
    
13.         return String.valueOf(c);
    
14.     }

复制代码

849

1.     public int maxDistToClosest(int[] seats) {
   
2.         int n = seats.length;
   
3.         int[] left = new int[n], right = new int[n];
   
4.         Arrays.fill(left, -1);
   
5.         Arrays.fill(right, -1);
   
6.         for(int i = 0; i < n; i++)
   
7.         {
   
8.             if(seats[i] == 1) right[i] = 0;
   
9.             else if(i > 0 && right[i - 1] >= 0)
   
10.                 right[i] = right[i - 1] + 1;
    
11.         }
    
12.         for(int i = n - 1; i >= 0; i--)
    
13.         {
    
14.             if(seats[i] == 1) left[i] = 0;
    
15.             else if(i < n - 1 && left[i + 1] >= 0)
    
16.                 left[i] = left[i + 1] + 1;
    
17.         }
    
18.         int d = 0;
    
19.         for(int i = 0; i < n; i++)
    
20.         {
    
21.             if(left[i] > 0 && right[i] > 0)
    
22.                 d = Math.max(d, Math.min(left[i], right[i]));
    
23.             else
    
24.                 d = Math.max(Math.max(left[i], right[i]), d);
    
25.         }
    
26.         return d;
    
27.     }

复制代码

851

1.     public int[] loudAndRich(int[][] richer, int[] quiet) {
   
2.         // reverse directions to find as subsets
   
3.         // sort subsets with quietness
   
4.         Map<Integer, Set<Integer>> map = new HashMap<>();
   
5.         int n = quiet.length;
   
6.         for(int i = 0; i < n; i++) map.put(i, new HashSet<>());
   
7.         for(int[] rich : richer)
   
8.         {
   
9.             map.get(rich[1]).add(rich[0]);
   
10.         }
    
11.         re = new int[n];
    
12.         Arrays.fill(re, -1);
    
13.         q = quiet;
    
14.         for(int i = 0; i < n; i++)
    
15.         {
    
16.             re[i] = findQ(i, map);
    
17.         }
    
18.         return re;
    
19.     }
    
20.    
    
21.     int[] re, q;
    
22.    
    
23.     int findQ(int k, Map<Integer, Set<Integer>> map)
    
24.     {
    
25.         if(re[k] >= 0)
    
26.             return re[k];
    
27.         
    
28.         int v = q[k], idx = k;
    
29.         for(int next : map.get(k))
    
30.         {
    
31.             int nextidx = findQ(next, map);
    
32.             if(v > q[nextidx])
    
33.             {
    
34.                 idx = nextidx;
    
35.                 v = q[nextidx];
    
36.             }
    
37.         }
    
38.         return idx;
    
39.     }

复制代码

佛了, 好像回复的帖子被check了..
849
没什么太多好说的, 一个是
```shift[i] += shift[i + 1] % 26```,
再一个是shift之后, 判断是否出界.
```if(c[i] > 'z') c[i] = (char)(c[i] - 26);```

850
基本上和做dominoes的方法差不多, 左右两个array, 看距离左边跟右边的最短距离. 如果是只有一边的话需要处理一下.
从左到右的处理方法
```
            if(seats[i] == 1) right[i] = 0;
            else if(i > 0 && right[i - 1] >= 0)
                right[i] = right[i - 1] + 1;
```
从右往左同理
851
基本上一个 dfs, 用一个global variable 做memoization即可, 记录当前index和它的子树的最小quietness. 这里我把richness反了一下, 差别不大.

今晚lintcode略简单啊，最后python居然mle了呵呵呵

democoffee 发表于 2018-6-16 10:57
今晚lintcode略简单啊，最后python居然mle了呵呵呵

爆炸， 我都不太会了。。

肥宅快乐水 发表于 2018-6-16 11:01
爆炸， 我都不太会了。。

啥都不说就是干。。上周阿里的很难偏acm了。。这周比较leetcode 风（其实我也是第一次玩lintcode）

democoffee 发表于 2018-6-16 11:04
啥都不说就是干。。上周阿里的很难偏acm了。。这周比较leetcode 风（其实我也是第一次玩lintcode）

你是真滴牛皮

吐槽下利口850吧： 这个 Segment tree 的方法要谁面试写出来 真是得给她跪下了：

https://leetcode.com/problems/rectangle-area-ii/solution/

好久没回头照顾这帖子了. 一部分原因是自己太菜了, 发现其实做不出来几道题.. 也不好意思班门弄斧.

但是总结就是提高, 所以决定还是把自己想法写下来..

https://www.lintcode.com/contest/41/

[lint821 | pass]
其实还想了挺多的. 先做的是scanline, 想用pq做. 然后发现不太会处理交汇时间, 就放弃了. 然后发现因为时间 (假设)是排序的, 所以就直接做2 pointer的方法. 如果两个interval 不相交, 就增加其中一个. 增加方法按start 排序. 如果相交的话, 交的interval 是 [max(a[0], b[0]), min(a[1], b[1])]. 相交之后该换哪个呢? 这段考虑了很久, 后来用的是 end time 排序. 其实也说的通, scheduling problem 都是按end 排序..

[lint898 | pass]
二分搜索每行里面1第一个出现的位置.

[lint1396 | fail]
很显然是一个union find 的题目, 但是我这里处理的非常不好, 一直 MLE, 就没做了.. 做法是造了一个 parent array, 以及parent set, O[n ^ 2]找后面每一个没有visit过的set, 用parent set 判断是否相交. 如果相交就把parent set合并起来.

[lint 722 | fail]
这题我用O[n ^ 2]的方法过了, 但是O[n]的方法是没想出来的..   大概想法是 Let's call A[i] = a_{0} ^ a_{1}^ ... ^ a_{i - 1}, thus target = find max (a_{i} ^ a_{i + 1} ^ ... ^ a_{j - 1}) = max(A[j] ^ A[i - 1]), where 0 <= i <= j <= n. Since A[j] is known at every step, then question boils down to finding the best A[j](^A[i*-1]). 然后就没想法了.. 不知道该怎么去找optimal A[i* - 1]

https://leetcode.com/contest/weekly-contest-92

[868 | pass]
比较直观的一道题， [col, row] = [row, col]即可

[866 | pass]
我用的是最直观的方法， 类似LCA的解法。 看左边与右边子树的深度， 如果一样即返回当前根。否则返回长的子树的那个subtree. 我直觉应该有一个更好的方法去做，不用每个点都看一次子树深度。 但是我知道这个方法一定过， 就懒得想了。

[867 | fail]
比较直接的方法去解， TLE。我看了一眼答案， 是说所有的8位数都不是prime， 可跳。。

[865 | fail]
其实没什么想法。。 也懒的想了