rayjcwu’s gists

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 / 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 / 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 / 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 / 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 / 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 / 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 / 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 / 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 / Barasheet 9

Created January 20, 2014 07:02

Your manager has dictated that you log all exceptions in an effort to diagnose some problems with a daily process. What statement is true about this effort to comply? 1. Except for the logged message, all the information about the original exception is lost. 2. One cannot throw an exception from within a catch block. 3. The catch specification o…

	void dailyProcessingSetup() {
	try {
	...
	} catch (Exception e) {
	log(e.getMessage());
	throw new RuntimeException("exception logged in dailyProcessingSetup");
	}
	}

Ray Wu rayjcwu