aligator4sah

mvn clean install

Install maven exclude tests

mvn install -DskipTests

Creating a project:

mvn archetype:generate -DgroupId=com.mycompany.app -DartifactId=my-app -DarchetypeArtifactId=maven-archetype-quickstart -DarchetypeVersion=1.4 -DinteractiveMode=false

aligator4sah

Console.log()

console.log("Object value: %o with string substitution", {string: "str", number: 10});

console.log("Object value: ", {string: "str", number: 10}, " with string substitution");

aligator4sah

//Solution 1: Union Find
/**
Union find algorithm:
Find: determine which subset a particular elements is in. This can be used for determining if two elements are in the same subset.
Union: join two subsets into a single subset

Assumption: the graph doesn't contain any self-loops

Example: chech if there is cycle in the graph
For each edge, make subsets using both the vertices of the edge. If both vertices are in the same subset, a cycle is found.

aligator4sah

//bfs solution
public class Solution {
	int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
	public List<int[]> pacificAtlantic(int[][] matrix) {
		List<int[]> res = new LinkedList<>();
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return res;
		}

		int n = matrix.length;

aligator4sah

//Solution 1: DFS solution




//Solution 2: DP solution



// Solution 3: DP preprocess plus DFS solution

aligator4sah

// Solution 1: dfs with memorization

public List<String> wordBreak(String s, List<String> wordDict) {
        Map<String, LinkedList<String>> map = new HashMap<>();
        Set<String> dict = new HashSet<>(wordDict);
	    return dfs(s, dict, map);
    }
    
    private List<String> dfs(String s, Set<String> wordDict, Map<String, LinkedList<String>> map) {
        if (map.containsKey(s)) {

aligator4sah

public class Solution {
  /**
 * Solution 1: Breadth first search
 * Consider each sate in the board as a graph node
 * find out the min distance between start node and final target node
 * initial state: original state( board )
 * expansion rule: every time we switch 0 to the adjacent position.
 * ternimate condition: when board state reach the target state
 * this can be seen as expand to a new node
 *

aligator4sah

public String decodeString(String s) {
		Deque<Integer> counts = new LinkedList<>();
		Deque<String> words = new LinkedList<>();

		int i = 0;
		words.offerFirst("");
		while (i < s.length()) {
			char ch = s.charAt(i);
			if (ch >= '0' && ch <= '9') {
				int value = ch - '0';

aligator4sah

/**
	 * Solutin 1: dfs + bfs
	 * use dfs to find the target k node in the tree
	 * use bfs to find the closest leaf node to the target node
	 * hashmap to record all back edges from child to parent
	 */
	public int findClosestLeaf(TreeNode root, int k) {
		//store all edges that trace node back to its parent
		Map<TreeNode, TreeNode> backMap = new HashMap<>();
		Queue<TreeNode> queue = new LinkedList<>();

aligator4sah

/**
	 * Corner cases:
	 * 1. number with only one pointer no zero after -- valid
	 * 2. number with only one e in the end -- valid
	 * 3. number with letters -- invalid
	 * 4. number with one signal ahead -- valid
	 * 5. number with multiple signals -- invalid
	 */
	public boolean isNumber(String s) {
        s = s.trim();