leetcode – Integer to Roman

对老中来说,不熟悉罗马数字的规律是个问题。其实就是那么几个符号,然后规律就是1,4,5,9,10然后每次十倍循环。算法就是给一个数,大于1000的时候就写上一个M, 还大于1000,再写一个M… 终于小于1000了,看看大于900不?,大于500不…如此类推。

/*
I = 1;
V = 5;
X = 10;
L = 50;
C = 100;
D = 500;
M = 1000;
*/

public class Solution {
    public String intToRoman(int num) {
        String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        StringBuilder ret = new StringBuilder();
        for (int i=0; i<values.length; i++) {
            while (num >= values[i]) {
                ret.append(symbols[i]);
                num -= values[i];
            }
        }
        return new String(ret);
    }
}

leetcode – Reverse Words in a String

题目不难,用String的API:trim()和split()就能搞定。为什么结果要用StringBuilder而不是String? 用String += 大数据会超时。用append就不会。看来new一个object还是会比较慢。

其中值得学习的是Java的正则表达式。
http://docs.oracle.com/javase/7/docs/api/java/util/regex/Pattern.html

表示所有white spaces:
http://stackoverflow.com/questions/225337/how-do-i-split-a-string-with-any-whitespace-chars-as-delimiters

“\\s+”
其中”\\s”是[ \\t\\n\\x0B\\f\\r]
看来特殊字符的“或”是用\隔开的。

public class Solution {
    public String reverseWords(String s) {
        if (s==null || s.length() ==0) return s;
        String[] words = s.trim().split(" +");
        StringBuilder ret = new StringBuilder();
        int len = words.length;
        for (int i=len-1; i>=0; i--) {
            ret.append(words[i]);
            if (i != 0) {
                ret.append(" ");
            }
        }
        return new String(ret);
    }
}

leetcode – 4Sum

给一个数组和一个目标数字,在数组里面找出所有4个数的组合,他们的和等于目标数字

我这里用的是把所有两个数字的和列出来,记录他们的index和他们的和,按和排列。然后就类似two sum,用两个指针,一个开头一个结尾。如果和大于目标,后面指针的往前面移动一步。如果和小于目标,前面的指针往后移动一步。如果和等于目标,就判断四个index有没重合,他们对应的四个数有没被用过(用HashSet记录)。如果都没有,加入结果。最后返回结果就行了

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        if (num==null || num.length<4) return ret;
        
        ArrayList<Two> pairs = new ArrayList<Two>();
        int n = num.length;
        for (int i=0; i<=n-2; i++) {
            for (int j=i+1; j<=n-1; j++) {
                Two curPair = new Two(i,j, num[i]+num[j]);
                pairs.add(curPair);
            }
        }
        
        Collections.sort(pairs, new Comparator<Two>() {
           public int compare(Two i, Two j) {
               return i.sum - j.sum;
           }
        });
        
        HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>();
        int m = pairs.size();
        int p = 0, q = m-1;
        while (p < q) {
            int sum4 = pairs.get(p).sum + pairs.get(q).sum;
            if (sum4 > target) { 
                q--; 
            } else if (sum4 < target) {
                p++;
            } else {
                int leftStart = p, rightEnd = q;
                int leftEnd = p, rightStart = q;
                if (pairs.get(p).sum == pairs.get(q).sum) {
                    leftEnd = q;
                    rightStart = p;
                } else {
                    while (pairs.get(leftEnd+1).sum == pairs.get(leftEnd).sum) {
                        leftEnd++;
                    }
                    while (pairs.get(rightStart-1).sum == pairs.get(rightStart).sum) {
                        rightStart--;
                    }
                }
                
                for (int i=leftStart; i<=leftEnd; i++) {
                    for (int j=rightStart; j<=rightEnd; j++) {
                        if (!pairs.get(i).goodWith(pairs.get(j))) {
                            continue;
                        }
                        ArrayList<Integer> list4 = new ArrayList<Integer>();
                        list4.add(num[pairs.get(i).index1]);
                        list4.add(num[pairs.get(i).index2]);
                        list4.add(num[pairs.get(j).index1]);                    
                        list4.add(num[pairs.get(j).index2]);                    
                        Collections.sort(list4);
                        if (!set.contains(list4)) {
                            ret.add(list4);
                            set.add(list4);
                        }
                    }
                }
		p = leftEnd+1;
		q = rightStart-1;
            }
        }
        return ret;
    }
}

class Two {
    int index1;
    int index2;
    int sum;
    
    Two(int index1, int index2, int sum) {
        this.index1 = index1;
        this.index2 = index2;
        this.sum = sum;
    }
    
    boolean goodWith(Two two) {
        return (index1 != two.index1 && index1 != two.index2
            && index2 != two.index1 && index2 != two.index2);
    }
}

leetcode – ZigZag Conversion

原题的例子不是很清楚,只有nRow=3的情况。以下是nRows=5的例子:

a    i    q
b   hj   pr
c  g k  o s  ...
d f  l n  t v
e    m    u

就是先打竖排列,然后上去,再下来。算法就是一行一行的生成。除了头尾两行,对某一行的某个字符,假设对应原字符串第k个字符,同一行下一个就是原字符串的第k+2*nRows-2个字符,如果没超过字符串长度len的话。那么对于头尾两行,再k和k+2*nRows-2之间,还应该有一个k+2*nRows-2-2*i,i为行的index。

特殊情况,nRows=1,就是它自己了。这个一定要特殊处理,因为2*nRows-2 = 2*1-2 = 0。下面解法的while loop会出不去。犯过这个错误,很不容易发现。

这题就是个index计算题。

public class Solution {
    public String convert(String s, int nRows) {
        if (s==null) return null;
        if (nRows == 1) return new String(s);
        int len = s.length();
        StringBuilder sb = new StringBuilder();
        final int diff = nRows + nRows - 2;
        for (int i=0; i<nRows; i++) {
            int index = i;
            while (index < len) {
                sb.append(s.charAt(index));
                index += diff;
                if (i!=0 && i!=nRows-1 && index-i-i<len) {
                    sb.append(s.charAt(index-i-i));
                }
            }
        }
        return new String(sb);
    }
}

leetcode – Gas Station

一堆加油站组成一个圈,对第i个加油站,里面有gas[i]那么多的油,然后走到第i+1个(如果是最后一个,就回到开头)要花cost[i]那么多油,假设油箱无限大,找出一个可能的起点,如果没有一个可以走完的起点,就返回-1。

算法是tow pointers,i1 = 0, i2 = n-1。这个算法我也不知道怎么描述好,还是看code吧。总之就是如果(i1)往后面走不够油了,那么起点就推后一个(i2),直到两个pointer相交。

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas==null || cost==null) return -1;
        int n = gas.length;
        if (cost.length != n) return -1;
        if (n==0) return -1;
        int i1 = 0, i2 = n-1;
        int tank = gas[0] - cost[0];
        while (i1 != i2) {
            if (tank >= 0) {
                i1++;
                tank += gas[i1] - cost[i1];
            } else {
                tank += gas[i2] - cost[i2];
                i2--;
            }
        }
        
        if (tank>=0) {
            if (n==1) 
                return 0;
            else
                return i2+1;
        }
        return -1;
    }
}

最后handle n==1的情况也可以写成这样,简洁一点

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas==null || cost==null) return -1;
        int n = gas.length;
        if (cost.length != n) return -1;
        if (n==0) return -1;
        int i1 = 0, i2 = n-1;
        int tank = gas[0] - cost[0];
        while (i1 != i2) {
            if (tank >= 0) {
                i1++;
                tank += gas[i1] - cost[i1];
            } else {
                tank += gas[i2] - cost[i2];
                i2--;
            }
        }
        
        if (tank>=0) return (i2+1)%n;
        return -1;       
    }
}

leetcode – N-Queens, N-Queens II

n x n 大小的国际象棋棋盘,找出所以放下n个互相不能吃掉的皇后的方法,N-Queens II是找出有几种这样方法。
一般找出所有的可能性的题目,都是DFS。这题算法不难,就是一行一行来,先放一个皇后在某一行的一个格子里,然后检查这个能不能被这行上面已经放了的皇后吃掉。如果可以被吃掉,那么这个格子就不能放了。如果这行后面还有格子,就重复以上步骤。如果找到一个可能的格子,记录下这行放了在哪一个格子,对下一行进行同样的操作。如果有幸能在最后一行找到一个可能的格子,那么就找到一种解法。I就记录这种解法,II就对可能解法数加一。

Debug了挺久的,主要是DFS没想清楚,在主函数里面还用了循环call递归的placeQueue,以后对DFS要注意检查这种错误。检查新放的皇后是否和已放的皇后们冲突的函数也容易写错,尤其是斜的。检查(i,j)和(i1,j2)是否冲突要看 j==j2, i-i1 = j-j2 || i-i1 == -(j-j2)。检查列好理解,斜的话,(i,j)和(i+k, j+k)或者(i+k, j-k)在同斜线上。

N-Queens

public class Solution {
    public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> ret = new ArrayList<String[]>(n);
        if (n==0) return ret;
        ArrayList<Integer> cols = new ArrayList<Integer>(n);
        for (int i=0; i<n; i++) {
            cols.add(0);
        }
        ArrayList<Integer[]> sln = new ArrayList<Integer[]>();
        placeQueue(0, cols, n, sln);

        // solutions
        for (int p=0; p<sln.size(); p++) {
            Integer[] curSolution = sln.get(p);
            String[] map = new String[n];
            for (int i=0; i<n; i++) {
                String oneRow = new String();
                for (int j=0; j<n; j++) {
                    if (j!=curSolution[i]) {
                        oneRow += ".";
                    } else {
                        oneRow += "Q";
                    }
                }
                map[i] = oneRow;
            }
            ret.add(map);
        }
        
        return ret;
    }
    
    public void placeQueue(int row, ArrayList<Integer> cols, 
        int n, ArrayList<Integer[]> ret) {
        if (row == n) {
            Integer[] copyCols = new Integer[n];
            for (int i=0; i<n; i++) {
                copyCols[i] = cols.get(i);
            }
            ret.add(copyCols);
            return;
        }
        for (int i=0; i<n; i++) {
            cols.set(row, i);
            if (checkValid(row, i, cols)) {
                placeQueue(row+1, cols, n, ret);
            }
        }
    }
    
    public boolean checkValid(int row, int col, ArrayList<Integer> cols) {
        //check columns
        for (int i=0; i<row; i++) {
            if (col == cols.get(i)) {
                return false;
            }
        }
        
        //check diagonal
        for (int i=0; i<row; i++) {
            if (row-i == col-cols.get(i) 
                || row-i == cols.get(i)-col) {
                return false;
            }
        }
        
        return true;
    }
}

N-Queens II

public class Solution {
    public int totalNQueens(int n) {
        if (n==0) return 0;
        ArrayList<Integer> cols = new ArrayList<Integer>(n);
        for (int i=0; i<n; i++) {
            cols.add(0);
        }
        int[] ret = new int[1];
        placeQueue(0, cols, n, ret);

        return ret[0];
    }
    
    public void placeQueue(int row, ArrayList<Integer> cols, 
        int n, int[] ret) {
        if (row == n) {
            ret[0]++;
            return;
        }
        for (int i=0; i<n; i++) {
            cols.set(row, i);
            if (checkValid(row, i, cols)) {
                placeQueue(row+1, cols, n, ret);
            }
        }
    }
    
    public boolean checkValid(int row, int col, ArrayList<Integer> cols) {
        //check columns
        for (int i=0; i<row; i++) {
            if (col == cols.get(i)) {
                return false;
            }
        }
        
        //check diagonal
        for (int i=0; i<row; i++) {
            if (row-i == col-cols.get(i) 
                || row-i == cols.get(i)-col) {
                return false;
            }
        }
        
        return true;
    }
}

leetcode – Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle. 

题目倒不算难,最直接的解法,开一个和原来三角形一样的空间,最后一行全部复制一遍,然后从倒数第二行开始,算每个位置开始到最后能做到的最小值。也就是 minSum[i][j] = triangle[i][j] + min(minSum[i+1][j], minSum[i+1][j+1])。注意triangle[i][j]下一行的邻居是triangle[i+1][j]和triangle[i+1][j+1]。

要用O(n)空间的话,注意每一行的最小值,只需要它的下一行最小值,再下面就没用了。所以可以开两个数组,重复利用空间。这两个数组长度为n,一共用了2n,所以额外空间是O(n)。

错误: 一开是把交换数组的code写到了生成上一行min的循环里面了,应该生成完成后交换的…

public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) return 0;
        int n = triangle.size();
        int m = triangle.get(n-1).size();
        if (m==0) return 0;
        
        int[] dp1 = new int[m];
        int[] dp2 = new int[m];
        for (int j=0; j<m; j++) {
            dp2[j] = triangle.get(n-1).get(j);
        }
        
        for (int i=n-2; i>=0; i--) {
            int p = triangle.get(i).size();
            for (int j=0; j<p; j++) {
                dp1[j] = triangle.get(i).get(j)
                    + Math.min(dp2[j], dp2[j+1]);
            }
            int[] tmp = dp2;
            dp2 = dp1;
            dp1 = tmp;
        }
        
        return dp2[0];
    }
}

leetcode – Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …

1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

一直以为这题挺难的,看看解法,直接数,算下一个是什么,然后重复n次的暴力方法。很多解法写得还挺难懂的,自己用最直接的思路写了一遍,居然一次通过了…

public class Solution {
    public String countAndSay(int n) {
        String ret = "1";
        for (int i=2; i<=n; i++) {
            ret = next(ret);
        }
        return ret;
    }
    
    public String next(String input) {
        String ret = new String();
        char[] inputChars = input.toCharArray();
        int count = 1;
        char cur = inputChars[0];
        for (int i=1; i<inputChars.length; i++) {
            if (inputChars[i] == cur) {
                count++;
            } else {
                ret = ret + count + cur;
                cur = inputChars[i];
                count = 1;
            }
        }
        ret = ret + count + cur;
        return ret;
    }
}

leetcode – Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles – The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

Sudoku规则:就是每一行,每一列,每个9X9的cell,1到9只出现一次。空的为’.’

没什么技术含量,就是把这三个条件都检查一遍,看1-9每个数字出现多少次,多于一次就肯定错

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        if (m!=9 || n!=9) return false;
        
        int[] table = new int[10];
        
        //check rows
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                if (board[i][j] != '.') {
                    table[board[i][j]-'0'] ++;
                }
            }
            for (int k=1; k<=9; k++) {
                if (table[k] > 1) {
                    return false;
                } else {
                    table[k] = 0;
                }
            }
        }
        
        //check columns
        for (int j=0; j<9; j++) {
            for (int i=0; i<9; i++) {
                if (board[i][j] != '.') {
                    table[board[i][j]-'0'] ++;
                }
            }
            for (int k=1; k<=9; k++) {
                if (table[k] > 1) {
                    return false;
                } else {
                    table[k] = 0;
                }
            }
        }
        
        //check cells
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                
                for (int p=3*i; p<3*i+3; p++) {
                    for (int q=3*j; q<3*j+3; q++) {
                        if (board[p][q] != '.') {
                            table[board[p][q]-'0'] ++;
                        }
                    }
                }
                
                for (int k=1; k<=9; k++) {
                    if (table[k] > 1) {
                        return false;
                    } else {
                        table[k] = 0;
                    }
                }
            
            }
        }
        
        return true;
    }
}

leetcode – Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L_0→L_n→L_1→L_(n-1)→L_2→L_(n-2)→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

就是把list分成两半,把后面哪一半用反过来的顺序插入前半部分。所以可以用两个pointer,快的一次走两步,慢的一次走一步,找到中间。然后把后一半放到stack里,然后一边pop stack一遍插入。

和其他linked list题目一样,都debug了好久。错误比如:忘了前一般用null结束。最好写几个简单的例子出来,搞清楚边界。

public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;
        while (fast.next != null) {
            fast = fast.next;
            if (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
        }
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode p = slow;
        while (p.next != null) {
            stack.push(p.next);
            p = p.next;
        }
        slow.next = null;
        
        ListNode end = null;
        p = head;
        while (p!=null && stack.size()>0) {
            ListNode top = stack.pop();
            top.next = p.next;
            p.next = top;
            if (p.next.next == null) {
                end = p.next;
            }
            p = p.next.next;
        }
        
        while (stack.size()>0) {
            end.next = stack.pop();
            end = end.next;
            end.next = null;
        }
        
        return;
    }
}
Create your own website, free on WordPress.com.Create your own website.
Start free