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;
    }
}

Leetcode 43. Multiply Strings

43. Multiply Strings

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 String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] pos = new int[m + n];
 
        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); 
                int p1 = i + j, p2 = i + j + 1;
                int sum = mul + pos[p2];
 
                pos[p1] += sum / 10; //进位 index从大到小,保证了所有位数都会调整
                pos[p2] = (sum) % 10; //调整
                //index越大,位数越小 是反向的
            }
        }  
 
        StringBuilder sb = new StringBuilder();
        for(int p : pos) 
            if(sb.length() != 0 || p != 0)  //排除开头为0的数组
                sb.append(p);
        return sb.length() == 0 ? "0" : sb.toString();
    }   
}

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;
        }
    }    
}

Leetcode 161. One Edit Distance

161. One Edit Distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if(s.length() > t.length()) 
            return isOneEditDistance(t, s);
        int m = s.length(), n = t.length();
        if(n - m > 1) return false;
        for(int i = 0; i < m; i++) {
            if(s.charAt(i) != t.charAt(i)) 
                return s.substring(i + 1).equals(t.substring(i + 1)) || s.substring(i).equals(t.substring(i + 1));
                // replace or delete(add)
        }
        return n > m; //n is one more than m
        // here is to determine there must be one edit distance 
        // equal condition doesn't count for true
    }
}