Leetcode: Palindrome Number

Problem

Leetcode link for this question
Determine whether an integer is a palindrome. Do this without extra space.

Analyze

This is the previous post on this question
This is easy question, just find the most left digit and then compare each digit from left-right ends to center.

Code

C++ code accept by Leetcode, which exclude negative number like -121 as palindrome

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0)
            return false;
        int highDigit = 1;
        while(x / highDigit >= 10)
            highDigit *= 10;
        int lowDigit = 1;
        while(highDigit > lowDigit){
            int high = (x / highDigit) % 10;
            int low = (x/lowDigit) % 10;
            if(high != low)
                return false;
            highDigit /= 10;
            lowDigit *= 10;
        }
        return true;
    }
};

C++ code for who consider negative number like -121 also as palindrome

class Solution {
public:
    bool isPalindrome(int x) {
        int highDigit = 1;
        while(x / highDigit >= 10 || x / highDigit <= -10)
            highDigit *= 10;
        int lowDigit = 1;
        while(highDigit > lowDigit){
            int high = (x / highDigit) % 10;
            int low = (x/lowDigit) % 10;
            if(high != low)
                return false;
            highDigit /= 10;
            lowDigit *= 10;
        }
        return true;
    }
};

Leetcode: String to Integer (atoi)

Problem

Leetcode link
Implement atoi to convert a string to an integer.

Analyze

This is the previous answer to this question

The complexity of this problem is how to handle edge cases.
For int, standard as 32-bit length, has a max value of (1<<31) - 1 and a min value of (1<<31).
When read each digit from string, need check if the result will be overflow.
And another situation is that the leading blank spaces, and possibly has + or -.

Code

class Solution {
public:
    const int max = (1<<31) - 1;
    const int min = -max - 1;

    inline bool willOverflow(int sign, int base, int digit) {
        static const int maxTenth = max / 10;
        static const int maxDigit = max % 10;
        static const int minTenth = - (min / 10);
        static const int minDigit = - (min % 10);
        if(sign == 1){
            return (base > maxTenth || base == maxTenth && digit > maxDigit);
        } else {
            return (base > minTenth || base == minTenth && digit > minDigit);
        }
    }

    // The test case only allow "    -123" like this, after hit sign or digit, can not take any invalid or blank char.
    int myAtoi(string str) {
        if (str.size() == 0) return 0;
        int sign = 1;
        bool gotNumber = false; //allow blank space before number
        bool gotSign = false; // allow <= 1 sign
        int result = 0;
        for(int i = 0; i < str.size(); ++i) {
            if(!gotNumber && str[i] == ' ') continue; 
            if(!gotNumber && !gotSign && (str[i] == '+' || str[i] == '-')){
                sign = str[i]=='-' ? -1 : 1;
                gotSign = true;
                gotNumber = true;
                continue;
            }
            if(str[i] < '0' || str[i] > '9')
                return result * sign;
            gotNumber = true;
            int digit = str[i] - '0';
            if(willOverflow(sign, result, digit))
                return sign == 1 ? max : min;
            result = result * 10 + digit;
        }
        return result * sign;
    }
};

Leetcode: Contains Duplicate II

Question

Contains Duplicate II
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

Analyze

It’s strait forward to using dictionary on this question. First run, save position of each number in the dictionary; Second run, check the dictionary to see if there is another duplication in this array and check the position of it.
But there is a situation that need take into consideration, that the array may contain the duplication multiple times. To deal with this, just checking in the first run, to see if the last position (if any) is close enough.

Code

C++ code

class Solution {
public:
    inline int abs(int v) {
        return v < 0 ? -v : v;
    }
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int, int> dict;
        for(int i=0; i<nums.size(); ++i) {
            if(dict.find(nums[i]) != dict.end()) {
                if(abs(dict[nums[i]]-i) <= k)
                    return true;
            }
            dict[nums[i]]=i;
        }
        for(int j=0; j<nums.size(); ++j){
            map<int,int>::iterator it = dict.find(nums[j]);
            map<int,int>::iterator endit = dict.end();
            if(endit != it){
                int i = it->second;
                if(i != j && abs(i-j) <= k)
                    return true;
            }
        }
        return false;
    }
};

Leetcode: Integer to Roman

Question:

Integer to Roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

Analyze:

Just handle each digit in the number.
For numbers from [0, 9], they are mapping to:
0 – ‘ ‘
1 – ‘I’
2 – ‘II’
3 – ‘III’
4 – ‘IV’
5 – ‘V’
6 – ‘VI’
7 – ‘VII’
8 – ‘VIII’
9 – ‘IX’

The patten is that for digit in [0,3], repeat ‘I’ digit times;
for digit == 4, ‘IV’
for digit in [5, 8], put digit-5 times ‘I’ after ‘V’;
for digit == 9, ‘IX’

Then from 10 – 90, using ‘X’, ‘L’, ‘C’ instead of ‘I’, ‘V’, ‘X’. So if we store all the available chars in an array, it just move the base index += 2 each time we handle next digit.

Code

C++ Code

char* intToRoman(int num) {
    char chars[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M', 'C', 'D'};
    char * result = malloc(100);
    if(num <= 0 || num >= 4000)
        return result;

    int tail = 100;
    int charBase = 0;
    while(num != 0)
    {
        int digit = num % 10;
        char temp[3];
        int templen = 0;
        if(digit <= 3)
        {
            for(int i = 1; i <= digit; ++i)
            {
                temp[i-1] = chars[charBase];
            }
            templen = digit;
        } 
        else if (digit == 4)
        {
            temp[0] = chars[charBase];
            temp[1] = chars[charBase + 1];
            templen = 2;
        }
        else if(digit <= 8)
        {
            temp[0] = chars[charBase + 1];
            templen = 1;
            for(int i = 6; i <= digit; ++i)
            {
                temp[i-5] = chars[charBase];
                templen += 1;
            }
        } 
        else
        {
            temp[0] = chars[charBase];
            temp[1] = chars[charBase + 2];
            templen = 2;
        }

        //copy temp to result
        tail = tail - templen;
        for(int i = 0; i < templen; ++i)
        {
            result[tail + i] = temp[i];
        }

        charBase += 2;
        num /= 10;
    }

    //move result to start
    for(int i = tail; i < 100; ++i) {
        result[i-tail] = result[i];
        result[i] = 0;
    }

    return result;
}

LeetCode: Reverse Integer

Previous Post

This is the previous post on same question.

Question

LeetCode Link
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321

Analyze

Careful about the overflow. For ruby, it’s not a problem. For c++, need more consideration.

Code

Ruby Code

# @param {Integer} x
# @return {Integer}
def reverse(x)
    sign = x >= 0 ? 1 : -1
    x = x.abs
    y = 0
    int_max = 2 ** 31 - 1
    while x > 0 do
        digit = x % 10
        y = y * 10 + digit
        if y > int_max
            y = 0
            break
        end
        x /= 10
    end
    y * sign
end

C++ Code

class Solution {
public:
    int reverse(int x) {
        int sign = 1;
        if(x < 0) {
            sign = -1;
            x = -x;
        }
        int int_max = (1 << 31) - 1; //notice the priority of << is lower than -
        int dime = int_max / 10;
        int tail = int_max % 10 + (sign == 1 ? 0 : 1);

        int y = 0;
        while(x > 0){
            int digit = x % 10;
            if(y > dime || (y == dime && digit > tail)){
                return 0;
            }
            y = y * 10 + digit;
            x /= 10;
        }
        return y * sign;
    }
};

LeetCode: ZigZag Conversion

Previous post

This is the old post on this question, using another method.

Question

Leetcode Link
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) //should return "PAHNAPLSIIGYIR".

Analyze

This question is simple, one method is that build strings for each row, and for each char in the string, determine the target row of the position based on the total row count, and append it to the target string. Then concat all the strings together in the last.

Code

The fast ruby version

# @param {String} s
# @param {Integer} num_rows
# @return {String}
def convert(s, num_rows)
    result = []
    tail_size = num_rows > 2 ? num_rows - 2 : 0
    group_size = num_rows + tail_size

    s.length.times do |i|
        in_group_position = i % group_size
        target_row = if in_group_position < num_rows
            in_group_position
        else
            num_rows - 1 - (in_group_position - num_rows)
        end
        result[target_row] ||= ""
        result[target_row] << s[i]
    end

    result
end

Screen Shot 2016-05-04 at 16.20.51

LeetCode Problem: Maximum Depth of Binary Tree

Recursively count the depth of tree node. One node’s depth is the maximum depth of it’s children’s depth + 1 or 0 if node is NULL.
递归计算就可以了,如果是空节点,深度是0,否则这个节点的子树的最大深度是其子节点最大深度 + 1。



Maximum Depth of Binary Tree Sep 30 ’12
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.



Code, 64ms pass large set

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(root == NULL) return 0;
        int leftdep = maxDepth(root->left);
        int rightdep = maxDepth(root->right);
        return 1 + std::max(leftdep,rightdep);
    }
};

LeetCode Problem: Valid Palindrome

To solving this problem, using two pointer to track the characters in the string. i, from the beginning of string; j, from the back of the string.
这个问题简单,只需要收尾两个指针相向而行,比较是否相等就可以了,过程中跳过不是字母也不是数字的字符。算法如下:

while i < j do {
  1.if s[i] is not alphanumeric, moving i forward and continue
  2.if s[j] is not alphanumeric, moving j backward and condinue
  3.if s[i] != s[j] (ignoring the cases) return false.
  4.moving i forward and j backward by one step
}
return true;



Valid Palindrome Jan 13
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.



Code, 60ms pass large set

class Solution {
    inline bool isAlpha(char c) {
        if(c >= 'a' && c <= 'z') return true;
        if(c >= 'A' && c <= 'Z') return true;
        if(c >= '0' && c <= '9') return true;
        return false;
    }
    inline char lower(char c) {
        if(c >= 'A' && c <= 'Z')
            return ('a' + (c-'A'));
        return c;
    }
public:
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i = 0, j = s.size() - 1;
        while(i < j) {
            if(!isAlpha(s[i])) {
                ++i;
                continue;
            }
            if(!isAlpha(s[j])) {
                --j;
                continue;
            }
            if(lower(s[i++]) != lower(s[j--])) {
                return false;
            }
        }
        return true;
    }
};



Code rewrite at 2013-2-4

class Solution {
    bool isValidChar(char c) {
        if (c >= '0' && c <= '9')
            return true;
        if (c >= 'a' && c <= 'z')
            return true;
        if (c >= 'A' && c <= 'Z') {
            return true;
        }
        return false;
    }
    char lower(char c) {
        if (c >= 'A' && c <= 'Z') {
            return 'a' + c - 'A';
        }
    }
public:
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(s.size() <= 1) return true;
        int si=0,ei=s.size()-1;
        while(si < ei) {
            while(si < ei && !isValidChar(s[si]))
                ++si;
            while(si < ei && !isValidChar(s[ei]))
                --ei;
            if(lower(s[si]) != lower(s[ei])) {
                return false;
            }
            ++si;--ei;
        }
        return true;
    }
};



Code rewrite at 2013-03-03

class Solution {
    bool isValid(char c) {
        if (c >= '0' && c <= '9')
            return true;
        if (c >= 'a' && c <= 'z')
            return true;
        if (c >= 'A' && c <= 'Z') {
            return true;
        }
        return false;
    }
    char lower(char c) {
        if (c >= 'A' && c <= 'Z') {
            return 'a' + c - 'A';
        }
    }
public:
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(s.size() <= 1) return true;
        int si=0,ei=s.size()-1;
        while(si < ei) {
            if(!isValid(s[si])) {
                ++si;
                continue;
            }
            if(!isValid(s[ei])) {
                --ei;
                continue;
            }
            if(lower(s[si++]) != lower(s[ei--])) {
                return false;
            }
        }
        return true;
    }
};

LeetCode Problem: Pascal’s Triangle II

Follow the algorithm in LeetCode Problem: Pascal’s Triangle, we can simple return the required row from the result.
从上一个题的算法LeetCode Problem: Pascal’s Triangle,可以得到一个简单的方法就是,在上一题的基础上,最后返回需要的行即可。

But, we can optimize this to use constant extra space, even better than the required O(k) extra space in the problem description below.
题目要求最好能用O(k)的额外空间,但是我们可以做的更好,甚至只用常数的额外空间就好了。

 [1,3,3,1],
 [1,4,6,4,1]

Take the above two rows as example, we can see that, the element in the last row is only relative to the element above it and the one before the element above it. So we can generate the last row from the previous row in backward order in place.Thus, we do not need the extra spaces.
拿上面这两行为例,每一个元素其实只与它上面一个和左上那一个元素相关。也就是说,如果要生成元素的下标是i的话,它只和i和i-1相关。所以我们可以用从后往前的顺序原地生成后一行。这样就不用任何辅助空间了。



Pascal’s Triangle II Oct 29 ’12
Given an index k, return the kth row of the Pascal’s triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?



Code, 16ms pass large test set

class Solution {
public:
    vector getRow(int rowIndex) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector ret;
        if(rowIndex < 0) return ret;
        for(int ir = 0; ir <= rowIndex; ++ir) {
            //put an 1 at the end of this row
            ret.push_back(1);
            //handle the rest of elements backward
            for(int ic = ir - 1; ic > 0; --ic) {
                ret[ic] = ret[ic] + ret[ic - 1];
            }
        }
        return ret;
    }
};

LeetCode Problem: Pascal’s Triangle

The problem is simple, each element in the triangle is the sum of two numbers above it.
这个题目简单,三角形中每一个元素的值是其上面两个值的和。

So, just build the rows one by one according the row above it. And the first row is {1}.
根据当前行的上面一层数字,就可以逐行生成整个三角形了。初值是第一行:{1}



Pascal’s Triangle Oct 28 ’12
Given numRows, generate the first numRows of Pascal’s triangle.
For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]



Code, 12ms pass large test set

class Solution {
public:
    vector > generate(int numRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector >ret;
        if(numRows == 0) return ret;
        //first row
        ret.push_back(vector(1,1));
        //rest rows;
        for(int nr = 2; nr <= numRows; ++nr) {
            vector thisrow(nr,1);
            vector &lastrow = ret[nr-2];
            for(int ic = 1; ic < nr - 1; ++ic) {
                thisrow[ic] = lastrow[ic-1] + lastrow[ic];
            }
            ret.push_back(thisrow);
        }
        return ret;
    }
};

LeetCode Problem: Populating Next Right Pointers in Each Node II

The code in the previous article LeetCode Problem: Populating Next Right Pointers in Each Node, Level traversal of binary tree is also adapted to this situation.
上一题LeetCode Problem: Populating Next Right Pointers in Each Node, Level traversal of binary tree的答案对这个题目仍然是适用的。



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

LeetCode Problem: Populating Next Right Pointers in Each Node, Level traversal of binary tree

It’s easy to doing this by using a queue, doing a level traversal of binary tree.
题目相对简单,用一个队列来进行广度优先遍历就可以了,用一个NULL来指示每一层的结束。



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



Code, 160ms pass the large test set.

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        queue q;
        if(root) {
            q.push(root);
            q.push(NULL);
        }
        while(q.size()) {
            TreeLinkNode *cur = q.front();
            q.pop();
            if(cur) {
                cur->next = q.front();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            } else {
                if (q.size()) q.push(NULL);
            }
        }
    }
};



Code rewrite at 2013-1-19, more simple

class Solution {
public:
    void connect(TreeLinkNode *root) {
        queue q;
        q.push(root);
        q.push(NULL);
        while(true) {
            TreeLinkNode *cur = q.front();
            q.pop();
            if(cur) {
                cur->next = q.front();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            } else {
                if (q.size() == 0 || q.front() == NULL) return;
                q.push(NULL);
            }
        }
    }
};

LeetCode Problem:Flatten Binary Tree to Linked List

We can notice that in the flattened tree, each sub node is the successor node of it’s parent node in the pre-order of the original tree. So, we can do it in recursive manner, following the steps below:
1.if root is NULL return;
2.flatten the left sub tree of root, if there is left sub-tree;
3.flatten the right sub-tree of root, if has;
4.if root has no left sub-tree, then root is flattened already, just return;
5.we need to merge the left sub-tree with the right sub-tree, by concatenate the right sub-tree to the last node in left sub-tree.
5.1.find the last node in the left sub tree, as the left is flattened, this is easy.
5.2.concatenate the right sub-tree to this node’s right child.
5.3.move the left sub-tree to the right for root.
5.4.clear the left child of root.
6.done.

<br>
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6



Code:48ms to accept with large test set.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) return;
        //1.flat the left subtree
        if (root->left)
            flatten(root->left);
        //2.flatten the right subtree
        if (root->right)
            flatten(root->right);
        //3.if no left return
        if (NULL == root->left)
            return;
        //4.insert left sub tree between root and root->right
        //4.1.find the last node in left
        TreeNode ** ptn = & (root->left->right);
        while (*ptn)
            ptn = & ((*ptn)->right);
        //4.2.connect right sub tree after left sub tree
        *ptn = root->right;
        //4.3.move left sub tree to the root's right sub tree
        root->right = root->left;
        root->left = NULL;
        
    }
};



Code rewrite at 2013-2-20, non-recursive version

class Solution {
public:
    void flatten(TreeNode *root) {
        bool f = true;
        stack t;
        TreeNode *pre = NULL;
        if(root) {
            t.push(root);
        }
        
        while(t.size()) {
            TreeNode *cur = t.top();
            if(f) {
                if(cur->left && cur->left != pre) {
                    t.push(cur->left);
                } else {
                    f = false;
                }
            } else {
                if(cur->right && cur->right != pre) {
                    t.push(cur->right);
                    f = true;
                } else {
                    t.pop();
                    //at this time, the sub-tree of cur is flattened, so just flatten the cur
                    TreeNode *left = cur->left;
                    if(left) {
                        TreeNode *lastLeft = left;
                        while(lastLeft->right) {
                            lastLeft = lastLeft->right;
                        }
                        lastLeft->right = cur->right;
                        cur->right = left;
                        cur->left = NULL;
                    }
                }
            }
            pre = cur;
        }
    }
};

LeetCode Problem:Distinct Subsequences

(2013-1-5更新了动态规划版本,见下面)
这题有点复杂,一开始拿到都不知道怎么下手。

尝试的路径是:
1·先试试看从T的size上简化看看。写一个例子S = aaaaa,T = a,很简单,数数就行。然后T=aa,发现没有太好的方法,怎么弄也算不出来最后结果。但是如果第一步查找记录下了所有的位置的话,只需要看该位置后面还有没出现T[1]就好了。比如S=aaba,T=ab,那么第一步查找得到{0,1,3},第二步只需要在这个集合内查看,S[0]后面有没有b,S[1]后面有没有b,S[3]后面有没有b。最后得到{02,12}两个结果。这样有了一个初步的算法,只不过非常消耗内存。小集合可以过,大集合内存超过限制。
2·内存如何超限的呢?比如当S=aaaa,T=aaa,的时候,第一轮结果{0,1,2,3},第二轮就变成了{01,02,03,12,13,23},可以看到,如果S再长一点的话,是很恐怖的。但是实际上从这里也能看出一点问题,就是02,12是可以合并的,因为下次它两个都会去查找S[2]之后有没有T[2],而且得到的结果是一样的。如果合并的话,不仅空间省了,时间也省了。所以就可以用一个int数组,记录在当前时刻(查找过程中T的下标),在S的某个位置结束的成功匹配个数。比如这个数组叫做matches,和S等大。那么第一轮下来matches[i] = (S[i] == T[0])。第二轮开始,针对每一个j = 1 … T.size() – 1,对matches中记录的每一个结束点去往后查找T[j],找到的话(比如在S[ii] == T[j]),那么新的matches[ii] += matches[i]。所以这里需要两个数组来回倒腾。最后写出代码220ms过了大集合测试。空间复杂度O(S.size()),时间复杂度O(S.size() * S.size() * T.size())。而且在查找的时候还可以简化,这样整体时间复杂度可以变成O(S.size() * T.size())



Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).
Here is an example:
S = “rabbbit”, T = “rabbit”
Return 3.



代码:220ms过大集合

class Solution {
public:
    int numDistinct(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (T.size() == 0 || S.size() == 0 || S.size() < T.size())
            return 0;
        
        //at each position i in S, how many matches could be found with the substring end at S[i]
        int *matches = new int[S.size()];
        //temporary array for updating matches.
        int *mtemp = new int[S.size()];

        //1.initialize
        for(int i = 0; i < S.size(); ++i) {
            matches[i] = (S[i] == T[0] ? 1 : 0);
            mtemp[i] = 0;
        }
        
        for(int j = 1; j < T.size(); ++j) {
            const char tj = T[j];//process the char T[j]
            for(int ilast = 0; ilast < S.size(); ++ilast) {
                if (matches[ilast] == 0)//no possible matches
                    continue;
                for(int i = ilast + 1; i < S.size(); ++i) {
                    if(S[i] == tj) {
                        mtemp[i] += matches[ilast];//and the match count in ilast to new location
                    }
                }
            }
            for(int ilast = 0; ilast < S.size(); ++ilast) {
                matches[ilast] = 0;
            }
            int * t = matches;//switch matches and mtemp
            matches = mtemp;
            mtemp = t;
        }
        
        int sum = 0;
        for(int i = 0; i < S.size(); ++i) {
            sum += matches[i];
        }
        return sum;
    }
};



代码1:小集合可以过,大集合内存超过

class Solution {
public:
    int numDistinct(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (T.size() == 0 || S.size() == 0)
            return 0;
        queue pls;//possible location start index in S
        
        //1.inite pls by searchin T[0] in S
        for(int i = 0; i < S.size(); ++i) {
            if (S[i] == T[0]) {
                pls.push(i);
            }
        }
        //2.one by one search T[j] in S, update the loast match index in pls or remove if no match fould
        const int levelEnd = -1;
        int j = 1;
        if(pls.size() && j < T.size()) pls.push(levelEnd);
        while(pls.size() && j < T.size()) {
            if(pls.size() > 1000) return 1000;
            char tj = T[j];
            int lasti = pls.front();
            pls.pop();
            if (lasti == levelEnd) {
                ++j;
                if (j == T.size()) 
                    break;
                if(pls.size()) pls.push(levelEnd);
            } else {
                for(int i = lasti + 1; i < S.size(); ++i) {
                    if(S[i] == tj) {
                        pls.push(i);
                    }
                }
            }
        }
        
        //3.finished
        return pls.size();
    }
};

<br>
Code rewrite at 2013-1-5
重写一次,用了动态规划搞定,时间复杂度是O(S.size() * T.size())

class Solution {
public:
    int numDistinct(string S, string T) {
        if(S.size() < T.size()) return 0;
        if(T.size() == 0) return 0;
        vector > ways (S.size(), vector(T.size(),0));
        //the first column
        ways[0][0] = (S[0] == T[0] ? 1 : 0);
        for(int is = 1; is < S.size(); ++is) {
            ways[is][0] = ways[is-1][0];
            if(T[0] == S[is]) {
                ways[is][0] += 1;
            }
        }
        //the remaining triangle
        for(int it = 1; it < T.size(); ++it) {
            //the item on the diagonal
            ways[it][it] = (S[it] == T[it] ? ways[it-1][it-1] : 0);
            //the items below
            for(int is = it + 1; is < S.size(); ++is) {
                ways[is][it] = ways[is-1][it];
                if(S[is] == T[it]) {
                    ways[is][it] += ways[is-1][it-1];
                }
            }
        }
        return ways[S.size()-1][T.size()-1];
    }
};



上面的代码用了O(S.size() * T.size())的空间,实际上没有必要,只需要2 * S.size()的空间就够了。

class Solution {
public:
    int numDistinct(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(S.size() < T.size()) return 0;
        if(T.size() == 0) return 0;
        int *ways = new int[S.size()];
        int *waysTemp = new int[S.size()];
        //the first charactor for T
        ways[0] = (S[0] == T[0] ? 1 : 0);
        for(int is = 1; is < S.size(); ++is) {
            ways[is] = ways[is-1];
            if(T[0] == S[is]) {
                ways[is] += 1;
            }
        }
        //the remaining charactors in T
        for(int it = 1; it < T.size(); ++it) {
            //the item on the diagonal
            waysTemp[it] = (S[it] == T[it] ? ways[it-1] : 0);
            //the items below
            for(int is = it + 1; is < S.size(); ++is) {
                waysTemp[is] = waysTemp[is-1];
                if(S[is] == T[it]) {
                    waysTemp[is] += ways[is-1];
                }
            }
            int *temp = ways;
            ways = waysTemp;
            waysTemp = temp;
        }
        int ret = ways[S.size()-1];
        delete ways;
        delete waysTemp;
        return ret;
    }
};



code rewrite at 2013-1-14, 36ms pass the large test

/*
Let ways(x,y) denote that from first x characters in S to first y characters in T needs ways(x,y) distinct ways.
then if we knew ways(i,j), i < n, i < m, then 
ways(n,m) = S[n-1] == T[m-1] ? ways(n-1,m-1) + ways(n-1,m) : ways(n-1,m)
ways(x,0) = x; x = 0,...,S.size()
ways(y,y) = S[y-1] == T[y-1] ? ways(y-1,y-1) : 0; y = 1,...,T.size()
*/
class Solution {
public:
    int numDistinct(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(S.size() < T.size()) return 0;
        int *ways = new int[S.size() + 1];
        int *waystemp = new int[S.size() + 1];
        for(int i = 0; i <= S.size(); ++i) {
            ways[i] = 1;
        }
        for(int lent = 1; lent <= T.size(); ++lent) {
            waystemp[lent] = (S[lent-1] == T[lent-1] ? ways[lent-1] : 0);
            for(int lens = lent + 1; lens <= S.size(); ++ lens) {
                waystemp[lens] = waystemp[lens - 1];
                waystemp[lens] += (S[lens-1] == T[lent-1] ? ways[lens-1] : 0);
            }
            int *temp = ways;
            ways = waystemp;
            waystemp = temp;
        }
        int ret = ways[S.size()];
        delete ways;
        delete waystemp;
        return ret;
    }
};

LeetCode题目:Convert Sorted List to Binary Search Tree

问题比上一个难一点,如果是可以用O(n)空间的话,倒是可以开一个数组放上这n个数,然后按上一个问题的解法去做。总体时间O(n),空间O(n)。

不过这题这样出应该不是这个意思。假如不用O(n)空间的话:
可以先数一下一共有多少个节点。O(n)时间。
然后去找到根节点(数数),然后根节点之前是左子树,之后是右子树,并且两个子树的节点个数都是可以直接计算出来的,递归解这个问题就可以了。
那么总体时间复杂度是O(n*logn),空间O(logn)



Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.



代码:114ms过大集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *formTree(ListNode *head, int count) {
        if(count <= 0) return NULL;
        int rootIndex = count / 2;
        ListNode *rootNode = head;
        for(int ir = 0; ir < rootIndex; ++ir) {
            rootNode = rootNode->next;
        }
        TreeNode *root = new TreeNode(rootNode->val);
        root->left = formTree(head,rootIndex);
        root->right = formTree(rootNode->next, count - rootIndex - 1);
        return root;
    }
public:
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        //1. find the node count, takes O(n) time
        int nodeCount = 0;
        for(ListNode *cur = head; cur != NULL; cur = cur->next) {
            ++nodeCount;
        }
        
        //2. form the tree with the middle as the root
        return formTree(head, nodeCount);
    }
};

LeetCode题目:Convert Sorted Array to Binary Search Tree

对排序的数组进行二分查找样式的遍历就行了。



Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.



代码:84ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *sortedArrayToBST(vector &num,int si, int ei) {
        if(si > ei) return NULL;
        int mid = (ei + si) / 2;
        TreeNode *root = new TreeNode(num[mid]);
        root->left = sortedArrayToBST(num,si,mid - 1);
        root->right = sortedArrayToBST(num,mid + 1,ei);
        return root;
    }
    
public:
    TreeNode *sortedArrayToBST(vector &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return sortedArrayToBST(num,0,num.size() - 1);
    }
};

LeetCode题目:Construct Binary Tree from Inorder and Postorder Traversal

这题和上一道题类似,也是首先在postorder中,最后那一个肯定是整棵树的根,然后在inorder中查找这个根,找到之后就能确定左子树和右子树的后序遍历和中序遍历,然后递归求解。



Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.



代码:120ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *buildTree(vector &iorder, int isi, int iei, vector &porder, int psi, int pei) {
        if(iei - isi < 0 || iei - isi != pei - psi) {
            return NULL;
        }
        //the porder[pei] is the root of this tree
        TreeNode *root = new TreeNode(porder[pei]);
        //find the root in the iorder to seperate it into left sub tree and right sub tree
        int riii = -1;//root index in inorder array
        for(int i = isi; i <= iei; ++i) {
            if(iorder[i] == root->val) {
                riii = i;
                break;
            }
        }
        if(riii == -1) return root;//error
        int lnodes = riii - isi;
        //for the left sub tree
        //the isi to riii - 1 in inorder array will be it's inorder traversal
        //and the psi to psi + lnodes - 1 in postorder array will be it's post order traversal
        root->left = buildTree(iorder, isi, riii - 1, porder, psi, psi + lnodes - 1);
        //for the right sub tree is similary to the left
        root->right = buildTree(iorder, riii + 1, iei, porder, psi + lnodes, pei - 1);
        return root;
    }
    TreeNode *buildTree(vector &inorder, vector &postorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return buildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() -1);
    }
};

LeetCode题目:Construct Binary Tree from Preorder and Inorder Traversal

这曾经是一道很难的题目,看来这一阵的锻炼确实是有效果的。


方法是,画一棵树出来,比如:

   1
 /   \
2     3
 \    /
  4  5

这棵树好用,在于其中包含了所有的可能性,(2度,1度(左右),0度节点都有)。
它的preorder是:1,2,4,3,5
他的inorder是:2,4,1,5,3


那么递归的看这个问题,首先preorder的第一个必然是根(1),然后此节点在inorder中的下标是2,那么在inorder中,处于1之前的两个节点2,4是左子树的;反之5,3是右子树的。
针对左子树,2,4就是它的inorder,而在preorder中,除开第一个根,数两个节点的子序列正好是2,4,这是左子树的preorder。这样这个问题就自然变成递归了:
即,其左子树的preorder是(2,4),inorder是(2,4);类似有右子树preorder(3,5),inorder(5,3)。
然后边界情况是某数的preorder和inorder遍历的长度都是1,比如{x},那么这棵树就是以x为值的节点。
这样就可以写出代码了。



Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.



代码:124ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef TreeNode TN;
class Solution {
    TN *buildTree(vector &preorder,int psi,int pei,
                  vector &inorder, int isi, int iei) {
        if(pei - psi < 0 || pei - psi != iei - isi) 
            return NULL;
        //root of sub tree
        TN *root = new TN(preorder[psi]);
        //find this value in inorder to locate the root in inorder
        int riii = -1;//root index in inorder
        for(int itemp = isi; itemp <= iei; ++ itemp) {
            if(inorder[itemp] == root->val) {
                riii = itemp;
                break;
            }
        }
        if(riii != -1) {
            //calculate the nodes count in left tree
            int leftCount = riii - isi;
            TN *left = buildTree(preorder,psi + 1, psi + leftCount, inorder, isi, riii - 1);
            root->left = left;
            TN *right = buildTree(preorder,psi + leftCount + 1,pei, inorder, riii + 1, iei);
            root->right = right;
        }
        return root;
    }
public:
    TreeNode *buildTree(vector &preorder, vector &inorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        TN *root = buildTree(preorder,0,preorder.size() - 1,inorder,0,inorder.size() - 1);
    }
};

LeetCode题目:Binary Tree Zigzag Level Order Traversal

比较简单,广度优先变一下就可以了,用一个bool记录是从左到右还是从右到左,每一层结束就翻转一下。



Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]



代码:28ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector > zigzagLevelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector > ret;
        if(NULL == root) return ret;
        
        queue que;
        que.push(root);
        que.push(NULL);//level end point
        
        bool l2r = true;//left to right
        
        vector level;
        while(true) {
            TreeNode *cur = que.front();
            que.pop();
            if(cur) {
                level.push_back(cur->val);
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            } else {
                if(l2r) {
                    ret.push_back(level);
                } else {
                    vector temp;
                    for(int i = level.size() - 1 ; i >= 0; --i) {
                        temp.push_back(level[i]);
                    }
                    ret.push_back(temp);
                }
                level.erase(level.begin(),level.end());
                l2r = !l2r;
                
                if(que.size() == 0) break;
                que.push(NULL);
            }
        }
        
        return ret;
    }
};

LeetCode题目:Binary Tree Maximum Path Sum

这道题好难,因为在一颗二叉树中有多种情况,这条最长的路径有可能是从某个中间节点直接到某个叶子节点的,也有可能是两条上述路径连接在一个中间节点上(这个中间节点可能是root也可能不是),也有可能只是一个单独的节点。

情况太多导致问题很复杂,不好分析,这题花了我至少两个小时去解决。

一开始从自上而下的方法去想,想到了可以计算出每一个节点到root的最大值,然后最后拼一下最大值,得到整体最大。但是这里假设了路径都是过root的。显然不对。

然后想level优先遍历的话,如果知道了上面的情况,下面一层可解么?陷入死胡同至少30min,gg。

然后想自下而上,如果知道了左右子树的情况,自身的情况能得到么?很快就有了肯定回答。
但是这个solution也相对复杂,针对每个节点需要知道的是:
1.终止在这个节点上(往自己子树走)的最大路径值是多少
2.经过这个节点的最大值是多少?(从左子树走过自己到右子树)
3.不经过此节点的子树中可能获得的最大值是多少?

在知道这三个量之后,问题变得明确可解了。那就是递归,先计算出左右子树的这三个值,然后:
1.终止在此节点的最大路径,首先是自己的值包含进去,然后如果终止在左或右子树的根节点的最大路径值大于0的话,加上这个值。
2.经过这个节点的最大值,很简单了,左右子树的端点最大值加上自己的值。
3.不经过此节点的最大值,直接查看左右子树中的这个值(如果有左右子树的话),还有左右子树的端点最大值。

这样最后就写出一个递归的算法。如何写成循环还没想好。

2013-1-18,更新了一个更简单的办法.

Question: Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

代码:

248ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Maxes{
public:
    int tmax;//max of terminated in self
    int pmax;//max of pass self
    int nmax;//max of non-relative to self
    Maxes() {tmax = pmax = 0; nmax = (1 << (sizeof(int) * 8 - 1));}
    inline int getMax() {
        int m = tmax;
        if(m < pmax) m = pmax;
        if(m < nmax) m = nmax;
        return m;
    }
};
class Solution {
public:
    Maxes maxPath(TreeNode *root) {
        Maxes m;
        if(NULL == root)
            return m;

        Maxes l = maxPath(root->left);
        Maxes r = maxPath(root->right);

        //tmax is the max value which terminated at this node
        //when all of it's children is negative, this is it's value
        //or add the max value terminated at it's children
        m.tmax = max(l.tmax,r.tmax);
        if(m.tmax < 0) m.tmax = 0;
        m.tmax += root->val;

        //pmax is the max value which is pass this node
        //that is it's value terminated at it's children (if have, or zero), add self value
        m.pmax = l.tmax + r.tmax + root->val;

        //nmax is the max value which not including current node
        if(root->left)
            m.nmax = l.getMax();
        if(root->right) {
            int rmax = r.getMax();
            if(m.nmax < rmax) m.nmax = rmax;
        }
        return m;
    }
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        Maxes m = maxPath(root);
        int ma = m.getMax();
        return ma;
    }
};

Code rewrite at 2013-1-18, 266ms pass large set, simpler

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int _curMax;
    //return the max path ending in root
    //and refresh the _curMax with the path sum that go through from left to root to right child.
    int maxWithRoot(TreeNode *root) {
        if(NULL == root) return 0;
        int leftmax = maxWithRoot(root->left);
        int rightmax = maxWithRoot(root->right);

        //the max from left child to right child, accross from root
        int arcmax = root->val;
        if(leftmax > 0) arcmax += leftmax;
        if(rightmax > 0) arcmax += rightmax;
        if(_curMax < arcmax) _curMax = arcmax;

        //the max that end in root
        int pathmax = root->val;
        int submax = std::max(leftmax,rightmax);
        if(submax > 0) pathmax += submax;
        if(_curMax < pathmax) _curMax = pathmax;

        return pathmax;
    }
public:
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        _curMax = INT_MIN;
        maxWithRoot(root);
        return _curMax;
    }
};

LeetCode题目:Binary Tree Level Order Traversal II

和上一题差不多,只不过最后输出的时候颠倒一下,另外:std::list才有push_front(),而std::vector没有这个方法。



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],
]



代码:40ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector > levelOrderBottom(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        list > retTemp;

        queue trace;
        trace.push(root);
        trace.push(NULL);
        
        vector curLevel;
        while(true) {
            TreeNode *cur = trace.front();
            trace.pop();
            if(cur) {
                curLevel.push_back(cur->val);
                if(cur->left) trace.push(cur->left);
                if(cur->right) trace.push(cur->right);
            } else {
                if(curLevel.size()) {
                    retTemp.push_front(curLevel);
                    curLevel.erase(curLevel.begin(),curLevel.end());
                    trace.push(NULL);
                } else {
                    break;
                }
            }
        }
        
        vector > ret;
        for(list >::iterator it = retTemp.begin(); it != retTemp.end(); ++it) {
            ret.push_back(*it);
        }
        return ret;
    }
};

LeetCode题目:Binary Tree Level Order Traversal

题目简单,经典方法。只不过这题需要每一个level单独作为一个vector输出,因此在每一个level结束的时候插入一个NULL标记。每当遇到这个标记,就说明一层已经完全访问了。



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]
]



代码:28ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector > levelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector > ret;
        if(NULL == root) return ret;
        queue trace;
        trace.push(root);
        trace.push(NULL);
        vector levelVals;
        while(true) {
            TreeNode *cur = trace.front();
            trace.pop();
            if(NULL == cur) {
                ret.push_back(levelVals);
                levelVals.erase(levelVals.begin(),levelVals.end());
                if(trace.size())
                    trace.push(NULL);
                else
                    break;
            } else {
                levelVals.push_back(cur->val);
                if(cur->left) trace.push(cur->left);
                if(cur->right) trace.push(cur->right);
            }
        }
        return ret;
    }
};



Code rewrite at 2012-12-22, 24ms pass the large test set

class Solution {
public:
    vector > levelOrder(TreeNode *root) {
        vector > ret;
        
        queue q;
        if(root) {
            q.push(root);
            q.push(NULL);
        }
        
        vector level;
        while(q.size()) {
            TreeNode *cur = q.front();
            q.pop();
            if(cur) {
                level.push_back(cur->val);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            } else {
                ret.push_back(level);
                level.erase(level.begin(),level.end());
                if(q.size()) q.push(NULL);
            }
        }
        
        return ret;
    }
};

LeetCode题目:Best Time to Buy and Sell Stock III,一维动态规划

和前两道题比起来的话,这道题最难了,因为限制了交易次数。
解决问题的途径我想出来的是:既然最多只能完成两笔交易,而且交易之间没有重叠,那么就divide and conquer。
设i从0到n-1,那么针对每一个i,看看在prices的子序列[0,…,i][i,…,n-1]上分别取得的最大利润(第一题)即可。
这样初步一算,时间复杂度是O(n2)。


改进:
改进的方法就是动态规划了,那就是第一步扫描,先计算出子序列[0,…,i]中的最大利润,用一个数组保存下来,那么时间是O(n)。
第二步是逆向扫描,计算子序列[i,…,n-1]上的最大利润,这一步同时就能结合上一步的结果计算最终的最大利润了,这一步也是O(n)。
所以最后算法的复杂度就是O(n)的。



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).



代码:12ms过大集合,一次性bug free,很happy

class Solution {
public:
    int maxProfit(vector &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(prices.size() <= 1)
            return 0;
            
        //stores the max profit in [0, ... , i] subarray in prices
        vector maxEndWith;
        {//build the maxEndWith.
            int lowest = prices[0];
            int maxprofit = 0;
            maxEndWith.push_back(0);
            for(int i = 1; i < prices.size(); ++i) {
                int profit = prices[i] - lowest;
                if(profit > maxprofit) {
                    maxprofit = profit;
                }
                maxEndWith.push_back(maxprofit);
                if(prices[i] < lowest) lowest = prices[i];
            }
        }
        
        int ret = maxEndWith[prices.size() - 1];
        {//reverse to see what is the maxprofit of [i, ... , n-1] subarray in prices
        //and meanwhile calculate the final result
            int highest = prices[prices.size() - 1];
            int maxprofit = 0;
            for(int i = prices.size() - 2; i >= 0; --i) {
                int profit = highest - prices[i];
                if(profit > maxprofit)  maxprofit = profit;
                int finalprofit = maxprofit + maxEndWith[i];
                if(finalprofit > ret) ret = finalprofit;
                if(prices[i] > highest) highest = prices[i];
            }
        }

        return ret;
    }
};

LeetCode题目:Best Time to Buy and Sell Stock II

这个更简单了,题目要求可以多次买卖,但是同一时间只能有一股在手里。
这样就可以在每次上升子序列之前买入,在上升子序列结束的时候卖出。相当于能够获得所有的上升子序列的收益。
而且,对于一个上升子序列,比如:5,1,2,3,4,0 中的1,2,3,4序列来说,对于两种操作方案:
一,在1买入,4卖出;
二,在1买入,2卖出同时买入,3卖出同时买入,4卖出;
这两种操作下,收益是一样的。


所以算法就是:从头到尾扫描prices,如果i比i-1大,那么price[i] – price[i-1]就可以计入最后的收益中。这样扫描一次O(n)就可以获得最大收益了。



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).



代码:44ms过大集合

class Solution {
public:
    int maxProfit(vector &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int p = 0;
        for(int i = 1; i < prices.size() ; ++i) {
            int delta = prices[i] - prices[i-1];
            if(delta > 0 ) {
                p += delta;
            }
        }
        return p;
    }
};

LeetCode题目:Best Time to Buy and Sell Stock

这个很简单,一次扫描完成。只需要找到最大增长即可。
从前往后,用当前价格减去此前最低价格,就是在当前点卖出股票能获得的最高利润。
扫描的过程中更新最大利润和最低价格就行了。
O(n)



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.



代码:52ms过大集合

class Solution {
public:
    int maxProfit(vector &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (prices.size() <= 1)
            return 0;
        int low = prices[0];
        int maxp = 0;
        for(int i = 1; i < prices.size(); ++i) {
            int profit = prices[i] - low;
            if(maxp < profit) maxp = profit;
            if(low > prices[i]) low = prices[i];
        }
        return maxp;
    }
};

LeetCode题目:ZigZag Conversion

直观的算法,写一下不同行数下的例子就能找到规律了。

 nRows = 2
0 2 4 6 ...
1 3 5 7
 nRows = 3
0   4   8  ...
1 3 5 7 9
2   6   10
 nRows = 4
0     6       12 ...
1   5 7    11
2 4   8 10  
3     9

先计算一下每一个zig包含的字符个数,实际上是zigSize = nRows + nRows – 2
然后一行一行的加s中的特定元素就行。
第一行和最后一行都只需要加一个字符,每一个zig,而且在s中的index间隔是zigSize。
中间每一行需要添加两个字符到结果中去。第一个字符同上;第二个字符和前面添加这个字符在s上的inde相差正好是zigSize – 2*ir。ir是行index。



ZigZag Conversion
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.



代码:80ms过大集合

class Solution {
public:
    string convert(string s, int nRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        if(nRows <= 1) return s;
        string ret;
        int zigsize = 2 * nRows - 2;
        for(int i = 0; i < nRows; ++i) {
            for(int base = i; ;base += zigsize) {
                if(base >= s.size())
                    break;
                ret.append(1,s[base]);
                if(i > 0 && i < nRows - 1) {
                    //middle need add ziggggging char
                    int ti = base + zigsize - 2 * i;
                    if(ti < s.size())
                        ret.append(1,s[ti]);
                }
            }
        }
        return ret;
    }
};

LeetCode题目:Word Search,回溯

回溯来解。
在back部分需要增加一段,因为对于word中第一个字符的位置是随意的;后面字符必须和前一个字符匹配位置相邻。



Word Search
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = “ABCCED”, -> returns true,
word = “SEE”, -> returns true,
word = “ABCB”, -> returns false.



代码:284ms过大集合

struct Pos{
    int row;
    int col;
    Pos(int r, int c):row(r),col(c) {;}
};

class Solution {
public:
    bool exist(vector > &board, string word) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rows = board.size();
        if(0 == rows) return false;
        int cols = board[0].size();
        if(0 == cols) return false;
        
        if(0 == word.size()) return false;
        
        vector trace;
        trace.push_back(Pos(0,0));
        bool forward = true;
        while(trace.size() > 0) {
            int curIndex = trace.size() - 1;
            Pos &curPos = trace.back();
            if(forward) {
                //find a child
                if(curIndex >= word.size()) return true;
                char curChar = word[curIndex];
                //check out of board
                if( curPos.row < 0 
                    || curPos.row >= rows 
                    || curPos.col < 0 
                    || curPos.col >= cols ) {
                    forward = false;
                    continue;
                }
                //check repeat
                for(int i = 0; forward && i < trace.size() - 1; ++i) {
                    if(trace[i].row == curPos.row && trace[i].col == curPos.col) {
                        forward = false;
                        break;
                    }
                }
                if(!forward) continue;
                //go on
                if(board[curPos.row][curPos.col] == curChar) {
                    Pos nextPos(curPos.row,curPos.col);
                    --nextPos.row;//position above
                    trace.push_back(nextPos);
                } else {
                    forward = false;
                }
            } else {
                if(trace.size() == 1) {
                    //first char in word ,find next available one
                    if(trace[0].row == rows - 1 && trace[0].col == cols - 1) {
                        //no available
                        trace.pop_back();
                    } else {
                        ++ trace[0].col;
                        if(trace[0].col == cols) {
                            trace[0].col = 0;
                            trace[0].row = trace[0].row + 1;
                        }
                        forward = true;
                    }
                } else {
                    Pos &lastpos = trace[trace.size() - 2];
                    //order as : above, right, down, left
                    if(curPos.col == lastpos.col) {
                        if(curPos.row < lastpos.row) {
                            //above to right
                            curPos.col = lastpos.col + 1;
                        } else {
                            //down to left
                            curPos.col = lastpos.col - 1;
                        }
                        curPos.row = lastpos.row;
                        forward = true;
                    } else {
                        if (curPos.col > lastpos.col) {
                            //right to down
                            curPos.row = lastpos.row + 1;
                            curPos.col = lastpos.col;
                            forward = true;
                        } else {
                            //no available
                            trace.pop_back();
                        }
                    }
                }
            }// end back if
        }//end while
        return false;
    }
};

LeetCode题目:Wildcard Matching

这题有点困难。
一开始用很直观的递归算法:逐个看p字符串的字符,针对不同的可能性,’‘,’?’,普通字符进行处理。但是遇到’‘的时候需要递归。这个算法很容易写出来,小集合过了,但是大集合会超时。

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



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”, “cab”) → false



Final代码:88ms过大集合

<

pre>
class Solution {
public:
//get pattens splited by ‘‘ or continuous ‘‘s
vector getPattens(const char p) {
vector ret;
int ei = 0;
string *s = NULL;
while(true) {
if(p[ei] == ‘
‘ || p[ei] == ‘\0’) {
if(s) {
//patten found
ret.push_back(*s);
delete s;
s = NULL;
}
if(p[ei] == ‘\0’) break;
} else {
if(!s) {
s = new string();
}
s->push_back(p[ei]);
}
++ei;
}
return ret;
}

int matchStr(const char *s, string &pat, int basei, int baseilmt) {
    for(; basei <= baseilmt; ++basei) {
        for(int j = 0; j < pat.size(); ++j) {
            if(pat[j] != '?' && pat[j] != s[basei + j])
                break;
            if(j == pat.size() - 1) {
                return basei;
            }
        }
    }
    return -1;
}

bool isMatch(const char *s, const char *p) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(s == NULL || p == NULL) return false;

    //1. get pattens splited by '*' or continuous '*'s
    vector<string> pattens = getPattens(p);
    if(pattens.size() == 0) {
        if(*p == '*') //p is pure '*'s
            return true;
        else //p is empty
            return *s == '\0';
    }

    //2. match each patten one by one on s
    int slen = strlen(s);
    int plen = strlen(p);
    int sb = 0;
    bool restrictFront = *p != '*';
    bool restrictRear = p[plen-1] != '*';
    for(int pi = 0; pi < pattens.size() ; ++pi) {
        string &pat = pattens[pi];
        int sbl = slen - pat.size();

        if(sbl < sb) return false;

        if(pi == 0 && restrictFront) {
            //first patten may be need to match exactly from 0
            sbl = 0;
        } else if (pi == pattens.size() - 1 && restrictRear) {
            //last patten may be need to match exactly from rear of s
            sb = slen - pat.size();
            sbl = sb;
            //cout<<sb<<","<<sbl<<"|";
        }

        int matchbase = matchStr(s,pat,sb,sbl);
        if(-1 == matchbase) {
            //cout<<"pat:"<<pi<<","<<pat;
            return false;
        }
        else {
            //cout<<sb<<","<<sbl<<","<<pat;
            sb = matchbase + pat.size();
        }
    }
    if(pattens.size() == 1) {
        if (restrictFront && restrictRear) {
            return s[sb] == '\0';
        }
        //cout<<s[sb];
        return true;
    }
    return true;


    for(int i = 0; i < pattens.size(); ++i){
        cout<<pattens[i];
        cout<<"|";
    }
    return false;
}

};



递归代码
这是正确的代码,小集合4ms过了,但是大集合超时。

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        char cs = *s;
        char cp = *p;
        if(cp == '\0') {
            return cs == cp;
        } else if (cp == '?') {
            if (cs == '\0') return false;
            return isMatch(s + 1,p + 1);
        } else if (cp == '*') {
            const char *st = s;
            for(; *st != '\0'; ++st) {
                if (isMatch(st, p+1)) return true;
            }
            return isMatch(st,p+1);
        } else if (cp != cs)
            return false;
        return isMatch(s + 1,p + 1);
    }
};



Code rewrite at 2013-1-23

class Solution {
    bool isMatch(const char *s, const string &p) {
        for(int i = 0; i < p.size(); ++i) {
            char cs = *(s+i);
            if (cs == '\0') return false;
            char cp = p[i];
            if (cp != '?' && cp != cs) return false;
        }
        return true;
    }
    vector splitPatten(const char *p) {
        vector splitp;
        string seg="";
        int ip = 0;
        while(true) {
            char c = *(p + ip);
            if (c == '\0' || c == '*') {
                //a segment found, if seg.size() > 0
                if(seg.size() > 0) {
                    //cout< splitp = splitPatten(p);
        //2.0.
        if(splitp.size() == 0) {
            //all the chararactors in p is *, or, p is empty
            if(strlen(p) == 0)
                return *s == '\0';
            return true;
        }
        //2.determin if the first seg is fix at front of s and the last seg is fix at the rear of s
        bool fixBegin = false,fixEnd = false;
        {
            if(*p!='*') fixBegin = true;
            if(*(p + strlen(p) - 1) != '*') fixEnd = true;
        }
        //3.go through all the patten's segemnts in p, 
        //check them one by one in s, 
        //with the consideration of fixBegin and fixEnd
        int si = 0;
        const int lens = strlen(s);
        for(int i = 0; i < splitp.size(); ++i) {
            string &patseg = splitp[i];
            //the last available start index in s
            int lastsi = lens - patseg.size();
            //match is impossible
            if(lastsi < si) return false;
            int ei = lastsi;
            //if this is the first pattern segment and we must match at the beginning of s
            if(i==0 && fixBegin) ei = si;
            //the similiar situation for last pattern segment
            if(i== splitp.size() - 1 && fixEnd) {
                si = lastsi;
                //the segment must from beginning of s and to ending of s.
                if (i==0 && fixBegin && 0!=si) return false;
            }
            
            bool matched = false;
            for(int iins=si; !matched && iins <= ei; ++iins) {
                matched = isMatch(s + iins,patseg);
                si = iins + patseg.size();
            }
            //there is an mismatch
            if(!matched) return false;
        }
        return true;
    }
};

LeetCode题目:Validate Binary Search Tree

就按照BST的要求进行递归,对于每一个子树,限制它的最大,最小值,如果超过则返回false。
对于根节点,最大最小都不限制;
对于第一层子节点,需要限制单边。(左子树限制最大值小于根,右子树最小值大于根);
再往下的层次需要在父节点的最大最小值限制之下,再满足由于父节点分割造成的进一步限制。

写了一个递归算法,就搞定了。时间上没有多余的计算,只不过如果栈溢出的话,需要改成循环可以解决。



Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.



代码:92ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValid(TreeNode *root, int maxVal, int minVal, bool checkMax, bool checkMin) {
        if(NULL == root) return true;
        if(checkMax && root->val >= maxVal) return false;
        if(checkMin && root->val <= minVal) return false;
        bool leftValid = isValid(root->left, root->val, minVal, true, checkMin);
        if(!leftValid) return false;
        return isValid(root->right, maxVal, root->val, checkMax, true);
    }
    bool isValidBST(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return isValid(root,0,0,false,false);
    }
};

LeetCode题目:Valid Sudoku

神奇了,只检查了每行重复、每列重复和每9宫格重复就过了大测试集合。
难道只要满足每行、每列、每9宫格不重复的数独都有解?



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
A partially filled sudoku which is valid.



代码:28ms过大集合

class Solution {
public:
    bool isValidSudoku(vector > &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rows = board.size();
        if(9 != rows) return false;
        int cols = board[0].size();
        if(9 != cols) return false;
        //1.check duplications in each row
        int dup[10];//hash for 1 to 9
        for(int ir = 0; ir < rows; ++ir) {
            for(int i = 0; i <= 9; ++i)
                dup[i] = 0;
            for(int i = 0; i < 9; ++i){
                char c = board[ir][i];
                if(c == '.')
                    ++dup[0];
                else {
                    int hash = c - '0';
                    if(dup[hash] == 1) {
                        return false;
                    } else {
                        ++dup[hash];
                    }
                }
            }
        }
        //2. check duplications in each cols
        for(int ic = 0; ic < cols; ++ic) {
            for(int i = 0; i <= 9; ++i)
                dup[i] = 0;
            for(int i = 0; i < 9; ++i){
                char c = board[i][ic];
                if(c == '.')
                    ++dup[0];
                else {
                    int hash = c - '0';
                    if(dup[hash] == 1) {
                        return false;
                    } else {
                        ++dup[hash];
                    }
                }
            }
        }
        //3. check duplications in each 3 * 3 grid
        for(int ir = 0; ir < rows; ir += 3) {
            for(int ic = 0; ic < cols; ic += 3) {
                for(int i = 0; i <= 9; ++i)
                    dup[i] = 0;
                for(int iir = 0; iir < 3; ++iir) {
                    for(int iic = 0; iic < 3; ++iic) {
                        char c = board[ir + iir][ic + iic];
                        if(c == '.')
                            ++dup[0];
                        else {
                            int hash = c - '0';
                            if(dup[hash] == 1) {
                                return false;
                            } else {
                                ++dup[hash];
                            }
                        }
                    }
                }
            }
        }
        return true;
    }
};

LeetCode题目:Valid Parentheses

用一个stack解决问题,从头到尾扫描一下,遇到左括号压栈,遇到右括号就将stack的top元素和其配对弹出。如果中间遇到问题不能配对,或者到最后stack不空,就返回false



Valid Parentheses
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.



代码:8ms过大集合

class Solution {
public:
    bool isValid(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        stack lefts;
        for(int i = 0 ; i < s.size() ;++i) {
            char c = s[i];
            if(c == '(' || c == '[' || c == '{') {
                lefts.push(c);
            } else {
                if (lefts.size() == 0) return false;
                char top = lefts.top();
                if (c == ')') {
                    if(top != '(') return false;
                } else if ( c == ']' ) {
                    if(top != '[') return false;
                } else if ( c == '}' ){
                    if(top != '{') return false;
                }
                lefts.pop();
            }
        }
        return lefts.size() == 0;
    }
};

LeetCode题目:Valid Number

从前往后扫描,用一些bool标记状态,其实可以预先画一些状态图出来,就更容易写代码了。



Valid Number
Validate if a given string is numeric.
Some examples:
“0” => true
” 0.1 ” => true
“abc” => false
“1 a” => false
“2e10” => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.



代码:32ms过大集合

class Solution {
public:
    bool isNumber(const char *s) {
        if (s == NULL || s[0] == '\0') return false;
        bool cansign = true;
        bool cane = false;
        bool havee = false;
        bool candot = true;
        bool onlyspace = false;
        bool havenum = false;
        bool numbegin = false;
        while(*s != '\0') {
            char c = *(s++);
            if (c == ' '){
                if (numbegin)
                    onlyspace = true;
                continue;//skip space
            } else if (onlyspace) {
                return false;
            }
            if (c == '+' || c == '-') {
                if(!cansign) return false;
                cansign = false;
                numbegin = true;
                continue;
            }
            if (c == 'e') {
                if(!cane) return false;
                cane = false;
                havenum = false;
                numbegin = true;
                cansign = true;
                havee = true;
                candot = false;
                continue;
            }
            if (c == '.') {
                if(!candot) return false;
                candot = false;
                numbegin = true;
                cansign = false;
                continue;
            }
            if (c >= '0' && c <= '9') {
                havenum = true;
                numbegin = true;
                cansign = false;
                if(!havee) cane = true;
            } else {
                return false;
            }
        }
        return havenum;
    }
};

LeetCode题目:Unique Paths II,二维动态规划

每个cell,如果自身没有障碍的话,可以从上面一个cell或者左边一个cell到达。所以用动态规划来解决很简单:
开一个数组(和输入矩阵的列数等大),记录到达该cell的可能路径个数。
逐行扫描输入矩阵,根据条件计算到达该cell可能的路径个数(只能从上面或者左边)。
最后输出这个数组的最后一个元素即可。

这样做的话,时间复杂度是O(rows * cols),空间复杂度是O(cols)



Unique Paths II
Follow up for “Unique Paths”:
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.

 [
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
 

The total number of unique paths is 2.
Note: m and n will be at most 100.



代码:24ms过大集合

class Solution {
public:
    int uniquePathsWithObstacles(vector > &obstacleGrid) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rows = obstacleGrid.size();
        if(rows == 0) return 0;
        int cols = obstacleGrid[0].size();
        if(cols == 0) return 0;
        int *preways = new int[cols];
        int *ways = new int[cols];
        
        //first row
        preways[0] = 1 - obstacleGrid[0][0];
        for(int i = 1; i  &rowobs = obstacleGrid[ir];
            for(int ic = 0; ic < cols; ++ic) {
                if(rowobs[ic] == 1) {
                    ways[ic] = 0;
                    continue;
                }
                //from cell above
                ways[ic] = preways[ic];
                //from left
                if(ic > 0) {
                    ways[ic] += ways[ic - 1];
                }
            }
            int *temp = preways;
            preways = ways;
            ways = temp;
        }
        return preways[cols-1];
    }
};

LeetCode题目:Unique Paths

只计算个数的话有简单算法,如果是m行,n列的矩阵,机器人从左上走到右下总共需要的步数是n + m – 2,其中向下走的步数是m -1。因此问题变成了在n + m -2个操作中,选择m – 1个时间点向下走,的选择方式有多少种。
那就是:Cm+n-2m-1
程序的话,加上一点trick让其不越界就行了。



Unique Paths
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.



代码:8ms过大集合

class Solution {
public:
    long long factor(int n,int start = 1) {
        long long  ret = 1;
        for(int i = start; i <= n; ++i)
            ret *= i;
        return ret;
    }
    int uniquePaths(int m, int n) {
        int right = n - 1;
        int down = m - 1;
        int total = right + down;
        int ba = max(right,down);
        long long ret = factor(total,ba + 1);
        ret /= factor(total - ba);
        return ret;
    }
};

LeetCode题目:Unique Binary Search Trees II

上一题可以用简单的办法算出了,这道题要输出所有可能的二叉树,就只能一个一个构造了。
写了一个递归的算法,114ms过了大测试集合



Unique Binary Search Trees II
Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.
For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.



代码:114ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode *copyTree(TreeNode *root) {
        if(NULL == root) return NULL;
        TreeNode *croot = new TreeNode(root->val);
        croot->left = copyTree(root->left);
        croot->right = copyTree(root->right);
        return croot;
    }
    vector generateTrees(int startval,int endval) {
        vector ret;
        if(endval < startval) {
            ret.push_back(NULL);
        }
        else {
            for(int rootval = startval; rootval <= endval; ++rootval) {
                vector temp;
                {//push root into ret
                    TreeNode *root = new TreeNode(rootval);
                    temp.push_back(root);
                }
                //process the left subtrees
                vector lefts = generateTrees(startval, rootval - 1);
                int count = temp.size();
                for(int ti = 0; ti < count; ++ti) {
                    TreeNode *root = temp[0];
                    temp.erase(temp.begin());
                    for(int li = 0; li < lefts.size(); ++li) {
                        TreeNode* left = lefts[li];
                        TreeNode *newroot = copyTree(root);
                        newroot->left = left;
                        temp.push_back(newroot);
                    }
                    //if(root) delete root;
                }
                //process the right subtrees
                vector rights = generateTrees(rootval + 1, endval);
                count = temp.size();
                for(int ti = 0; ti < count; ++ ti) {
                    TreeNode *root = temp[0];
                    temp.erase(temp.begin());
                    for(int ri = 0; ri < rights.size(); ++ri) {
                        TreeNode *copyExpand = copyTree(root);
                        copyExpand->right = rights[ri];
                        temp.push_back(copyExpand);
                    }
                    //if(root) delete root;
                }
                for(int i = 0; i < temp.size(); ++i) {
                    ret.push_back(temp[i]);
                }
            }
        }
        return ret;
    }
public:
    vector generateTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return generateTrees(1,n);
    }
};

LeetCode题目:Unique Binary Search Trees,一维动态规划

用一维动态规划解。
Sigma(左边的子树可能状态 * 右边子树可能状态) = 当前个数的nodes形成的BST总数。



Unique Binary Search Trees
Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3



代码:8ms过大集合

class Solution {
public:
    int numTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n <= 1) return n;
        //ways[i] rep. the number of ways with i nodes
        int *ways = new int[n + 1];
        ways[0] = 1;
        ways[1] = 1;
        for(int i = 2 ; i <= n; ++i) {
            ways[i] = 0;
            for(int left = 0; left < i; ++ left) {
                //with number of left noeds in the left sub-tree
                int lways = ways[left];
                int rways = ways[i - left - 1];
                ways[i] += lways * rways;
            }
        }
        int ret = ways[n];
        delete [] ways;
        return ret;
    }
};

LeetCode题目:Two Sum

很直接的算法,时间O(n2)。
如果要改进的话,可以先排序,内层二分来做。不过需要排序的时候记录下下标的变化,因为结果是要返回下标的。
而且,返回结果中的下标是从1开始的。



Two Sum
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

代码:16ms过大集合

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> ret;
        if(numbers.size() <= 1) return ret;
        //find min/max for trim
        int vmin = numbers[0];
        int vmax = numbers[0];
        for(int i = 1; i < numbers.size(); ++i) {
            if(numbers[i] < vmin)
                vmin = numbers[i];
            if(numbers[i] > vmax)
                vmax = numbers[i];
        }
        for(int i0 = 0; i0 < numbers.size() - 1; ++ i0) {
            int v0 = numbers[i0];
            int starget = target - v0;
            if(starget < vmin || starget > vmax) continue;
            for(int i1 = i0 + 1; i1 < numbers.size(); ++ i1) {
                if(numbers[i1] == starget) {
                    ret.push_back(i0 + 1);
                    ret.push_back(i1 + 1);
                    return ret;
                }
            }
        }
        return ret;
    }
};

New C++ solution

// new C++ solution using map updated 2016-04-22
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> valueIndexMap;
        for(int i = 0; i < nums.size(); i++)
            valueIndexMap[nums[i]] = i;
        vector<int> indices;
        for(int i = 0; i < nums.size(); i++) {
            int remain = target - nums[i];
            if(valueIndexMap.find(remain) != valueIndexMap.end() && valueIndexMap[remain] != i){
                indices.push_back(i);
                indices.push_back(valueIndexMap[remain]);
                return indices;
            }
        }
        return indices;
    }
};

new Ruby solution

# ruby solution updated 2016-04-22
def two_sum(nums, target)
    map = {}
    nums.each_with_index{|v,i| map[v] = i}
    nums.each_with_index do |v,i|
        remain = target - v
        if (ri = map[remain]) != nil && i != ri
            return [i, ri]
        end
    end
end

new Java solution

// Java solution update 2016-04-22
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0 ; i < nums.length; i++){
            map.put(nums[i], i);
        }
        int[] result = new int[2];
        for(int i = 0 ; i < nums.length; i++){
            int remain = target - nums[i];
            if(map.containsKey(remain)){
               int ri = map.get(remain);
               if(i != ri){
                    result[0] = i;
                    result[1] = ri;
                    break;
                } 
            }

        }
        return result;
    }
}

new C solution updated 2016-04-22

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int * results = malloc(sizeof(int) * 2);
    bool found = false;
    for(int i = 0 ; i < numsSize && !found; ++i)
        for(int j = i+1 ; j < numsSize && !found; ++j){
            if(nums[i]+nums[j] == target){
                results[0] = i;
                results[1] = j;
                found = true;
            }
        }
    return results;
}

LeetCode题目:Triangle,动态规划

逐行扫描,计算在每一个位置能取得的最小sum,实际上是该元素上面两个能取得的最小sum中最小的那一个sum加上自己的值。
动态规划,只需要开一个数组重复利用就行了。



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.



代码:40ms过大集合

class Solution {
public:
    int minimumTotal(vector > &triangle) {
        int rows = triangle.size();
        if(0 == rows) return 0;
        int *minSums = new int[rows];
        int *temp = new int[rows];
        
        for(int r = 0; r < rows; ++r) {
            vector trow = triangle[r];
            if(trow.size() != r + 1) return 0;//input error occur
            //first should be last 0 add trow[0]
            temp[0] = trow[0] + (r > 0 ? minSums[0] : 0);
            //from 1 to r - 1, the min from above to parants add self
            for(int i = 1; i < r; ++ i) {
                temp[i] = trow[i] + min(minSums[i-1],minSums[i]);
            }
            //last element, just like the first one. only can add self to the last element above.
            if(r > 0)
                temp[r] = trow[r] + minSums[r-1];
            //swap temp with minSums
            int *tswap = temp;
            temp = minSums;
            minSums = tswap;
        }
        
        //scan the minSums, find out the minimum one
        int m = minSums[0];
        for(int i = 1; i < rows; ++i) {
            if(minSums[i] < m)
                m = minSums[i];
        }
        
        delete temp;
        delete minSums;
        return m;
    }
};



Code rewrite at 2012-12-30

class Solution {
public:
    int minimumTotal(vector > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int levels = triangle.size();
        if(levels<=0) return 0;
        vector *psum = new vector(levels,0);
        vector *psumtemp = new vector(levels,0);
        (*psum)[0] = triangle[0][0];
        for(int ilevel = 1; ilevel < levels; ++ilevel) {
            vector &level = triangle[ilevel];
            const int levelsize = level.size();
            //only one path could arrive to the first and last number in a level
            (*psumtemp)[0] = (*psum)[0] + level[0];
            //if (level.size() > 1)
            (*psumtemp)[levelsize - 1] = (*psum)[levelsize - 2] + level[levelsize - 1];
            //there are 2 pathes for the middle numbers.
            for(int ipos = 1; ipos < levelsize - 1; ++ipos) {
                int tsum = (*psum)[ipos] + level[ipos];
                if(tsum > (*psum)[ipos-1] + level[ipos]) {
                    tsum = (*psum)[ipos-1] + level[ipos];
                }
                (*psumtemp)[ipos] = tsum;
            }
            //swap the psum and psumtemp
            vector *ptemp = psum;
            psum = psumtemp;
            psumtemp = ptemp;
        }
        //scan the psum and output the minnimum sum
        int minsum = (*psum)[0];
        for(int i = 1; i < levels; ++i) {
            if(minsum > (*psum)[i])
                minsum = (*psum)[i];
        }
        //clearup
        delete psum;
        delete psumtemp;
        return minsum;
    }
};



Code rewrite at 2013-1-17

class Solution {
public:
    int minimumTotal(vector > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rows = triangle.size();
        if(0 == rows) return 0;//error
        int *sumrow = new int[rows];
        int *sumrowtemp = new int [rows];
        sumrow[0] = triangle[0][0];
        for(int ir = 1; ir < rows; ++ir) {
            vector &trirow = triangle[ir];
            sumrowtemp[0] = sumrow[0] + trirow[0];
            for(int ic = 1; ic < trirow.size(); ++ic) {
                int minsum = sumrow[ic-1];
                if(ic < trirow.size()-1 && sumrow[ic] < minsum) {
                    minsum = sumrow[ic];
                }
                sumrowtemp[ic] = minsum + trirow[ic];
            }
            int *temp = sumrow;
            sumrow = sumrowtemp;
            sumrowtemp = temp;
        }
        int ret = sumrow[0];
        for(int ic = 1; ic < rows; ++ic) {
            if(ret > sumrow[ic]) ret = sumrow[ic];
        }
        delete sumrow;
        delete sumrowtemp;
        return ret;
    }
};

LeetCode题目:Trapping Rain Water

算法很简单,核心思想是:对某个值A[i]来说,能trapped的最多的water取决于在i之前最高的值leftMostHeight[i]和在i右边的最高的值rightMostHeight[i]。(均不包含自身)。如果min(left,right) > A[i],那么在i这个位置上能trapped的water就是min(left,right) – A[i]。

有了这个想法就好办了,第一遍从左到右计算数组leftMostHeight,第二遍从右到左计算rightMostHeight,在第二遍的同时就可以计算出i位置的结果了,而且并不需要开空间来存放rightMostHeight数组。

时间复杂度是O(n),只扫了两遍。



Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!



代码,44ms过大集合

class Solution {
public:
    int trap(int A[], int n) {
        //no way to contain any water
        if(n <= 2) return 0;
        
        //1. first run to calculate the heiest bar on the left of each bar
        int *lmh = new int[n];//for the most height on the left
        lmh[0] = 0;
        int maxh = A[0];
        for(int i = 1; i < n; ++i) {
            lmh[i] = maxh;
            if(maxh < A[i]) maxh = A[i];
        }
        int trapped = 0;
        
        //2. second run from right to left, 
        // caculate the highest bar on the right of each bar
        // and calculate the trapped water simutaniously
        maxh = A[n-1];
        for(int i = n - 2; i > 0; --i) {
            int left = lmh[i];
            int right = maxh;
            int container = min(left,right);
            if(container > A[i]) {
                trapped += container - A[i];
            }
            if(maxh < A[i]) maxh = A[i];
        }
        delete lmh;
        return trapped;
    }
};

LeetCode题目:Text Justification

直观的算法,就是解决临界状况要细心。
算法还可以用一下逻辑改得简洁些:
如果是最后一行或者该行只有一个单词,采用左对齐,不插入多余空格,右边补全空格的方式;
其它情况下,采用两端对齐,插入多余空格在中间的方式。
这样下来应该会简洁一些。



Text Justification
Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ‘ ‘ when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”]
L: 16.
Return the formatted lines as:
[
“This is an”,
“example of text”,
“justification. ”
]
Note: Each word is guaranteed not to exceed L in length.
Corner Cases:
A line other than the last line might contain only one word. What should you do in this case?
In this case, that line should be left-justified.



代码:24ms过大集合

class Solution {
public:
    vector fullJustify(vector &words, int L) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector rslt;
        if(0 == words.size()) return rslt;
        int si = 0, ei = si;
        int len = 0;
        while(true) {
            for(ei = si; ei < words.size(); ++ei) {
                if(len + (ei - si) + words[ei].size() > L) {
                    break;
                }
                len += words[ei].size();
            }
            --ei;
            if(ei < si) ei = si;
            //form the string
            if(si >= ei) {
                //only one word on this line
                string line = words[si];
                line.append(L - line.size(), ' ');
                rslt.push_back(line);
            } else {
                //multiple words on this line
                bool lastline = (ei == (words.size() - 1));
                int spaceBase = (L - len) / (ei - si);
                int bonus = (L - len) - spaceBase * (ei - si);
                if(lastline) {
                    //lastline
                    spaceBase = 1;
                    bonus = 0;
                }
                string line = words[si];
                for(int i = si + 1; i <= ei; ++i) {
                    int space = spaceBase;
                    if(bonus > 0) {
                        ++space;
                        --bonus;
                    }
                    line.append(space,' ');
                    line.append(words[i]);
                }
                if(lastline) {
                    line.append(L - len - ei + si,' ');
                }
                rslt.push_back(line);
            }
            //progress
            si = ei + 1;
            len = 0;
            if(si >= words.size()) break;
        }//end while
        return rslt;
    }
};