zac-xin’s gists

zac-xin / TestBST.java

Created December 20, 2012 23:19

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {

zac-xin / MergeIntervals.java

Created December 20, 2012 23:06

Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].

	/**
	* Definition for an interval.
	* public class Interval {
	* int start;
	* int end;
	* Interval() { start = 0; end = 0; }
	* Interval(int s, int e) { start = s; end = e; }
	* }
	*/

zac-xin / climbStairs.java

Created December 20, 2012 22:21

Climb stairs. You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

	public class Solution {
	public int climbStairs(int n) {
	// Start typing your Java solution below
	// DO NOT write main() function

	if( n == 0 \|\| n == 1 \|\| n == 2)
	return n;

	int array[] = new int[n + 1];

zac-xin / sortedArrayToBST.java

Created December 9, 2012 16:34

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {

zac-xin / InsertCyclicSortedList.java

Created November 26, 2012 03:02

InsertCyclicSortedList

	package Chapter2;

	public class InsertCyclicSortedList {
	public static void main(String args[]){
	IntNode n1, n2, n3, n4, n5, n6,n7, n8, n9;
	n9 = new IntNode(27, null);
	n8 = new IntNode(16, n9);
	n7 = new IntNode(14, n8);
	n6 = new IntNode(12, n7);
	n5 = new IntNode(8, n6);

zac-xin / SlidingWindowMaximum.java

Created November 23, 2012 04:47

SlidingWindowMaximum

	package others;
	import java.util.Deque;
	import java.util.LinkedList;

	public class SlidingWindowMaximum {
	public static void main(String args[]){
	int arr[] = {1, 3, -1, -3, 5, 3, 6, 7, 8};
	int b[] = slidingWindowMaximum(arr, 3);
	for(int i = 0; i< b.length ; i++){
	System.out.print(b[i]+ " ");

zac-xin / testPalindromeNumber.java

Created November 23, 2012 03:26

testPalindromeNumber

	package others;

	public class testPalindromeNumber {
	public static void main(String args[]) {
	System.out.println(test(35553));
	}

	public static boolean test(int n) {
	int k = 1;
	while (n / k > 10) {

zac-xin / threeSum.java

Created November 23, 2012 02:38

3sum

	package others;

	import java.util.Arrays;
	import java.util.ArrayList;

	public class threeSum {
	public static void main(String args[]) {
	int arr[] = {-7 , 8, 9, 2 , -3, -5, 3, 2, 5, 1, 2, -4};
	System.out.println(getThreeSum(arr));
	}

zac-xin / PrintZigZagOrder.java

Created November 15, 2012 03:15

Print a binary tree in zig zag level order

	/*
	* Print a binary tree in zig zag level order
	*/

	package Chapter4;

	import java.util.Stack;

	public class PrintZigZagOrder {
	public static void main(String args[]){

zac-xin / ReverseString.java

Created November 15, 2012 03:02

Reverse a string recursively



	public class ReverseString {
	public static void main(String args[]){
	String s = "reverse test 123456789";
	char[] array = s.toCharArray();
	reverse(array, 0, array.length - 1);
	System.out.println(array);
	}