滋衣螺古如普

Posted on | Edited on | In | | Views:
Symbols count in article: 41k | Reading time ≈ 42 mins.

迎难而上，祝我好运。

字符串长度

  • 要求不能用length内建方法。

    1
    2
    3
    4
    5
    6
    private int getStrLen(String str) {
        if (str == null || str.equals("")) {
            return 0;
        }
        return 1 + getStrLen(str.substring(1));
    }

  • 上面这个复杂度达到了O(N^2). 其实循环除了根据长度界定范围，还有一个for-each可以用，所以可以先转成charArray再for-each来找。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    private int getStrLen(String str) {
        if (str == null || str.equals("")) {
            return 0;
        }
        int index = 0;
        char[] sChar = str.toCharArray();
        for (char c: sChar) {
            index++;
        }
        return index;
    }

  • 此外，利用StringIndexOutOfBoundsException可以降到O(N).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    private int getStrLen(String str) {
        if (str == null || str.equals("")) {
            return 0;
        }
        int index = 0;
        while (true) {
            try {
                char c = str.charAt(index);
                index++;
            } catch (Exception e) {
                return index;
            }
        }
    }

BST验证

  • 常见的错误是直接greedy，只判断当前节点和孩子的大小。但BST的定义是比「所有的左子树都大、比右都小」。

  • 方法一：中序遍历时每次都判断前后两个元素的大小关系。又分为recursive和iterative的。

    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
     // recursive: 全局的prev记录当前节点前一个是谁，比较大小
    private TreeNode prev = null;
    private boolean validateBST1(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!validateBST1(root.left)) {
            return false;
        }
        if (prev != null && prev.val >= root.val) {
            return false;
        }
        prev = root;
        return validateBST1(root.right);
    }
     
    // iterative: 用stack不断深入左节点，直到空再将栈顶与prev比较，然后进入右子树，继续不断向左。
    private boolean validateBST2(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (prev != null && prev.val >= root.val) {
                return false;
            }
            prev = root;
            root = root.right;
        }
        return true;
    }

  • 方法二：分治，为左右子树给定范围（min, max），在递归时更新左子树的上界、更新右子树的下界。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    private boolean validateBST3(TreeNode root) {
        return dvcq(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean dvcq(TreeNode root, long min, long max) {
        if (root == null) {
            return true;
        }
        if (root.val <= min || root.val >= max) {
            return false;
        }
        return dvcq(root.left, min, Math.min(root.val, max))
                && dvcq(root.right, Math.max(root.val, min), max);
    }

走迷宫

  • 给一个grid走迷宫，有障碍物，四个方向随便走，要左上角到右下角的最短路径
  • BFS方法，进入循环时记录需要遍历的点的个数同时更新步数，从当前点开始往下、右、上、左的顺序走，如果没访问过且不是障碍物就放入queue，第一个到达右下角的就是最短路了。
    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
    private int shortestPath(int[][] grid){
        if (grid == null || grid.length == 0 || grid[0].length == 0 || grid[0][0] == 1) {
            return 0;
        }
        boolean[][] visited = new boolean [grid.length][grid[0].length];
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0));
        visited[0][0] = true;
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            step++;
            while (size-- > 0) {
                Point curr = q.poll();
                if (curr.x == grid.length - 1 && curr.y == grid[0].length - 1) {
                    return step;
                }
                // down
                if (curr.x + 1 < grid.length && grid[curr.x + 1][curr.y] != 1 &&
                        !visited[curr.x + 1][curr.y]) {
                    visited[curr.x + 1][curr.y] = true;
                    q.add(new Point(curr.x + 1, curr.y));
                }
                // right
                if (curr.y + 1 < grid[0].length && grid[curr.x][curr.y + 1] != 1 &&
                        !visited[curr.x][curr.y + 1]) {
                    visited[curr.x][curr.y + 1] = true;
                    q.add(new Point(curr.x, curr.y + 1));
                }
                // up
                if (curr.x >= 1 && grid[curr.x - 1][curr.y] != 1 &&
                        !visited[curr.x - 1][curr.y]) {
                    visited[curr.x - 1][curr.y] = true;
                    q.add(new Point(curr.x - 1, curr.y));
                }
                // left
                if (curr.y >= 1 && grid[curr.x][curr.y - 1] != 1 &&
                        !visited[curr.x][curr.y - 1]) {
                    visited[curr.x][curr.y - 1] = true;
                    q.add(new Point(curr.x, curr.y - 1));
                }
            }
        }
        return -1;
    }

Lowest Common Ancestor

  • 任意二叉树的最小共同祖先。

  • recursive：先看当前root是否符合其中一个，是就返回当前root，否则看看是否分居左、右，是也返回当前root，再否则看看需要深入到哪一边。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    private TreeNode getLCA(TreeNode root, TreeNode n1, TreeNode n2) {
    	if (root == null) {
    		return null;
    	}
    	if (root == n1 || root == n2) {
    		return root;
    	}
    	TreeNode left = getLCA(root.left, n1, n2);
    	TreeNode right = getLCA(root.right, n1, n2);
    	if (left != null && right != null) {
    		return root;
    	}
    	if (left == null && right == null) {
    		return null;
    	}
    	return left == null? right: left;
    }

  • follow-up：如果每个节点还给多一个parent引用

    1
    2
    3
    4
    5
    6
    7
    8
    9
    class TreeNodeP {
        int val;
        TreeNodeP left;
        TreeNodeP right;
        TreeNodeP parent;
        public TreeNodeP(int val) {
            this.val = val;
        }
    }

  • 方法一：将其中一个节点一路上溯到root，将沿途的节点全部存入Set，然后再从另一个节点上溯，看看沿途哪个在set里。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public TreeNodeP getLCA2(TreeNodeP p, TreeNodeP q) {
        Set<TreeNodeP> set = new HashSet<>();
        while (p != null) {
            set.add(p);
            p = p.parent;
        }
        while (q != null) {
            if (set.contains(q)) {
                return q;
            }
            q = q.parent;
        }
        return null;
    }

  • 方法二：先分别求两个节点的深度，将两个节点上溯到相同高度后，同时上溯并在每一步都判断是否相等。

    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 TreeNodeP getLCA3(TreeNodeP p, TreeNodeP q) {
        int hp = getH(p);
        int hq = getH(q);
        while (hp > hq) {
            p = p.parent;
            hp--;
        }
        while (hq > hp) {
            q = q.parent;
            hq--;
        }
        while (p != null && q != null && p != q) {
            p = p.parent;
            q = q.parent;
        }
        return p;
    }
    private int getH(TreeNodeP root) {
        int h = 0;
        while (root != null) {
            h++;
            root = root.parent;
        }
        return h;
    }

找第一个unique的字符

  • 方法一：遍历两次，第一次统计次数，第二次碰到次数为1的即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public int firstUniqChar2(String s) {
            if (s == null || s.length() == 0) {
                return -1;
            }
            char[] sChar = s.toCharArray();
            int[] bucket = new int [256];
            for (int i = 0; i < sChar.length; i++) {
            	bucket[sChar[i]]++;
            }
            for (int i = 0; i < sChar.length; i++) {
            	if (bucket[sChar[i]] == 1) {
            		return i;
            	}
            }
            return -1;
        }

  • 方法二：只遍历一次，利用LinkedHashMap维护存入的顺序，在统计次数的同时，将次数为1的放入linkedhashmap，如果后续再碰到字符就remove掉，最后就输出第一个就好。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
        char[] sChar = s.toCharArray();
        int[] bucket = new int [256];
        Map<Character, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < sChar.length; i++) {
            if (bucket[sChar[i]]++ == 0) {
                map.put(sChar[i], i);
            } else {
                map.remove(sChar[i]);
            }
        }
        Iterator it = map.entrySet().iterator();
        if (it.hasNext()) {
            Map.Entry pair = (Map.Entry)it.next();
            return (Integer)pair.getValue();
        }
        return -1;
    }

  • 方法三，双指针，慢指针指向当前只出现了一次的，快指针往后统计次数。每次都要判断慢指针指向的是不是已经需要更新了，更新时用while一路往后。当快指针消耗完，慢指针就是了。但感觉也算是遍历两次了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public int firstUniqChar(String s) { 
        if (s == null || s.length() == 0) {
            return -1;
        }
        int len = s.length(); 
        int slow = 0, fast = -1; 
        int[] count = new int[256]; 
        char[] c = s.toCharArray(); 
        while (++fast < len){ 
            count[c[fast]] ++; 
            while (slow < len && count[c[slow]] > 1) {
                slow++; 
            }
            if (slow == len) {
                return -1;
            }
        }
        return slow; 
    }

wordBreak

  • 给一个字符串和一个字典，判断该字符串能否通过空格拆分成单词，使得这些单词都来自dict。

  • 方法一：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
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
            return false;
        }
        Set<String> wordSet = new HashSet<>();
        int maxLen = 0;
        for (String word: wordDict) {
            wordSet.add(word);
            maxLen = Math.max(maxLen, word.length());
        }
        if (wordSet.contains(s)) return true;
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(0);
        // use a set to record checked index to avoid repeated work.
        // This is the key to reduce the running time to O(N^2).
        boolean[] visited = new boolean[s.length() + 1];
        visited[0] = true;
        while (!queue.isEmpty()) {
            int currIndex = queue.poll();
            for (int i = currIndex + 1; i <= s.length() && i - currIndex <= maxLen; i++) {
                if (visited[i]) continue;
                if (wordSet.contains(s.substring(currIndex, i))) {
                    if (i == s.length()) return true;
                    queue.offer(i);
                    visited[i] = true;
                }
            }
        }
        return false;
    }

  • 方法二：DFS中也是给定起点，往后遍历看能否找到，如果找到就以该处为起点继续向后，如果找不到，就直接把终点对应都索引标注起来，这样之后再碰到以该点起始都就知道不行了（因为以它结尾都不行，就算后面可以也没用）。

    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
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
            return false;
        }
        Set<String> wordSet = new HashSet<>();
        int maxLen = 0;
        for (String word: wordDict) {
            wordSet.add(word);
            maxLen = Math.max(maxLen, word.length());
        }
        if (wordSet.contains(s)) return true;
        boolean[] visited = new boolean[s.length() + 1];
        return dfs(s, 0, maxLen, wordSet, visited);
    }
    private boolean dfs(String s, int index, int maxLen, Set<String> dict, boolean[] visited){
        // base case
        if (index == s.length()) return true;
        // check memory
        if (visited[index]) return false;
        // recursion
        for (int i = index + 1; i <= s.length() && i - index <= maxLen; i++){
            String t = s.substring(index, i);
            if (dict.contains(t))
                if (dfs(s, i, maxLen, dict, visited))
                    return true;
                else
                    visited[i] = true;  // 以i结尾啊是不行的
        }
        visited[index] = false;
        return false;
    }

  • 方法三：DP。dp[i]表示取长度为i的字串是否都是dict里的，因此当发现一段子串来自dict之后，还需要看前一位是否true才可以判断当前是否true。 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public boolean workBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
            return false;
        }
        Set<String> wordSet = new HashSet<>();
        int maxLen = 0;
        for (String word: wordDict) {
            wordSet.add(word);
            maxLen = Math.max(maxLen, word.length());
        }
        boolean[] dp = new boolean [s.length() + 1];
        for (int i = 1; i <= s.length(); i++) {
            for (int j = i - 1; j >= 0 && i - j <= maxLen; j--) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

four missing nums in 1-100

  • 方法一：暴力找，用个辅助数组。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public int[] missingNum(int[] nums) {
        if (nums == null || nums.length != 96) {
            return new int[]{0,0,0,0};
        }
        boolean[] mark = new boolean[100];
        for (int i = 0; i < 100; i++) {
            mark[i - 1] = true;
        }
        int[] ans = new int [4];
        int index = 0;
        for (int i = 0; i < 100 && index < 4; i++) {
            if (!mark[i]) {
                ans[index++] = i + 1;
            }
        }
        return ans;
    }

  • follow-up: 如果内存不够，数组很大，怎么破？分批查找，引入一个累加都offset，方法中虽然还是找1-100的，但加上offset就是真实值了。

  • follow-up: 如果排好序，怎么优化？从头往后看，一旦index和数值差有变化，前一位就是missing的。但是如果都堆积在最末尾，那就要单独讨论了。

Git是什么

  • Git is a version control system - a tool to manage your source code history.
  • 允许不联网状态下建立本地仓库，通过branch方式分散，用merge合并。联网后有一个remote repo，可以和本地的repo record同步，pull = fetch + merge.

介绍一个数据结构

  • 大致有：Array, List, Set, Map, Queue, Stack, Tree, BST, Heap, Graph
  • Tree: binary tree(Traverse?); BST(validate)?

pass by reference和pass by value?

  • Pass by reference: the caller and the callee use the same variable for the parameter. If the callee modifies the parameter variable, the effect is visible to the caller’s variable.
  • Pass by value: the caller and callee have two independent variables with the same value. If the callee modifies the parameter variable, the effect is not visible to the caller.
  • Java is passing by value, but when pass value of object as parameter, that value is actually reference to that object. Though we can’t change the reference relation from callee method, we can still modify the object itself through that reference.

Fibonacci sum

  • 求斐波那契数列前n项之和，即0 ~ (n - 1)。

  • 首先看看基本的斐波那契数列怎么求。

    1
    2
    3
    4
    5
    6
    private static int fib(n) {
        if (n < 2) {
            return n;
        }
        return fib(n - 2) + fib(n - 1);
    }

  • 方法一：自然想到连续调用，显然复杂度非常高O(n ^ 2)，因为重复计算了很多。

    1
    2
    3
    4
    5
    6
    private static int fibSum1(int n) {
        if (n < 2) {
            return n;
        }
        return fibSum1(n - 1) + fib(n);
    }

  • 方法二：基于规律，fibSum(n) = fibSum(n - 1) + fib(n) = fibSum(n - 1) + fib(n - 2) + fib(n - 1) = fibSum(n - 1) + fibSum(n - 2) - fibSum(n - 3) + fibSum(n - 1) - fibSum(n - 2) = fibSum(n - 1) * 2 - fibSum(n - 3)。

    1
    2
    3
    4
    5
    6
    7
    8
    private static int fibSum(int n) {
        if (n < 2) {
            return n;
        }
        int prev1 = fibSum(n - 1);
        int prev3 = fibSum(n - 3);
        return (prev1 * 2)- prev3;
    }

  • 方法三：算是DP吧，用数组记录每一项fib，顺便求和。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    private static int fibSum2(int n) {
        if (n < 2) {
            return n;
        }
        int[] fibArray = new int [n + 1];
        fibArray[1] = 1;
        Int sum = 1;
        for (int i = 2; i <= n; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
            sum += fibArray[i];
        }
        return sum;
    }

  • 方法四：更绝的规律，直接求后两项的fib，然后减1即得。

    1
    2
    3
    4
    5
    6
    7
    private static int fibSum4(int n) {
        if (n < 2) {
            return n;
        }
        int f = fib(n + 2);
        return f - 1;
    }

LRU Cache(146)

  • 模拟Least Recently Used缓存，当要插入新的entry(key, value)时规模不够，最近最少用到的entry会被清除。要求get和put都是O(1)。
  • 由于有键值对，肯定要有Map。key是整数，而put的时候，value不能真的存给的整数value，而是存双向链表中的一个节点，该节点的val再存给定的整数value。put还需要考虑是否是更新，更新则要把原节点val更新后拖到头部；在get的时候，也要注意拖到链表头部。当需要移除最近最少使用元素的时候，就需要把最后一个节点删掉，同时在map中删掉，所以链表节点中还需要存key才能去map中删。双向链表根据节点来删除是O(1)的，因为可以直接访问前后两个节点（单向链表提供待删除节点和它前一个节点也可以做到constant time）。
    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
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    public class LRUCache {
        private class DoublyListNode {
            int key;
            int value;
            DoublyListNode prev;
            DoublyListNode next;
            private DoublyListNode(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
        int capacity;
        int currSize;
        DoublyListNode head, tail;
        HashMap<Integer, DoublyListNode> map;
        public LRUCache(int capacity) {
            this.capacity = capacity;
            map = new HashMap<Integer, DoublyListNode>();
            currSize = 0;
            head = new DoublyListNode(0, 0);    // 伪头部
            tail = new DoublyListNode(0, 0);    // 伪尾部
            head.prev = null;
            head.next = tail;
            tail.prev = head;
            tail.next = null;
        }
        public int get(int key) {
            DoublyListNode node = map.get(key);
            if (node != null) {
                moveToFirst(node);
                return node.value;
            } else {
                return -1;
            }
        }
        public void put(int key, int value) {
            DoublyListNode node = map.get(key);
            if (node == null) {
                node = new DoublyListNode(key, value);
                currSize++;
                if (currSize > capacity) {
                    currSize--;
                    map.remove(popLast().key);  // 尾部的
                }
                add(node);
                map.put(key, node);
            } else {
                node.value = value;
                moveToFirst(node);
            }
        }
        private void add(DoublyListNode node) {
            DoublyListNode nextOfHead = head.next;
            head.next = node;       // 插入到头部的下一位，需要调整头指针的指向
            node.prev = head;
            nextOfHead.prev = node;
            node.next = nextOfHead;
        }
        private void remove(DoublyListNode node) {
            DoublyListNode prevOfNode = node.prev;
            DoublyListNode nextOfNode = node.next;
            
            prevOfNode.next = nextOfNode;
            nextOfNode.prev = prevOfNode;
        }
        private DoublyListNode popLast() {
            DoublyListNode last = tail.prev;
            remove(last);
            return last;
        }
        // 被get了，就需要挪到头部，先删除再插入到头部即可
        private void moveToFirst(DoublyListNode node) {
            remove(node);
            add(node);
        }
    }
    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache obj = new LRUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */

扫雷(529)

  • 点击一个位置，根据是否有雷更新棋盘。如果是雷，直接改成叉叉并返回；如果没有点开并且周围八个相邻格子有雷，则改成雷的数目并返回；如果周围都没有雷，就扩散到相邻格子继续更新。

  • 方法一：根据描述本身就蕴含了递归，所以自然想到DFS。

    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
    49
    50
    51
    52
    53
    54
    class Solution {
        public char[][] updateBoard(char[][] board, int[] click) {
            if (board == null || board.length == 0 || board[0].length == 0
               || click == null || click.length < 2) {
                return new char [0][0];
            }
            int rowCount = board.length, colCount = board[0].length;
            int row = click[0], col = click[1];
            if (board[row][col] == 'B') {   // 已经点开了就直接返回
                return board;
            }
            if (board[row][col] == 'M') {   // 是雷就gg
                board[row][col] = 'X';
            } else {
                int count = 0;              // 计算雷的个数
                for (int i = -1; i < 2; i++) {
                    int tempRow = row + i;
                    if (tempRow < 0 || tempRow >= rowCount) {
                        continue;
                    }
                    for (int j = -1; j < 2; j++) {
                        int tempCol = col + j;
                        if (tempCol < 0 || tempCol >= colCount) {
                            continue;
                        }
                        if (board[tempRow][tempCol] == 'M') {
                            count++;
                        }
                    }
                }
                if (count > 0) {
                    board[row][col] = (char)('0' + count);
                } else {
                    board[row][col] = 'B';      // 改为已经reveal，并扩散到周围unreveal的邻居
                    for (int i = -1; i < 2; i++) {
                        int tempRow = row + i;
                        if (tempRow < 0 || tempRow >= rowCount) {
                            continue;
                        }
                        for (int j = -1; j < 2; j++) {
                            int tempCol = col + j;
                            if (tempCol < 0 || tempCol >= colCount) {
                                continue;
                            }
                            if (board[tempRow][tempCol] == 'E') {   // DFS the unrevealed
                                updateBoard(board, new int[]{tempRow, tempCol});
                            }
                        }
                    }
                }
            }
            return board;
        }
    }

  • 方法二：BFS，Queue中存放点击之后扩散的点（如果有的话），一直扩散直到Queue为空。但是和DFS需要区别的是，由于BFS会将相邻的所有E的格子都入队，很可能会出现重复，所以就直接在更新时就赋值为B，防止重复入队。

    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
    49
    50
    51
    52
    53
    54
    55
    56
    57
    class Solution {
        public char[][] updateBoard(char[][] board, int[] click) {
            if (board == null || board.length == 0 || board[0].length == 0
               || click == null || click.length < 2) {
                return new char [0][0];
            }
            Queue<int[]> q = new LinkedList<>();
            int rowCount = board.length, colCount = board[0].length;
            q.add(click);
            while (!q.isEmpty()) {
                int[] curr = q.poll();
                int row = curr[0], col = curr[1];   // 和DFS相比少了判断为B的步骤
                if (board[row][col] == 'M') {
                    board[row][col] = 'X';
                } else {
                    int count = 0;
                    for (int i = -1; i < 2; i++) {
                        int tempRow = row + i;
                        if (tempRow < 0 || tempRow >= rowCount) {
                            continue;
                        }
                        for (int j = -1; j < 2; j++) {
                            int tempCol = col + j;
                            if (tempCol < 0 || tempCol >= colCount) {
                                continue;
                            }
                            if (board[tempRow][tempCol] == 'M') {
                                count++;
                            }
                        }
                    }
                    if (count > 0) {
                        board[row][col] = (char)('0' + count);
                    } else {
                        board[row][col] = 'B';
                        for (int i = -1; i < 2; i++) {
                            int tempRow = row + i;
                            if (tempRow < 0 || tempRow >= rowCount) {
                                continue;
                            }
                            for (int j = -1; j < 2; j++) {
                                int tempCol = col + j;
                                if (tempCol < 0 || tempCol >= colCount) {
                                    continue;
                                }
                                if (board[tempRow][tempCol] == 'E') {   // BFS the unrevealed
                                    q.add(new int[]{tempRow, tempCol});
                                    board[tempRow][tempCol] = 'B';  // IMPORTANT!!!
                                }
                            }
                        }
                    }
                }
            }
            return board;
        }
    }

Reverse Integer

  • 给一个整数，求它各个位数字反转后的新的整数。
  • 需要考虑：反转之后越界？末尾是零的话反转到首位怎么表示？
  • 起始末尾是0如果按照正常数学操作是不用单独考虑的，越界就需要通过每一步与214748364进行比较了，一是防止这一部分就越界了、二是防止后一位加上来之后又越界了（需要分正负判断）。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public int reverse(int x) {
        int ans = 0;
        while (x != 0) {
            int curr = Math.abs(ans);
            if (curr > 214748364) {     // 解决反转后越界问题
                return 0;
            }
            if (curr == 214748364) {    // 解决反转后越界问题
                int limit = x < 0? 8: 7;
                if (x / 10 > limit) {
                    return 0;
                }
            }
            ans = ans * 10 + (x % 10);  // 更新反转数by加上x当前末尾数
            x /= 10;
        }
        return ans;
    }

Reverse Bits

  • 给一个数字，反转它对应的bit形式。
  • 此时就不需要考虑什么越界了，因为都是32位，反转了bit也是可以表示出来的。

  • 就从末尾开始通过AND取bit，不断加到result里。注意移位必须是unsigned。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result += n & 1;
            n >>>= 1;       // CATCH: must do unsigned shift
            if (i < 31)     // CATCH: for last digit, don't shift!
                result <<= 1;
        }
        return result;
    }

  • follow-up：如果这个函数会被反复调用，如何优化？

  • 优化无非时间空间，空间这里是没啥优化了，那么时间呢？时间优化通常就需要牺牲一点空间，也就是cache中间计算的结果。这里的「中间结果」可以利用bit的规律，将每8 bit（即1 byte）的结果缓存到map中，后续如果碰到了就直接从map中取这部分就好了。
    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
    public int reverseBits(int n) {
        byte[] bytes = new byte[4];
        for (int i = 0; i < 4; i++)     // convert int into 4 bytes
            bytes[i] = (byte)((n >>> 8*i) & 0xFF);
        int result = 0;
        for (int i = 0; i < 4; i++) {
            result += reverseByte(bytes[i]); // reverse per byte
            if (i < 3)
                result <<= 8;
        }
        return result;
    }
    private final Map<Byte, Integer> cache = new HashMap<Byte, Integer>();
    private int reverseByte(byte b) {
        Integer value = cache.get(b); // first look up from cache
        if (value != null)
            return value;
        value = 0;
        // reverse by bit
        for (int i = 0; i < 8; i++) {
            value += ((b >>> i) & 1);
            if (i < 7)
                value <<= 1;
        }
        cache.put(b, value);
        return value;
    }

黑杰克

  • （不确定题目描述）给一堆扑克牌，1～10是本身面值，JQK是10，而A可以是1也可以是11（同一组牌中只能确定一个取值），求最接近21的组合。例如A,A,J = 12, J,J,A,2 = 23, A,2 = 13。
  • 似乎就是贪心法，先将所有牌加起来，如果没有A就那样，如果有A就先保守地取1并统计A的出现次数，加完之后再比较sum + A_count * 10表示A都取11时的结果，两个取更接近21即可。

三维空间求点

  • 三维空间给定N个点的坐标(x, y, z)，找到N个点其中的一个点，使得其他点到这个点的距离总和最小。
  • 先遍历一遍求所有点的中心点，然后再遍历一遍看看哪个点离中心点最近。

Design tic tac toe(348)

  • XXOO游戏，两个玩家，每一行、每一列、两条对角线都是一样的话，对应玩家就赢了。要设计一个class，其中包含move函数，给坐标和玩家编号，在图里放，如果该玩家赢了就返回玩家编号。每行、每列需要统计两个玩家各自的个数，如果都是其中一个玩家都就赢了，两条对角线也是。
  • 记录行、列、两条对较线。区分两个玩家的O和X就通过正负一来判断，这样如果有一个玩家赢了就意味着一路相加结果是n或者-n
    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
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    class TicTacToe {
        private int[] rows;
        private int[] cols;
        private int diag1, diag2;
        private int n;
        /** Initialize your data structure here. */
        public TicTacToe(int n) {
            rows = new int [n];
            cols = new int [n];
            diag1 = 0;
            diag2 = 0;
            this.n = n;
        }
        
        /** Player {player} makes a move at ({row}, {col}).
            @param row The row of the board.
            @param col The column of the board.
            @param player The player, can be either 1 or 2.
            @return The current winning condition, can be either:
                    0: No one wins.
                    1: Player 1 wins.
                    2: Player 2 wins. */
        public int move(int row, int col, int player) {
            if (row < 0 || row >= n || col < 0 || row >= n || player < 1 || player > 2) {
                return 0;
            }
            int addVal = player == 1? -1: 1;
            // for diag1
            if (row == col) {
                diag1 += addVal;
                if (isConnect(diag1)) {
                    return player;
                }
            }
            
            // for diag2
            if (row + col == n - 1) {
                diag2 += addVal;
                if (isConnect(diag2)) {
                    return player;
                }
            }
            
            // for row
            rows[row] += addVal;
            if (isConnect(rows[row])) {
                return player;
            }
            
            // for col
            cols[col] += addVal;
            if (isConnect(cols[col])) {
                return player;
            }
            return 0;
        }
        
        private boolean isConnect(int val) {
            return val / n != 0;
        }
    }

Anagrams(49)

  • 给一个String数组，求其中各字符串的anagram，即「相同字符组合的字符串」，并将相同的放在一个List中。
  • 取每个字符串出来，排个序作为key去找map里对应的index，如果存在index就找到ansList中对应index的那一行，插到末尾；如果不存在说明是新的，就把当前ansList的规模作为新的index存入map。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public List<List<String>> groupAnagrams(String[] strs) {
            List<List<String>> ans = new ArrayList<>();
            if (strs == null || strs.length == 0) {
                return ans;
            }
            
            Map<String, Integer> map = new HashMap<>();
            for (String str: strs) {
                char[] sChar = str.toCharArray();   // sort str
                Arrays.sort(sChar);             
                String newStr = new String(sChar);  // the key to get the index in ans
                if (map.containsKey(newStr)) {
                    int index = map.get(newStr);
                    ans.get(index).add(str);
                } else {
                    map.put(newStr, ans.size());
                    List<String> temp = new ArrayList<>();
                    temp.add(str);
                    ans.add(temp);
                }
            }    
            return ans;
        }

Anagramii(438)

  • 给两个字符串，求后者的anagram在前者中子串的所有出现的index。
  • 又是字串问题，考虑双指针。先统计后者的每个字符各出现了几次，并确定有多少个不同的字符。然后双指针从前者头部走起，快指针往后取，直到剩余字符为0，然后慢指针再跟进，碰到map中存在的key就说明当前是anagram其中一个字符，需要加回来，同时判断该字符计数是否从0变成了1，是的话就不能再移慢指针了。此时判断慢指针到快指针之间是不是anagram的长度，是就说明start的index需要放入ans了。
    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
    public List<Integer> findAnagrams(String s, String t) {
        List<Integer> result = new LinkedList<>();
        if (t.length() > s.length()) {      // 如果后者比前者还长，根本不可能是anagram
            return result;
        }
        Map<Character, Integer> map = new HashMap<>();
        for(char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int counter = map.size();   // 多少个不同的字符
        int begin = 0, end = 0;
        int head = 0;
        int len = Integer.MAX_VALUE;   
        while (end < s.length()) {
            char c = s.charAt(end);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                if (map.get(c) == 0)    // 消耗了一个字符
                    counter--;
            }
            end++;       
            while (counter == 0) {
                char tempc = s.charAt(begin);
                if (map.containsKey(tempc)) {
                    map.put(tempc, map.get(tempc) + 1);
                    if (map.get(tempc) > 0) {
                        counter++;      // 恢复了一个字符
                    }
                }
                if (end - begin == t.length()) {
                    result.add(begin);
                }
                begin++;
            }
        }
        return result;
    }

Reverse linked list between m and n

  • 反转链表，给定了范围从m到n。
  • 其实就是从m开始，将最后一个节点插入到前面，逐个反转直到n。
    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
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null) 
            return null;
        ListNode dummy = new ListNode(0); // create a dummy node to mark the head of this list
        dummy.next = head;
        ListNode pre = dummy;   // make a pointer pre as a marker for the node before reversing
        for(int i = 0; i < m - 1; i++)   // 直到m的前一位
            pre = pre.next;
        
        ListNode start = pre.next;  // a pointer to the beginning of a sub-list that will be reversed
        ListNode then = start.next; // a pointer to a node that will be reversed
        
        // 1 - 2 -3 - 4 - 5 ; m = 2; n = 4 ---> pre = 1, start = 2, then = 3
        // dummy -> 1 -> 2 -> 3 -> 4 -> 5
        
        for(int i = 0; i < n - m; i++) {
            start.next = then.next;     // 当前的首位.next指向当前末尾的next
            then.next = pre.next;       // 当前末尾的next改指向前一位的next
            pre.next = then;            // 该前一位指向为当前末尾，完成反转
            then = start.next;          // 更新当前末尾
        }
        
        // first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
        // second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)
        return dummy.next;
    }

BST中给个target求最接近的值

  • 需要考虑如果树本身为空？接近target的值有两个取大的还是小的？还要注意，target是double而树节点的值都是int！所以需要的话还需要强制转换一下。

  • 方法一：recursive，先取当前节点与target比较，如果大于target就看左子树会不会更接近，否则看右子树。最后与递归结果比较即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public int closestValue(TreeNode root, double target) {
        if (root == null) 
            return Integer.MAX_VALUE;   
        int currVal = root.val;
        TreeNode kid = target < currVal ? root.left : root.right;
        if (kid == null) 
            return currVal;
        int kidVal = closestValue(kid, target);
        return Math.abs(currVal - target) < Math.abs(kidVal - target) ? currVal : kidVal;
    }

  • 方法二：iterative，持续更新root直到空，，一路上不断更新结果。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public int closestValue(TreeNode root, double target) {
        if (root == null) 
            return Integer.MAX_VALUE;   
        int closest = root.val;
        while (root != null) {
            if (Math.abs(closest - target) >= Math.abs(root.val - target)) {
                closest = root.val;
            }
            root = target < root.val? root.left: root.right;
        }
        return closest;
    }

BST中给个target求其中大于target的最小值。

  • 方法一：recursive，比较当前节点与target，若小于等于，则需要更大的值；若已经大于了，还需要进左子树看看有没有更接近target的。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public int closestLarger(TreeNode root, double target) {
        if (root == null) 
            return Integer.MAX_VALUE;
        int currVal = root.val;
        if (currVal <= target) {    // 当前小于等于目标说明得去右子树找大于的
            return cloestLarger(root.right, target);
        } else {        // 当前已经大于目标了，则还要进左子树找大于的，然后取更小的
            return Math.min(currVal, closetLarger(root.left, target));
        }
    }

  • 方法二：iterative

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public int closestLarger(TreeNode root, double target) {
        if (root == null) 
            return Integer.MAX_VALUE;
        int ans = Integer.MAX_VALUE;
        while (root != null) {
            if (root.val <= target) {
                root = root.right;
            } else {
                ans = root.val;
                root = root.left;
            }
        }
        return ans;
    }

二叉树根到叶路径和(113)

  • 给一个二叉树和一个目标值，求所有根到叶的路径使经过节点值之和等于target。
  • 路径中会不会出现负数？
  • 方法一：DFS，从根开始搜索，每次深入之前将target减去当前节点的值。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(root, sum, ans, new ArrayList<Integer>());
        return ans;
    }
    private void dfs(TreeNode root, int sum, List<List<Integer>> ans, List<Integer> curr) {
        if (root == null) {
            return;
        }
        curr.add(root.val);
        if (root.val == sum && root.left == null && root.right == null) {
            ans.add(new ArrayList<Integer>(curr));
        } else {
            dfs(root.left, sum - root.val, ans, curr);
            dfs(root.right, sum - root.val, ans, curr);
        }
        curr.remove(curr.size() - 1);
    }

2sum给一个target，求在数组中能否找到两个数之和等于它。
https://leetcode.com/problems/two-sum/description/
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

转array189

  • 方法一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public class Solution {
        public void rotate(int[] nums, int k) {
            if (k < 0) {
                return;
            }
            k = k % nums.length;
            if (k == 0) {
                return;
            }
            int[] temp = new int [k];
            System.arraycopy(nums, nums.length - k, temp, 0, k);
            System.arraycopy(nums, 0, nums, k, nums.length - k);
            System.arraycopy(temp, 0, nums, 0, k);
        }
        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    • 方法二：
      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
      全部reverse之后再分两部分reverse。
      public class Solution {
          public void rotate(int[] nums, int k) {
              if (k < 0) {
                  return;
              }
              k = k % nums.length;
              if (k == 0) {
                  return;
              }
              reverse(nums, 0, nums.length - 1);
              reverse(nums, 0, k - 1);
              reverse(nums, k, nums.length - 1);
          }
          private void reverse(int[] nums, int start, int end) {
              while (start < end) {
                  swap(nums, start, end);
                  start++;
                  end--;
              }
          }
          private void swap(int[] nums, int i, int j) {
              int temp = nums[i];
              nums[i] = nums[j];
              nums[j] = temp;
          }
      }

乘积[238]

  • 给一个数组，求除了当前数字之外剩余数字之积

  • 一：维护左侧乘积和右侧乘积

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public class Solution {
        public int[] productExceptSelf(int[] nums) {
            if (nums == null || nums.length < 1) {
                return new int [0];
            }
            int[] ans = new int [nums.length];
            int[] left = new int [nums.length];
            int[] right = new int [nums.length];
            left[0] = 1;
            for (int i = 1; i < nums.length; i++) {
                left[i] = left[i - 1] * nums[i - 1];
            }
            right[nums.length - 1] = 1;
            for (int i = nums.length - 2; i >= 0; i--) {
                right[i] = right[i + 1] * nums[i + 1];
            }
            
            for (int i = 0; i < nums.length; i++) {
                ans[i] = left[i] * right[i];
            }
            return ans;
        }
    }

  • 二：ans初始化为1，left表示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public class Solution {
        public int[] productExceptSelf(int[] nums) {
            if (nums == null || nums.length < 1) {
                return new int [0];
            }
            int[] ans = new int [nums.length];
            Arrays.fill(ans, 1);
            int left = 1, right = 1;
            for (int i = 0; i < nums.length; i++) {
                ans[i] *= left;
                ans[nums.length - 1 - i] *= right;
                left *= nums[i];
                right *= nums[nums.length - 1 - i];
            }
            return ans;
        }
    }

[299]

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
public class Solution {
    public String getHint(String secret, String guess) {
        if (secret == null || guess == null || secret.length() != guess.length()
            || secret.length() == 0 || guess.length() == 0) {
            return "0A0B";
        }
        char[] cSecret = secret.toCharArray();
        char[] cGuess = guess.toCharArray();
        int[] bucket = new int [10];
        int hit = 0, match = 0;
        for (int i = 0; i < cSecret.length; i++) {
            if (cSecret[i] == cGuess[i]) {
                match++;
            } else {
                if (bucket[cSecret[i] - '0'] < 0) {
                    hit++;
                }
                bucket[cSecret[i] - '0']++;
                if (bucket[cGuess[i] - '0'] > 0) {
                    hit++;
                }
                bucket[cGuess[i] - '0']--;
            }
        }
        return match + "A" + hit + "B";
    }
}

[314]

  • 垂直方向从左到右层级遍历二叉树。
    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
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        
        Map<Integer, ArrayList<Integer>> map = new HashMap<>();
        Queue<TreeNode> q = new LinkedList<>();
        Queue<Integer> cols = new LinkedList<>();
        q.add(root); 
        cols.add(0);
        int min = 0;
        int max = 0;
        
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            int col = cols.poll();
            
            if (!map.containsKey(col)) {
                map.put(col, new ArrayList<Integer>());
            }
            map.get(col).add(node.val);
            if (node.left != null) {
                q.add(node.left); 
                cols.add(col - 1);
                min = Math.min(min, col - 1);
            }
            
            if (node.right != null) {
                q.add(node.right);
                cols.add(col + 1);
                max = Math.max(max, col + 1);
            }
        }
        for (int i = min; i <= max; i++) {
            res.add(map.get(i));
        }
        return res;
    }

[53]

Linux命令行

awk:分析与处理
  • 对文本进行逐行分段处理，awk '条件类型1{动作1} 条件类型2{动作2}' filename. awk的处理流程是:
    1. 读第一行, 将第一行资料填入变量 $0, $1… 等变量中
    2. 依据条件限制, 执行动作(awk一次处理是一行, 而一次中处理的最小单位是一个区域)
    3. 接下来执行下一行
  • 三个变量：NF: 每一行处理的字段数，NR 目前处理到第几行，FS 目前的分隔符。
    sed:编辑
    以行为单位的文本编辑工具，sed可以直接修改档案，sed [-nef] '[动作]' [输入文本]
  • -n : 安静模式, 一般sed用法中, 来自stdin的数据一般会被列出到屏幕上, 如果使用-n参数后, 只有经过sed处理的那一行被列出来.
  • -e : 多重编辑, 比如你同时又想删除某行, 又想改变其他行, 那么可以用 sed -e ‘1,5d’ -e ‘s/abc/xxx/g’ filename
  • -f : 首先将 sed的动作写在一个档案内, 然后通过 sed -f scriptfile 就可以直接执行 scriptfile 内的sed动作 (没有实验成功, 不推荐使用)
  • -i : 直接编辑, 这回就是真的改变文件中的内容了, 别的都只是改变显示. (不推荐使用)
    动作:
  • a 新增, a 后面可以接字符串, 而这个字符串会在新的一行出现. (下一行)
  • c 取代, c 后面的字符串, 这些字符串可以取代 n1,n2之间的行
  • d 删除, 后面不接任何东西
  • i 插入, 后面的字符串, 会在上一行出现
  • p 打印, 将选择的资料列出, 通常和 sed -n 一起运作 sed -n ‘3p’ 只打印第3行
  • s 取代, 类似vi中的取代, 1,20s/old/new/g
    grep:截取
    文本搜集工具, 结合正则表达式非常强大.grep [要匹配的内容] [文件名].
  • -c : 只输出匹配的行
  • -I : 不区分大小写
  • -h : 查询多文件时不显示文件名
  • -l : 查询多文件时, 只输出包含匹配字符的文件名
  • -n : 显示匹配的行号及行
  • -v : 显示不包含匹配文本的所有行(我经常用除去grep本身)
    tail
  • 从文档末尾往前取