里口战拖 - 通向法斗的道路

最近一直都没怎么刷题，感觉离目标越来越远，赶紧开一贴督促自己~

目前概况：LC做了300多，但是断断续续感觉不够系统，而且也不是bug free一遍AC，很多时候都需要试好几遍。五月份回国两周，回来以后准备开始海投

女票说要养法斗，奈何囊中羞涩目前只是属于养自己阶段~估计，百题一法斗，十题一条腿吧

317. Shortest Distance from All Buildings
从每一个1的位置开始bfs，计算到每个0的距离。
AC的时间位于两个驼峰之间。。。不知道前面的AC是怎么写的。待研究 4/21

1. class Solution {
   
2.    
   
3.     private int[] dx = { 0, -1, 0, 1 };
   
4.     private int[] dy = { 1, 0, -1, 0 };
   
5.    
   
6.     public int shortestDistance(int[][] grid) {
   
7.         int row = grid.length, col = grid[0].length;
   
8.         int[][] count = new int[row][col];
   
9.         
   
10.         ArrayList<Integer> buildx = new ArrayList<>();
    
11.         ArrayList<Integer> buildy = new ArrayList<>();
    
12.         for(int i = 0; i < row; i++){
    
13.             for(int j = 0; j < col; j++){
    
14.                 if(grid[i][j] == 1){
    
15.                     buildx.add(i);
    
16.                     buildy.add(j);
    
17.                 }
    
18.                 if(grid[i][j] != 0){
    
19.                     count[i][j] = -1;
    
20.                 }
    
21.             }
    
22.         }
    
23.         
    
24.         for(int i = 0; i < buildx.size(); i++){
    
25.             bfs(grid, count, buildx.get(i), buildy.get(i));
    
26.         }
    
27.         
    
28.         int res = Integer.MAX_VALUE;
    
29.         for(int i = 0; i < row; i++){
    
30.             for(int j = 0; j < col; j++){
    
31.                 if(count[i][j] != - 1){
    
32.                     res = Math.min(res, count[i][j]);
    
33.                 }
    
34.             }
    
35.         }
    
36.         return res == Integer.MAX_VALUE ? -1 : res;
    
37.     }
    
38.    
    
39.     // (m,n) is 1
    
40.     private void bfs(int[][] grid, int[][] count, int m, int n){
    
41.         Queue<Integer> x = new LinkedList<>();
    
42.         Queue<Integer> y = new LinkedList<>();
    
43.         
    
44.         int row = grid.length, col = grid[0].length, steps = 0;
    
45.         int[][] distance = new int[row][col];
    
46.         distance[m][n] = -1;
    
47.         for(int i = 0; i < 4; i++){
    
48.             x.offer(m + dx[i]);
    
49.             y.offer(n + dy[i]);
    
50.         }
    
51.         
    
52.         while(x.size() > 0){
    
53.             int size = x.size();
    
54.             steps += 1;
    
55.             for(int i = 0; i < size; i++){
    
56.                 int px = x.poll();
    
57.                 int py = y.poll();
    
58.                 if(px < 0 || px >= row || py < 0 || py >= col || distance[px][py] != 0 || count[px][py] == -1) continue;
    
59.                 if(grid[px][py] != 0) {
    
60.                     distance[px][py] = -1;
    
61.                     continue;
    
62.                 }
    
63.                 distance[px][py] = steps;
    
64.                 for(int j = 0; j < 4; j++){
    
65.                     x.offer(px + dx[j]);
    
66.                     y.offer(py + dy[j]);
    
67.                 }
    
68.             }
    
69.         }
    
70.         
    
71.         for(int i = 0; i < row; i++){
    
72.             for(int j = 0; j < col; j++){
    
73.                 if(count[i][j] != -1){
    
74.                     if(distance[i][j] <= 0){
    
75.                         count[i][j] = -1;
    
76.                     }else{
    
77.                         count[i][j] += distance[i][j];
    
78.                     }
    
79.                 }
    
80.             }
    
81.         }
    
82.         
    
83.     }   
    
84. }

复制代码

769. Max Chunks To Make Sorted
768. Max Chunks To Make Sorted II

第一问没有仔细看题，直接理解成第二问的样子，想了半天用Stack解。看了解法以后才看懂题。面试大忌。
第二问贴个解法上来。速度貌似很慢，应该是O(2N)的样子吧？Java中木有C#中的Tuple，有点郁闷...

1. class Solution {
   
2.      class Tuple<A, B> {
   
3.         A a;
   
4.         B b;
   
5.         public Tuple(A a, B b){
   
6.             this.a = a;
   
7.             this.b = b;
   
8.         }
   
9. 
   
10.         public A getMin(){
    
11.             return this.a;
    
12.         }
    
13. 
    
14.         public B getMax(){
    
15.             return this.b;
    
16.         }
    
17.     }
    
18.    
    
19.     public int maxChunksToSorted(int[] arr) {
    
20.         Stack<Tuple<Integer, Integer>> stack = new Stack<>();
    
21.         if(arr==null||arr.length==0) return 0;
    
22.         stack.push(new Tuple<Integer, Integer>(arr[0], arr[0]));
    
23.         for(int i = 1; i < arr.length; i++){
    
24.             Tuple<Integer, Integer> tmp = stack.peek();
    
25.             if(arr[i] >= tmp.getMax()) {
    
26.                 stack.push(new Tuple<Integer, Integer>(arr[i], arr[i]));
    
27.             }else if(arr[i] >= tmp.getMin()){
    
28.                 continue;
    
29.             }else{
    
30.                 tmp = stack.pop();
    
31.                 int curMax = tmp.getMax();
    
32.                 while(stack.size() > 0 && stack.peek().getMax() > arr[i]){
    
33.                     tmp = stack.pop();
    
34.                 }
    
35.                 int curMin = Math.min(tmp.getMin(), arr[i]);
    
36.                 stack.push(new Tuple<Integer, Integer>(curMin, curMax));
    
37.             }
    
38.         }
    
39.         return stack.size();
    
40.     }
    
41. }

复制代码

很久没来，最近回国又忙了一点其他的事情，今儿开始继续。。。

826. Most Profit Assigning Work：
排序，更新每个difficulty可以达到的最大profit，然后二分查找。 排序： 难度从低到高，profit从高到低；二分查找的时候考虑right=0的edge case

221. Maximal Square: 先用brute force解的，mn square的复杂度，居然木有超时。。。dp
652. Find Duplicate Subtrees:  dfs; computeIfAbsent(), 第一次见，高端了

775. Global and Local Inversions:

1. class Solution {
   
2.     public boolean isIdealPermutation(int[] A) {
   
3.         int n = A.length;
   
4.         int curMax = 0;
   
5.         for(int i = 0; i < n; i++){
   
6.             if(i != 0 && curMax >= A[i]) continue;
   
7.             curMax = Math.max(curMax, A[i]);
   
8.             for(int j = i+2; j < n; j++){
   
9.                 if(A[j] < A[i]) return false;
   
10.             }
    
11.         }
    
12.         return true;
    
13.     }
    
14. }

复制代码

运气好了可以过，还是看答案吧。。。[/i][/i][/i]
464. Can I Win：187ms，没用bitwise operation，就酱了。。。
735. Asteroid Collision： stack
542. 01 Matrix: bfs
718. Maximum Length of Repeated Subarray: dp

[i][i]6/12
[/i][/i]

394. Decode String

s = "3[a2[c]]", return "accaccacc".
两个stack04/18

62 63 Unique Paths 1/2

dp 一维数组

697. Degree of an Array

Easy题。只是没想到这题真的需要三个hashmap 20行代码，以为10行左右应该可以搞定的。

4/19

331. Verify Preorder Serialization of a Binary Tree

两种解法：
1. stack: https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78566/Java-intuitive-22ms-solution-with-stack
2. parent-child的个数： https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78551/7-lines-Easy-Java-Solution

第二种方法可以简单的扩展到postorder上。

1.     public boolean isValidSerialization(String postorder) {
   
2.         String[] tree = postorder.split(",");
   
3.         int diff = 0;
   
4.         for(String s : tree){
   
5.             diff -= 1;
   
6.             if(diff > -1) return false;
   
7.             if(!s.equals("#")) diff += 2;
   
8.         }
   
9.         return diff == -1;
   
10.     }

复制代码

4/19

348. Design Tic-Tac-Toe

O(N*N) 和 O(N) space 两个解， 不觉得这个是个design问题

4/19

449. Serialize and Deserialize BST

preorder的做法 跟331有点像 deserialize的时候通过二分找到右子树 感觉比NlgN快一点 应该介于 N 和 NlgN之间

有空回来看 297. Serialize and Deserialize Binary Tree

4/20

297. Serialize and Deserialize Binary Tree

1. private int index = 0;
   
2. 
   
3. // Decodes your encoded data to tree.
   
4.     public TreeNode deserialize(String data) {
   
5.         if(data == null || data.length() == 0) return null;
   
6.         this.index = 0;
   
7.         String[] tree = data.split(",");
   
8.         return dePreorder(tree);
   
9.     }
   
10.    
    
11.     private TreeNode dePreorder(String[] tree){
    
12.         // if(index >= tree.length) return null;
    
13.         if(tree[index].equals("#")) {
    
14.             index++;
    
15.             return null;
    
16.         };
    
17.         TreeNode node = new TreeNode(Integer.parseInt(tree[index++]));
    
18.         node.left = dePreorder(tree);
    
19.         node.right = dePreorder(tree);
    
20.         return node;
    
21.     }

复制代码

有这样的一个class variable感觉会简单很多吧，不过题目要求 Do not use class member/global/static variables to store states.
但是每次都reset index不是也就相当于没有state么？

4/20

3. Longest Substring Without Repeating Characters

map里放出现的次数 或者出现的位置

4/21