java

Binary Tree Traversal, Part 1

2019-10-23

outline:

pre-order, post-order, in-order traversal of binary tree
level-order traversal of binary tree

pre-order, post-order, in-order traversal of binary tree

pre-order:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }
    
    public void preorder(TreeNode node, List res) {
        if (node != null) {
            res.add(node.val);
            preorder(node.left, res);
            preorder(node.right, res);
        }
    }
}

post-order:

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }
    
    public void postorder(TreeNode node, List res) {
        if (node != null) {
            postorder(node.left, res);
            postorder(node.right, res);
            res.add(node.val);
        }
    }
}

in-order:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }
    
    public void inorder(TreeNode node, List res) {
        if (node != null) {
            inorder(node.left, res);
            res.add(node.val);
            inorder(node.right, res);
        }
    }
}

level-order

recursive method:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int level = 0;
        if (root == null)
            return res;
        level_recur(root, res, level);
        return res;
    }
    
    public void level_recur(TreeNode node, List<List<Integer>> res, int level) {
        // add new level if necessary
        if (res.size() == level)
            res.add(new ArrayList<Integer>());      
        // add current value to corresponding level
        res.get(level).add(node.val);
        // recursion
        if (node.left != null)
            level_recur(node.left, res, level+1);
        if (node.right != null)
            level_recur(node.right, res, level+1);
    }
}

iterative method:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null)
            return res;
        int level = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()) {
            res.add(new ArrayList<Integer>());
            int level_len = queue.size();
            for (int i = 0; i < level_len; i++) {
                TreeNode cur = queue.remove();
                res.get(level).add(cur.val);
                if (cur.left != null)
                    queue.add(cur.left);
                if (cur.right != null)
                    queue.add(cur.right);
            }
            level += 1;
        }
        return res;
    }
}

Backtracking Leetcode Summary, Part 2

2019-10-22

Subsets
Palindrome
Combination Sum, repeated number used
Combination Sum, unique number used

Subsets:

Problem Description: Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets.
Few Key Points:

This algorithm is very close to that of permutation. The only difference is that this counts for subsets instead of permutations.
One of the key point is to keep the order, don’t permute like the permutation algorithm

Code:
backtracking part, takes parameters:

result: LinkedList>
current: ArrayList
nums: nums to extract from

cur_idx: current index
Note: when adding to result, convert the current list into a new list

public void backtrack(List<List<Integer>> l, 
                      List<Integer> tmpList, 
                      int [] nums, 
                      int start) {
    l.add(new ArrayList<>(tmpList));
    for (int i = start; i < nums.length; i++) {
        tmpList.add(nums[i]);
        backtrack(l, tmpList, nums, i+1);
        tmpList.remove(tmpList.size() - 1);
    }
}

The solution part:

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> tmp = new ArrayList<Integer>();
    int start = 0;
    backtrack(res, tmp, nums, start);
    return res;
}

Palindrome:

Problem Description: Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
e.g.:
Input: “aab”
Output:
[[“aa”,”b”],
[“a”,”a”,”b”]]
Few Key Points:
An utility function can be used to determine if str is palindrome or not.
Code:
backtrack:

public void backtrack(List<List<String>> result, 
                      List<String> tmp, 
                      String str, 
                      int index) {
    if (index == str.length()) 
        result.add(new ArrayList<String>(tmp));
    else {
        for (int i = index; i < str.length(); i++) {
            if (isPalindrome(str, index, i)) {
                tmp.add(str.substring(index, i+1));
                backtrack(result, tmp, str, i+1);
                tmp.remove(tmp.size()-1);
            }
        }
    }
}

Check if str is palindrome:

public boolean isPalindrome(String str, int s, int e) {
    while (s < e) {
        if (str.charAt(s++) != str.charAt(e--))
            return false;
    }
    return true;
}

The solution part:

public List<List<String>> partition(String s) {
    List<List<String>> res = new LinkedList<List<String>>();
    List<String> list = new ArrayList<String>();
    int idx = 0;
    backtrack(res, list, s, idx);
    return res;
}

Combination Sum, repeat allowed

Problem Description: Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times.
e.g.:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[[7],
[2,2,3]]
Codes:
backtrack:

public void backtrack(List<List<Integer>> res, 
                 List<Integer> tmp, 
                 int[] cand, 
                 int rem, 
                 int cur) {
    if (rem == 0) {
        res.add(new ArrayList<Integer>(tmp));
    } else if (rem < 0) {
        return;
    } else {
        for (int i = cur; i < cand.length; i++) {
            if (rem >= cand[i]) {
                tmp.add(cand[i]);
                backtrack(res, tmp, cand, rem - cand[i], i);
                tmp.remove(tmp.size()-1);
            } else {
                break;
            }
        }
    }
}

The solution part:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> tmp = new ArrayList<Integer>();
    int cur = 0;
    int rem = target;
    Arrays.sort(candidates);
    backtrack(res, tmp, candidates, rem, cur);
    return res;
}

Combination Sum, no repeats

Problem Description: Same as combination sum, with only difference that each number can only be used once.

Codes:
backtrack: (added while loop to eliminate repeating results)

public void backtrack(List<List<Integer>> res, 
                 List<Integer> tmp, 
                 int[] cand, 
                 int rem, 
                 int cur) {
    if (rem == 0) {
        res.add(new ArrayList<Integer>(tmp));
    } else if (rem < 0) {
        return;
    } else {
        for (int i = cur; i < cand.length; i++) {
            if (rem >= cand[i]) {
                tmp.add(cand[i]);                    
                backtrack(res, tmp, cand, rem - cand[i], i+1);
                tmp.remove(tmp.size()-1);
                while (i < cand.length-1 && cand[i] == cand[i+1])
                    i += 1;
            } else {
                break;
            }
        }
    }
}

The solution part is the same as the last section.

Backtracking Leetcode Summary, Part 1

2019-10-18

N-Queens
Permutation

N-Queens:

Problem Description: The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
Thought Process in Short: Backtracking with DFS. We know each row has one queen, so we move from top line to the bottom line line by line, checking each column, and two diagonals.
Few Key Points:

For all “hill” diagonals row + column = const, and for all “dale” diagonals row - column = const.
There could be the only one queen in a row and the only one queen in a column.

Algorithms:

Start from the first row = 0.
Iterate over the columns and try to put a queen in each column.
1. If square (row, column) is not under attack
  1. Place the queen in (row, column) square.
  2. Exclude one row, one column and two diagonals from further consideration.
  3. If all rows are filled up row == N
    - That means that we find out one more solution.
      Else
    - Proceed to place further queens backtrack(row + 1).
  4. Now backtrack : remove the queen from (row, column) square.

Codes:
Initialize log variables:

int rows[];
int hills[];
int dales[];
int n;
List<List<String>> output = new ArrayList();
int queens[];

Checking if a cell is under attack:

public boolean isNotUnderAttack(int row, int col) {
    int res = rows[col] + hills[row - col + 2 * n] + dales[row + col];
    if (res == 0) {
        return true;
    } else {
        return false;
    }
}

Method placing and removing queens:

public void placeQueen(int row, int col) {
    queens[row] = col;
    rows[col] = 1;
    hills[row - col + 2 * n] = 1;
    dales[row + col] = 1;
}

public void removeQueen(int row, int col) {
    queens[row] = 0;
    rows[col] = 0;
    hills[row - col + 2 * n] = 0;
    dales[row + col] = 0;
}

Adding a solution to existing solutions:

public void addSolution() {
    List<String> solution = new ArrayList<String>();
    for (int i = 0; i < n; ++i) {
        int col = queens[i];
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < col; ++j) {
            sb.append(".");
        }
        sb.append("Q");
        for (int j = 0; j < n - col - 1; ++j) {
            sb.append(".");
        }
        solution.add(sb.toString());
    }
    output.add(solution);
}

The actual backtracking process:

public void backtrack (int row) {
    for (int col = 0; col < n; col++) {
        if (isNotUnderAttack(row, col)) {
            placeQueen(row, col);
            if (row + 1 == n) {
                addSolution();
            } else {
                backtrack(row + 1);
            }
            removeQueen(row, col);
        }
    }
}

Main function of solution:

public List<List<String>> solveNQueens(int n) {
    this.n = n;
    rows = new int[n];
    hills = new int[4 * n - 1];
    dales = new int[2 * n - 1];
    queens = new int[n];
    
    backtrack(0);
    return output;
}

Permutation:

One of the more basic backtracking problem.
Algorithms:

If the first integer to consider has index n that means that the current permutation is done.
Iterate over the integers from index first to index n - 1.
1. Place i-th integer first in the permutation, i.e. swap(nums[first], nums[i]).
2. Proceed to create all permutations which starts from i-th integer : backtrack(first + 1).
3. Now backtrack, i.e. swap(nums[first], nums[i]) back.

Code：
BFS to find solutions, then backtracking to reverse to previous states. The following is the backtracking part.

public void backtrack(int n, 
                      ArrayList<Integer> nums, 
                      List<List<Integer>> res, 
                      int first_idx) {
    if (first_idx == n) {
        res.add(new ArrayList<Integer>(nums));
    }
    for (int i = first_idx; i < n; i++) {
        # swap first and ith
        Collections.swap(nums, first_idx, i);
        backtrack(n, nums, res, first_idx+1);
        # swap back to original
        Collections.swap(nums, first_idx, i);
    }
}

Main function of solution:

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new LinkedList();
    ArrayList<Integer> nums_list = new ArrayList<Integer>();
    for (int num : nums) {
        nums_list.add(num);
    }
    int n = nums.length;
    backtrack(n, nums_list, res, 0);
    return res;
}

Multiple Thread (Runnable vs. Thread), Part 1

2019-02-09

Multi-threading states
Java thread init methods
Examples of Thread and Runnable

Multi-threading states

new: 新建状态，保持这个状态直到程序start()
ready: 调用了start()，就绪状态的线程处于就绪队列中，要等待JVM里线程调度器的调度
running: 获取了CPU资源，执行run()里面的指令
suspend: 失去所占用资源之后，该线程就从运行状态进入阻塞状态。在睡眠时间已到或获得设备资源后可以重新进入就绪状态。可以分为三种
- 等待阻塞: wait()
- 同步阻塞: 线程在获取synchronized同步锁失败后
- 其他阻塞: 其他阻塞：通过调用线程的sleep()或join()发出了I/O请求时，线程就会进入到阻塞状态
dead: 一个运行状态的线程完成任务或者其他终止条件发生时，该线程就切换到终止状态

Java thread init methods

Java 提供了三种创建线程的方法

通过实现Runnable接口
通过继承Thread类本身
通过Callable和Future创建线程

Java thread example

// class extending Thread
import java.util.*;
// new class
class MyThread extends Thread {
    private int ticket = 10;
    private String name;
    private Random rand = new Random();
    // constructors
    public MyThread(String name) {
        this.name = name;
        System.out.println(this.name + " starts with " + this.ticket + ".");
    }
    // Override the run function to implement functionality
    @Override
    public void run() {
        for (int i = 0; i < 500; i++) {
            if (this.ticket > 0) {
                // create a random number between two sales
                int nxt = rand.nextInt(20) * 10;
                this.ticket--;
                System.out.println(this.name + " sold a ticket, now has " + this.ticket + " tickets.");
                try {
                    Thread.sleep(nxt);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
        System.out.println("Now, " + this.name + " has ended.");
    }
}
// method to run the class above
public class ThreadDemo {
    public static void main(String[] args) {
        System.out.println("start");
        MyThread mt1 = new MyThread("Counter 1");
        MyThread mt2 = new MyThread("Counter 2");
        MyThread mt3 = new MyThread("Counter 3");
        mt1.start();
        mt2.start();
        mt3.start();
    }
}

Runnable Example

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.Random;
// now using Runnable interface instead of extending a class
public class MyRunnable implements Runnable{
    private int ticket = 30;
    private Random rand = new Random();
    private Lock lock = new ReentrantLock();
    public MyRunnable() {
        System.out.println("This class starts with " + this.ticket + " tickets.");
    }
    // overriding the run method just as before
    @Override
    public void run() {
        while (this.ticket > 0) {
            // tryLock() checks if the lock is available, takes the lock and return true if yes, else return false
            if (lock.tryLock()){
                try {
                    // command to execute with the lock
                    System.out.println(Thread.currentThread().getName() + " acquired lock.");
                    this.ticket--;
                    System.out.println(Thread.currentThread().getName() + " sold a ticket, now has " + this.ticket + " tickets.");
                } catch (Exception e) {
                    System.err.println(e);
                } finally {
                    // releasing the lock
                    System.out.println(Thread.currentThread().getName() + " released lock.");
                    lock.unlock();
                }
                // wait for a random length after selling a ticket
                int nxt = rand.nextInt(20) * 10;
                try {
                    Thread.sleep(nxt);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            } 
            // if lock is not available, wait
            else {
                try {
                    Thread.sleep(10);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
        System.out.println("Now, " + Thread.currentThread().getName() + " has ended.");
    }
}

ZEXI JIN

java

Binary Tree Traversal, Part 1

pre-order, post-order, in-order traversal of binary tree

level-order

Backtracking Leetcode Summary, Part 2

Subsets:

Palindrome:

Combination Sum, repeat allowed

Combination Sum, no repeats

Backtracking Leetcode Summary, Part 1

N-Queens:

Permutation:

Multiple Thread (Runnable vs. Thread), Part 1

Multi-threading states

Java thread init methods

Java thread example

Runnable Example