wangchauyan

/*
  Implement an algorithm to detemine if a string has all unique characters. 
  What if you cannot use additional data structure.
*/

// solution 1, with an array, time complexity = O(n), space complexity = O(1)
public class  solution  {
    public boolean isUniqueChar(String str) { 
        if(str == null || str.length() == 0)
            return false;

wangchauyan

/*
Give a string, and a dictionary, find out if this string could be segmented by a space which's substring 
are in this dictionary. 

For example, String "leetcode", dictionary ["leet", "code"], 
then return true, cause this string could be segmented as "leet code";
*/

public class Solution {
    public boolean wordBreak(String str, Set<String> dict) {

wangchauyan

/*
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) {
        if(n == 0 || n == 1) return 1; 
        int finalWays = 0; 
        int f1 = 1;
        int f2 = 1;

wangchauyan

public class Solution {
    public int[] plusOne(int[] array) {
        if (array == null) return null;
        int carry = 0; 
        for(int i = array.length-1; i >= 0; i--) {
            array[i] += (i == array.length-1 ? 1+carry : carry);
            carry = array[i]/10;
            array[i] %= 10;
        }
        if(carry == 0) return array;

wangchauyan

/*
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
*/

wangchauyan

/*
Given a string, find the length of the longest substring without repeating characters. 
For example, the longest substring without repeating letters for "abcabcbb" is "abc", 
which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
*/
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) return 0; 
        
        // Time Complexity = O(n*2) = O(n), Space Complexity = O(n)

wangchauyan

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

wangchauyan

public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true; 
        if(checkHeight(root) == -1) return false;
        else return true;
    }
    
    int checkHeight(TreeNode node) {
        if(node == null) return 0;
        int leftHeight = checkHeight(node.left);

wangchauyan

package wcy.leetcode.gist;

/**
 * Created by ChauyanWang on 12/19/14.
 */
public class string2Int {
    public int atoi(String number) {
        if (number == null || number.length() == 0) return 0;

        double result = 0;

wangchauyan

package wcy.leetcode.gist;

/**
 * Created by ChauyanWang on 12/20/14.
 */
public class romanToInt {
    int getInteger(char c) {
        switch (c) {
            case 'i': return 1;
            case 'v': return 5;