Longest SubString Without Repeating Characters LeetCode

开始我用的int [] 来存index，发现不行，因为我不知道具体里面有多少个字符。看了下大牛答案，用的是Hashmap非常好用啊。 要想写的快，方法得对。

public int lengthOfLongestSubstring(String s) {
        if (s==null || s.length() == 0) return 0;
     
        Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
        int start = 0;
        int end = 0;
        int len = s.length();
        int result = 0;
     
        while (end < len) {
            Integer c = new Integer(s.charAt(end));
            if (!hm.containsKey(c)){
                hm.put(c, end);
            } else {
                int diff = end - start;
                if (diff > result) result = diff;
                Integer index = hm.get(c);
                start = Math.max(start, index + 1);
                hm.put(c,end);
            }
            end++;
        }
        return (result > (end - start)) ? result : (end - start);
    }

Wow. I was on the right track. For two passes solution, using a boolean array.

public int lengthOfLongestSubstring(String s) {
        boolean[] exist = new boolean [256];
        int i=0, maxLen = 0;
        for (int j=0; j<s.length(); j++) {
            while (exist[s.charAt(j)]) {
                exist[s.charAt(i)] = false;
                i++;
            }
            exist[s.charAt(j)] = true;
            maxLen = Math.max(j-i+1, maxLen);
        }
        return maxLen;
    }

For one pass solution, using a integer array.

Median of Two Sorted Array LeetCode

这个题也可以是findKthElement from two sorted Array。 思路很简单就是不停的把A，B两个Array分别切成两段。这样比较中间值，把小值得小的部分和大数的大的部分（估计只有我自己懂）去掉。最后终止条件为三种，1. A的size为0,2，B的size为0， 3 Kth为0.
当Kth为0的时候，意味着两边都有一个元素，kth为0，我们就选两个剩余元素小的那个。

难点：实现过程中，下标一定要注意。

public double findMedianSortedArrays(int A[], int B[]) {
        int lenA = A.length;
        int lenB = B.length;
        int total = lenA + lenB;
       
        if (total % 2 != 0) {
            return ((double)findKthElement(A, B, total/2, 0, lenA - 1, 0, lenB - 1));
        } else {
            return (findKthElement(A, B, total/2 - 1, 0, lenA - 1, 0, lenB - 1) +
                    findKthElement(A, B, total/2, 0, lenA - 1, 0, lenB - 1)) /2;
        }
    }
   
    private double findKthElement(int[] A, int[] B, int kth, int startA, int endA, int startB, int endB){
        int sizeA = endA - startA + 1;
        int sizeB = endB - startB + 1;
       
        if (sizeA == 0) return B[startB + kth];
        if (sizeB == 0) return A[startA + kth];
        if (kth == 0) return A[startA] > B[startB] ? B[startB] : A[startA];
       
        //Binary Search
        int midA = sizeA * kth /(sizeA + sizeB);
        int midB = kth - midA - 1;
       
        //Match to the original index
        midA += startA;
        midB += startB;
       
        if (A[midA] < B[midB]) {
            kth -= midA - startA + 1;
            endB = midB;
            startA = midA + 1;
        } else {
            kth -= midB - startB + 1;
            endA = midA;
            startB = midB + 1;
        }
        return findKthElement(A, B, kth, startA, endA, startB, endB);
    }

Restore IP Addresses LeetCode

这个题，在我写了无数次的DFS之后，还是卡住了，这个题容易出现bug的地方很多。

比如终止条件有三种要想到，太长太短或者是正好找到。
第二个问题是，当一个字段开头为0的时候，直接跳到下一个字段。
第三个问题是，在储存的时候，会在后面多加一个点要去掉，并且存之前判断是否有重复。
public ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> result = new ArrayList<String>();
        if (s==null || s.length() < 4) return result;
        String ip = "";
        generate(s, 0, 0, result, ip);
        return result;
    }
 
    public void generate(String s, int start, int depth, ArrayList<String> result, String ip){
        int MAX_DEPTH = 4;
        // there are three conditions to stop the DFS
        // too long
        if (s.length() - start > (MAX_DEPTH - depth) * 3) return ;
        // too short
        if (s.length() - start < MAX_DEPTH - depth) return;
        //found one possible solution
        if (depth == 4){
            //remove the "."
            ip = ip.substring(0, ip.length() - 1);
            if (!result.contains(ip)) result.add(ip);
            return;
        }
        //update every depth
        int num = 0;
        for (int i = start; i < Math.min(start + 3, s.length()); i++){
            num = num*10 + (s.charAt(i) - '0');
         
            if (num <=255){
                generate(s, i+1, depth+1, result, ip + num + ".");
            }
            //if this depth start with 0, then we go to the next depth
            if (num == 0) break;
        }
    }

Previous solution is not clear since we did not make it as specific as possible.
DFS is key function
isValid is checking each small string is valid or not.

public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();
        if (s.length() < 4 || s.length() > 12) return result;
        dfs(result, "" ,s ,0);
        return result;
    }
   
    private void dfs(List<String> result, String currString, String s, int count) {
        if (count == 3 && isValid(s)) {
            result.add(currString+s);
            return;
        }
        for (int i=1; i<4 && i <s.length();i++) {
            String tempString = s.substring(0,i);
            if (isValid(tempString)) {
                dfs(result, currString+tempString+".", s.substring(i), count+1);
            }
        }
    }
   
    private boolean isValid(String s) {
        if (s.charAt(0) == '0') return s.length() == 1;
        int value = Integer.parseInt(s);
        return value>=0 && value<=255;
    }

Remove Duplicates from Sorted Array II LeetCode

水题 需要一个counter来记录出现了几次。
update the count first and the count will be condition to store the value.

public int removeDuplicates(int[] A) {
        if (A.length < 3) return A.length;
        int index = 1;
        int count = 1;
        for (int i = 1; i < A.length; i++){
     
            if (A[i] == A[i-1]){
                count++;
            } else {
                count = 1;
            }
         
            if (count <= 2){
                A[index] = A[i];
                index++;
            }
        }
        return index;
    }

Remove Duplicate from Sorted Array LeetCode

简单题，发现对Array掌握的还不错啊。

public int removeDuplicates(int[] A) {
        int index = 0;
        for (int i = 0; i < A.length; i++){
           
            if (i== 0 || (i >0 && A[i] != A[i - 1])) {
                A[index] = A[i];
                index++;
            } else {
                continue;
            }
        }
        return index;
    }

Letter Combinations LeetCode

鉴于我对DFS的练习实在太少了，突击练了一下。
发现难道是不难，一定要把终止条件，写的很清楚。

public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> result = new ArrayList<String>();
        //Stop
        if (null == digits || digits.length() == 0){
            result.add("");
            return result;
        }
        String[] map = {"abc","def","ghi","jkl","mno","pqrs", "tuv", "wxyz"};
        for (String str : letterCombinations(digits.substring(1))) {
            for (char c : map[digits.charAt(0) - '0' - 2].toCharArray()){
                result.add(c + str);
            }
        }
        return result;
    }

Reverse Integer LeetCode

这个题三个地方需要注意，正负，开始为0，以及Overflow.
一般做过atoi，都知道会有正负和overflow，开头为0，我直接写出来的程序已经误打误撞解决了。

Overflow有几种处理方式，第一是throw exception， 第二个是判断边界条件，可以写的很严格，也可以用MAX_VALUE/10.

public int reverse(int x) {
        //正负问题
       boolean negative = x < 0 ? true: false;
       int result = 0;
       int temp = Math.abs(x);
       int rightDigit = 0;
     
       //0开头的问题已经解决了
       while (temp != 0) {
           rightDigit = temp % 10;
           result = result * 10 + rightDigit;
           temp = temp/10;
       }
     
       if (result > Integer.MAX_VALUE) {
           return Integer.MAX_VALUE;
       }
       return negative == true ? result*(-1) : result;
    }

Palindrome Partitioining LeetCode

这个题是最典型的DFS问题，无奈我对DFS掌握的实在不怎么样。这个题很有可能面试的时候联系Trie问一问，我一定要看下Trie，稍后发总结。

要点： temp当中存的就是没一个DFS伸到最深处，然后把结果存到result里面。

时间复杂度为O(n^2)

public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        ArrayList<String> temp = new ArrayList<String>();
       
        findPartition(s,0,temp,result);
        return result;
    }
   
    public void findPartition(String s, int begin, ArrayList<String> temp,
        ArrayList<ArrayList<String>> result){
            int len = s.length();
            if (begin >= len) {
                ArrayList<String> copy = new ArrayList<String>();
                for (int j = 0; j < temp.size(); j++){
                    copy.add(temp.get(j));
                }
                result.add(copy);
            }
           
            for (int i = begin; i < len; i++){
                if (isPalindrome(s, begin, i)) {
                    temp.add(s.substring(begin, i+1));
                    findPartition(s, i+1, temp, result);
                    temp.remove(temp.size() - 1);
                }
            }
    }
   
    public boolean isPalindrome(String s, int begin, int end){
        while (begin < end) {
            if (s.charAt(begin++) != s.charAt(end--)) return false;
        }
        return true;
    }

Sum Root to Leaf Number LeetCode

这个题是DFS。 需要注意的是，碰到根节点的时候需要判断处理一下。

public int sumNumbers(TreeNode root) {
        return helper(root, 0);
    }
    public int helper(TreeNode root, int current){
        if (root == null) return 0;
     
        current = current * 10 + root.val;
     
        int sum = 0;
        sum += helper(root.left, current);
        sum += helper(root.right, current);
     
       //千万别忘记
        if (sum == 0){
            sum = current;
        }
        return sum;
    }

Find a cleaner solution:
public int sumNumbers(TreeNode root) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        return helper(root, 0);
    }
   
    public int helper(TreeNode root, int current){
        if(root == null) return 0;
       
        if (root.left == null && root.right == null) {
            return current*10+root.val;
        }
        return helper(root.left, current*10+root.val) + helper(root.right, current*10+root.val);
    }

Binary Tree Level Order Traversal II LeetCode

这个题跟I是一模一样的，我偷懒了，我直接存的时候给他逆序存了一下。

public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
       if (root == null) return result;
       Queue<TreeNode> q = new LinkedList<TreeNode>();
       q.add(root);
     
       int currentElement = 1;
       while (q.size() != 0) {
           ArrayList<Integer> currentLevel = new ArrayList<Integer>();
           int nextElement = 0;
           for (int i = 0; i < currentElement; i++){
               TreeNode curr = q.poll();
               currentLevel.add(curr.val);
             
               if (curr.left != null) {
                   q.add(curr.left);
                   nextElement++;
               }
               if (curr.right != null) {
                   q.add(curr.right);
                   nextElement++;
               }
           }
           result.add(0,currentLevel);
           currentElement = nextElement;
       }
       return result;
    }

check this solution. It seems much easier than the previous one.

public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) return result;
       
        List<TreeNode> nodeList = new ArrayList<TreeNode>();
        List<Integer> valueList = new ArrayList<Integer>();
        nodeList.add(root);
        valueList.add(root.val);
        result.add(valueList);
       
        while (nodeList.size() > 0) {
            List<TreeNode> tempNodeList = new ArrayList<TreeNode>();
            List<Integer> tempValueList = new ArrayList<Integer>();
            for (int i = 0; i < nodeList.size(); i++) {
                TreeNode currNode = nodeList.get(i);
                if (currNode.left != null) {
                    tempNodeList.add(currNode.left);
                    tempValueList.add(currNode.left.val);
                }
                if (currNode.right != null) {
                    tempNodeList.add(currNode.right);
                    tempValueList.add(currNode.right.val);
                }
            }
            if (tempValueList.size() > 0) {
                result.add(0, tempValueList);
            }
            nodeList = tempNodeList;
        }
        return result;
    }

Binary Tree Level Order Traversal LeetCode

这个题思路很简单，利用一个Queue来存所有的node，然后利用两个counter来存当前层的元素个数，和下一层的元素个数。
BFS 现在BFS写的越来越熟练了，DFS还是不够熟练。


public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null) return result;

Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(root);

int currentElement = 1;

while (q.size() != 0 ){
int nextElement = 0;
ArrayList<Integer> currentLevel = new ArrayList<Integer>();
//check every node in the current level
for (int i = 0; i < currentElement; i++){
TreeNode curr = q.poll();
currentLevel.add(curr.val);
//check the left and right of the current node
//If it's not null, we add the node in the queue and update the nextElement
if (curr.left != null) {
q.add(curr.left);
nextElement++;
}
if (curr.right != null) {
q.add(curr.right);
nextElement++;
}
}
result.add(currentLevel);
currentElement = nextElement;
}
return result;
    }

Decode Ways LeetCode

很简单就两个case需要看下，一个是有0的时候，有0的时候如果前方的数，不是1或者2，直接返回0，有0就将当前的dp table 里的数字为0，因为他只有出现10 或者20.
另一种情况就是1* 或者2*。 2*只可能是到26.所以出现的这个情况的话就是会有两种组合。一所以就是加上dp[i+2]。
普通情况就是照抄前一个table的元素。

public int numDecodings(String s) {
        if (s == null || s.length() == 0) return 0;
        int len = s.length();
        int[] dp = new int[len + 1];
       
        dp[len] = 1;
       
        for (int i = len - 1; i>=0; i--){
            if (s.charAt(i) - '0' == 0) {
                dp[i] = 0;
                if (i > 0 && (s.charAt(i - 1) - '0' == 0 || s.charAt(i - 1) - '0' > 2)){
                    return 0;
                }
            } else {
                dp[i] = dp[i + 1];
                if (i + 1 <s.length() && (s.charAt(i) - '0' == 1 ||(s.charAt(i) - '0' == 2 && s.charAt(i + 1) - '0' <= 6))){
                    dp[i] += dp[i+2];
                }
            }
        }
        return dp[0];
    }

Word Search LeetCode

DFS， 这个里面搞了一个boolean二维数组，来记录该path是否已经经过该字母。
注意上下左右的边界条件。

public boolean exist(char[][] board, String word) {
        int height = board.length;
        int width = board[0].length;
        boolean[][] visited = new boolean[height][width];
        for (int i = 0; i < height; i++){
            for (int j = 0; j < width; j++){
                if (search(board,visited, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
 
    private boolean search(char[][] board, boolean[][] visited,int row, int col,
                    String word, int index){
        if (word.charAt(index) != board[row][col]) {
            return false;
        }
        if (index == word.length() - 1) {
            return true;
        }
     
        int height = board.length;
        int width = board[0].length;
        visited[row][col] = true;
        //up
        if (row > 0 && !visited[row - 1][col]
            && search(board, visited, row - 1, col, word, index + 1)){
            return true;
        }
        //down
        if (row < height - 1 && !visited[row + 1][col]
            && search(board, visited, row + 1, col, word, index +1)) {
            return true;
        }
        //left
        if (col > 0 && !visited[row][col - 1]
            && search(board, visited, row, col - 1, word, index + 1)){
            return true;      
        }
        //right
        if (col < width - 1 && !visited[row][col+1]
            && search(board, visited, row, col + 1, word, index + 1)){
            return true;      
        }
        // if we did not find the path we need set this position as unvisited
        visited[row][col] = false;
     
        return false;
    }

If we can use the the letters multiple times, then the code can be like this.
    //Using more than once
    public static boolean existDup(char[][] board, String word) {
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (helperDup(board, word.substring(1), i, j))
                        return true;
                }
            }
        }
        return false;
    }
   
    private static boolean helperDup(char[][] board, String tempWord, int row, int col) {
        if (tempWord.length() == 0) return true;
       
        //Stay the same place
        if (board[row][col] == tempWord.charAt(0)) {
        if (helperDup(board, tempWord.substring(1), row, col)) {
        return true;
        }
        }
       
        //Go LEFT
        if (row > 0 && board[row - 1][col] == tempWord.charAt(0)) {
            if (helperDup(board, tempWord.substring(1), row-1, col))
            return true;
        }
        //Go RIGHT
        if (row <board.length-1 && board[row + 1][col] == tempWord.charAt(0)) {
            if (helperDup(board, tempWord.substring(1), row+1, col))
            return true;
        }
        //Go UP
        if (col > 0 && board[row][col-1] == tempWord.charAt(0)) {
            if (helperDup(board, tempWord.substring(1), row, col-1))
            return true;
        }
        //Go DOWN
        if (col < board[0].length - 1 && board[row][col+1] == tempWord.charAt(0)) {
            if (helper(board, tempWord.substring(1), row, col+1))
            return true;
        }
        return false;
    }

SubSets LeetCode

这个题也是不停的往里写数，没有重复非常容易解决。

public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        result.add(new ArrayList<Integer>());
        Arrays.sort(S);
     
        for (int i = 0; i < S.length; i++){
            int size = result.size();
            for (int j = 0; j < size; j++){
                ArrayList<Integer> temp = new ArrayList<Integer>();
                temp.addAll(result.get(j));
                temp.add(S[i]);
                result.add(temp);
            }
        }
        return result;
    }

Leetcode changed the return type as <List<List<Integer>>. The updated solution is as follows:

public List<List<Integer>> subsets(int[] S) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        result.add(new ArrayList<Integer>());
        Arrays.sort(S);
       
        for (int i=0; i<S.length; i++) {
            List<List<Integer>> newResult = new ArrayList<List<Integer>>();
            newResult.addAll(result);
            for (List<Integer> sub : newResult){
                List<Integer> temp = new ArrayList<Integer>();
                temp.addAll(sub);
                temp.add(S[i]);
                result.add(temp);
            }
           
        }
        return result;
       
    }

Combinations LeetCode

这个题就是用下递归，逐个把最大的数放入combine（i-1, k-1)中，成为combine （i, k).

举个例子容易理解些。 combine（3， 1） 成为 combine （4， 2）

[1, 4] [2, 4] [3, 4]
[1, 3] [2, 3]
[1, 2]
我觉得这个题用recursive写非常的清晰和整齐。我自己都被程序感动了。

代码如下
public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        if (n < k) return null;
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (k == 1){
            for (int i = 1; i <= n; i++){
                ArrayList<Integer> current = new ArrayList<Integer>();
                current.add(i);
                result.add(current);
            }
        } else {
            for (int i = n; i >= k; i--){
                for (ArrayList<Integer> current : combine(i-1, k-1)){
                    current.add(i);
                    result.add(current);
                }
            }
        }
        return result;
    }

Sqrt LeetCode

原来没觉得这道题难，看来第一遍刷leetcode没有把testcase设计的非常精准。现在我重新写出现了两个问题。 第一个问题就是要判断数字是否大于1，因为0和1这两个case比较特殊。
第二个问题就是涉及到越界的问题。
我倾向于第二种，就是最后数据类型转换的时候要小心。

第一种写法
public int sqrt(int x) {
        double diff = 0.01;     // 误差
        int low = 0;
        int high = x;
       
        while(low <= high){
            // 注意越界！所以用double来存
            double mid = low + (high-low)/2;
            if(Math.abs(mid*mid-x) <= diff){
                return (int)mid;
            }else if(x > mid*mid+diff){
                low = (int)mid+1;
            }else if(x < mid*mid-diff){
                high = (int)mid-1;
            }
        }
       
        // 当找不到时候，这是low,high指针已经交叉，取较小的，即high
        return high;
    }

第二种写法：
 public int sqrt(int x) {
        if (x==0 || x==1) return x;
        long low = 1;
        long high = x;
        long mid = 0;
     
        while (low <= high){
            mid = (low + high)/2;
            Long upper = mid + 1;
            if (mid*mid <=x && upper*upper >x){
                break;
            }
            if (mid*mid > x){
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
    return new Long(mid).intValue();
    }

Newton Method.

public int sqrt(int x) {
        if (x==0) return 0;
        double lastY = 0;
        double y=1;
        while (y != lastY) {
            lastY = y;
            y = (y+x/y)/2;
        }
        return (int)(y);
    }

AddBinary LeetCode

从最长的最后一位往前加，保证是从最低位加到最高位。
搞不懂，之前都可以通过的。

public String addBinary(String a, String b) {
        String result = "";
int lenA = a.length();
int lenB = b.length();
int maxLen = lenA > lenB ? lenA : lenB;
int curr = 0;
int currA = 0;
int currB = 0;
int carry = 0;

for(int i = 0; i < maxLen; i++){
//current bit of string a
if(lenA > 0) currA = a.charAt(lenA - 1) - '0';
else currA = 0;
//current bit of string b
if(lenB > 0)currB = b.charAt(lenB - 1) - '0';
else currB = 0;
//addition
curr = (currA + currB + carry)%2;
carry = (currA + currB + carry)/2;
result = curr + result;
lenA--; lenB--;
}


if (carry == 1) return "1" + result;
else return result;

    }
}

Anagrams LeetCode

把每个词汇的字母进行排序，然后当做Key，放到HashMap中，实现很容易。
开始以为每个group存到一个ArrayList里面呢。

public ArrayList<String> anagrams(String[] strs) {
        ArrayList<String> result = new ArrayList<String>();
        HashMap<String, ArrayList<String>> hm = new HashMap<String, ArrayList<String>>();
for (String str : strs){
char[] chars = str.trim().toCharArray();
Arrays.sort(chars);
String key = new String(chars);

if (hm.containsKey(key)){
hm.get(key).add(str);
} else {
ArrayList<String> temp = new ArrayList<String>();
temp.add(str);
hm.put(key, temp);
}
}

for (ArrayList<String> group : hm.values()){
if (group.size()>1){
result.addAll(group);
}
}
return result;
    }

Permutations LeetCode

因为不考虑重复，就是不停的往一个ArrayList里面插数。
例如 1 2 3 4，现在想加入5.
就在5个不同的位置加入5. 成为 51234， 15234， 12534， 12354， 12345

难的在permutation2.稍后就写2.


NonRecursion Version:

public ArrayList<ArrayList<Integer>> permute(int[] num) {
       ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
       result.add(new ArrayList<Integer>());
       //Adding each element to the result
       for (int i=0; i<num.length; i++) {
           ArrayList<ArrayList<Integer>> current = new ArrayList<ArrayList<Integer>>();
           //Adding the element to each permutation (e.x, 3 [1, 2])
           for (ArrayList<Integer> perm : result) {
               //Adding the element to each place for each location
               for (int j=0; j<=perm.size();j++) {
                   perm.add(j,num[i]);
                   ArrayList<Integer> temp = new ArrayList<Integer>(perm);
                   current.add(temp);
                   perm.remove(j);
               }
           }
           result = new ArrayList<ArrayList<Integer>>(current);
       }
       return result;
    }

RemoveElement LeetCode

水题。碰到target的数就跳过。

public int removeElement(int[] A, int elem) {
            int index = 0;
            for (int i=0; i<A.length; i++){
                if (A[i]!=elem) {
                    A[index++]=A[i];
                }
            }
        return index;  
    }

Swap Nodes in Pairs LeetCode

我最怕就是linkedlist的题，绕一绕就把我绕糊涂了。这个题比较简单，一共就两个节点换。

第一开始用recursion 的方法写了一下，顺利通过。
第二次用iterative的方法写了一下，出了点小问题。经改正顺利通过。

纯实现题，无思路可言。
Recursive
public ListNode swapPairs(ListNode head) {
        if (head == null) return null;
        else if (head.next == null) return head;
        else {
            ListNode nextHead = swapPairs(head.next.next);
            ListNode temp = head.next;
            head.next = nextHead;
            temp.next = head;
            return temp;
        }
    }

Iterative
public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        ListNode prev = dummy;
        ListNode curr = head;
        prev.next = head;
       
        while (curr!=null && curr.next!=null){
            ListNode nextHead = curr.next.next;
            prev.next = curr.next;
            curr.next.next = curr;
            curr.next = nextHead;
            prev = curr;
            curr = nextHead;
        }
        return dummy.next;
    }

Merge K Sorted Lists LeetCode

思路: 先写两个lists merge的case，然后两两进行merge

时间复杂度为 log（K)*M
K为List的个数， M为最大List的长度。

public ListNode mergeKLists(ArrayList<ListNode> lists) {
int last = lists.size()-1;
if (last < 0) return null;
while (last > 0){
int curr = 0;
while (curr<last){
lists.set(curr, mergeTwoSortedList(lists.get(curr++), lists.get(last--)));
}
}
return lists.get(0);
}
//Merge two sorted list
public ListNode mergeTwoSortedList(ListNode l1, ListNode l2){
ListNode temp = new ListNode(-1);
ListNode prev = temp;

while(l1!=null && l2!=null){
if (l1.val>l2.val) {
prev.next = l2;
l2 = l2.next;
} else {
prev.next = l1;
l1 = l1.next;
}
prev = prev.next;
}

if (l1!=null) prev.next = l1;
if (l2!=null) prev.next = l2;

return temp.next;
}

Generate Parentheses LeetCode

这个题唯一绕一点的是递归过程中，返回的值。
比如n=3。 左边为（（的时候，这个时候，我们要么加左括号，然后lps=3， 补足右括号。
要么加右括号，加完右括号，我们可以选择加左括号或者右括号。

public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<String>();
        generate(res, "", 0, 0, n);
        return res;
    }
 
    public void generate(ArrayList<String> res, String temp, int lps, int rps, int n){
        if (lps==n){
            for (int i=0; i<n-rps;i++){
                temp += ")";
            }
            res.add(temp);
            return;
        }
        generate(res, temp+"(", lps+1, rps, n);
        if (rps<lps)
        generate(res, temp+")", lps, rps+1, n);
    }

Integer to Roman LeetCode

为了简化，把所有的可能为负的元素看成一个整体。比如90， 40这些直接看成一个整体。担心会出现XIII这种情况，所以设置了一个times来看到底出现了几次。

public String intToRoman(int num) {
        int[] numbers = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols ={"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
       
        String roman = "";
        int i = 0;
        while(num>0){
            int times = num/numbers[i];
            num -= times * numbers[i];
            while (times>0){
                roman += symbols[i];
                times--;
            }
            i++;
        }
        return roman;
    }

RomanToInteger LeetCode

唯一需要注意的是，100,10,1有可能是负的。判断一下就好。

public int romanToInt(String s) {
        int[] numbers = {1000, 500, 100, 50, 10, 5, 1};
        char[] symbols = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
        HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
        for (int i=0; i<numbers.length; i++){
            hm.put(symbols[i], numbers[i]);
        }
        //calculate the integer
        char[] charArr = s.toCharArray();
        int result = hm.get(charArr[s.length()-1]);
        for (int i=0; i<s.length()-1; i++){
            result += hm.get(charArr[i])
                    *(hm.get(charArr[i])>=hm.get(charArr[i+1]) ? 1 : -1);
        }
        return result;
    }

Add Two Number LeetCode

两个linkedlist相加，从低位到高位，很容易。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return helper(l1,l2,0);
    }
    public ListNode helper(ListNode l1, ListNode l2, int carry){
        if (l1==null && l2==null && carry==0) return null;
        if (l1!=null){
            carry+=l1.val;
            l1=l1.next;
        }
        if (l2!=null){
            carry+=l2.val;
            l2=l2.next;
        }
        ListNode current = new ListNode(carry%10);
        current.next = helper(l1,l2,carry/10);
        return current;
    }

Word Ladder II LeetCode

Word Ladder太简单了，这个题的难点是如何在规定时间过LC的test case. 写了一下午，无数次超时。快死了，看了下答案，发现我超时主要是trace back的时候出的问题。按照大牛的方法改了一下，过了。
思路：visited 是用hashmap来存储经过的路径path，注意这里path是hashset，所以顺序还是需要稍后的traceback 方法来找到。
            level是用hashmap存储到start的距离，跟Word ladder里的ladderMap是一样的。
           queue是实现BST

唯一不同的是visited里面存了整个路径出现的string。

看下代码吧，我要是面试面到这个题，我就认了。

注意：1. 其中有两个情况是要把string加入hashset的，第一种情况是string在dict里面，但是不在level里面，第二种情况是string在dict里面，也在level里面，但是到start的距离更小。
2. 在traceback过程中不要怕占用空间，敞开用。不然java不容易过。

public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        HashMap<String, HashSet<String>> visited = new HashMap<String, HashSet<String>>();
HashMap<String, Integer> level = new HashMap<String, Integer>();
LinkedList<String> queue = new LinkedList<String>();
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();

if(start == null || end == null || start.length()!=end.length()) return result;

HashSet<String> path = new HashSet<String>();
int minLen = Integer.MAX_VALUE;
visited.put(start, path);//only difference from word ladder I
level.put(start, 1);
queue.add(start);

while(!queue.isEmpty()){
String head = queue.remove();
char[] chars = head.toCharArray();
for(int i = 0; i < head.length(); i++){
char old = chars[i];
for(char letter = 'a'; letter <= 'z'; letter++){
chars[i] = letter;
String nextWord = new String(chars);
//two possible situations
//level does not contain nextWord
//level contains nextWord and near the start
if(dict.contains(nextWord) && (!level.containsKey(nextWord)
|| (level.containsKey(nextWord) && level.get(nextWord) > level.get(head)))){
//we update the path, visited, level
if(visited.containsKey(nextWord)){
visited.get(nextWord).add(head);
}else{
path = new HashSet<String>();
path.add(head);
visited.put(nextWord, path);
level.put(nextWord, level.get(head) + 1);
queue.add(nextWord);
}
}

if(nextWord.equals(end)){
if(level.get(head) < minLen){
ArrayList<String> entry = new ArrayList<String>();
entry.add(end);
result.addAll(backtrace(head,visited,entry));
minLen = level.get(head)+1;
}else{
break;
}
}
chars[i] = old;

}
}
}
return result;
}

private ArrayList<ArrayList<String>> backtrace(String end,
HashMap<String, HashSet<String>> visited, ArrayList<String> path) {
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
ArrayList<String> entry = new ArrayList<String>(path);
entry.add(0,end);
if(visited.get(end).size()<1){
result.add(entry);
return result;
}

for(String str : visited.get(end)){
result.addAll(backtrace(str,visited,entry));
}
return result;
}

Word Ladder LeetCode

思路很简单。用一个queue储存BST过程中经过的结点。为了防止会重复，搞一个HashMap，存储经历过的String，这样再次经过的时候，不将String放入Queue中。 HashMap中还有一个作用，就是可以存储从Start开始每个String距离这个start的距离。

简单讲： Queue BST
                 HashMap 防止重复，记录距离。

注意：HashSet里面的function应该是contains，写的太快写成了containsKey.

public int ladderLength(String start, String end, HashSet<String> dict) {
       Queue<String> q = new LinkedList<String>();
       Map<String, Integer> ladderMap = new HashMap<String, Integer>();
       q.offer(start);
       ladderMap.put(start,1);
     
       //BST
       while(!q.isEmpty()){
           String head = q.poll();
           int ladderLength = ladderMap.get(head)+1;
           for (int i=0; i<head.length();i++){
               StringBuilder sb = new StringBuilder(head);
               for (char letter='a'; letter<='z'; letter++){
                   sb.setCharAt(i, letter);
                   String nextWord = sb.toString();
                   if (nextWord.equals(end)) return ladderLength;
                   if (!ladderMap.containsKey(nextWord)&&dict.contains(nextWord)){
                       ladderMap.put(nextWord, ladderLength);
                       q.offer(nextWord);
                   }
               }
           }
       }
       return 0;
     
    }

SetMatrixZeroes LeetCode

思路： 拿矩阵的第一行第一列作为0的存储。跟新建一个长度为m,n的两个array的思路一样。
第一行和列如何判断呢，加两个变量，记录第一行第一列就好了。
注意：在扫描的时候只需要从index为1的地方可是设置为0就好了

写的无比啰嗦，不过都满足条件，一遍过的ds方法。
public void setZeroes(int[][] matrix) {
       
       boolean firstRow = false;
       boolean firstCol = false;
     
       int row = matrix.length;
       int col = matrix[0].length;
       //check the first row
       for (int j=0; j<col; j++){
           if (matrix[0][j]==0){
               firstRow=true;
               break;
           }
       }
     
       //check the first col
       for (int i=0; i<row; i++){
           if (matrix[i][0]==0){
               firstCol=true;
               break;
           }
       }
       
        //save all the results in the first col and first row
        for (int i=0; i<row; i++){
            for (int j=0; j<col; j++){
                if (matrix[i][j]==0){
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }
       
        //check the first row
        for (int j=1; j<col; j++){
            if (matrix[0][j]==0){
                for (int i=0; i<row; i++){
                    matrix[i][j]=0;
                }
            }
        }
       
        //check the first col
        for (int i=1; i<row; i++){
            if (matrix[i][0]==0){
                for (int j=0; j<col; j++){
                    matrix[i][j]=0;
                }
            }
        }
       
        if (firstRow){
            for (int j=0; j<col; j++){
                matrix[0][j]=0;
            }
        }
       
        if (firstCol){
            for (int i=0; i<row; i++){
                matrix[i][0]=0;
            }
        }
    }