Labels

Saturday, January 31, 2015

Binary Tree Level Order Traversal II


Binary Tree Level Order Traversal II



 


Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
] 
 
Naive Way: 这题,不就是之前那题把list的顺序倒过来吗。然后用了一个stack倒转顺序。

 
/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        List<List<Integer>> rlst = new ArrayList<List<Integer>>();

        Stack<List<Integer>> stack = new Stack<List<Integer>>();

        Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();

        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        if(root==null){return rlst;}

        queue.add(root);

        map.put(root,0);

        while(!queue.isEmpty()){

            TreeNode node = queue.poll();

            int layer = map.get(node);

            List<Integer> list;

            if(rlst.size() > layer){

                list = rlst.get(layer);

            }else{

                list = new ArrayList<Integer>();

                rlst.add(list);

            }

            rlst.get(layer).add(node.val);

            if(node.left!=null){

                queue.add(node.left);

                map.put(node.left, layer+1);

            }

            if(node.right!=null){

                queue.add(node.right);

                map.put(node.right, layer+1);

            }

        }

        for(int i = 0;i < rlst.size();i++)

            stack.push(rlst.get(i));

        rlst.clear();

        while(!stack.isEmpty()){

            rlst.add(stack.pop());

        }

        return rlst;

    }

} 


Improved Way:能否直接得到倒转的list而不是得到正的再颠倒它呢。

 

Binary Tree Level Order Traversal


Binary Tree Level Order Traversal



Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
] 
 
 
Naive Way: 一看就觉得这不是BFS吗。用以前的做法,用queue进行BFS遍历,用一个Map存节点对应的层数。
不知道是不是应该有更好的做法。

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> rlst = new ArrayList<List<Integer>>();

        Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();

        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        if(root==null){return rlst;}

        queue.add(root);

        map.put(root,0);

        while(!queue.isEmpty()){

            TreeNode node = queue.poll();

            int layer = map.get(node);

            List<Integer> list;

            if(rlst.size() > layer){

                list = rlst.get(layer);

            }else{

                list = new ArrayList<Integer>();

                rlst.add(list);

            }

            rlst.get(layer).add(node.val);

            if(node.left!=null){

                queue.add(node.left);

                map.put(node.left, layer+1);

            }

            if(node.right!=null){

                queue.add(node.right);

                map.put(node.right, layer+1);

            }

        }

        return rlst;

    }

}

Best Time to Buy and Sell Stock II


Best Time to Buy and Sell Stock II



 


Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Naive Way: 这个感觉这样一改就跟原题不是一个套路了。很直观的感觉就是,买,直到下一个不是递增的,卖。一开始应该得先找到第一个递增区间的起点。

算法复杂度是O(n)

public class Solution {
    public int maxProfit(int[] prices) {
        int opt = 0;
        int begin = 0, end = 0;
        while(end + 1< prices.length){
            begin = end+1;
            while(begin < prices.length){
                if(prices[begin] > prices[begin-1])
                    break;
                begin++;
            }
            begin--;
            end = begin;
            while(end + 1 < prices.length){
                if(prices[end+1] < prices[end])
                    break;
                end++;
            }
            opt += prices[end] - prices[begin];
        }
        return opt;
    }
}


Improved Way: Discuss里有一种Greedy的算法,很好。一旦有股票的价格比前一天的高,就可以加上这个差价,即能赚就买。因为比如:
1  2  3  4  5
max profit = 5-1 = 4;
greedy      = 5-4 + 4-3 + 3-2 + 2-1 = 4;

虽然题目不让在同一天买卖,但实际上在递增的区间中同一天买卖和第一天买最后一天卖是一样。这是否也说明了炒股票应该见好就收呢。

public class Solution {
    public int maxProfit(int[] prices) {
        int opt = 0;
        int p = 0;
        while(++p < prices.length){
            opt += Math.max(prices[p]-prices[p-1],0);
        }
        return opt;
    }
}

Friday, January 30, 2015

Best Time to Buy and Sell Stock


Best Time to Buy and Sell Stock



 



 


Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Naive Way: 这道题是课本DP那章的一道原题,我才想起来我当时做过。于是就用DP做了。
基本逻辑为
opt[i] //表示第ii所能获得的最大利润
// base case
opt[0] = 0
// iteration
opt[i] = max(opt[i-1], p[i] - min)

因为不需要内层循环访问之前的opt, 看来O(1)的space就足够了。

public int maxProfit(int[] prices) {
        if(prices.length==0){return 0;}
        int opt = 0;
        int min = prices[0];
        for(int i = 1;i < prices.length;i++){
            opt = Math.max(opt, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return opt;
    }

Best Time to Buy and Sell Stock III


Best Time to Buy and Sell Stock III



 


Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Naive Way:因为在前面已经有了卖一次的代码,可以认为是交易两次和交易一次的比较,交易一次则采用之前的代码,交易两次则将视为将数组切割成两段,对每一段求一次交易的最大值,然后相加,着要求对每一位置作为切割点遍历。这样的算法复杂度是O(n^2)。

public int maxProfit(int[] prices) {
        if(prices.length <= 3){
            return subProfit(prices);
        }
        int max = 0;
        for(int i = 1;i < prices.length-1;i++){
            int sub1[] = new int[i];
            int sub2[] = new int[prices.length - i];
            for(int j = 0;j < i;j++)
                sub1[j] = prices[j];
            for(int j = i;j < prices.length;j++)
                sub2[j-i] = prices[j];
            int cur = subProfit(sub1)+subProfit(sub2);
            if(cur > max)
                max = cur;
        }
        return max;
    }
   
    private int subProfit(int[] prices) {
        if(prices.length == 0){return 0;}
        int opt = 0;
        int min = prices[0];
        for(int i = 1;i < prices.length;i++){
            if(prices[i] < min)
                min = prices[i];
            opt = Math.max(prices[i] - min, opt);
        }
        return opt;


还有一种想法就是感觉最多两次交易应该是跟最大值最小值有关的,找出第一个递减区间之后的最大值和第二大值,以及最小值和第二小值,应该可以通过分类讨论得到答案,但是这样做感觉就是数学方法而不是计算机方法。

那么比较正确的思路应该是扩展成k然后去想一个通用的解法。




Improved Way: 被告知有DP的解法,于是决定自己先试着做一下,那么走正常DP的思路。

opt[i][j] //表示在0~j天里最多交易i次能获得的最大利润
// base case
opt[0][j] = 0 (0 <= j <= n)  最多交易0次无利润
opt[i][0] = 0 (0 <= i <= k) 在0天里无法交易
// itreation
opt[i][j] = max(opt[i][j-1], max(opt[i-1][t] + p[j]-p[t+1]))  可能与j-1天相同,可能增加一次交易。

这样的做法算法复杂度是O(kn^2),空间复杂度是O(nk)

private int maxProfit(int[] p, int k){
        int opt[][] = new int[k+1][p.length+1];
        // base case
        for(int i = 0;i <= k;i++)
            opt[i][0] = 0;
        for(int j = 0;j <= p.length;j++)
            opt[0][j] = 0;
        // iteration
        for(int i = 1;i <= k;i++){
            for(int j = 1;j <= p.length;j++){
                opt[i][j] = opt[i][j-1];
                for(int t = 0;t < j;t++)
                    opt[i][j] = Math.max(opt[i][j], opt[i-1][t] + p[j-1] - p[t]);
            }
        }
        return opt[k][p.length];
    }


看了一下Discuss上的解法才知道这个世界牛人真多,在https://oj.leetcode.com/discuss/15153/a-clean-dp-solution-which-generalizes-to-k-transactions上这位提出了将第三层循环写入第二层循环的做法,让人大呼过瘾。

我们可以注意到以上逻辑关键的一步:opt[i][j] = max(opt[i][j-1], max(opt[i-1][t] + p[j]-p[t+1]))
分解下来就是
如果第i天无交易,那么就是opt[i][j] = opt[i][j-1].
如果做出交易决定,就要看在之前t天里正好做i-1次交易, 加上p[j]-p[t+1]这最后一次交易,哪一个第t天带来最大利润。
后半部分 max(opt[i-1][t] + p[j-1] - p[t])
           =    max(p[j-1] + (opt[i-1][t] - p[t]))
           =    p[j-1] + max(opt[i-1][t] - p[t])
           =    p[j-1] + preMax
其中max(opt[i-1][t] - p[t])这一部分,我们是可以用O(1)的时间写进第二层循环中的。
因为t的范围是[0,j), 也就是说,每一次 for(int j = 1;j <= p.length;j++) 的循环末尾,我们都将当前opt[i-1][j] - p[j] 与之前一次的 preMax相比较,就可以得到新的preMax给下一次循环用了。而preMax的初始值就是opt[i-1][0] - p[0]了,因为正好 for(int j = 1;j <= p.length;j++) 这个循环中j是从1开始的。

这样算法复杂度就成了O(kn),对应这一题就是O(n)了。

private int maxProfit(int[] p, int k){
        int opt[][] = new int[k+1][p.length+1];
        // base case
        for(int i = 0;i <= k;i++)
            opt[i][0] = 0;
        for(int j = 0;j <= p.length;j++)
            opt[0][j] = 0;
        // iteration
        for(int i = 1;i <= k;i++){
            int preMax = opt[i-1][0] - p[0];
            for(int j = 1;j <= p.length;j++){
                opt[i][j] = opt[i][j-1];
                opt[i][j] = Math.max(opt[i][j], preMax + p[j-1]);
                preMax = Math.max(preMax, opt[i-1][j]-p[j]);
            }
        }
        return opt[k][p.length];
    }

忽然有种感觉,以前算法课上很多DP的题目貌似都是要内层循环要遍历之前所有的,说不定都可以这样把之前所有的这个循环套入内层循环中。

N-Queens


N-Queens



 


The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
] 
 
Naive Way: 这道题可以直观感受到并不是巧妙的算法的,应该是要brute force遍历所有情况。
对于这种题,类似的还有解数独那道题,我都是想到DFS来解的。
但同样是DFS,解法的复杂性,所用的空间大小,back trace的难度,都是很值得想的。
 
这是我的解法。使用了一个矩阵做容器,DFS遍历,带回溯,每次放置一个Q,对应覆盖位置+1,
回溯时每一个Q的对应覆盖位置-1。每次都检测是否填完,填完则记录进结果。运行时间在所有用Java
的人中排在后面。 



class Node{
        int x, y;
        Node(int a,int b){x = a;y = b;}
    }
    
    public List<String[]> solveNQueens(int n) {
        List<String[]> rlst = new ArrayList<String[]>();
        Stack<Node> stack = new Stack<Node>();
        char[][] board = new char[n][n];
        for(int i = 0;i < n;i++){for(int j = 0;j < n;j++){board[i][j] = '0';}}
        
        // initialize stack
        for(int i = 0;i < n;i++){
            Node node = new Node(0,i);
            stack.push(node);
        }
        
        // DFS
        while(!stack.isEmpty()){
            Node node = stack.pop();
            board[node.x][node.y] = 'Q';
            boolean hasNext = false;
            
            // set new Q
            addBoard(board, node.x, node.y);
            if(isFinished(board) && node.x==n-1){
                String[] strs = new String[n];
                for(int i = 0;i < n;i++){
                    StringBuilder str = new StringBuilder();
                    for(int j = 0;j < n;j++)
                        str.append(board[i][j]=='Q'?'Q':'.');
                    strs[i] = str.toString();
                }
                rlst.add(strs);
            }
                
            // push next row
            if(node.x+1 < n){
                for(int j = 0;j < n;j++){
                    if(board[node.x+1][j]=='0'){
                        Node next = new Node(node.x+1,j);
                        stack.push(next);
                        hasNext = true;
                    }
                }
            }
                
            if(!hasNext || (isFinished(board) && node.x==n-1)){
                // back trace
                if(!stack.isEmpty()){
                    Node peek = stack.peek();
                    for(int i = node.y;i >= 0;i--)
                        if(board[node.x][i]=='Q')
                            minusBoard(board,node.x,i);
                            
                    for(int i = node.x-1;i >= peek.x;i--)
                        for(int j = n-1;j >= 0;j--)
                            if(board[i][j] =='Q')
                                minusBoard(board,i,j);
                }
            }
            
        }
        
        return rlst;
    }
    
    private boolean isFinished(char[][] b){
        for(int i = 0;i < b.length;i++)
            for(int j = 0;j < b[0].length;j++)
                if(b[i][j]== '0')
                    return false;
        return true;
    }
    
    private void addBoard(char[][] b, int x, int y){
        for(int i = 0;i < b.length;i++)
            b[i][y] = b[i][y]=='Q'?b[i][y]:(char)(b[i][y]+1);
        for(int j = 0;j < b[0].length;j++)
            b[x][j] = b[x][j]=='Q'?b[x][j]:(char)(b[x][j]+1);
        for(int i = 1;i < b.length;i++){
            if(x+i >= 0 && x+i < b.length && y+i >= 0 && y+i < b[0].length)
             b[x+i][y+i] = b[x+i][y+i]=='Q'?b[x+i][y+i]:(char)(b[x+i][y+i]+1);
            if(x+i >= 0 && x+i < b.length && y-i >= 0 && y-i < b[0].length)
             b[x+i][y-i] = b[x+i][y-i]=='Q'?b[x+i][y-i]:(char)(b[x+i][y-i]+1);
            if(x-i >= 0 && x-i < b.length && y+i >= 0 && y+i < b[0].length)
             b[x-i][y+i] = b[x-i][y+i]=='Q'?b[x-i][y+i]:(char)(b[x-i][y+i]+1);
            if(x-i >= 0 && x-i < b.length && y-i >= 0 && y-i < b[0].length)
             b[x-i][y-i] = b[x-i][y-i]=='Q'?b[x-i][y-i]:(char)(b[x-i][y-i]+1);
        }
        return;
    }
    
    private void minusBoard(char[][] b, int x, int y){
     for(int i = 0;i < b.length;i++)
            b[i][y] = b[i][y]=='Q'?b[i][y]:(char)(b[i][y]-1);
        for(int j = 0;j < b[0].length;j++)
            b[x][j] = b[x][j]=='Q'?b[x][j]:(char)(b[x][j]-1);
        for(int i = 1;i < b.length;i++){
            if(x+i >= 0 && x+i < b.length && y+i >= 0 && y+i < b[0].length)
             b[x+i][y+i] = b[x+i][y+i]=='Q'?b[x+i][y+i]:(char)(b[x+i][y+i]-1);
            if(x+i >= 0 && x+i < b.length && y-i >= 0 && y-i < b[0].length)
             b[x+i][y-i] = b[x+i][y-i]=='Q'?b[x+i][y-i]:(char)(b[x+i][y-i]-1);
            if(x-i >= 0 && x-i < b.length && y+i >= 0 && y+i < b[0].length)
             b[x-i][y+i] = b[x-i][y+i]=='Q'?b[x-i][y+i]:(char)(b[x-i][y+i]-1);
            if(x-i >= 0 && x-i < b.length && y-i >= 0 && y-i < b[0].length)
             b[x-i][y-i] = b[x-i][y-i]=='Q'?b[x-i][y-i]:(char)(b[x-i][y-i]-1);
        }
        b[x][y] = '0';
        return;
    }
 



Improved Way:N Queens II

 

Thursday, January 29, 2015

Intersection of Two Linked Lists


Intersection of Two Linked Lists



 


Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
begin to intersect at node c1.

Notes:
  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.
Naive Way: 对每一A node, 遍历一遍B node,看是否交汇。这样的算法复杂度是O(n^2)。
但是题目要求了O(n) ,说明就一定存在O(n)的解法。链表有一个重要的特性就是有指针。
这些指针可以被灵活使用,这里让我想起了Populating Next Right Pointers in Each Node II里那个把next指针指向父节点的人,当时这个做法一下子直接打破了常规的想法,让指针不再局限于它的名字,我们其实也可以将left 和 right指向父节点什么的,这种约定俗成的变量名造成了先入为主的思维,往往会限制我们的想法。

那么看来要实现O(n)就必须利用好这些指针了,但是这道题不同于树,每一个节点只有一个指针,如果我们改变某一个指针,就断掉了,就无法修复了。所以我们不能断掉这些指针,但仍可以在不断掉整个链的情况下改变这些指针。

一开始我的想法是交叉A 链表和B链表的指针,看能不能弄出些名堂,但是无论怎么交叉,都只是将A和B前面的部分增长变短,问题就变成了对一个长度不同的A,B链表求交汇点。所以这样的尝试是失败的。

其实有一个节点的指针是一直没有用的,就是最后一个节点的指针,连接它到任意一个位置都改变了整个链表的结构,没错,增加了一个圈。这时才发现题目中的Notes是在给提示,前面有做过用龟兔赛跑的办法求圈的起始位置的题目,这里就可以用上了。当把尾部节点的指针链接至任意一个链表的开头,就变成一个含圈链表求圈起始位置的题目。而龟兔赛跑的算法复杂度正好是O(n)。具体龟兔赛跑是怎么回事,这里有一个比较好的教程Detecting a Loop in Singly Linked List - Tortoise & Hare

这道题是自己想出来的,还是比较开心。
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // edge case
        if(headA == null || headB == null){return null;}
        // connect list A into a circle
        ListNode temp = headA;
        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = headA;
        // find the start node of the circle
        ListNode hare = headB;
        ListNode tortoise = headB;
        while(true){
            // hare step 2 forward
            if(hare.next != null){
                hare = hare.next;
                if(hare.next != null){
                    hare = hare.next;
                }else{
                    temp.next = null;
                    return null;
                }
            }else{
                temp.next = null;
                return null;
            }
            // tortoise step 1 forward
            if(tortoise.next != null){
                tortoise = tortoise.next;
            }else{
                temp.next = null;
                return null;
            }
            // check if they meet
            if(hare == tortoise){
                break;
            }
        }
        hare = headB;
        while(hare != tortoise){
            hare = hare.next;
            tortoise = tortoise.next;
        }
        // break list A into singly list
        temp.next = null;
       
        return hare;
    }
}

 



 



 

Count and Say


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.

Naive Way: 很有趣的题目。第一次写就成功了,看来是一道简单的题目。通过读取上一次的String生成当前的String。

public class Solution {
    public String countAndSay(int n) {
        String str = "1";
        for(int i = 2;i <= n;i++){
            int j = 0;
            String newStr = "";
            while(j < str.length()){
                int count = 1;
                while(j+count < str.length()){
                    if(str.charAt(j)!=str.charAt(j+count))
                        break;
                    count++;
                }
                newStr += (char)(count+'0');
                newStr += str.charAt(j);
                j += count;
            }
            str = newStr;
        }
        return str;
    }
}

Improved Way: Discuss里有用recursive写的,感觉会更舒服些。

 

GitHub - Leetcode


 我的所有Leetcode代码都在https://github.com/Larrylianj/Leetcode_Java.git


 我的所有Leetcode代码都在https://github.com/Larrylianj/Leetcode_Java.git

Longest Palindromic Substring


Longest Palindromic Substring




Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.




Naive Way: 遍历一遍,对每一个字符都左右遍历直至不对称。这样算法复杂度是O(n^2)。这道题作为DP的教材题目当时也是有想过用Opt(i,j)来表示s[i..j]是否为回文。



 



逻辑为:



// base case



For all i:



opt[i,i] = 1;



opt[i,j] = 0; (i > j)



// iteration 



opt[i,j] = opt[i+1,j-1] && s[i]==s[j]



 



 现在想想这个方法不仅也是O(n^2)的run time,而且还要用O(n^2)的space,真不是一个好方法。下面是我第一次的做法,写得非常不好,应该用begin index和end index记录substring而不是每一次都替换它。而且需要分奇数和偶数。



 






public String longestPalindrome(String s) {
        String result = s;
        int longest = 0;
        for(int i = 1;i < s.length();i++){
            int j = 1;
            if(s.charAt(i-1)==s.charAt(i)){
                while(i-1-j >=0 && i+j < s.length()){
                    if(s.charAt(i-1-j)!=s.charAt(i+j))
                        break;
                    j++;
                }
                if(2*j > longest){
                    longest = 2*j;
                    result = s.substring(i-j,i+j);
                }
            }
            j = 1;
            while(i-j >= 0 && i+j < s.length()){
                if(s.charAt(i-j)!=s.charAt(i+j))
                    break;
                j++;
            }
            if(2*j-1 > longest){
                longest = 2*j-1;
                result = s.substring(i-j+1,i+j);
            }
        }
        return result;
    }



Improved Way:这个世界上有了人类,就必然有牛一点的人类。1337c0d3r在博客中详细讲解了O(n)的实现方法,同时还推荐了一个中国人写得解法:

  Manacher's ALGORITHM: O(n)时间求字符串的最长回文子串 



 



我是看这个中国人的博客所写的做法,很清楚。用自己的语言写一写这个方法,加深印象。



 



1.首先对字符串做一个预处理:



baaaa



#b#a#a#a#a#



这样做在不改变回文关系的情况下,将奇数和偶数进行了统一。因为不存在连续两个相同字符的情况,所有回文都变成了奇数。



2.然后设置一个pivot,这个pivot是当前覆盖范围最长的字符所在的位置,一开始的时候应该要先初始第一个字符的最长回文为1,然后当前覆盖范围最长的就是第一个字符了。



3.看pivot(s[p])的覆盖范围是否包含了现在正在处理的字符s[i]:


如果不包含,说明pivot(s[p])的信息不能提供给当前字符s[i]有用的信息,老老实实左右匹配算该字符的最长回文数。


如果包含,因为知道pivot(s[p])两侧是对称的,那么当前位置s[i]在pivot的镜面位置s[2*p-i] =s[j]上的字符应该是一样的。不只是这样,可以知道,从s[j]到s[p]和从s[p]到s[i]这段距离内的字符是对称的,那么在pivot的覆盖范围内从s[i]向右也应该有部分字符是与s[j]向左是对称的。



4. 接步骤3中第二个如果,在pivot的覆盖范围内从s[i]往右也应该有部分字符是与s[j]向左是对称的,


如果我们知道s[j]的覆盖范围要小于这个距离(即s[j]的覆盖范围完全在pivot的覆盖范围之内),s[i]的往右去的那一部分就应该跟s[j]往左去的那一部分完全对称。可以得到  s[i]的覆盖范围=s[j]的覆盖范围


如果s[j]的覆盖范围要大于这个距离(即pivot的覆盖范围是与s[j]的覆盖范围有交集),那么我们知道在pivot的覆盖范围内,s[j]所覆盖的与s[i]所覆盖的范围是一样的。那么s[i]再往右去的覆盖范围就无法得知,此时依然要在这个基础老老实实匹配。




例如:当前黑体位置是pivot=5,拥有最大覆盖范围4,我们要求index=6位置的覆盖范围。红体是pivot覆盖范围的边界。

 

首 先,6是在(5-4, 5+4])= (1,9)这个范围内的,说明pivot的覆盖范围能为我们提供一些信息。然后镜面的位置是4,它的覆盖范围(4-3,4+3) = (1,7)是在pivot的覆盖范围内的,而对应当前位置6,可以得知(6-3,6+3) = (3,9)这个范围和(4-3,4+3)的内容是完全一致的,因为(1,9)范围内的内容是对称的。



0  1  2  3  4  5  6  7  8  9  10

 



#  b  #  a  #  a  #  a  #   a   # 

 



1  2  1  2  3  4





6的覆盖范围至少是3。



 

 



0  1  2  3  4  5  6  7  8  9  10

 



#  b  #  a  #  a  #  a  #   a   # 

 



1  2  1  2  3  4  3





但 是因为pivot=5的覆盖范围正好和镜像4的覆盖边界重合,我们不能确定6的当前覆盖范围(3,9)往右的情况。所以还不能直接写6的覆盖范围是3。后 面的还得老老实实匹配,但是可以在3的基础上进行匹配了。比如(3,9)是当前范围,下一个要匹配的就是3和9,然后是2和10...



0  1  2  3  4  5  6  7  8  9  10

 



#  b  #  a  #  a  #  a  #   a   # 

 



1  2  1  2  3  4  3

 

 



 最后匹配到2和10发现不能再继续,填写6位置处新的覆盖范围5。



0  1  2  3  4  5  6  7  8  9  10

 



#  b  #  a  #  a  #  a  #   a   



1  2  1  2  3  4  5

 

 




最后发现新的覆盖范围(6-5,6+5) = (1,11)已经超出就的最大覆盖范围,pivot的(1,9),所以把6设为新的pivot。 



 


0  1  2  3  4  5  6  7  8  9  10

 



#  b  #  a  #   a  #  a  #   a   




1  2  1  2  3   4  5



 



 



然后继续下一个字符。




我写的这个太粗燥,估计大家可能看不懂,建议点击上面的链接去看看详细的解释。



下面是我根据该方法写的代码:


public class Solution {
    public String longestPalindrome(String s) {
        String str = preProcess(s);
        int f[] = new int[str.length()];
        int longest = 0;
        int begin = 0, end = 0;
        
        // initialize
        int p = 0; // pivot
        f[0] = 1;
        
        // general case
        for(int i = 1;i < str.length();i++){
            
            int right = p+f[p]; // get pivot's right most range
            f[i] = 1; // if pivot's range not covers i, start from 1
            if(right > i){ // if pivot's range covers i
                if(right - i > f[2*p-i]) // if mirror's range is within pivot's range
                    f[i] = f[2*p-i];
                else // if pivot's range gives out but the right side still not decided
                    f[i] = right - i;
            }
            
            while(i-f[i] >= 0 && i + f[i] < str.length()){
                if(str.charAt(i-f[i])!=str.charAt(i+f[i]))
                    break;
                f[i]++;
            }
            
            if(f[i] + i > f[p] + p)
                p = i;
        }
        
        for(int i = 0;i < f.length;i++){
            if(f[i] > longest){
                longest = f[i];
                begin = (i-f[i]+1)/2;
                end = (i+f[i]-1)/2;
            }
        }
        
        return s.substring(begin,end);
    }
    
    private String preProcess(String s){
        StringBuilder str = new StringBuilder();
        str.append('#');
        for(int i = 0;i < s.length();i++){
            str.append(s.charAt(i));
            str.append('#');
        }
        return str.toString();
    }
}

 



Wednesday, January 28, 2015

Excel Sheet Column Title


Excel Sheet Column Title



 


Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example:
    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 
 
 
Naive way: 或者从前往后提取字符,或者从后往前提取字符。
这道题咋看之下像是小学做过的10进制取每一位,但是细看之下有一个不同点。
我把它写成对应10进制便于理解。
 
10进制
0 -> null 
1 -> A
2 -> B
3 -> C
...
9 -> I
10-> J
11-> AA
12-> AB
...
19-> AI
20-> AJ
21-> BA
...

正常10进制是有一个0的,当9到10的时候是要进位的,而这个相当于9直接变成11。
这个不同点告诉我们不能使用正常的10进制取每一位的方法。但是除了要进位的时候,其他数值
都是与10进制数一一对应的。 于是我列了个表。
 
    1   10  100
1   1   x   x    A
9   9   x   x    I
10  10  x   x    J
11  1   1   x    AA
20  10  1   x    AJ
21  1   2   x    BA
30  10  2   x    BJ
40  10  3   x    CJ 
100 10  9   x    IJ
110 10  10  x    JJ
120 10  1   1    AAJ
130 10  2   1    ABJ


这样就很明了了。10到11, 20到21, 110到120,都有一个不符合一般规律的跳变,这里需要单独处理。
基本逻辑为:
如果该数除以pow(10,i)的余数不为0,比如1,2,3...9除以10的余数都不为0,就写对应的字母。
如果概述除以pow(10,i)的余数为0,比如10,20,100..除以10的余数都为0,就写pow(10,i),这里是10。
然后每一次都减去用掉的部分直到该数变为0.
当然要把10换成26. 

public class Solution {

    int base = 26;

    public String convertToTitle(int n) {

        String s = "";

        int i = 0;

        while(n!=0){

            int num = n%(int)Math.pow(base,i+1)==0?(int)Math.pow(base,i+1):n%(int)Math.pow(base,i+1);

            num /= (int)Math.pow(base,i);

            s += (char)(num-1 + 'A');

            n -= num*(int)Math.pow(base,i);

            i++;

        }

        

        return new StringBuilder(s).reverse().toString();

    }

}

Improved Way: 这道题其实是挺难的,我第一次做就在如何对应数字和字母上耗了好久。但是通过这样列表的分析一切都明了了。
省时省力。下面是我第一次的做法,采用完全不同的方法,是从左往右进行的。
 
从左往右进行不能直接取商,必须得先减去之前所有幂次方的和(对应lowerPart),然后每次的幂次方和都要对应减小。
总之很蛋疼,两种算法的复杂度都是O(logn)以26为底。

private static final int base = 26;
    public String convertToTitle(int n) {
     String s = "";
        int digits = (int)Math.floor(Math.log(n)/Math.log(base));
        int lowerPart = 0;
        for(int i = 0;i < digits;i++)
            lowerPart += (int)Math.pow(base,i);
        while(n != 0){
            int divisor = (int)Math.pow(base,digits);
            int number = (n-lowerPart)/divisor;
            if(number!= 0)
                s += (char)(number+'A'-1);
            n -= number*divisor;
            digits--;
            lowerPart -= (int)Math.pow(base,digits);
        }
        return s;
    }



 

Search Insert Position


Search Insert Position



 


Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Naive Way: 一次遍历直到大于等于target。好傻的方法,我第一次就是这么写的。

    // O(n)
    public int searchInsert(int[] A, int target) {
        for(int i = 0;i < A.length;i++){
            if(A[i] == target){return i;}
            if(A[i] > target){return i;}
        }
        return A.length;
    }

Improved Way: 作为一个程序员看到这样的题没有想到binary search真是一件很忧伤的事情。第二次做法是改了一下binary search

// O(logn)
    public int searchInsert(int[] A, int target) {
        if(A.length==0){return 0;}
        int begin = 0, end = A.length-1;
        int middle = 0;
        if(target <= A[begin]){return 0;}
        if(target >= A[end]){return end+1;}
        while(begin < end){
            middle = (begin+end)/2;
            if(A[middle]==target)
                return middle;
            if(A[middle] < target && A[middle+1] >= target)
                return middle+1;
            if(A[middle] > target)
                end = middle;
            if(A[middle+1] < target)
                begin = middle+1;
        }
        return 0;
    }

类似要用binary search的思想的还有Remove-duplicates-from-sorted-array

 

Populating Next Right Pointers in Each Node


Populating Next Right Pointers in Each Node



 


Given a binary tree
    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
  • You may only use constant extra space.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7
After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL 
 
 
Naive Way: 这里有一个重要限制是constant space.所以不能用stack或者queue来进行遍历。
这里有个问题困扰了我,如何在不用extra space的前提下遍历一颗无父指针二叉树呢。答案是不可能的!
因为二叉树有两个分支,无论先遍历哪一边分支,都必须要记下兄弟节点,否则一旦往下走就不能回头。
而且光记录一个兄弟节点还不行,必须把同一层的兄弟节点都记录下来,这样是和BFS,DFS相对应的O(n)
space。
 
明白这一点很重要,说明这道题在坑人。
 
终于过了好久,我发现这道题的next指针导致了我们可以用constant space去遍历一整棵树。 
因为如果我们知道next指针,就可以通过父节点的next指针访问到同一层的兄弟节点。也就是说,
我们不仅要连起这些next指针,还要利用之前连好的这些next指针方便我们连下一层的next指针。

简单的逻辑描述为:
如果一个节点为左节点,其next为父亲的右节点。
如果一个节点为右节点,其next为父亲节点的next节点的左节点(如果有的话)。
并且由于next指针是从左指向右的,我觉得应该从左往右进行遍历。通过next获得下一个要
处理的节点。
 
写点有点别扭,用了一个do-while语句。但是思想应该是对的。一层一层来,从左到右,
每一层都要记下最左边的子节点,作为下一层遍历的开头。

/**

 * Definition for binary tree with next pointer.

 * public class TreeLinkNode {

 *     int val;

 *     TreeLinkNode left, right, next;

 *     TreeLinkNode(int x) { val = x; }

 * }

 */

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root==null)
            return;
        TreeLinkNode leftMost = root;
        TreeLinkNode node = null;
        while(leftMost.right!=null && leftMost.left!=null){
            node = leftMost;
            leftMost = node.left;
            do{
                node.left.next = node.right;
                node.right.next = node.next==null?null:node.next.left;
                node = node.next;
            }while(node!=null);
        }
    }
}
 

 

Populating Next Right Pointers in Each Node II


Populating Next Right Pointers in Each Node II



 


Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
  • You may only use constant extra space.
For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL 
 
 
Naive Way:这次多了一个不满秩的条件,很明显的意图是要看能否通过修改第一次的代码得到。
 
第一次的代码:
public void connect(TreeLinkNode root) {
        if(root==null)
            return;
        TreeLinkNode leftMost = root;
        TreeLinkNode node = null;
        while(leftMost.right!=null && leftMost.left!=null){
            node = leftMost;
            leftMost = node.left;
            do{
                node.left.next = node.right;
                node.right.next = node.next==null?null:node.next.left;
                node = node.next;
            }while(node!=null);
        }
    }
 
我想基本结构应该是不变,但是现在左子节点和右子节点都可能不存在。分析一下不存在的时候该怎么办:
1.如果左子节点不存在,最左边的节点就应该是右节点。
2.如果右子节点不存在,next该指向的是父节点的next节点的左子节点。
很棒,这两点是相互作用的.对于找最左子节点和右节点分别写了对应函数,发现二者仅一处不同。

private TreeLinkNode searchLeft(TreeLinkNode node){
        if(node==null)
            return null;
        if(node.left!=null)
            return node.left;
        if(node.right!=null)
            return node.right;
        return searchLeft(node.next);
    }
 

private TreeLinkNode searchRight(TreeLinkNode node){
        if(node==null)
            return null;
        if(node.right!=null)
            return node.right;
        return searchLeft(node.next);
    }
 
 
替换相应部分的结果为:
(这里结束条件需要略作改动,因为不能再用是否满秩作为判断条件。后来想想,应该第一个也这样写的) 
 
public void connect(TreeLinkNode root) {
       if(root==null)
           return;
       TreeLinkNode leftMost = root;
       TreeLinkNode node = null;
       while(leftMost!=null){
           node = leftMost;
           leftMost = searchLeft(node);
           do{
              if(node.left!=null)
                   node.left.next = searchRight(node);
               if(node.right!=null)
                   node.right.next = searchLeft(node.next);
               node = node.next;
           }while(node!=null);
       }
   } 


Improved Way: 这样是否就已经可以了呢。我在discuss中看到一个很有意思的想法。有个人先把搜友节点的next节点指向父节点,然后展开BFS把next pointer指向下一个。感觉和我的思路是一样的,都是要先把上一层的next连好,记下下一层最左边的,然后通过上一层的next找同层的兄弟节点。但是把next指向父节点就有了无限可能性,因为可以no extra space从下往上遍历节点了。

以下代码是leetcode用户 pavan.singitham的。


public class Solution {
public void connect(TreeLinkNode root) {
    if(root == null) {
        return;
    }
    root.next = null;
    pointChildrenToParents(root);
    rotateNextClockwise(root);
}

// point each child's next pointer to the parent
private void pointChildrenToParents(TreeLinkNode root) {
    if(root == null) {
        return;
    }
    if(root.left != null) {
        root.left.next = root;
        pointChildrenToParents(root.left);
    }
    if(root.right != null) {
        root.right.next = root;
        pointChildrenToParents(root.right);
    }
}

// now update the next pointer 1-level at a time to point to the next node in that level
private void rotateNextClockwise(TreeLinkNode root) {
    if(root == null) {
        return;
    }

    TreeLinkNode firstNodeInNextLevel = null; // save first node in next level for bfs
    while(root != null) {
        if(firstNodeInNextLevel == null) {
            firstNodeInNextLevel = (root.left != null)? root.left : root.right;
        }
        if(root.right != null) {
            if(root.left != null) {
                root.left.next = root.right;
            }
            root.right.next = findNextChild(root.next);
            root = (root.right.next != null) ? root.right.next.next: null;
        }
        else if(root.left != null) {
            root.left.next = findNextChild(root.next);
            root = (root.left.next != null) ? root.left.next.next: null;
        }
        else {
            root = root.next;
        }
    }

    rotateNextClockwise(firstNodeInNextLevel);
}

// traverse next chain till we find a child for current level
private TreeLinkNode findNextChild(TreeLinkNode root) {
    for(TreeLinkNode tmp = root; tmp != null; tmp = tmp.next) {
        if(tmp.left != null) {
            return tmp.left;
        }
        else if(tmp.right != null) {
            return tmp.right;
        }
    }
    return null;
} 
} 


看到一个更好的代码,思路是一样的,带式代码质量好很多。来自leetcode的 davidtan1890用户。


public void connect(TreeLinkNode root) {

        while(root != null){
            TreeLinkNode tempChild = new TreeLinkNode(0);
            TreeLinkNode currentChild = tempChild;
            while(root!=null){
                if(root.left != null) { currentChild.next = root.left; currentChild = currentChild.next;}
                if(root.right != null) { currentChild.next = root.right; currentChild = currentChild.next;}
                root = root.next;
            }
            root = tempChild.next;
        }
    }