# Blog

## Leetcode 406. Queue Reconstruction by Height

This is a classic problem. The solution is easy but heuristic.
Firstly, we can attach the code here.
Leetcode406

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int[][] reconstructQueue(int[][] people) { if (people == null || people.length == 0 || people[0].length == 0) { return people; }   Arrays.sort(people, (a, b)->a[0]==b[0]?a[1]-b[1]:b[0]-a[0]);   List<int[]> temp = new ArrayList<>(); for (int[] pp : people) { temp.add(pp[1], pp); }   int[][] res = new int[people.length][2]; for (int i = 0; i < people.length; i++) { res[i][0] = temp.get(i)[0]; res[i][1] = temp.get(i)[1]; } return res;   } }```
• Time complexity: O(n^2)
• Space Complexity: O(n)
• This is not the best one, which the best time complexity can be achieved by BST.

## Algorithm Analysis

We can easily know that for the shortest one standing backmost, pair[1] is his correct location in the final answer. In other words, there is no relationship between this person and others.
We can eliminate this person and the problem of n people is converted to subproblem of (n-1) people. And another step is to insert this person based on his pair[1].
Based on this way, we can compress the problem until only one person. It is easy to implement in this way.

## Java Basics

1. Visibility of Java modifiers

public accessed to all components
protected accessed to all components in the same package and subclass in the different package
default accessed to all components in the same package
private accessed only to the components in the same package

2. final, finally, finalize

final means once the reference is assigned, it cannot be reassigned

• for class, it cannot be inherited
• for method, it cannot be overiden
• for variable, it cannot be modified
• 3.synchronized

Synchronized methods:

• When a thread executes synchronized methods of one object, any other thread which is going to execute any synchronized methods in this object is blocked.
• hapopens-before state is stored, so the change of states can be visible to all threads.
• Synchronized objects:

• hapopens-before state is stored, so the change of states can be visible to all threads.

## Look up the listener of ports

lsof -i:[port num]
`lsof -i:3306`

## Some notes about stack! Mainly register based!

ESP in stack

ESP是指得栈顶指针。
由于寄存器的长度32bit，所以对寄存器压栈出栈的内存esp改变量都是4byte，即4个地址单位。

Transfer from user mode to kernel mode

CS:IP cs是代码段寄存器，保存了代码段的基址，IP是指令指针,保存了当前指令的offset

### 系统调用

系统在通过系统调用,有用户态切换到内核态时，需要把参数和系统调用号传递到内核态，通过寄存器实现。
具体的，通过eax传输调用号，通过其他通用寄存器传输参数，根据寄存器的限制，最多系统调用只能传递5个参数。
当需要更多的参数，或者更大的数据传输时，通过传递一个pointer to a user-mode address which contains the other parameters到寄存器
参考LKD第三版，73页，74页。

## Leetcode 721. Accounts Merge

### 721. Accounts Merge

#### BFS

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution { public List<List<String>> accountsMerge(List<List<String>> accounts) { Map<String, String> emailToName = new HashMap(); Map<String, ArrayList<String>> graph = new HashMap(); for (List<String> account: accounts) { String name = account.get(0); for (int i =1; i<account.size(); i++) { String email = account.get(i); graph.computeIfAbsent(email, x-> new ArrayList<String>()).add(account.get(1)); //return the ref tp a new Arraylist.add(..) //also the key value pair is put to map graph.computeIfAbsent(account.get(1), x-> new ArrayList<String>()).add(email); //反向链接 emailToName.put(email, name); } } //graph是类似邻接链表的有向图结构，只包含email //emailToName 记录了邮件名到给定名字的映射   Set<String> seen = new HashSet(); List<List<String>> ans = new ArrayList(); for (String email: graph.keySet()) { if (seen.add(email)) { Deque<String> stack = new LinkedList<>(); stack.push(email); List<String> component = new ArrayList(); //Use bfs to search neighbours while (!stack.empty()) { String node = stack.pop(); component.add(node); for (String nei: graph.get(node)) { if (!seen.contains(nei)) { seen.add(nei); stack.push(nei); } } } Collections.sort(component); component.add(0, emailToName.get(email)); ans.add(component); } } return ans; } }```

#### Union Find

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution { public List<List<String>> accountsMerge(List<List<String>> accounts) { DSU dsu = new DSU(); Map<String, String> emailToName = new HashMap(); Map<String, Integer> emailToID = new HashMap(); int id = 0; for (List<String> account: accounts) { String name = ""; for (String email: account) { if (name == "") { name = email; continue; } emailToName.put(email, name); if (!emailToID.containsKey(email)) { emailToID.put(email, id++); } dsu.union(emailToID.get(account.get(1)), emailToID.get(email)); } }   Map<Integer, List<String>> ans = new HashMap(); for (String email: emailToName.keySet()) { int index = dsu.find(emailToID.get(email)); ans.computeIfAbsent(index, x-> new ArrayList()).add(email); } for (List<String> component: ans.values()) { Collections.sort(component); component.add(0, emailToName.get(component.get(0))); } return new ArrayList(ans.values()); } } class DSU { int[] parent; public DSU() { parent = new int[10001]; for (int i = 0; i <= 10000; ++i) parent[i] = i; } public int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } public void union(int x, int y) { parent[find(x)] = find(y); } }```

## File system

总结了一下文件系统：（linux三大系统之一）
首先推荐一篇不错的入门文章，适合有一定基础的同学看一下。
Anatomy of the Linux file system
讲解了linux文件系统的基本架构。

User mode -> sys call -> VFS -> individual file system -> dentry and inode cache -> buffer cache (mainly io) -> block devices

然后，应当熟悉几个常用的文件系统函数(libc为例）
熟悉重点的kernel数据结构

Inode
Dentry
Block
Super-block

当然，权限管理也是很重要的一部分，常见的命令chmod要会使用。

## Leetcode 44. Wildcard Matching

### 377. Combination Sum IV

#### DP

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 public class Solution { public boolean isMatch(String s, String p) { boolean[][] match=new boolean[s.length()+1][p.length()+1]; match[s.length()][p.length()]=true; for(int i=p.length()-1;i>=0;i--){ if(p.charAt(i)!='*') break; else match[s.length()][i]=true; //倒着走 } for(int i=s.length()-1;i>=0;i--){ for(int j=p.length()-1;j>=0;j--){ if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?') match[i][j]=match[i+1][j+1]; else if(p.charAt(j)=='*') match[i][j]=match[i+1][j]||match[i][j+1]; // match[i][j]=match[i+1][j] means * match form XXX to XXX[i] // match[i][j]=match[i][j+1] means * match *empty* else match[i][j]=false; } } return match[0][0]; } }```

#### Two pointer

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public boolean isMatch(String s, String p) { int i = 0; int j = 0; int lastStar = -1; int lastMatch = -1; while(i < s.length()){ if(j<p.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?')){ i++; j++; }else if(j<p.length() && p.charAt(j) == '*'){ lastStar = j; lastMatch = i; j++; // consider the * would mean empty }else if(lastStar != -1){ j = lastStar+1; // i = ++lastMatch; }else{ return false; } } while(j < p.length() && p.charAt(j) == '*') j++; return j == p.length(); } }```

## Leetcode 377. Combination Sum IV

### 377. Combination Sum IV

#### Top-down DP

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int combinationSum4(int[] nums, int target) { int[] comb = new int[target + 1]; comb[0] = 1; for (int i = 1; i < comb.length; i++) { for (int j = 0; j < nums.length; j++) { if (i - nums[j] >= 0) { comb[i] += comb[i - nums[j]]; } } } return comb[target]; } }```

#### Bottom up Memoication

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { private int[] dp;   public int combinationSum4(int[] nums, int target) { dp = new int[target + 1]; Arrays.fill(dp, -1); dp[0] = 1; return helper(nums, target); }   private int helper(int[] nums, int target) { if (dp[target] != -1) { return dp[target]; } int res = 0; for (int i = 0; i < nums.length; i++) { if (target >= nums[i]) { res += helper(nums, target - nums[i]); } } dp[target] = res; return res; } }```

## Leetcode 670. Maximum Swap

### 670. Maximum Swap

#### DP

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int maximumSwap(int num) { String str = num + ""; int[] table = new int[str.length()]; int maxIndex = str.length()-1; for(int i = str.length() -1; i>=0; i--){ if(str.charAt(i) >= str.charAt(maxIndex) || i == str.length()-1){ table[i] = i; if(str.charAt(i) > str.charAt(maxIndex)) maxIndex = i; }else{ table[i] = maxIndex; } } System.out.println(Arrays.toString(table)); for(int i =0; i<str.length(); i++){ if(table[i] != i){ return Integer.parseInt(str.substring(0,i) +str.charAt(table[i]) + str.substring(i+1,table[i]) + str.charAt(i) + str.substring(table[i]+1)); } } return num; } }```

#### Bucket

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int maximumSwap(int num) { char[] digits = Integer.toString(num).toCharArray();   int[] buckets = new int[10]; for (int i = 0; i < digits.length; i++) { buckets[digits[i] - '0'] = i; }   for (int i = 0; i < digits.length; i++) { for (int k = 9; k > digits[i] - '0'; k--) { if (buckets[k] > i) { char tmp = digits[i]; digits[i] = digits[buckets[k]]; digits[buckets[k]] = tmp; return Integer.valueOf(new String(digits)); } } }   return num; } }```