shixiaoyu

public String convertSimulation(String s, int nRows) {
    if (s == null || s.length() == 0 || nRows <= 0) {
        return "";
    }

    if (nRows == 1) {
        return s;
    }

    int size = s.length();

shixiaoyu

public int[][] generateMatrix(int n) {
    assert n >= 0;

    int[][] res = new int[n][n];

    this.generateMatrixHelper(0, 0, n, n, res, 1);
    return res;
}

private void generateMatrixHelper(

shixiaoyu

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new ArrayList<>();

    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return res;
    }

    this.printSpiralOrder(0, 0, matrix.length, matrix[0].length, res, matrix);

    return res;

shixiaoyu

public int coinChangeDP(int[] coins, int amount) {
    if (coins == null || coins.length == 0) {
        return -1;
    }
    // lookup contains the min number of coins needed to reach the amount(i.e., index)
    int[] lookup = new int[amount + 1];
    lookup[0] = 0;

    for (int i = 1; i <= amount; i++) {
        int min = Integer.MAX_VALUE;

shixiaoyu

public int hIndex(int[] citations) {
    if (citations == null || citations.length == 0) {
        return 0;
    }

    // because we need from 0 to citations.length, h-index in [0, citations_length]
    int[] counts = new int[citations.length + 1];

    for (int i = 0; i < citations.length; i++) {
        /*

shixiaoyu

public static void main(String[] args) {
    CloneGraph cg = new CloneGraph();

    // construct the example graph
    Node n1 = new Node(1, new ArrayList<>());
    Node n2 = new Node(2, new ArrayList<>());
    Node n3 = new Node(3, new ArrayList<>());
    Node n4 = new Node(4, new ArrayList<>());
    n1.neighbors.addAll(Arrays.asList(new Node[]{n2, n4}));
    n2.neighbors.addAll(Arrays.asList(new Node[]{n3, n3}));

shixiaoyu

// exactly the same as BFS except used a stack to mimic the recursion, technically any BFS can be written
// in DFS by using a stack
public Node cloneGraphDFSUsingStack(Node node) {
    if (node == null) {
        return node;
    }
    Map<Node, Node> lookup = new HashMap<>();
    Node t = new Node(node.val, new ArrayList<>());
    lookup.put(node, t);

shixiaoyu

public Node cloneGraphDFSWithRecursion(Node node) {
    if (node == null) {
        return node;
    }
    Map<Node, Node> lookup = new HashMap<>();
    return this.cloneGraphHelper(node, lookup);
}

/**
 * A dfs helper using recursion to make a copy of each node recursively via neighbors

shixiaoyu

public Node cloneGraphBFS(Node node) {
    if (node == null) {
        return node;
    }

    Map<Node, Node> lookup = new HashMap<>();

    Queue<Node> q = new LinkedList<>();
    q.add(node);
    lookup.put(node, new Node(node.val, new ArrayList<>()));

shixiaoyu

private int max = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
	maxPathSumHelper(root);
	return this.max;
}

public int maxPathSumHelper(TreeNode root) {
	if (root == null) {
		return 0;