Work Around Bugs: June 2013

Monday, June 24, 2013

cc150_2.3,2.4

2.3 Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.

public static boolean deleteNode(LinkedListNode n){
if(!n || !n->next) return false;
n.data = n.next.data;
n.next = n.next.next;
return true;
}

2.4 Write code to partition a linked list around a value x, such that all nodes less than x
come before alt nodes greater than or equal to x.

public LinkedListNode partition(LinkedListNode node, int x){
LinkedListNode index = node, cur = node;
while(cur){
     if(cur.data < x){
int temp = cur.data;
            cur.data = index.data;
            index.data = temp;
            index = index.next;
     }
    cur = cur.next;
    }
return node;
}

Thursday, June 20, 2013

singleton pattern

deal with multithreading:
1, synchronization: if it's used rarely in the application
public class Singleton{
private Singleton(){}
private static Singleton uniqueInstance;
public static synchronized Singleton getInstance(){
    if(uniqueInstance == null){
        uniqueInstance = new Singleton();
    }
    return uniqueInstance;
}
// other methods
}

2， make an eagerly created instance

public class Singleton{
private Singleton(){}
private static Singleton uniqueInstance = new Singleton();
public static Singleton getInstance(){
    return uniqueInstance;
}
// other methods
}

3, double check lock

public class Singleton{
private Singleton(){}
private static volatile Singleton uniqueInstance;
public static Singleton getInstance(){
    if(uniqueInstance == null){
synchronized(Singleton.class){
if(uniqueInstance == null)
          uniqueInstance = new Singleton();
       }
    }
    return uniqueInstance;
}
// other methods
}

cc150_2.2

Implement an algorithm to find the kth to last element of a singly linked list.

LinkedListNode nthToLast(LinkedListNode head, int k) {
if(k <= 0) return null;
LinkedListNode prev = head;
LinkedListNode cur = head;
while(cur && k > 1){
     cur = cur.next;
   k--;
}
if(!cur) return null;
while(cur.next){
     cur = cur.next;
     prev = prev.next;
}

return prev;
}

cc150_2.1

Write code to remove duplicates from an unsorted linked list.

//method: hashtable
public static void deleteDups(LinkedListl\lode n) {
   Hashtable table = new Hashtable();
   LinkedListNode prev = null;
   while(n){
       if(table.containsKey(n.data)){
          prev.next = n.next;
      }
      else table.put(n.data, true);
      n = n.next;
   }

}

tips: Hashtable vs HashMap
There are several differences between HashMap and Hashtable in Java:

Hashtable is synchronized, whereas HashMap is not. This makes HashMap better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.
Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.
One of HashMap's subclasses is LinkedHashMap, so in the event that you'd want predictable iteration order (which is insertion order by default), you could easily swap out the HashMap for a LinkedHashMap. This wouldn't be as easy if you were using Hashtable.

http://stackoverflow.com/questions/40471/differences-between-hashmap-and-hashtable

Wednesday, June 19, 2013

cc150_1.8

Assume you have a method isSubstring which checks if one word is a substring
of another. Given two strings, si and s2, write code to check Ifs2 is a rotation of si
using only onecalltoisSubstring (e.g., "waterbottLe" is a rotation of "erbottLewat").

public boolean isRotation(String si, String s2){
if(s1.length() != s2.length() || s1.length() == 0) return false;
return isSubstring(s1+s1, s2) ;
}

cc150_1.7

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and
column are set to 0.

public void setZeros(int[][] matrix) {
boolean[] column = new boolean[matrix[0].length];
for(int i = 0; i < matrix.length; i++){
     for(int j = 0; j < matrix[0].length; j++){
if(column[j]) continue;
          if(matrix[i][j] == 0) {
           //set i-th row and j-th col zero
   for(int k = 0; k < matrix[0].length; k++){
                   matrix[i][k] = 0;
             }
             for(int k = 0; k < matrix.length; k++){
                   matrix[k][j] = 0;
             }
   //mark column and move to next row
             column[j] = true;
             break;
          }
    }
}
}

cc150_1.6

Given an image represented by an NxN matrix, where each pixel in the image is
4 bytes, write a method to rotate the image by 90 degrees. Can you do this in
place?

public void rotate(int[][] matrix, int n){
for(int i = 0; i < n/2; i++){
   for(int j = i; j < n-1-i; j++){
      int tmp = matrix[i][j];
      matrix[i][j] = matrix[j][n-i-1];
      matrix[j][n-i-1] = matrix[n-i-1][n-j-1];
      matrix[n-i-1][n-j-1] = matrix[n-j-1][i];
      matrix[n-j-1][i] = matrix[i][j];
    }
}
}

cc150_1.5

Implement a method to perform basic string compression using the counts of
repeated characters. For example, the string aabcccccaaa would become
a2blc5a3. If the "compressed" string would not become smaller than the original
string, your method should return the original string.

//use StringBuffer to avoid useless copying
public String compressBad(String str){
   int count = 1, n = str.length();   if(n == 0) return null;
   StringBuffer res =new StringBuffer();
   for(int i = 1; i < n; i++){
      if(str.charAt(i) == str.charAt(i-1)){
          count++;
      }
   else {
          res.append(str.charAt(i-1));
    res.append(count);
          count = 1;
   }
res.append(str.charAt(n-1));
res.append(count);
String cp = res.toString();
if(cp.length() < n) return cp;
else return str.
}

//if don't use StringBuffer, first figure out the new size, then do backtracking to get desired string from a new char array.

cc150_1.4

Write a method to replace all spaces in a string with '%20'. You may assume that the
string has sufficient space at the end of the string to hold the additional characters,
and that you are given the "true" length of the string. (Note: if implementing in Java,
please use a character array so that you can perform this operation in place.)

public void replaceSpaces(char[] str, int length) {
int spacecount = 0, newlength, index;
for(int i = 0; i < length; i++){
     if(str[i] == ' ') spacecount++;
}
index = length + (spacecount<<1);
str[index--] = '\0';
for(int i = length - 1; i >= 0; i--){
       if(str[i] != ' ') str[index--] = str[i];
     else{
          str[index--] = '0';
          str[index--] = '2';
str[index--] = '%';
      }
}
}

cc150_1.3

Given two strings, write a method to decide if one is a permutation of the other.

//method 1: sort and compare
String sort(String s){
char[] content = s.toCharArray();
java.util.Arrays.sort(content);
return new String(content);
}

public boolean permutation(String s, String t){
if(s.length() != t.length()) return false;
return sort(s).equals(sort(t));
}

//method 2: hash and compare
public boolean permutation(String s, String t) {
if (s.length() != t.lengthQ) return false;
int[] count = new int[256];
for(int i = 0; i < s.length(); i++){
     int ch = s.charAt(i);
     count[ch]++;
}
for(int i = 0; i < s.length(); i++){
     count[ch]--;
    if(count[ch] < 0) return false;
}

return true;

}

cc150_1.1

1.1 Implement an algorithm to determine if a string has all unique characters. What if
you cannot use additional data structures?
//if it's ASCII characters: 256 candidates
public boolean isUnique(String str){
if(str.length() > 256) return false;
boolean[] v = new boolean[256];
for(int i = 0; i < str.length(); i++){
int ch = str.charAt[i];
      if(v[ch]) return false;
      v[ch] = true;
}
return true;
}

//use bit to save space: assume that it's a~z characters: 26 candidates, so one int = 32 bits is enough.
public boolean isUnique(String str){
int checker = 0;
for(int i = 0; i < str.length(); i++){
    int ch = str.charAt[i] - 'a';
    if( (checker & (1<<ch)) ) return false;
    checker |= (1<<ch);
}
return true;
}

Monday, June 17, 2013

Scramble string (C++ code)

Leetcode Scramble String, Apr 30 '121887 / 5901
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
思路：直接递归做超时了，因此改用DP，恩，其实是个很典型的DP题了。

bool isScramble(string s1, string s2) {
int n = s1.size();
if(s2.size() != n) return false;
if(n == 0) return true;
bool A[n][n][n+1];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
A[i][j][1] =(s1[i] == s2[j])? true : false;
}
}
for(int k = 2; k < n+1; k++){
for(int i = 0; i <= n - k; i++){
for(int j = 0; j <= n - k; j++){
A[i][j][k] = false;
for(int m = 1; m < k; m++){
if(A[i][j][m] && A[i+m][j+m][k-m]) A[i][j][k] = true;
if(A[i][j+k-m][m] && A[i+m][j][k-m]) A[i][j][k] = true;
}
}
}
}
return A[0][0][n];
}

暴力解法：
bool isScramble(string s1, string s2) {
        if(s1.size() != s2.size()) return false;
        if(s1 == s2) return true;
        int n = s1.length();
        if(n == 0) return true;
        if(n == 1) return s1 == s2;

       for(int i = 1; i < n; i++){

         string s1left = s1.substr(0,i), s1right = s1.substr(i, n-i);
         string s2left = s2.substr(0, i), s2right = s2.substr(i, n-i);
         string s2left2 = s2.substr(0, n-i), s2right2 = s2.substr(n-i, i);

        if(isScramble(s1left, s2left) && isScramble(s1right, s2right)) return true;
        if(isScramble(s1left, s2right) && isScramble(s1right, s2left)) return true;
        if(isScramble(s1left, s2left2) && isScramble(s1right, s2right2)) return true;
        if(isScramble(s1left, s2right2) && isScramble(s1right, s2left2)) return true;

        }
        return false;
    }

Path Sum II (C++ code)

Leetcode Path Sum II, Oct 14 '122982 / 8423
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

思路：递归。用完某个node之后记得把值pop出来。

void findpath(TreeNode *root, int sum, vector<vector<int>> &res, vector<int> &path){
if(!root->left && !root->right){
if(sum == 0) res.push_back(path);
return;
}
if(root->left){
path.push_back(root->left->val);
findpath(root->left, sum - root->left->val, res, path);
path.pop_back();
}
if(root->right){
path.push_back(root->right->val);
findpath(root->right, sum - root->right->val, res, path);
path.pop_back();
}
}
vector<vector<int> > pathSum(TreeNode *root, int sum) {
vector<vector<int>> res;
vector<int> path;
if(!root) return res;
path.push_back(root->val);
findpath(root, sum - root->val, res, path);
return res;
}

Path sum(C++ code)

Leetcode Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
思路：递归。要注意的是valid path必须是从root到leaf,如果只有一边没有孩子，是不算叶子的。。

bool hasPathSum(TreeNode *root, int sum) {
if(!root) return false;
int update = sum - root->val;
if(!root->left && !root->right) return (update == 0)? true : false;
return hasPathSum(root->left, update) || hasPathSum(root->right, update);
}

Longest Consecutive Sequence(C++ code)

Leetcode Longest Consecutive Sequence, Feb 143855 / 11012

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

思路：信息只要存储在区间的两个端点就行了。所以建立一个map，对于端点来说，值是对应区间的长度。每次进来一个新数i, 检查i-1, i+1是否在map中，如果是，则更新相应的端点值就行了。同时更新最长长度候选值。
ps: 不写code好像也没多久啊，竟然就手生了。。看来还是应该每天练一道。

int longestConsecutive(vector<int> &num) {
unordered_map<int,int> v;
int res = 1;
for(int i = 0; i < num.size(); i++){
if(v.find(num[i]) != v.end() ) continue;
v[num[i]] = 1;
if(v.find(num[i]-1) != v.end()) v[num[i]] += v[num[i]-1];
if(v.find(num[i]+1) != v.end()) v[num[i]] += v[num[i]+1];
if(v.find(num[i]-1) != v.end()) v[num[i] - v[num[i] - 1] ] = v[num[i]];
if(v.find(num[i]+1) != v.end()) v[num[i] + v[num[i] + 1] ] = v[num[i]];
res = max(res, v[num[i]]);
}
return res;
}