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:

  • any access to this object is blocked
  • hapopens-before state is stored, so the change of states can be visible to all threads.
  • 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为例)
    read, write, stat, open, close
    熟悉重点的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;
        }
    }