rayjcwu’s gists

rayjcwu / Barasheet 10

Created January 20, 2014 07:06

This code efficiency was recently improved by exchanging StringBuffer for StringBuilder. A collague notes however that this code runs inside a multi-threaded process and that although StringBuilder is faster, it is not thread safe. Identify the true statement. 1. In this context, the StringBuilder instance is appropriately used by a single threa…

	public class Contact {

	String email;
	...

	public String toString() {
	// StringBuffer sb = new StringBuffer();
	StringBuilder sb = new StringBuilder();
	sb.append(first)
	.append(" ")

rayjcwu / IntArrayProdExceptOne

Created January 22, 2014 01:36

Given an array of integer A, output another array B with the same size, B[i] = Prod_{j != i} A[j]

	// A = [1, 2, 3, 4, 5, 6]
	// L = [1, 2, 6, 24, 120, 720]
	// R = [720, 720, 360, 120, 30, 6]

	// first version
	int [] prod (int []A) {
	final int N = A.length;
	int []L = new int[N];
	int []R = new int[N];

rayjcwu / PeekingIterator

Created January 22, 2014 01:53

add peek() to an iterator interface, peek() will return what you will get if you call next() next time, it will not move iterator forward

	// without lazy initialization
	class PeekingIterator implements Iterator<T> {

	private Iterator <T> it;

	private T nextV;
	private boolean hasPeekV
	private T peekV;

	public PeekingIterator (Iterator <T> iterator) {

rayjcwu / NChooseMPermutation

Created January 22, 2014 02:22

Given a string with length N, generate all permutations of choosing M characters from that string

	class NChooseMPermutation {
	TreeSet<String> ans = new TreeSet<String>();

	public Set <String> perm (String str, int M) {
	char [] charAry = str.toCharArray();
	final int N = str.length();
	perm(Str, 0, charAry, N, M);
	}

	public void perm (String str, int i, char[] charAry, int N, int M) {

rayjcwu / LongestValidParenthesis

Last active January 4, 2016 18:49

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2. Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

	// 1 dim DP version

	/*
	( ( ( ) ) ) ( ) )
	8 4 2 0 0 0 2 0 0 0
	\| \| \|
	+---------+-+
	*/
	public int longestValidParentheses(String s) {
	final int N = s.length();

rayjcwu / StockTrade

Created February 10, 2014 08:30

http://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/, http://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/, http://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

	public int maxProfit1(int[] prices) {
	if (prices.length == 0) {
	return 0;
	} else {
	int maxProfit = 0;
	int minPrice = prices[0];
	for (int i = 1; i < prices.length; i++) {
	maxProfit = Math.max(maxProfit, prices[i] - minPrice);
	minPrice = Math.min(minPrice, prices[i]);
	}

rayjcwu / Sort List

Created February 10, 2014 08:44

http://oj.leetcode.com/problems/sort-list/

	// constant space => quick sort
	public class Solution {

	// insert node in front of head linked list
	private ListNode insertFront(ListNode head, ListNode node) {
	// if head is null (empty list)
	// works fine
	node.next = head;
	return node;
	}

rayjcwu / SurroundedRegions

Created February 10, 2014 08:52

http://oj.leetcode.com/problems/surrounded-regions/

	public class Solution {
	public void solve(char[][] board) {
	final int M = board.length;
	if (M == 0) {
	return;
	}
	final int N = board[0].length;
	boolean [][] visited = new boolean[M][N];

	for (int i = 0; i < M; i++) {

rayjcwu / ZigZag Conversion

Last active August 29, 2015 13:56

	public class Solution {
	public String convert(String s, int nRows) {
	if (nRows == 1) {
	return s;
	}

	final int strLen = s.length();
	final int blockSize = 2 * nRows - 2;
	char [] result = new char[strLen];

rayjcwu / PalindromePartition

Created February 10, 2014 22:13

	public int minCut(String s) {
	final int N = s.length();
	char []str = s.toCharArray();

	// build palindrome
	boolean [][] palindrome = new boolean[N][N];
	for (int i = N - 1; i >= 0; --i) {
	for (int j = i; j < N; j++) {
	if (i == j \|\|
	(str[i] == str[j] && (j - i == 1 \|\| palindrome[i + 1][j - 1]))) {

Ray Wu rayjcwu