比赛review帖

每周都打一下比赛, 有时候觉得自己倍牛逼就想炫耀, 有时候觉得自己特sb什么也不会.

这个帖子里自己给自己做总结, 每周的比赛题目.

主要是lintcode 和 leetcode吧! 加油!

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.     }

复制代码

miugel 发表于 2018-7-15 10:22
这周发挥比较好，四道题都能直接有思路，最后一道题写错了个地方，最后整体WA了一次。

1. 直接从右往左 ...

刚看了一眼题目， 确实不难. 基本解法跟你差不多。。

[868]
做binary shift， 如果当前是1即更新最长gap

[869]
预处理所有2^n, 排序后放入Set<String>. 对N排序后寻找string

[870]
我对着B做了一次排序，因为要求返回的跟原始B的数字一一对应。
用TreeMap记录A中数字， 找ceiling element。如果没有返回firstkey

[871]
这题我之前见过， 是POJ2431
用PQ就可以做了。
```
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int sumfuel = startFuel;
        Queue<int[]> q = new PriorityQueue<>((a, b) -> (b[1] - a[1]));
        int i = 0, n = stations.length, re = 0;
        sumfuel = startFuel;
        while(i < n && stations[i][0] <= sumfuel) q.offer(stations[i++]);  // will visit these from starting position
        while(sumfuel < target && !q.isEmpty())
        {
            // now add fuel
            if(!q.isEmpty())
            {
                sumfuel += q.poll()[1];
                re++;
            }
            // run again
            while(i < n && stations[i][0] <= sumfuel) q.offer(stations[i++]);  // will visit these stations
        }
        if(sumfuel >= target) return re;
        return -1;
    }
```

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

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

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]

我也每周打leetcode，目标8月前存够积分换件衣服。。。共勉

democoffee 发表于 2018-6-7 11:30
我也每周打leetcode，目标8月前存够积分换件衣服。。。共勉

加油加油，12周每周前200就拿到了！我发现h不出意外如果答的够快3道题差不多能进100-200，然后4道肯定前100的(

肥宅快乐水 发表于 2018-6-8 00:03
加油加油，12周每周前200就拿到了！我发现h不出意外如果答的够快3道题差不多能进100-200，然后4道肯定前1 ...

楼主不行啊。。12*50 = 600啊 得120周。。。

我也打比赛。。因为自己太菜了 想每周过来教育一下自己「怎么这种题都不会」
共勉。。

democoffee 发表于 2018-6-8 00:54
楼主不行啊。。12*50 = 600啊 得120周。。。

尴尬！看来我只能两年后拿体恤了(

有没有人建个群,大家讨论交流

肥宅快乐水 发表于 2018-6-8 06:38
尴尬！看来我只能两年后拿体恤了(

两年是upper bound，说不定哪次运气好，排到前三的话，速度就极大加速了。

佛了， 今天lintcode爆炸。。 只做出来第一道。。

···
        map.put(0, -1);
        for(int i = 0, k = 0; i < n; i++)
        {
            if(S.charAt(i) == 'A') k++;
            else k--;
            if(map.containsKey(k)) len = Math.max(len, i - map.get(k));
            else map.put(k, i);
        }
···

肥宅快乐水 发表于 2018-6-8 20:11
佛了， 今天lintcode爆炸。。 只做出来第一道。。

···

我也来跟lz打个卡。。

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