Longest Increasing Subsequence

Leetcode 300
Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

O(n^2):
Naive solution is use array T[] to track the LIS for each element in the original array. We have to track all the elements because the LIS can only increase for previous element which are smaller than current element.

public class Solution {
    public int lengthOfLIS(int[] nums) {
        // naive solution, keep another array to store the LIS so far. O(n^2)
        if (nums==null || nums.length == 0) return 0;
        int[] lens = new int[nums.length];
        int maxsofar = 1;
        for (int i = 0; i < nums.length; i++) {
            lens[i] = 1;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if ((lens[j]+1) > lens[i]) {
                        lens[i] = lens[j] + 1;
                    }
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (lens[i] > maxsofar) maxsofar = lens[i];
        }
        return maxsofar;
    }
}

Leetcode 52 - N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Backtracking (recursive)
RecursiveNQueens(Q[1 .. n],r):
if r = n + 1
    print Q
else for j ← 1 to n
    legal ← True
    for i ← 1 to r − 1
        if (Q[i] = j) or (Q[i] = j + r − i) or (Q[i] = j − r + i)
        legal ← False
    if legal
        Q[r] ← j
        RecursiveNQueens(Q[1 .. n],r + 1)

Bit Manipulation

Bit Manipulation

常用operators:
~        unary bitwise complement operator, inverts a bit pattern
<<       signed left shift operator
>>       signed right shift operator
>>>     unsigned right shift operator, a zero into the leftmost position
&        bitwise AND
^         bitwise exclusive OR   (必须有且只有一个为真才行）
|          bitwise inclusive OR

特性：
（n&(n-1) == 0) true if n is power of 2. (or if n=1)
  n^n = 0
可以用来判断两个词有没有重复字符

常见问题：
Leetcode 136 - Single Number
Leetcode 268 - Missing Number
Leetcode 318 - Maximum Product of Word Lengths

Class and Project - Design and Refactoring

Goal: Design a class to support path finding through a maze
Questions:
1. What do I want to do with the graph?
2. What is the ration of edges to nodes? (adj list or matrix?)
3. How do I need to access to nodes/edges?
4. What properties do nodes and edges need to store?

Objects that make sense, whose data and methods go together.
Interfaces are clean; private data (or data structures) are not exposed.
Easy and fast to do the operations you want to do.
Methods are short and easy to read and understand.

DFS is not short!
Solution: refactor! - restruture code without changing functionality
Each method should have one task!

还可以创建一个MazeEdge class
以及一个Coordinate class来存coordinate。

Leetcode 217 - Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

需要能够快速查询，然后有一个数和对应出现次数的对应，所以想到用Hashtable
Solution1:

import java.util.*;
public class Solution {
    public boolean containsDuplicate(int[] nums) {
        Hashtable nummap = new Hashtable();
        for (int n : nums) {
            if (nummap.get(n) != null) return true;
            else nummap.put(n,1);
        }
        return false;
    }
}

其实只关心每个num出现没出现，0或者1，所以用不到map，只需要知道有没有就可以，所以hashset就可以。
Solution2:

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet numset = new HashSet();
        for (int n : nums) {
            if (!numset.add(n)) return true;
        }
        return false;
    }
}

黑白棋 - Java

黑白棋规则：
棋盘共有8行8列共64格。开局时，棋盘正中央的4格先置放黑白相隔的4枚棋子（亦有求变化相邻放置）。通常黑子先行。双方轮流落子。只要落子和棋盘上任一枚己方的棋子在一条线上（横、直、斜线皆可）夹着对方棋子，就能将对方的这些棋子转变为我己方（翻面即可）。如果在任一位置落子都不能夹住对手的任一颗棋子，就要让对手下子。当双方皆不能下子时，游戏就结束，子多的一方胜。

参考：
http://blog.csdn.net/da_keng/article/details/47779141

Leetcode 242 - Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

做法1：

把两个string都sort好，然后比较之。
Time: O(nlogn)
Space: O(1)

这样的话答案78.41%

public class Solution {
    public boolean isAnagram(String s, String t) {
        char[] ss = s.toCharArray();
        Arrays.sort(ss);
        String sss = new String(ss);
        char[] tt = t.toCharArray();
        Arrays.sort(tt);
        String ttt = new String(tt);
        return sss.equals(ttt);
    }
}

做法2： 用一个数组存起来
似乎比sort还要慢一些, 46.32%, 8ms。

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        else if (s.length() == 0) return true;
        int[] numbychar = new int[256];
        int num_unique = 0;
        int num_complete = 0;
        char[] s_char = s.toCharArray();
        for (char c : s_char) {
            if (numbychar[c] == 0) num_unique++;
            ++numbychar[c];
        }
        for (int i = 0; i < t.length(); i++) {
            int c = (int) t.charAt(i);
            if (numbychar[c] == 0) return false;
            --numbychar[c];
            if (numbychar[c] == 0) {
                ++num_complete;
                if (num_complete == num_unique) {
                    return i==t.length()-1;
                }
            }
        }
        return false;
    }
}

Improve the 2nd solution: use a hashtable

import java.util.*;
public class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()) return false;
        
        Hashtable 
            theTableS = new Hashtable(),
            theTableT = new Hashtable();
        for (char i:s.toCharArray()) {
            if (theTableS.containsKey(i))
                theTableS.put(i,theTableS.get(i)+1);
            else theTableS.put(i,1);
        }
        for (char i:t.toCharArray()) {
            if (theTableT.containsKey(i)) 
                theTableT.put(i,theTableT.get(i)+1);
            else theTableT.put(i,1);
        }
        return theTableT.equals(theTableS);
    }
}

Leetcode 238 - Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
O(n), 所以只能扫一遍就得到该有的信息，自然想到的是左边扫一遍右边扫一遍。
省空间的话简单，右边扫的时候直接把答案存起来。

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        //keep track of product of left elements in the array
        // then scan from right to left to multiply the right elements
        int n = nums.length;
        int[] results = new int[n];
        results[0] = 1;
        for (int i = 1; i < n; i++) {
            results[i] = results[i-1] * nums[i-1];
        }
        int right = 1;
        for (int i = n-1; i >= 0; i--) {
            results[i] *= right;
            right *= nums[i];
        }
        return results;
    }
}

Leetcode 73 - Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Naive Approach:
For word1, use insert/delete/replace to generate all strings as its children, then for each children, generate all strings etc...
But the tree will expand too fast.
Solutions:
1. DP
2. Pruning (delete the nodes that are not actual English words).

I/O Classes and Objects in Java and Read a Line

System.out is a PrintStream object that outputs to the screen

System.in is an InputStream object that reads from the keyboard

But System.in doesn't have methods to read a line directly.  There is a method
called readLine that does, but it is defined on BufferedReader objects.

- How do we construct a BufferedReader?  One way is with an InputStreamReader.
- How do we construct an InputStreamReader?  We need an InputStream.
- How do we construct an InputStream?  System.in is one.
(You can figure all of this out by looking at the constructors in the online
Java libraries API--specifically, in the java.io library.)

InputStream objects (e.g. System.in) read raw data from some source (like Keyboard), but don't format the data.
InputStreamReader objects compose the raw data into characters (2 bytes long in Java).
BufferedReader objects compose the characters into entire lines of text.

Java program that reads a line from the keyboard and prints it on the screen.

 import java.io.*;

class SimpleIO {
     public static void main(String[] args) throws Exception {
          BufferedReader keybd = 
               new BufferedReader(new InputStreamReader(System.in));
          System.out.println(keybd.readLine());
     }
}

How to read a line of text: With readLine on BufferedReader
How to create a BufferedReader: With an InputStreamReader
How to create a InputStreamReader: With an InputStream
How to create InputStream: With a URL

public class BufferedReader extends Reader

BufferedReader is a class 

Code:

import java.net.*;
import java.io.*;
class WHWWW {
    public static void main(String[] arg) throws Exception {
        URL u = new URL("http://www.whitehouse.gov/");
        InputStream ins = u.openStream();
        InputStreamReader isr = new InputStreamReader(ins);
        BufferedReader whiteHouse = new BufferedReader(isr);
        System.out.println(whiteHouse.readLine());
    }
}