Thursday, November 28, 2013

32. Longest Valid Parentheses ---------H

Q:
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

A:

 ---------------4th pass ----split into two round,  first find matching position of  ')' ,  and then combine them 

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        vector<int> matched(n, -1);
        vector<int> stack; // stack of non matched (
        for(int i =0;i<n;i++){
            if(s[i] == '('){
                stack.push_back(i);
            }else{
                if(not stack.empty()){
                    matched[i] = stack.back();
                    stack.pop_back();
                }
            }
        }
        // find the left most match
        int res = 0;
        for(int i= 0;i<n;i++){
            if(matched[i] >=0){
                int pre = matched[i];
                if(pre-1>=0 && matched[pre-1] >=0){
                    pre = matched[pre-1];
                }
                matched[i] = pre; // this need UPDATED
                res = max(res, i - pre + 1);
            }
        }
        return res;
    }
};

直觉就是用DP算法。
把输入,从empty的情况,开始加入。来看待。
记录下来,与之匹配的left parentheses的位置。  最后,再计算总长度。


---------------------------第二遍-----------------O(n)的复杂度-----即使是()()的向后跳的情况,也是最多发生O(n)次------------------------
思想是: 从后向前,记录一个该点最远可以达到的距离。
以后每一个新的位置 i ,如果是‘(’  首先找到它的match位置,(可能是 i+1 ,也可能是 farestMatch[i] +1 处)   。
找到match后,再查看是否是()()()这种情况, 并且加上。

public class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int n = s.length();
        int[] farestMatch = new int[n];
        for (int i = 0; i < n; i++)
            farestMatch[i] = -1;

        // count from back, at each potision,record farest matching position
        int maxLength = 0;
        for (int i = n - 2; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                // if next position does NOT has its matching
                int k = i + 1;// to be next tested position
                if (farestMatch[i + 1] > 0) // if i+1 position already has it
                                            // matching
                    k = farestMatch[i + 1] + 1;
                if (k < n && s.charAt(k) == ')') {
                    farestMatch[i] = k;
                    // now add possible ()()()() loops
                    while (farestMatch[i] + 1 < n && farestMatch[farestMatch[i] + 1] > 0)
                        farestMatch[i] = farestMatch[farestMatch[i] + 1];

                    maxLength = Math.max(maxLength, farestMatch[i] - i + 1);
                }
            }
        }
        return maxLength;
    }
}

----------------------------3rd Pass-------------------------------------
这次是彻底的O(n)。  而不用那个while 循环。
思想是:  用一个数组,记录其到最左端match 的位置。
          遍历的时候,用stack,记录其前一个match的位置。  然后,每次combine前一个,即得到所有的,最长的match的长度。

public class Solution {
    public int longestValidParentheses(String s) {
        int res = 0,  n = s.length();
        int [] A = new int[n]; // remember A[i]'s furthest matching position
        Arrays.fill(A,-1);
        for(int i =1;i<n;i++){
            if(s.charAt(i) ==')'){
                int pre = i-1;
                if(A[pre] >=  0) // pre position has no match
                    pre = A[pre]-1;
                if(pre>=0 && s.charAt(pre)=='('){
                    A[i] = pre;
                    if(pre-1>=0 && A[pre-1]>=0)
                        A[i] = A[pre-1];
                    res = Math.max(res, i-A[i]+1);
                }
            }
        }
        return res;
    }
}




Mistakes:
1:  当最终计算最大长度的时候,  我随手写了个    if (mostLeftMatchPos[i] > 0 ){
但是, 应该,是    if (mostLeftMatchPos[i] >= 0 ){ 的。
哎,不知道为什么,当时能那样写。
2: 开始, 当输入  为“())的时候,陷入了死循环。
原因是当回头看到的是  与left 没有匹配的情况的时候。  光记得 update nRightMinusLeft 去了, 忘了把j的位置再减一。
3: 当计算longest的时候, 光考虑与之前的单独match了,却没有考虑输入为 “()() ”的情况。
因此,需要在for循环里加一个while语句。



Learned:
1:  不要想着, 精简代码。  重要的,是思路清楚。  最好是(只要复杂度不变) 先解决小问题。不要想着一步到位。  做正确才是最重要的。
例如,这里,刚开始,不要想着, 直接建立leftMostMatch 而,仅仅去找leftMatch即可。
至于()()这种情况。我们完全可以基于leftMatch数组再计算。


130. Surrounded Regions -M

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
Example:
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
Explanation:
Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

A:

用图像里的growing思想呗。 每碰到一个 o  就开始检测。直到出了边界或者确认包围(转换成X)  嗯,首先是把边界的设 为 标识 @ , 然后grow,
 虽然,也用了小技巧,来提速,但是,这个的实现,还是有点儿慢了。 具体实现,在最后(learned section的下面)

下面这个方法,是利用grow un-surrouned O, 方法。
简单来讲,就是先从四周开始,一层层地剥开。
但是,这样的假设是不成立的, 原因在于, 无法回溯到 zig-zag形式的。

哎,还是回到前面的思路, 考虑到,我们是对200*200的一个巨大的0闭环内没有通过。
我们考虑从四周开始grow un-surrouned region(也就是把上面的2个思路并起来。


class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if(m==0)
            return;
        int n = board[0].size();        
        vector<vector<int> > stack;
        for(int i =0;i<m;++i)
            for(int j =0;j<n;++j)
                if((i==0 || i==m-1 || j==0 || j==n-1 ) && board[i][j] =='O')
                    stack.push_back(vector<int>{i,j});
        // change boundary 'O' --> 'A',
        while(not stack.empty())
        {
            vector<vector<int>> newS;
            for(auto tmp : stack)
            {
                int i = tmp[0], j = tmp[1];
                board[i][j] = 'A';
                if(i>0 && board[i-1][j] =='O')
                    newS.push_back(vector<int>{i-1,j});
                if(i+1<m && board[i+1][j] =='O')
                    newS.push_back(vector<int>{i+1,j});
                if(j>0 && board[i][j-1] =='O')
                    newS.push_back(vector<int>{i,j-1});
                if(j+1<n && board[i][j+1] =='O')
                    newS.push_back(vector<int>{i,j+1});
            }
            stack = newS;
        }
        for(int i =0;i<m;++i)
            for(int j =0;j<n;++j)
                if(board[i][j]=='O')
                    board[i][j] = 'X';
                else if(board[i][j] == 'A')
                    board[i][j] = 'O';
        
    }
};


Mistakes:
2: 处于速度考虑,我们search的时候,尽量通过从4个边来,从内往里search???
3: 还是有一些拼写错误,  主要来自于copy 上面的代码(因为重复性太多)

----------------------------这个更改,删掉了copy vector这个步骤, 节省了空间-------------
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if(m==0)
            return;
        int n = board[0].size();        
        vector<vector<int> > posList;
        for(int i =0;i<m;++i)
            for(int j =0;j<n;++j)
                if((i==0 || i==m-1 || j==0 || j==n-1 ) && board[i][j] =='O')
                    posList.push_back(vector<int>{i,j});
        // change boundary 'O' --> 'A',
        for(int cur = 0;cur<posList.size();++cur)
        {
            int i = posList[cur][0], j = posList[cur][1];
            board[i][j] = 'A';
            if(i>0 && board[i-1][j] =='O')
                posList.push_back(vector<int>{i-1,j});
            if(i+1<m && board[i+1][j] =='O')
                posList.push_back(vector<int>{i+1,j});
            if(j>0 && board[i][j-1] =='O')
                posList.push_back(vector<int>{i,j-1});
            if(j+1<n && board[i][j+1] =='O')
                posList.push_back(vector<int>{i,j+1});
        }
        for(int i =0;i<m;++i)
            for(int j =0;j<n;++j)
                if(board[i][j]=='O')
                    board[i][j] = 'X';
                else if(board[i][j] == 'A')
                    board[i][j] = 'O';
    }
};



Learned:
1: 在将就效率的时候,就不要搞些递归, 尽量用interative,  来存储中间数据。


--------------下面的这个,too  slow----------coz  we have use too many dfs ---------
public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0)
            return;
        int m = board.length;
        int n = board[0].length;
        // DFS track the border
        // for first and last rows
        for (int j = 0; j < n; j++) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }
        // for most left and most right columns
        for (int i = 1; i < m - 1; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        // flip all inner O into X , and boarder @ into O
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                else if (board[i][j] == '@')
                    board[i][j] = 'O';
    }

    private void dfs(char[][] board, int i, int j) {
        if (board[i][j] != 'O')
            return;
        board[i][j] = '@'; // set as a flag
        int m = board.length;
        int n = board[0].length;

        if (i - 1 >= 0 && board[i - 1][j] == 'O')// up
            dfs(board, i - 1, j);
        if (i + 1 < m && board[i + 1][j] == 'O')// down
            dfs(board, i + 1, j);
        if (j - 1 >= 0 && board[i][j - 1] == 'O')// left
            dfs(board, i, j - 1);
        if (j + 1 < n && board[i][j + 1] == 'O')// right
            dfs(board, i, j + 1);
    }
}

Wednesday, November 27, 2013

150. Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +-*/. Each operand may be an integer or another expression.
Note:
  • Division between two integers should truncate toward zero.
  • The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.
Example 1:
Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

A:

       每遇到运算符,就提出最后面的两个,运算,并保存。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> mystack;
        for(auto s:tokens)
        {
            if(s == "+" || s == "-" || s == "*" || s == "/")
            {
                int a = mystack.top();
                mystack.pop();
                int b = mystack.top();
                mystack.pop();
                if(s == "+")
                    mystack.push(b+a);
                if(s == "-")
                    mystack.push(b-a);
                if(s == "*")
                    mystack.push(b*a);
                if(s == "/")
                    mystack.push(b/a);
            }else{
                mystack.push(stoi(s));
            }
        }
        return mystack.top();
    }
};

Mistakes:
1 : 没有考虑 当一个数为:负数的时候, 例如 -2,  如果只检查首字母, 就会误认为是运算符。
2: 刚开始,自以为是了。  用double类型保持中间值。
    没想到,作者是不用的。   用int数组就行。

----------第二遍-----------
3: 由于是从 + 的情况直接copy 的代码,  对于 -   / 的情况,没有考虑 a,b 的顺序要调过来的。


Learned:





Tuesday, November 26, 2013

148. Sort List -M

Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5

A:

----------------------------merge sort   ---------------------------
First divide into two list, and merge them (append to the end of a new list) , which is of O(n) complexity.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(not head || not head->next)
           return head;
        //divide into two list
        ListNode* slow = head, *fast = head->next;
        while(not fast && fast->next)      // this is what you made mistake
        {
            slow = slow->next;
            fast = fast->next;
            if(fast)
                fast=fast->next;
        }
        auto p1 = sortList(slow->next);
        slow->next = NULL;
        auto p2 = sortList(head);
        return merge(p1,p2);
    }
private:
    ListNode* merge(ListNode* p1, ListNode* p2)
    {
        ListNode* pre = new ListNode(0);
        ListNode* tail = pre;
        while(p1 || p2)
        {
            if(not p1)
            {
                tail->next = p2;
                break;
            }
            if(not p2)
            {
                tail->next = p1;
                break;
            }
            if(p1->val <p2->val)
            {
                tail->next = p1;
                p1 = p1->next;
            }else{
                tail->next = p2;
                p2 = p2->next;
            }
            tail = tail->next;
        }
        return pre->next;
    }
};







Mistakes: 

2: when updating runner after a while loop, always remember to set runner= runner.next; after extracting Header2 list.

 3: Coz we forget updating the tail  even after we already done inserting the list.
 4:  日!!!!!!
 刚开始, return 命令行上面的一句:         header= newHeader; 应该写成
        header.next = newHeader.next;  就对了。
╮(╯▽╰)╭, 基础不行啊。Tiger ,这种SB的问题,你都能犯~~~~~~ 搞了爷们儿2个小时。 艹


Learned:
1: in C++,  to judge whether a node is null, we have 3 method
       a)  node == NULL
       b)  ! node
       c) not node


Monday, November 25, 2013

Insertion Sort List

Q:
Sort a linked list using insertion sort.
A:
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode header = new ListNode(Integer.MIN_VALUE);
        while(head!=null){
            ListNode tmp = head;
            head = head.next;
            
            ListNode runner = header;
            while(runner.next!=null && runner.next.val < tmp.val)
                runner = runner.next;
            
            tmp.next = runner.next;
            runner.next = tmp;
        }
        return header.next;
    }
}

Mistakes:
1: 当插入到比tail更前的的时候,  忘了break来跳出循环。
---------------第二遍--------------
1: 忘了把preNode 在whileloop的时候,先置为 newHeader
2:  after  checking preNode == null,    Mistakenly wrote
 tmp.next = preNode.next.next ;                        what the hell, can you make this mistake???????

Learned:



Friday, November 8, 2013

Wildcard Matching ~~~~~~~~~~~~~~~~~~~~~~~

Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
A:
1: 先用递归,估计会嫌太慢。先做出来再说吧。

 嗯,确实很慢。问题主要出在* 上。 下面是递归的解法。

public class Solution {
    public boolean isMatch(String s, String p) {
        if(s.length() ==0){
            if(p.length()==0)
                return true;
            else
                return p.charAt(0) =='*'? isMatch(s, p.substring(1)) : false;
        }
        if(p.length() ==0)
            return false;

        if(s.charAt(0) == p.charAt(0) || p.charAt(0) == '?')
            return isMatch(s.substring(1), p.substring(1));
        else if( p.charAt(0) == '*' )
            return isMatch(s,p.substring(1)) || isMatch(s.substring(1),p);
        else
            return false;
    }
}
上面这个解法,对于输入:
"babbbaabbaaaaabbababaaaabbbbbbbbbbabbaaaabbababbabaa", "**a****a**b***ab***a*bab" 
就会严重超时。

问题就出在 倒数第二个return 语句上,|| 后面那个helper()。当s只match了一个。这样效率很低。

  Solution 2
贪心算法,只需要依据连续的’*',将p分割成一些不带’*'的子串。然后在s中依次匹配就好了,只不过需要特殊照顾一下首尾两个子串:
1.对于开头不是’*'的p,第一个子串必须从s[0]开始匹配
2.对于结尾不是’*'的p,最后一个子串必须在s的尾巴上匹配

--------------------------确实快了很多,可是,当*后面的第一个字符串(非通配符)在s中match的次数过多的时候, 速度会显著降低。-------------------这时候,我们就不需要匹配所有的。 只需要找到匹配的即可。 嗯,如果是最后的字串,需要匹配最后的位置。
还需要继续优化。




-------------------solution 3 -----------------------
我们提出solution 3,  也就是把? 和其余的字符串放一起。
因此, p = "a???*a??b"被我们分成  [a,  ???, * ,   a??b] 四个子pattern。 这样出了第一个前面没有*外, 别的子pattern前面都有*, 可以随便移动位置。 (当然,需要自己写 字符匹配的函数。这个很简单)
 ----------------这里深入分析了8种解法----------- (还有代码)
--------------------- 这是第二遍的实现--------------思路跟solution3 一样-------只是更简洁了----

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) // should not occur
            return false;
        if (s.length() == 0)
            return p.length() == 0 || (p.length() == 1 && p.charAt(0) == '*');
        if (p.length() == 0)// if run this line, s.length() != 0
            return false;
        // check the first is *
        if (p.charAt(0) != '*') {
            int firstStartIndex = p.indexOf("*");
            if (firstStartIndex < 0) { // if p does not contains *
                return s.length() == p.length() && findFirstMatch(s, p) == 0;
            } else { // / p contains *
                String partP = p.substring(0, firstStartIndex);
                int matchPos = findFirstMatch(s, partP);
                if (matchPos != 0) { // if not fint at the first place
                    return false;
                } else { // we have find match at first place
                    s = s.substring(partP.length());
                    p = p.substring(partP.length());
                }
            }
        }
        String[] patternP = p.split("\\*");
        // all patternP[i] have a * ahead
        for (int i = 0; i < patternP.length; i++) {
            String nonStarP = patternP[i];
            int matchPos = findFirstMatch(s, nonStarP);
            if (matchPos < 0) {
                return false;
            } else {
                s = s.substring(matchPos + nonStarP.length());
            }
        }
        // if last have *,  or s is all matched
        return p.charAt(p.length() - 1) == '*' || s.length() == 0;
    }

    private int findFirstMatch(String s, String p) {
        // p does not contains *
        for (int i = 0; i <= s.length() - p.length(); i++) {
            // test substirng and p
            boolean isMatch = true;
            for (int j = 0; j < p.length(); j++) {
                char chS = s.charAt(i + j);
                char chP = p.charAt(j);
                if (chP != '?' && chS != chP) {
                    isMatch = false;
                    break;
                }
            }
            if (isMatch) { // if found match
                return i;
            }
        }
        return -1;
    }
}


Mistakes:
1: 当方法2的时候,没有考虑这种情况
Input: "", ""
Output: false
Expected: true
2:方法2的时候, 由于没有考虑到 p = "*"的情况。
而我们初始条件的startIndex = 0 是第一个valid情况。 而每次startIndex跳到下一个情况(或者越出右边界一位)
这样,就产生了错误。

3: 在用s的startIndex ==0 的初始情况的时候,没有考虑,当s为空的情况。 导致error.

4: when the substring is "?", at first ,we simply skip to next, but it is WRONG. we need also check whether s has the character with it.

5: 当遇到?的时候,我们仅仅startIndex跳到下一个了, 可是,没有注意
s="aa"
p ="*?"的情况时,我们需要多跳几个。  因此,还是需要把*?的顺序,调整成?*

Learned:
1: 好像在leetcode里,不用考虑,输入是null  的情况。
2:
         s = "aa";
         System.out.println( s.lastIndexOf("a", 0));
这里,很诡异的,输出竟然是0  而不是1.  ----------------原因如下。
public int lastIndexOf(String str, int fromIndex)
Returns the index within this string of the last occurrence of the specified substring, searching backward starting at the specified index. 


 -----------------第二遍-----------
1: 用 * 来split ,  命令要写成:   str.split("\\*");    -------- 要用双反斜线
2: 注意, split函数,是可以得到数组的某个元素为 “”的。


  --------------------------------下面 是 别人的代码------------ C++------------

Analysis:

For each element in s
If *s==*p or *p == ? which means this is a match, then goes to next element s++ p++.
If p=='*', this is also a match, but one or many chars may be available, so let us save this *'s position and the matched s position.
If not match, then we check if there is a * previously showed up,
       if there is no *,  return false;
       if there is an *,  we set current p to the next element of *, and set current s to the next saved s position.

e.g.

abed
?b*d**

a=?, go on, b=b, go on,
e=*, save * position star=3, save s position ss = 3, p++
e!=d,  check if there was a *, yes, ss++, s=ss; p=star+1
d=d, go on, meet the end.
check the rest element in p, if all are *, true, else false;

Note that in char array, the last is NOT NULL, to check the end, use  "*p"  or "*p=='\0'".
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const char* star=NULL;
        const char* ss=s;
        while (*s){
            if ((*p=='?')||(*p==*s)){s++;p++;continue;}
            if (*p=='*'){star=p++; ss=s;continue;}
            if (star){ p = star+1; s=++ss;continue;}
            return false;
        }
        while (*p=='*'){p++;}
        return !*p;
    }
};


-------------------------------------------------第三遍----------------想利用上面的想法, 也用递归来做的。结果还是超时。----------------------------然后就又是按照* 来split,然后线性查找即可--------  因此,这道题目,复杂度应该是在O(n)的--------------

对于前后的non- start string 的问题,我们事先匹配后,消去即可。

public class Solution { 
    public boolean isMatch(String s, String p) {
        if(p.length()==0)
            return s.length()==0;
        if(s.length()==0)
            return p.charAt(0)=='*' && isMatch(s,p.substring(1));
        if(p.charAt(0) !='*'){// delete all before first *
            return (p.charAt(0)=='?' || p.charAt(0)==s.charAt(0)) && isMatch(s.substring(1),p.substring(1));
        }
        if(p.charAt(p.length()-1) !='*'){ // delete all after last *
            char ch = p.charAt(p.length()-1);
            return (ch=='?' || ch ==s.charAt(s.length()-1)) && isMatch(s.substring(0,s.length()-1),p.substring(0,p.length()-1));
        }
        // now at the two end of p,  are *
        String[] P = p.split("\\*");
        int firstMatchPos = 0;
        for(int i =0;i< P.length; i++){
            if( P[i].length()==0)
                continue;
            firstMatchPos = findMatch(s, firstMatchPos,P[i]);
            if(firstMatchPos<0)
                return false;
            firstMatchPos += P[i].length();
        }
        return true;
    }
    private int findMatch(String s, int start, String p){// this p does not contain *
        for(int i =start;i <= s.length()-p.length();i++){
            //check the whole p
            boolean found = true;
            for(int j=0;j<p.length();j++){
                if( p.charAt(j) !='?' && p.charAt(j) != s.charAt(j+i)){
                    found = false;
                }
            }
            if(found)
                return i;
        }
        return -1;
    }
}

-------------------------------又一种思路---------------------
贪心的策略,能匹配就一直往后遍历,匹配不上了就看看前面有没有'*'来救救场,再从'*'后面接着试。
这个解法,其实就是我们最上面的哪种,但是,用两个index而不用递归,大大节省了时间。

public class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0, j = 0;
        int star = -1, mark = -1;
        while (i < s.length()) {
            if (j < p.length()
                    && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
                ++i;
                ++j;
            } else if (j < p.length() && p.charAt(j) == '*') {
                star = j++;
                mark = i;
            } else if (star != -1) {
                j = star + 1;
                i = ++mark;
            } else {
                return false;
            }
        }
        while (j < p.length() && p.charAt(j) == '*') {
            ++j;
        }
        return j == p.length();
    }
}



Thursday, November 7, 2013

145. Binary Tree Postorder Traversal -----------M

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Follow up: Recursive solution is trivial, could you do it iteratively?

 

Example 1:

Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [2,1]

Example 5:

Input: root = [1,null,2]
Output: [2,1]

 

Constraints:

  • The number of the nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
A:
不论是用两个stack (还是每次加到前面,最后reverse回来)原理都是一样的。 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> S;
        if(root)
            S.push(root);
        
        while(not S.empty()){
            auto cur = S.top();
            S.pop();
            if(cur->left)
                S.push(cur->left);
            if(cur->right)
                S.push(cur->right);
            res.push_back(cur->val);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};


Mistakes:
1: 忘了先check root为null 的情况
--------------------------第三遍------(用了一个stack,一个set(set来记录是否被visited过))--------------------
2:  把if写成了while   ,  哎,丢死人了
3:  写成了先  压栈右边,再压栈左边的了。     这个, 当时是考虑到正常顺序,是要先遍历左子树,再遍历右子树的。   但是, 但是没有考虑到, 其实,我们是reversely 加入到al的最前面的。 因此,  要先遍历右子树的。


public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
         List<Integer> result = new LinkedList();
         if(root ==null)
            return result;
         Stack<TreeNode> stack = new Stack();
         Set<TreeNode> set = new HashSet();
         stack.push(root);
         set.add(root);
         while(!stack.isEmpty()){
             TreeNode node = stack.pop();
             if(set.contains(node)){// first time to find this node
                stack.push(node);
                if(node.right!=null){
                    stack.push(node.right);
                    set.add(node.right);
                }
                if(node.left!=null){
                    stack.push(node.left);
                    set.add(node.left);
                }
                 set.remove(node);
             }else{// node should be printed directly
                 result.add(node.val);
             }
         }// end of while
         return result;
    }
}


Learned:



128. Longest Consecutive Sequence

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

A:
由于自己很少很少用HashMap, 因此,遇到了这个用2个HashMap 连用的情况,还是很抓瞎的。 花了近3个小时,才弄出来。哎

思想比较简单: for each   val = num[i],  we map val to the key value, where key is the start of Interval, where val lies.( if val does not find ,we insert.)
and in the second HashMap, we map the key to the interval.
步骤如下:
 if val is not found ,
case 1) check if (val -1 ) and (val +1) exist, if it is, then combine these two intervals
case 2) find (val-1),  add val to this left interval , and interval.end++
case 3) find (val+1) , add val to this right interval, and  interval.start--
case 4) val is isolate,  simply add this list.
always update the maxLen of this list.
 代码如下:
public class Solution {
   public int longestConsecutive(int[] num) {
        // map the num[i] value to a key ( used in next HashMap) , which is the start of interval 
        HashMap<Integer, Integer> map2Key = new HashMap<Integer, Integer>();
        // map key value to interval 
        HashMap<Integer, Interval> map2Interval = new HashMap<Integer, Interval>();
        int maxLen = 0;
        for (int i = 0; i < num.length; i++) {
            int val = num[i];
            if(! map2Key.containsKey(val)) {// first time to find value
                int key;// check val -1 and val +1, 
                if(map2Key.containsKey(val -1)  && map2Key.containsKey(val +1)){// val is in middle
                    // merge two list, and delete the val+1 map
                    int keyLow = map2Key.get(val -1);
                    int keyHigh = map2Key.get(val + 1);
                    map2Interval.get(keyLow).end = map2Interval.get(keyHigh).end;
                    //update all the map2Key values
                    for(int j = val; j<= map2Interval.get(keyHigh).end ;j++){
                        map2Key.put(j, keyLow );
                    }
                    map2Interval.remove(keyHigh);                    
                    key = keyLow;
                }else if(map2Key.containsKey(val -1)){ // val is at right
                    map2Key.put(val, map2Key.get(val-1));
                    key = map2Key.get(val-1);
                    map2Interval.get(key).end++;
                }else if(map2Key.containsKey(val +1)){
                    map2Key.put(val, map2Key.get(val+1));
                    key = map2Key.get(val + 1);
                    map2Interval.get(key).start--;
                }else{ // the new value is isolate
                    key = val;
                    map2Key.put(val, val);
                    map2Interval.put(key, new Interval(val,val));
                }
                // update maxLen
                maxLen = Math.max(maxLen, map2Interval.get(key).end - map2Interval.get(key).start+1);
            }
        }
        return maxLen;
    }
}

--------------------------第二遍-------------看了网上的,别人的思路了------
 思路如下:----
  • Put the number into HashSet, O(n);
  • Check the num[] from the first to the last
    • get value of num[i],remove it from set, low = num[i]-1; high = num[i]+1;
    • check if the low and high are in the set
      • if yes. low or high expand 1; remove this number from set
      • if no. continue;
    • calculate the value of low and high. get longest
  • return longest
public class Solution {
   public int longestConsecutive(int[] num) {
        // use only one hashMap
        Set<Integer> set = new HashSet<Integer>();
        
        for(int i = 0; i< num.length;i++)
            set.add(num[i]);
        int maxLength =0;
        for(int i = 0; i< num.length;i++){
            if( !set.contains(num[i]))// it is already find
                continue;
            int low = num[i]-1;
            int high = num[i] +1;
            while(set.contains(low)){
                set.remove(low);
                low--;
            }
            while(set.contains(high)){
                set.remove(high);
                high++;
            }
            maxLength = Math.max(maxLength, high-low -1);
        }
        return maxLength;
    }
} 

----------------------第三遍 -----------------------------
比第二遍的改进就是,  low= num[i] , 这样就可以同时删除num[i] 这个节点了。



Mistakes:
1:  in case 1, when two list are merged.
     we should point all the val values in the high part of the list,, with their mapping key value to  leftInterval.start


Learned:



129. Sum Root to Leaf Numbers --M

Q:
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
    1
   / \
  2   3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
A:    
Note:   A leaf node has no children.
思路不是很清晰,先用一个最简单的方法。实现了,看看有什么问题需要注意的吧。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int res = 0;
        if(root)
            helper(root, 0, res);
        return res;
    }
private:
    void helper(TreeNode* root, int preSum, int & res){
        int curSum =  preSum * 10 + root->val;
        if(!root->left && !root->right)
            res += curSum;
        else{
            if(root->left)
                helper(root->left, curSum, res);
            if(root->right)
                helper(root->right, curSum, res);
        }
    }
};


----------------------------因此我们分别计算左右子树,再加起来,就accept了--------------------
public class Solution {
      public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getSum(root,  0);
    }

    private int getSum(TreeNode node,  int curSum) {
        // return the new sum of the of the current
        if (node.left == null && node.right == null) {// find leaf
            return  (node.val + curSum * 10);            
        }
        int sumLeft =0, sumRight =0;
        if (node.left != null) { // go further left
            sumLeft = getSum(node.left,  curSum * 10 + node.val);
        }
        if (node.right != null) {// go further left
            sumRight = getSum(node.right, curSum * 10 + node.val);
        }
        return sumLeft + sumRight;
    }
}



Mistakes:
1 :  思路不清晰。   刚开始走了弯路, 去生成新的tree去了。其实是不需要新的tree的。
当然,也可以在getSum()方法中,传递一个 preSum 参数,来记录前序节点的和。


Learned:
leetcode 中,添加了新的类变量,会导致一系列问题。
 见买买提链接

use a data member.
and the result are accumulated...


I think your algorithm is right. But you use static vars, which might cause problem. Because maybe OJ just creates one instance of class solution, and uses it on many test cases. So you had better reset them. This is the only reason I can come up with. I am not sure. You can use a vector to track the node instead.
 ---------------1337
yes. that's the problem.
and i initialized it to 0 in the function and here we go.

【 在 stupidrobot (robot) 的大作中提到: 】
: 谨慎估计你添加新的类变量了


下面的解法,是不对的。Tiger 自己想想,是哪里不对了。
public class SumRootToLeafNumbers2 {
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getSum(root, 0, 0);
    }

    private int getSum(TreeNode node, int totalSum, int curSum) {
        // return the new sum of the of the current
        if (node.left == null && node.right == null) {// find leaf
            totalSum += (node.val + curSum * 10);
            return totalSum;
        }
        if (node.left != null) { // go further left
            totalSum += getSum(node.left, totalSum,curSum * 10 + node.val);
        }
        if (node.right != null) {
            totalSum += getSum(node.right,totalSum, curSum * 10 + node.val);
        }
        return totalSum;
    }
}







答案就在于,左右子树的结果,不应该是 totalSum +=   , 而仅仅 totalSum= 就可以了。


45. Jump Game II ~~~~~~~~仔细体会方法2

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

A:

First, try the one-by-one step to move further.
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> DP(n,INT_MAX); //DP to find each minimum jump
        DP[0] =0;
        for(int i = 0;i<n;i++){
            for(int j = i+1;j <= min(n-1, i+nums[i]); j++){
                DP[j] = min(DP[j], DP[i] + 1 );
            }
        }
        return DP[n-1];
    }
};

***************Exceed the time limit **************

Each round, we found the right most reachable position, and update all positions before it.







这个应该算是DP问题吧.
思路 来自 问题1:  i_th position 用k步的时候,之前的节点,都可以在不超过k步内达到。
因此,先建立minJump的一些节点,如果然后,没有按照 A[i] 跳到的地方,就直接copy 后面的节点的step 值。   这样,一个while loop就完了。

这样之后, 再update后面的minJump。 哎呀,比较乱,还是看代码吧。

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> DP(n, INT_MAX);
        DP[0] = 0;
        int start = 0,end = 0;
        while(start < n-1){
            int rightMost = -1;
            for(int i = start; i<= end; i++){                
                rightMost = min(n-1,  max(rightMost, i + nums[i]  )  );
            }
            // assign the minStep for next few available position
            for(int i = end+1; i<= rightMost; i++){
                DP[i] = DP[start]+1;
            }
            start = end+1;
            end = rightMost;
        }
        return DP[n-1];
    }
};

---------------------------------3 rd pass-------------------------same idea, but instead of allocating an Array, we use constant space.----------------------------------------

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int curStart = 0, curEnd = 0; // current level of start and end
        int res = 0;
        while(curEnd < n-1){ // use curEnd NOT curStart
            int mostRight = -1;
            res++;
            // from curStart till most recent,
            for(int i =curStart;i<= curEnd;i++){
                mostRight = max(mostRight, i + nums[i]);
            }
            mostRight = min(mostRight, n-1);
            curStart = curEnd +1;
            curEnd = mostRight;
        }
        return res;
    }
};

Mistakes:
1: 刚开始的思路错误。 而没有借助problem 1的思路。 搞得晚上1点多到2点多。也没弄完这道题。哎, 早点儿睡觉啊,Tiger

Learned:



Wednesday, November 6, 2013

57. Insert Interval -------M

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

 

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Example 3:

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

Example 4:

Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]

Example 5:

Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]

 

Constraints:

  • 0 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= intervals[i][0] <= intervals[i][1] <= 105
  • intervals is sorted by intervals[i][0] in ascending order.
  • newInterval.length == 2
  • 0 <= newInterval[0] <= newInterval[1] <= 105
A:
就是简单的查找,并入。

------------------------2nd pass-----------------------------------------------
就是先插入。如果是插入的,就直接返回。如果是合并了的,就直接从合并的位置,往后一个个check ,看是否要合并。
----Error:   合并了一个,以后的也要检查哦


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        bool used= false;
        for(int i =0; i< intervals.size(); i++){     
            auto t = intervals[i];
            if(not used ){
                if(t[1] < newInterval[0]){
                    res.push_back(t);
                }else if(t[0] > newInterval[1]){
                    res.push_back(newInterval);
                    used = true;
                    i--;
                }else{ // they have over lap
                    t[0] = min(t[0], newInterval[0]);
                    t[1] = max(t[1], newInterval[1]);
                    used = true;
                    res.push_back(t);
                }
            }else{// already used   res.empty() == false
                if(res.back()[1] >= t[0] ){
                    res.back()[1] = max(t[1], res.back()[1]);
                }else{
                    res.push_back(t);
                }
            }
        }
        if(not used){
            res.push_back(newInterval);
        }
        return res;
    }
};

Mistakes:
1:没有处理intervals为空的edge case.  肏~~~~~~~~~~
2: