手动开始90天刷题计划

在职, 但刷题不可少。计划1/21/2018  - 4/21/2018
准备第一遍， 周末每天15题，工作日每天5题。

现在也偏senior了，适当也会兼顾design。

可以和楼主一起刷题么？

主要准备Linkedin和Uber的题库

超高频必考

Nested List Weight Sum Easy        Real        1/21        LC 339 DFS
Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list -- whose elements may also be integers or other lists. Example 1:Given the list [[1,1],2,[1,1]], return 10. (four 1's at depth 2, one 2 at depth 1) Example 2: Given the list [1,[4,[6]]], return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27)       
思路就是写一个help function, 传入它的层数，如果是整数则， sum加入层数乘以整数值，否则加上递归下一层。
https://leetcode.com/problems/nested-list-weight-sum/description/

1. class Solution {
   
2.     public int depthSum(List<NestedInteger> nestedList) {
   
3.         return   depthSum(nestedList, 1);
   
4.     }
   
5.    
   
6.     public int depthSum(List<NestedInteger> nestedList, int level) {
   
7.         int sum = 0;
   
8.         for (NestedInteger item : nestedList) {
   
9.             if(item.isInteger()) {
   
10.                 sum += level * item.getInteger();
    
11.             } else {
    
12.                 sum += depthSum(item.getList(), level + 1);
    
13.             }
    
14.         }
    
15.         return sum;
    
16.     }
    
17. }

复制代码

       

                                                                               

超高频必考

Shortest Word Distance II Medium        Real        1/21        LC 244 Hash Table
This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it? Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list. For example,  Assume that words = ["practice", "makes", "perfect", "coding", "makes"]. Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = "makes", word2 = "coding", return 1. Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
思路就是用一个hashmap存word对应的position list， 然后在查找function里面two pointer求shortest.
https://leetcode.com/problems/shortest-word-distance-ii/description/

1. class WordDistance {
   
2.     Map<String, List<Integer>> map;
   
3.    
   
4.     public WordDistance(String[] words) {
   
5.         map = new HashMap<>();
   
6.         for (int i = 0; i < words.length; i++) {
   
7.             if(!map.containsKey(words[i])) {
   
8.                 map.put(words[i], new ArrayList<Integer>());
   
9.             }
   
10.             map.get(words[i]).add(i);
    
11.         }
    
12.     }
    
13.    
    
14.     public int shortest(String word1, String word2) {
    
15.         List<Integer> list1 = map.get(word1);
    
16.         List<Integer> list2 = map.get(word2);
    
17.         int shortest = Integer.MAX_VALUE;
    
18.         int index1 = -1;
    
19.         int index2 = -1;
    
20.         for(int i = 0, j = 0; i < list1.size() && j < list2.size();) {
    
21.             index1 = list1.get(i);
    
22.             index2 = list2.get(j);
    
23.             if(index1 > index2) {
    
24.                 shortest = Math.min(shortest, index1 - index2);
    
25.                 j++;
    
26.             } else {
    
27.                 shortest = Math.min(shortest, index2 - index1);
    
28.                 i++;
    
29.             }
    
30.         }
    
31.         return shortest;
    
32.     }
    
33. }
    
34. 
    
35. /**
    
36. * Your WordDistance object will be instantiated and called as such:
    
37. * WordDistance obj = new WordDistance(words);
    
38. * int param_1 = obj.shortest(word1,word2);
    
39. */

复制代码

超高频必考

Nested List Weight Sum II Medium        Real        1/21        LC 364  DFS
Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list -- whose elements may also be integers or other lists. Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight. Example 1: Given the list [[1,1],2,[1,1]], return 8. (four 1's at depth 1, one 2 at depth 2) Example 2: Given the list [1,[4,[6]]], return 17. (one 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17)   
思路就是观察这些数据层数越少的加的次数越多，可以用两个变量一个叫weighted, unweighted，weighted每走一层加一次unweighted这样就好了，注意用一个新的arraylist存每层的元素。
https://leetcode.com/problems/nested-list-weight-sum-ii/description/

1. class Solution {
   
2.     public int depthSumInverse(List<NestedInteger> nestedList) {
   
3.        int unweighted = 0;
   
4.        int weighted = 0;
   
5.        while(!nestedList.isEmpty()) {
   
6.            List<NestedInteger> list = new ArrayList<>();
   
7.            for(NestedInteger item : nestedList) {
   
8.                if (item.isInteger()) {
   
9.                    unweighted += item.getInteger();
   
10.                } else {
    
11.                    list.addAll(item.getList());
    
12.                }
    
13.            }
    
14.            nestedList = list;
    
15.            weighted += unweighted;
    
16.        }
    
17.        return weighted;
    
18.     }
    
19. }

复制代码