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页。

    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 285. Inorder Successor in BST

    285. Inorder Successor in BST

    中序遍历: 左中右
    sucessor: 下一个

    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 {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            TreeNode res = null;
            while(root!=null) {
                if(root.val > p.val) {
                    res = root;
                    root = root.left;
                }
                else root = root.right;
            }
            return res;
        }
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            if (root == null || p == null) {
                return null;
            }
            if (root.val <= p.val) {
                return inorderSuccessor(root.right, p);
            } else {
                TreeNode node = inorderSuccessor(root.left, p);
                return node != null ?  node :  root;
            }
        }    
    }