3Sum Closest -- Leetcode

Question:

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Answer:

public int threeSumClosest(int[] nums, int target) {

        Arrays.sort(nums);

        int res = 0, min = Integer.MAX_VALUE;

        

        for(int i=0; i < nums.length; ++i){

            int j = i+1;

            int k = nums.length - 1;

            while(j < k){

                int sum = nums[i] + nums[j] + nums[k];

                int diff = Math.abs(sum - target);

                if( diff < min){

                    min = diff;

                    res = sum;

                }

                if(sum < target){

                    j++;

                }else{

                    k--;

                }

            }

        }

        return res;

}

3Sum Smaller -- Leetcode

Question:

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Answer:
Time: O(n^2), sort method.
public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int count = 0;
     
        for(int i=0; i < nums.length; ++i){
            int j = i+1;
            int k = nums.length - 1;

            while(j < k){
                if(nums[i] + nums[j] + nums[k] < target){
                    count += (k-j);
                    j++;
                }else if(nums[i] + nums[j] + nums[k] >= target){
                    k--;
                }
            }
        }
        return count;
}

Android Timer example

package com.example.androidtimer;

import android.app.Activity;
import android.os.Bundle;
import android.view.Menu;
import android.view.MenuItem;
import android.os.Handler;
import android.os.SystemClock;
import android.view.View;
import android.widget.Button;
import android.widget.TextView;

public class MainActivity extends Activity {

private Button startButton;
private Button pauseButton;

private TextView timerValue;

private long startTime = 0L;

private Handler customHandler = new Handler();

long timeInMilliseconds = 0L;
long timeSwapBuff = 0L;
long updatedTime = 0L;

@Override
public void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);

timerValue = (TextView) findViewById(R.id.timerValue);

startButton = (Button) findViewById(R.id.startButton);

startButton.setOnClickListener(new View.OnClickListener() {

                        public void onClick(View view) {

startTime = SystemClock.uptimeMillis();
customHandler.postDelayed(updateTimerThread, 0);
}
});

pauseButton = (Button) findViewById(R.id.pauseButton);

pauseButton.setOnClickListener(new View.OnClickListener() {

public void onClick(View view) {

timeSwapBuff += timeInMilliseconds;
customHandler.removeCallbacks(updateTimerThread);
}
});
}

private Runnable updateTimerThread = new Runnable() {

public void run() {

timeInMilliseconds = SystemClock.uptimeMillis() - startTime;

updatedTime = timeSwapBuff + timeInMilliseconds;

int secs = (int) (updatedTime / 1000);
int mins = secs / 60;
secs = secs % 60;
int milliseconds = (int) (updatedTime % 1000);
timerValue.setText("" + mins + ":"
+ String.format("%02d", secs) + ":"
+ String.format("%03d", milliseconds));
customHandler.postDelayed(this, 0);
}
};
}

Android -- Eventbus

/*

public class EventBus {

HashMap<String, List<Event>>

public void register(String eventName, Event event) {};

public void unregister(String eventName, Event event){};

public void postEvent(String eventName, Object Data){};

public interface Event {

  void onEvent(Object data);

}

}

*/

class EventBus {

  private Map<String, List<Event>> map;

  

  public EventListener() {

    map = new HashMap<String, List<Event>>();

  }

  

  public void register(String eventName, Event event) {

    if (map.containsKey(eventName)) {

      map.get(eventName).add(event);

    } else {

      List<Event> events = new ArrayList<Event>();

      events.add(event);

      map.put(eventName, events);

    }

  };

  

  public void unregister(String eventName, Event event) {

    if (map.containsKey(eventName)) {

      map.get(eventName).remove(event);

    }

  };

  public void postEvent(String eventName, Object data) {

if(map.containsKey(eventName)){

List<Event> events = map.get(eventName);

for(Event event : events){

event.doEvent(data);

}

}

 

/*

    Event event = new Event();

    event.doEvent(data);

    this.register(eventName, event);

    */

  };

} 

class Event {

  private Object data;

  

  public void doEvent(Object data) {

    this.data = data;

  };

}

Valid Palindrome -- Leetcode

Question:

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Answer:
public boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            char a = s.charAt(i);
            char b = s.charAt(j);

            while (i < j && !Character.isLetter(a) && !Character.isDigit(a)) {
                a = s.charAt(++i);
            }

            while (j > i && !Character.isLetter(b) && !Character.isDigit(b)) {
                b = s.charAt(--j);
            }

            if (Character.toLowerCase(a) != Character.toLowerCase(b)) {
                return false;
            }
        }
        return true;
    }

Answer 2:

/*

public class EventBus {

HashMap<String, List<Event>>

public void register(String eventName, Event event) {};

public void unregister(String eventName, Event event){};

public void postEvent(String eventName, Object Data){};

public interface Event {

  void onEvent(Object data);

 }

}

*/

class EventBus {

  private Map<String, List<Event>> map;

  

  public EventListener() {

    map = new HashMap<String, List<Event>>();

  }

  

  public void register(String eventName, Event event) {

    if (map.containsKey(eventName)) {

      map.get(eventName).add(event);

    } else {

      List<Event> events = new ArrayList<Event>();

      events.add(event);

      map.put(eventName, events);

    }

  };

  

  public void unregister(String eventName, Event event) {

    if (map.containsKey(eventName)) {

      map.get(eventName).remove(event);

    }

  };

  public void postEvent(String eventName, Object data) {

if(map.containsKey(eventName)){

List<Event> events = map.get(eventName);

for(Event event : events){

event.doEvent(data);

}

}

 

/*Event event = new Event();

    event.doEvent(data);

    this.register(eventName, event);

    */

  };

} 

class Event {

  private Object data;

  public void doEvent(Object data) {

    this.data = data;

  };

}

Inorder Successor in BST -- Leetcode

Question:

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

Answer:
1. Iterative: O(h) + O(1)
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        //case 1 : if p has right subtree
        if(p.right != null){
            return minNode(p.right);
        }
       
        //case 2 : p has no right child, succ is the parent of p
        TreeNode succ = null;
        // Start from root and search for successor down the tree
        while(root != null & root != p){
            if(p.val < root.val){
                succ = root;
                root = root.left;
            }
            else if(p.val > root.val){
                root = root.right;
            }
        }
        return succ;
    }
   
    public TreeNode minNode(TreeNode root){
        if(root==null)return null;
        while(root.left != null){
            root = root.left;
        }
        return root;
    }

2. Recursive: O(h) + O(1)
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        return Util(root, p, null, null);
    }

    public TreeNode Util(TreeNode root, TreeNode p, TreeNode min, TreeNode max){
        if(p.val >= root.val){
            if(root.right != null){
                return Util(root.right, p, root, max);
            }else{
                return max;
            }
        }
        //if p.val < root.val
        else{
            if(root.left != null){
                return Util(root.left, p, min, root);
            }else{
                return root;
            }
        }
    }

Find smallest larger element than target in BST

Question:

Given a BST:

                 10

        7                    14

    4      8      12              19

                         13     16    20

   

[4,7,8,10,12,13,14,16,19,20]

Q1.  Find smallest larger element than target,  

     Example: input: target = 13,  output: 14

Q2.  Find largest smaller element than target,  

     Example: input: target = 13,  output: 12

Answer:

public class Solution {

//Q1.  Find smallest larger element than target:           Time:O(logn), Space:O(1)

public static int findNLR(TreeNode root, int target, int min, int max) throws Exception{

              //if root.val > target, return the smallest element in the subtree

        if(root.val > target){

               if(root.left != null){

                            //go left branch

                      return findNLR(root.left, target, min, root.val);

               }else{

                      return root.val;

                }

         }          

        else{

              if(root.right != null){

                          //go right branch

                     return findNLR(root.right, target, root.val, max);

              }else{

                      if(max != Integer.MAX_VALUE){

                             return max;

                     }

                     else{

                            throw new Exception();

                      }

              }

        }           

}

public static int findNL(TreeNode root, int target) throws Exception{

         return findNLR(root, target, Integer.MIN_VALUE, Integer.MAX_VALUE);

}

//Q2.  Find largest smaller element than target:               Time:O(logn), Space:O(1)

public static int findPSL(TreeNode root, int target, int min, int max) throws Exception{

                  //if root.val < target, return the largest element in the subtree

        if(root.val < target){

             if(root.right!=null){

                            //go right branch

                    return findPSL(root.right, target, root.val, max);

             }else{

                    return root.val;

             }

        }

        else{

               if(root.left!=null){

                            //go left branch

                      return findPSL(root.left, target, min, root.val);

               }else{

                      if(min != Integer.MIN_VALUE){

                            return min;

                      }

                      else{

                             throw new Exception();

                      }

               }

         }

}

public static int findPS(TreeNode root, int target) throws Exception{

         return findPSL(root, target, Integer.MIN_VALUE, Integer.MAX_VALUE);

}

   

  public static void main(String[] args) throws Exception {

        TreeNode root = new TreeNode(10);

        root.left = new TreeNode(7);

        root.right = new TreeNode(14);

        root.left.left = new TreeNode(4);

        root.left.right = new TreeNode(8);

        root.right.left = new TreeNode(12);

        root.right.left.right = new TreeNode(13);

        root.right.right = new TreeNode(19);

        root.right.right.left = new TreeNode(16);

        root.right.right.right = new TreeNode(20);

        int res = findNL(root, 13);

        System.out.println(res);   

   }

}

Binary Tree Path -- Leetcode

Question:

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

Answer:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<String>();
        if(root==null){
            return res;
        }
       
        List<List<Integer>> tmp = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        Util(root, path, tmp);
       
        for(int i=0;i<tmp.size();++i){
            List<Integer> path_int = tmp.get(i);
            String path_str = convertStr(path_int);
            res.add(path_str);
        }
        return res;
    }
   
    public void Util(TreeNode root, List<Integer> path, List<List<Integer>> res){
        if(root==null){
            return;
        }
        //edge case
        path.add(root.val);
        if(root.left==null && root.right==null){
            //clone a new path array
            ArrayList<Integer> path_new = new ArrayList<Integer>(path);
            res.add(path_new);
            //backtrack!
            path.remove(path.size()-1);
            return;
        }
        //Recursive case
        Util(root.left, path, res);
        Util(root.right, path, res);
        //backtrack!
        path.remove(path.size()-1);
        return;
    }
   
    public String convertStr(List<Integer> path){
        if(path == null || path.size()==0) return null;
       
        StringBuilder sb = new StringBuilder();
        int len = path.size();
        for(int i=0; i<len-1; ++i){
            sb.append(path.get(i));
            sb.append("->");
        }
        sb.append(path.get(len-1));
        return sb.toString();
    }
}

Number of Island -- Leetcode

Question:

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

Answer:
1. Inplace, Time: O(m*n), Space:O(1)

public class Solution {

    public int numIslands(char[][] grid) {

        if(grid==null)return 0;

        int m = grid.length;

        if(m==0)return 0;

        int n = grid[0].length;

        int count=0;

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

            for(int j=0;j<n;++j){

                if(grid[i][j]=='1'){

                    count++;

                    DFS(grid, i,j);

                }

            }

        }

        return count;

    }

    public void DFS(char[][] grid, int i, int j){

        int m=grid.length, n=grid[0].length;

        if(i<0||i>=m||j<0||j>=n)return;

        if(grid[i][j]!='1'){

            return;

        }

        grid[i][j]='2';

        DFS(grid,i-1,j);

        DFS(grid,i,j-1);

        DFS(grid,i+1,j);

        DFS(grid,i,j+1);

        return;

    }

}


2.  Time: O(m*n), Space:O(m*n), using additional boolean[m][n] flag.
public class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null)return 0;
        int m = grid.length;
        if(m==0)return 0;
        int n = grid[0].length;
        int count=0;
        boolean[][] flag;
       
        flag = new boolean[m][];
        for(int i=0;i<m;++i){
            flag[i] = new boolean[n];
            for(int j=0;j<n;++j){
                flag[i][j]=false;
            }
        }
               
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(grid[i][j]=='1' && flag[i][j]==false){
                    count++;
                    DFS(grid,i,j,flag);
                }
            }
        }
        return count;
    }

    public void DFS(char[][] grid, int i, int j, boolean[][] flag){
        //check valid boundary
        int m=grid.length, n=grid[0].length;
        if(i<0||i>=m||j<0||j>=n)return;
       
        if(grid[i][j]=='1' && flag[i][j]==false){
            flag[i][j]=true;
            DFS(grid,i-1,j,flag);
            DFS(grid,i,j-1,flag);
            DFS(grid,i+1,j,flag);
            DFS(grid,i,j+1,flag);
        }
        return;
    }
}