面试刷题咯～每天10道～

从12.18开始有Google等面试，特此开帖刷题。会把每日刷题的题号及思维过程放在这。求加大米。

加油加油 拿大包裹！！

寒假跟进楼主刷题 加油

楼主加油, 我也在刷题

地里面经：https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=461716&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3089%5D%5Bvalue%5D%5B2%5D%3D2%26searchoption%5B3089%5D%5Btype%5D%3Dcheckbox%26searchoption%5B3046%5D%5Bvalue%5D%3D1%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311%26orderby%3Ddateline&_dsign=8251b7c6
Leetcode 852 Peak Index in a Mountain Array

这道题很简单，其实就是peak finding，也就可以用binary search的思想。
我在之前刷leetcode时总觉得很奇怪为什么能够用binary search来做这种题，总感觉如果不遍历一遍就心里不踏实。只是把这个当做一个公式来用。
后来我仔细 想了想，发现背后的intuition是：
只要存在peak，那么就会有左边和右边小于中间的情况。

这样的话，binary search只要发现有上升和下降的时候就会锁定一块区间，然后慢慢挪过去，最终找到我们想要的值。这也是为什么binary search能够不需要遍历整个数组就能够完成peak finding的任务。

Leetcode 281 Zigzag Iterator
在此题discussion板块有很多人直接用iterator class, 个人感觉面试中如果要求你实现一个iterator应该是不能使用已有的iterator的。希望有小伙伴来回答回答~
因为只有两个list，所以我们可以创建两个int变量来记录两个list目前的进度。还有一个boolean变量来记录目前需要返回的值在哪一个list中。
在hashnext中只需要判断是否两个list都不小于总长度了，是就直接false。
在next中，先把之前的boolean变量reverse一下，说明我们进入下一个list，然后分别给两个if语句。
第一个if 判断index1 是否小于list1的长度 而且 （boolean为true，或者是list2满了）
第二个if 判断index2 是否小于list2的长度 而且 （boolean为false，或者是list1满了）

这样就完成啦~
但我在想，因为这种方法是需要把两个list储存起来，如果数据量大的话，这样是不现实的。应该只能保存iterator。如果是iterator的话，可以用一个linkedlist,讲两个iterator存在一个list里。需要用的时候就remove出来，只要不是empty的，就在add进去，就会在linkedlist的尾端。这样，下次remove就是另一个vector了。

1. public class ZigzagIterator {
   
2.     int i1 = 0;
   
3.     int i2 = 0;
   
4.    
   
5.     boolean flag = false;
   
6.    
   
7.     List<Integer> l1;
   
8.     List<Integer> l2;
   
9.    
   
10.     public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
    
11.         l1 = v1;
    
12.         l2 = v2;
    
13.     }
    
14. 
    
15.     public int next() {
    
16.         flag = !flag;
    
17.         
    
18.         if (i1 < l1.size() && (flag  || i2 >= l2.size()))
    
19.             return l1.get(i1++);
    
20.             
    
21.         if (i2 < l2.size() && (!flag || i1 >= l1.size()))
    
22.             return l2.get(i2++);
    
23.         
    
24.         return -1;
    
25.     }
    
26. 
    
27.     public boolean hasNext() {
    
28.         return i1 < l1.size() || i2 < l2.size();
    
29.     }
    
30. }

复制代码

Leetcode 200 Number of Islands
我现在一看到connected就本能反应UnionFind;
遍历一遍整个grid,如果是0就直接continue；如果是1就判断它的上下左右，如果上下左右为1，就分别union他们。
在Union find的实现过程中，我们首先遍历一遍，count一遍所有出现的1。 之后没Union一次就减少一个。这样一来，count的值就是最后岛屿的数量。
代码如下

1. class Solution {
   
2.     class unionFind{
   
3.         int[] id;
   
4.         int count = 0;
   
5.         
   
6.         public unionFind(char[][] grid)
   
7.         {
   
8.             int rows = grid.length;
   
9.             int cols = grid[0].length;
   
10.             id = new int[rows*cols];
    
11.             for(int i=0;i<rows;i++)
    
12.             {
    
13.                 for(int j=0;j<cols;j++)
    
14.                     if(grid[i][j] == '1')
    
15.                         count++;
    
16.             }
    
17.             
    
18.             
    
19.             for(int i=0;i<rows*cols;i++)
    
20.             {
    
21.                 id[i] = i;
    
22.             }
    
23.         }
    
24.         
    
25.         
    
26.         public int find(int p)
    
27.         {
    
28.             while(p != id[p]) {
    
29.                 id[p] = id[id[p]];
    
30.                 p = id[p];
    
31.             }
    
32.             return p;
    
33.         }
    
34.         
    
35.         public void union(int x, int y)
    
36.         {
    
37.             int rootx = find(x);
    
38.             int rooty = find(y);
    
39.             
    
40.             if(rootx!=rooty)
    
41.             {
    
42.                 id[rootx] = rooty;
    
43.                 count--;
    
44.             }else
    
45.                 return;
    
46.                
    
47.         }
    
48.     }
    
49.    
    
50.    
    
51.    
    
52.     public int numIslands(char[][] grid) {
    
53.         if(grid.length == 0 || grid[0].length == 0) return 0;
    
54.         unionFind uf = new unionFind(grid);
    
55.         int rows = grid.length;
    
56.         int cols = grid[0].length;
    
57.         for(int i=0;i<rows;i++)
    
58.         {
    
59.             for(int j=0;j<cols;j++)
    
60.             {
    
61.                 if(grid[i][j] != '1')
    
62.                 {
    
63.                     continue;
    
64.                 }else
    
65.                 {
    
66.                     if(i-1 >= 0 && grid[i-1][j] == '1')
    
67.                     {
    
68.                         int cur = i*cols + j;
    
69.                         int connect = (i-1)*cols + j;
    
70.                         uf.union(cur,connect);
    
71.                     }
    
72.                     if(j-1 >= 0 && grid[i][j-1] == '1')
    
73.                     {
    
74.                         int cur = i*cols + j;
    
75.                         int connect = i*cols + j-1;
    
76.                         uf.union(cur,connect);
    
77.                     }
    
78.                     if(i+1 < rows && grid[i+1][j] == '1')
    
79.                     {
    
80.                         int cur = i*cols + j;
    
81.                         int connect = (i+1)*cols + j;
    
82.                         uf.union(cur,connect);
    
83.                     }
    
84.                     if(j+1 < cols && grid[i][j+1] == '1')
    
85.                     {
    
86.                         int cur = i*cols + j;
    
87.                         int connect = i*cols + j+1;
    
88.                         uf.union(cur,connect);
    
89.                     }
    
90.                 }
    
91.             }
    
92.         }
    
93.         return uf.count;
    
94.     }
    
95. }

复制代码

[/i][/i][/i][/i][/i]

楼主加油！
关于281我是自己新建了一个class来打包list和i，然后用queue来实现zigzag，我觉得这样可以很好的拓展到k个输入

shaonan 发表于 2018-12-1 01:07
楼主加油！
关于281我是自己新建了一个class来打包list和i，然后用queue来实现zigzag，我觉得这样可以很好 ...

嗯嗯，是的。你也加油！如果要拓展到N个，用iterator的话更方便实现，方法应该是和我上面写的一样。但如果是保存data的话，queue确实很方便去实现。

Leetcode 489 Robot Room Cleaner
这题是一个难度hard的题，同时也经常看到在面经里出现。
这个题的难点个人认为在于没有给房间的环境和起始点，也就是说你需要去维护一个相对坐标来查看你是否之前已经visited（做DFS的时候）。
但是我们可以默认我们的起始点在（0，0），基于这个我们来做DFS。如果向上，y坐标+1, 反之-1；
这里我用hashset<String>来保存之前visit过的点。格式是“x,y”。
写一个dfs函数，从0，0开始走， 每到一个点，clean 然后从各方向走一遍move一次。当一个点走完的时候，要回到之前那个点。

1. class Solution {
   
2.    
   
3.     int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
   
4.     public void cleanRoom(Robot robot) {
   
5.         Set<String> visited = new HashSet<>();
   
6.         visited.add("0-0");
   
7.         
   
8.         dfs(robot, 0, 0, 0, visited);
   
9.     }
   
10.    
    
11.     // [x, y] is the relative position from the initial point
    
12.     private void dfs(Robot robot, int x, int y, int curDir, Set<String> visited) {
    
13.         
    
14.         robot.clean();
    
15.         for (int i = 0; i < 4; i++) {
    
16.             int nextDir = (curDir + i) % 4;
    
17.             int newX = x + dirs[nextDir][0];
    
18.             int newY = y + dirs[nextDir][1];
    
19.             
    
20.             if (!visited.contains(newX + "-" + newY) && robot.move()) {
    
21.                 visited.add(newX + "-" + newY);
    
22.                 dfs(robot, newX, newY, nextDir, visited);
    
23.             }
    
24.             
    
25.             robot.turnRight();
    
26.         }
    
27.         
    
28.         robot.turnRight();
    
29.         robot.turnRight();
    
30.         robot.move();
    
31.         robot.turnRight();
    
32.         robot.turnRight();
    
33.     }
    
34. }

复制代码

Leetcode 100 Same Tree
也是很简单的一道题。首先看是否p,q都是null,若是，直接返回true,如果其中一个是，则false, 然后再比较p,q 的val,如果val不相等 return false。再递归调用p左边和q左边，p右边和q右边。

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     public boolean isSameTree(TreeNode p, TreeNode q) {
    
12.         //left
    
13.         if(p == null && q==null)
    
14.             return true;
    
15.         if(p == null || q == null)
    
16.             return false;
    
17.         
    
18.         if(p.val != q.val)
    
19.             return false;
    
20.         
    
21.         while(p.val == q.val)
    
22.         {
    
23.             return isSameTree(p.left,q.left) &&isSameTree(p.right,q.right);
    
24.         }
    
25.         
    
26.         return true;
    
27.     }
    
28.    
    
29.    
    
30. }

复制代码

面经：给定一个bytes的大小，和packet的capacity，要不output最有的packet发送方案？但是有两个goal: 1)减少packets的数量2）减少packet中最大值。
比如bytes是30，capacity是9。 那么最佳的方案是8，8，8，6 即用4个packet，packet中最大的为8。 如果是9，9，9，3则不行，因为最大的为9.

这道题我的思路是，首先将每个包填满，然后看有多少个packet，这个packet数量肯定是最少的。然后再去分配packet中bytes个数。
首先我们知道最后一个packet的数量是最少，即少于9.（上面那个例子）
我们最多把这个值升到8，否则就不能满足减少最大bytes数的要求了。
那么我们就有8-3=5 的上升空间。因为这些空间都是从之前填满的packet中来的，我们可以算出，每个packet减少多少bytes：5/3 = 1
那么我们就得到8，8，8，6了

1.   public static int[] optimize_packets(int bytes, int capacity)
   
2. {
   
3.         int smallest_packets = bytes/capacity; // 30/9 = 3;
   
4.         if(bytes%capacity != 0)
   
5. {
   
6.                 smallest_packets+=1; //4
   
7. 
   
8.         }else
   
9. {
   
10.         int[] res = new int[smallest_packets];
    
11.         for(int re: res)
    
12.                 re = capacity;
    
13. 
    
14.         return res;
    
15. }       
    
16. 
    
17.         int last_packet_bytes = bytes - capacity*(smallest_packets-1); //30 -9*3 = 3
    
18.         int increase_space = capacity-1-last_packet_bytes;
    
19. //9-1-3 =5       
    
20.         int decrese_each_pack = increase_space/(smallest_packets-1);
    
21.         // 5/3 = 1;
    
22.         int[] res = new int[smallest_packets];
    
23.         for(int i=0;i<smallest_packets-1;i++)
    
24.         {
    
25.                 res[i] = capacity - decrese_each_pack;
    
26.                 //8,8,8,6
    
27.         }
    
28. 
    
29.         res[smallest_packets-1] = last_packet_bytes + decrese_each_pack*(smallest_packets-1);
    
30.         // 3+1*3 = 6
    
31.         return res;
    
32.                
    
33. }

复制代码

link: https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=462021&extra=&page=1&_dsign=a716aee6
刚刚在地里看到一个面经。有一个sorted array, 要求返回一个arr是之前arr元素的平方且是sorted

lz一开始的想法很naive，直觉是先square每个元素再sort。但在上面的链接里， dengzeyu147提出的方法很不错。
然后我准备根据这个自己再重新写一遍思路和代码。
因为会有负数的出现，所以有可能负数部分的元素在平方后会出现在最终结果的右边。比如[-8, -4, 1, 2]=》[1, 4, 16, 64]
我们需要比较负数平方和正数平方。
但因为input是一个sort好的input， 我们可以先从负数最小 和正数最大开始比较，然后设置好两个pointer，如果一方大于另一方，则挪动指针，把大的那一方放到结果里。最后因为负数部分和正数部分的长度可能会不一样，我们需要最后处理一下长度长的那一部分剩余的。

1.   public static int[] square(int[] input)
   
2. {
   
3.         int[] res = new int[input.length];
   
4. 
   
5.         int left = 0;
   
6.         int right = input.length-1;
   
7.        
   
8. int index = input.length -1;
   
9. 
   
10. while(input[left] < 0 && input[right] >= 0)
    
11. {
    
12.         if(input[left]*input[left] > input[right]*input[right])
    
13.         {//16>9
    
14.                 res[index--] = input[left]*input[left];
    
15.                 left++;
    
16.         }
    
17. else
    
18.         {
    
19.                 res[index--] = input[right]*input[right];
    
20.                 right--;
    
21.         }
    
22. }
    
23. 
    
24. while(input[left] < 0 && left < input.length)
    
25. {
    
26.         res[index--] = input[left]*input[left];
    
27.         left++;
    
28. }
    
29. 
    
30. while(input[right] >= 0 && right < input.length)
    
31. {
    
32.         res[index--] = input[right]*input[right];
    
33.         right--;
    
34. }
    
35. return res;
    
36. }

复制代码