Linux

du -sh 文件或目录名称：列出文件或目录的总容量
du -ah 文件或目录名称：列出所有的文件与目录容量

df -h: 列出系统内所有的filesystem

Git

版本回退：
git log: 查看提交历史
git log --graph: 查看分支合并图
git reflog: 查看命令历史
git reset --hard commit_id: 回退到了某个版本
git reset --hard HEAD^: 回退到上一个版本
git reset --hard HEAD~10: 回退到之前第十个版本

撤销修改：
git checkout -- file: 可以丢弃工作区的修改(或删除操作), 让file这个文件回到最近一次git commit或git add时的状态
git reset HEAD file: 可以把暂存区的修改撤销掉，重新放回工作区

分支管理：
git merge --no-ff -m <commit-info> <branch-name>: 强制禁用Fast forward模式，Git就会在merge时生成一个新的commit，从分支历史上就可以看出分支信息

git stash: 把当前工作现场“储存”起来
git stash apply: 恢复储存的内容，但是恢复后，stash内容并不删除
git stash drop: 删除stash的内容
git stash pop: 恢复的同时把stash内容也删了
git stash apply stash@{0}: 如果有多次stash的话，选择恢复某个stash内容

配置别名：
git config --global alias.lg "log --color --graph --pretty=format:'%Cred%h%Creset -%C(yellow)%d%Creset %s %Cgreen(%cr) %C(bold blue)<%an>%Creset' --abbrev-commit"

实际工作：
git checkout mainline
git pull
git checkout dev
git rebase mainline
(resolve conflicts + commit)
git checkout mainline
git merge dev
git push origin mainline

Sliding Window Second Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. 

For example:
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3. 
Then, return the second max sliding window [1, -1, -1, 3, 5, 6] .

/* time: amortized O(n), space:O(n) */
import java.util.*;

public class Solution {
public static int[] test(int[] nums, int k) {
if (nums == null || nums.length <= 1 || k <= 1) {
return nums;
}
if (k > nums.length) {
k = nums.length;
}
int[] res = new int[nums.length - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
int maxNumIndex = 0;
int index = 0;
for (int i = 1; i < nums.length; i++) {
if (!deque.isEmpty() && deque.peek() < i - k + 1) {
deque.poll();
}
if (maxNumIndex < i - k + 1) {
maxNumIndex = deque.poll();
}
if (nums[i] > nums[maxNumIndex]) {
int temp = maxNumIndex;
maxNumIndex = i;
while (!deque.isEmpty() && temp > deque.peek()) {
deque.poll();
}
deque.offerFirst(temp);
} else {
while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offer(i);
}
if (i >= k - 1) {
res[index++] = nums[deque.peek()];
}
}
return res;
}
public static void main(String[] args) {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int[] t0 = test(nums, 1);
int[] t1 = test(nums, 2);
int[] t2 = test(nums, 3);
int[] t3 = test(nums, 4);
int[] t4 = test(nums, 5);
int[] t5 = test(nums, 6);
int[] t6 = test(nums, 7);
int[] t7 = test(nums, 8);
int[] t8 = test(nums, 9);
int[] t9 = test(nums, 10);
System.out.println(Arrays.toString(t0));
System.out.println(Arrays.toString(t1));
System.out.println(Arrays.toString(t2));
System.out.println(Arrays.toString(t3));
System.out.println(Arrays.toString(t4));
System.out.println(Arrays.toString(t5));
System.out.println(Arrays.toString(t6));
System.out.println(Arrays.toString(t7));
System.out.println(Arrays.toString(t8));
System.out.println(Arrays.toString(t9));
}
}

Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.


/* method 1: 
 * time:O(m*n*4^L), space:O(m*n), m: board's row, n: board's column, L: word size
 * Imagine this is a tree,  this quadtree's height is L(L is length of word) and its total node number is
 * 4^0 + 4^1 + ... + 4^L = 1/3 * ( 4^(L+1) - 1 ). So the time complexity of this dfs solution is  * mnO(4^L).
 */
public class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        int width = board.length;
        int length = board[0].length;
        boolean[][] visited = new boolean[width][length];
        for (int y = 0; y < width; y++) {
        for (int x = 0; x < length; x++) {
        if (exist(board, y, x, words, 0, visited)) {
                                return true;
                        }
        }
        }
        return false;
    }
    
    private boolean exist(char[][] board, int y, int x, char[] words, int i, boolean[][] visited) {
    if (i == words.length) {
            return true;
        }
    if (y < 0 || x < 0 || y == board.length || x == board[y].length || visited[y][x] == true) {
            return false;
        }
    if (board[y][x] != words[i]) {
            return false;
        }
    visited[y][x] = true;
    boolean exist = exist(board, y, x + 1, words, i + 1, visited)
               || exist(board, y, x - 1, words, i + 1, visited)
               || exist(board, y + 1, x, words, i + 1, visited)
               || exist(board, y - 1, x, words, i + 1, visited);
    visited[y][x] = false;
    return exist;
    }

}



/* method2:
 * time:O(m*n*4^L), space:O(1)
 *
 * board[y][x] ^= 256 it's a marker that the letter at position x,y is a part of word we search.
 * After board[y][x] ^= 256 the char became not a valid letter. After second board[y][x] ^= 256
 * it became a valid letter again.
 */

public class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        int row = board.length;
        int column = board[0].length;
        for (int y = 0; y < row; y++) {
         for (int x = 0; x < column; x++) {
         if (exist(board, y, x, words, 0)) {
                              return true;
                        }
         }
        }
        return false;
    }
    
    private boolean exist(char[][] board, int y, int x, char[] words, int i) {
     if (i == words.length) {
            return true;
        }
     if (y < 0 || x < 0 || y == board.length || x == board[y].length) {
            return false;
        }
     if (board[y][x] != words[i]) {
            return false;
        }
     board[y][x] ^= 256;
     boolean exist = exist(board, y, x + 1, words, i + 1)
                 || exist(board, y, x - 1, words, i + 1)
                 || exist(board, y + 1, x, words, i + 1)
                 || exist(board, y - 1, x, words, i + 1);
     board[y][x] ^= 256;
     return exist;
    }

}

K closest points

/*
 * Find the K closest points to the origin in 2D plane, given an array containing N points.
 * You can assume K is much smaller than N and N is very large.
 * You need only use standard math operators (addition, subtraction, multiplication, and division).
 */
import java.util.*;

class Point {
    double x;
    double y;
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}
public class Solution {
private static double distance(Point a, Point b) {
        return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    }
public static Point[] closestPoint(Point[] array, final Point origin, int k) {
        if (k >= array.length) {
        // return array;
        k = array.length;
        }
        if (k <= 0) {
        return new Point[0];
        }
        Point[] res = new Point[k];
        PriorityQueue<Point> maxHeap = new PriorityQueue<>(k + 1, new Comparator<Point>() {
            @Override
            public int compare(Point a, Point b) {
                return Double.compare(distance(b, origin), distance(a, origin));
            }
        });
        for(Point p : array) {
        maxHeap.offer(p);
        if (maxHeap.size() > k) {
        maxHeap.poll();
        }
        }
        for(int i = k - 1; i >= 0; i--) {
        res[i] = maxHeap.poll();
        }
        return res;
    }

    public static void main(String[] args) {
        Point origin = new Point(0, 0);
        Point[] input = new Point[]{new Point(0, 2), new Point(1, 1), new Point(-1, 0), new Point(2, 0), new Point(3, 0)};
        Point[] output = closestPoint(input, origin, 3);
        System.out.println("input");
        for(Point i : input) System.out.print("("+i.x+", "+i.y+") ");
        System.out.println("");
        System.out.println("output");
        for(Point i : output) System.out.print("("+i.x+", "+i.y+") ");
    }
}

Implement a fix-sized queue using array

Implement a fix-sized queue using array.


import java.util.*;

public class Queue<T> {
private int front;
private int rear;
private int size;
private final T[] queue;

public Queue(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("Size cannot be less than or equal to zero.");
}
size = 0;
front = 0;
rear = -1;
queue = (T[])new Object[capacity];
}

public int size() {
return size;
}

public void enQueue(T item) {
if (size == queue.length) {
throw new IllegalStateException("Queue is full.");
}
rear = (rear + 1) % queue.length;
queue[rear] = item;
size++;
}

public T deQueue() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty.");
}
T value = queue[front];
front = (front + 1) % queue.length;
size--;
return value;
}

public boolean isEmpty() {
return size == 0;
}

public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Queue is Empty.");
}
return queue[front];
}

@Override
public String toString() {
int s = size;
int head = front;
String str = "[";
while (s > 1) {
str += queue[head];
str += ", ";
s--;
head = (head + 1) % queue.length;
}
if (s == 1) {
str += queue[head];
}
str += "]";
return str;
}

    public static void main(String[] args) {
        Queue<Integer> newQueue = new Queue<>(5);
        newQueue.enQueue(10);
        newQueue.enQueue(20);
        newQueue.enQueue(30);
        newQueue.enQueue(40);
        newQueue.enQueue(50);
        System.out.println(newQueue.toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.toString());
        newQueue.enQueue(60);
        newQueue.enQueue(70);
        System.out.println("Size should be 5, the result is " + newQueue.size());
        System.out.println("Should be false, the result is " + newQueue.isEmpty());
        System.out.println(newQueue.toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.toString());
        System.out.println("Size should be 0, the result is " + newQueue.size());
        System.out.println("Should be true, the result is " + newQueue.isEmpty());
    }
}

Roman to Integer

/*

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

*/

//time: O(n), space:O(1)
public class Solution {
    public int romanToInt(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int res = map.get(s.charAt(s.length() - 1));
        for (int i = s.length() - 2; i >= 0; i--) {
            if (map.get(s.charAt(i)) >= map.get(s.charAt(i + 1))) {
                res += map.get(s.charAt(i));
            } else {
                res -= map.get(s.charAt(i));
            }
        }
        return res;
    }
}