LeetCode 94. Binary Tree Inorder Traversal

Aug 22, 2016

题目描述:

Given a binary tree, return the inorder traversal of its nodes’ values.

For example: Given binary tree [1,null,2,3],

1
2
3
4
5
6
1
 \
  2
 /
3

return [1,3,2].

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

返回一个树的中序遍历序列, 既然题目要求不用递归用迭代, 那么就可以使用栈来模拟递归. 因为使用栈来模拟无法直到栈顶的节点的左子树有没有访问过, 所以还要同时记录每个节点的状态. 我用-1表示未访问左子树, 0表示已访问左子树未访问右子树, 1表示左右子树都已经访问过.

一开始我用vector来作为栈使用, 运行时间4ms, 查看discuss后换用deque运行时间变为0ms. vector在分配的内存不够的情况下的扩充操作真的开销很大.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * 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<int> inorderTraversal(TreeNode *root) {
        deque<TreeNode*> path;
        deque<int> nodeState;
        vector<int> ret;
        if(root == NULL) return ret;
        
        path.push_back(root);
        nodeState.push_back(-1);
        
        TreeNode *node;
        while(!path.empty()){
            node = path.back();
            if(nodeState.back() == 1){
                path.pop_back();
                nodeState.pop_back();
            }
            else if(node->left && nodeState.back() == -1){
                nodeState.back() = 0;
                path.push_back(node->left);
                nodeState.push_back(-1);
            }
            else if(!node->left && nodeState.back() == -1){
                nodeState.back() = 0;
            }
            else if(node->right && nodeState.back() == 0){
                ret.push_back(node->val);
                nodeState.back() = 1;
                path.push_back(node->right);
                nodeState.push_back(-1);
            }
            else{
                ret.push_back(node->val);
                nodeState.back() = 1;
            }
            
        }

        return ret;
    }
};

安装YCM中遇到的问题

Aug 22, 2016

说到VIM的代码补全, YouCompleteMe算是一个非常有名的插件了, 只不过由于它提供的功能已经大大超过了一个文本编辑器的功能, 所以安装起来相当复杂. 在这里记录自己在安装过程中遇到的问题, 安装步骤参考官方手册: http://valloric.github.io/YouCompleteMe/

操作系统Ubuntu 14.04

YouCompleteMe unavailable: requires Vim compiled with Python (2.6+ or 3.3+) support

当前的VIM版本不支持Python脚本, 我通过安装vim-nox解决.

编译ycm_core library时提示’stdexcept’ file not found

通过sudo apt-get install clang安装clang.

运行时提示: The ycmd server SHUT DOWN (restart with ‘:YcmRestartServer’). YCM core library compiled for Python 2 but loaded in Python 3. Set the ‘g:ycm_server_python_interpreter’ option to a Python 2 interpreter path.

在vimrc中加入let g:ycm_server_python_interpreter='/usr/bin/python'来指定python2.x的程序路径.

LeetCode 93. Restore IP Addresses

Aug 21, 2016

题目描述:

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example: Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

返回从一个字符串中可以得到多少个合法的IP地址, 使用回溯法遍历所有可能的组合. 由于最多只能有四个数字组成IP地址, 所以可以用四重循环来实现.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        int p = 0;
        vector<string> re;
        if(s.length() > 12 || s.length() < 4) return re;
        string a, b, c, d;
        for(int i = 1; i <= 3 && i <= s.size() - 3; i++){
            a = s.substr(0, i);
            if(!checkValid(a)) continue;
            for(int j = 1; j <= 3 && i + j <= s.size() - 2; j++){
                b = s.substr(i, j);
                if(!checkValid(b)) continue;
                for(int k = 1; k <= 3 && i + j + k <= s.size() - 1; k++){
                    c = s.substr(i + j, k);
                    if(!checkValid(c)) continue;
                    for(int l = 1; l <= 3 && i + j + k + l <= s.size(); l++){
                        if(i + j + k + l != s.size())
                            continue;
                        d = s.substr(i + j + k, l);
                        if(checkValid(d)){
                            string t;
                            t = a + "." + b + "." + c + "." + d;
                            re.push_back(t);
                        }
                    }
                }
            }
        }
        return re;
    }
    
    bool checkValid(string s){
        if(s[0] == '0' && s.size() != 1)
            return false;
        int n = std::stoi(s);
        return n > 255 ? false : true;
    }
};

LeetCode 92. Reverse Linked List II

Aug 21, 2016

题目描述:

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

在只遍历一次并且不使用额外存储空间的情况下反转单向链表中第m个节点到第n个节点中的节点. 这道题目要求只遍历一次并且不使用额外空间, 那么就要用两个指针来记录当前节点与前一节点, 对于m与n之间的节点, 将当前节点指向前一节点. 第m-1个节点和第n+1个节点在最后处理.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode *start, *end, *p = head, *prev = nullptr, *startPrev = nullptr;
        int i = 0;
        while(p != nullptr){ // 查找翻转开始的节点
            i++;
            if(i == m){
                start = p;
                startPrev = prev;
                break;
            }
            prev = p;
            p = p->next;
        }
        
        p = start;
        ListNode *pp = p->next;
        
        while(i != n){ // 翻转节点
            ListNode *tmp = pp->next;
            pp->next = p;
            p = pp;
            pp = tmp;
            i++;
        }
        
        start->next = pp; // 翻转后的头结点
        if(startPrev){ // 判断是不是从第一个节点开始翻转
            startPrev->next = p;
            return head;
        }
        else
            return p;
    }
};

LeetCode 91. Decode Ways

Aug 20, 2016

题目描述:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

1
2
3
4
5
'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

动态规划, 最后一个字母可以是一位数字或者两位数字. 在最后一位不是0时可以是一位数字, 在倒数第二位为1, 或倒数第二位为2且最后一位小于等于6时可以为两位数字, 解码的不同方法数量为这两种情况之和.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int numDecodings(string s) {
        if(s.empty()) return 0;
        if(s[0] == '0') return 0;
        int num[2] = {1, 0};
        for(int i = 1; i < s.size(); i++){
            int one;
            if(s[i] != '0')
                one = num[0] + num[1];
            else
                one = 0;
                
            int two = 0;
            if(s[i - 1] == '1'){
                two = num[0];
            }
            else if(s[i - 1] == '2' && s[i] <= '6'){
                two = num[0];
            }
            num[0] = one;
            num[1] = two;
        }
        return num[0] + num[1];
    }
};

LeetCode 90. Subsets II

Aug 19, 2016

题目描述:

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example, If nums = [1,2,2], a solution is:

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

返回一个包含重复元素的集合的所有子集, 要求不能重复. 获得子集的思路都是使用回溯法, 如果不考虑重复问题, 那么整个的实现过程可以分为两步:

  1. 实现从nums中获得n个元素的所有情况函数, 使用递归, 即先取一个元素, 然后从之后的数组中再取n-1个元素.
  2. 从nums中取得1个到nums.size()个元素

对于去除重复的情况, 在选择元素的时候跳过之后的与该元素相等的元素就可以避免重复, 为此, 要先对nums排序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    vector<vector<int>> ret;
    int len;
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> path;
        ret.push_back(path);
        len = nums.size();
        for(int i = 1; i <= len; i++){
            subsetWithN(nums, 0, i, path);
        }
        return ret;
    }
    
  	// 从nums中从start开始取得n个元素并放入ret中
    void subsetWithN(vector<int> &nums, int start, int n, vector<int> &path){
        if(n == 0){
            ret.push_back(path);
            return;
        }
        for(int i = start; i <= len - n; i++){
            path.push_back(nums[i]);
            subsetWithN(nums, i + 1, n - 1, path); // 递归调用
            path.pop_back();
            while(i + 1 <= len - n && nums[i] == nums[i + 1]){
                i++;
            }
        }
    }
};

LeetCode 89. Gray Code

Aug 19, 2016

题目描述:

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

1
2
3
4
5
00 - 0
01 - 1
11 - 3
10 - 2

Note: For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

计算Gray code, 两个数的二进制表示只有一位不同, 则这两个数为gray code. 这个题有多个可能的解, 但是LeetCode只判断一种正确解, 就是每次变换尽可能低位的二进制位.

变换一个数中的某一位可以通过位运算实现, 所以主要问题就在如何判断一个数是否已经出现, 我使用unordered_set来保存已经选出来的gray code. 因为测试数据只有12组, 所以也可以使用一个2^12 + 1大小的数组来保存数字有没有出现过.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ret = {0};
        int bits = 0;
        unordered_set<int> codes;
        codes.insert(0);
        int i = 0;
        while(i < n){
            int tmpBits = bits ^ (1 << i);
            if(codes.count(tmpBits)){
                i++;
            }
            else{
                codes.insert(tmpBits);
                ret.push_back(tmpBits);
                bits = tmpBits;
                i = 0;
            }
        }
        return ret;
    }
};

LeetCode 88. Merge Sorted Array

Aug 19, 2016

题目描述:

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

合并两个有序数组, 合并的结果放在第一个数组中, 数组长度通过函数参数给出, 所以不能使用size()成员函数来获得数组长度.

使用另一个数组nums3来保存原来nums1的元素, 然后再逐个比较nums2和nums3中的元素大小, 放入nums1中.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> nums3;
        for(int i = 0; i < m; i++){
            nums3.push_back(nums1[i]);
        }
        int p = m + n - 1;
        while(!nums2.empty() || !nums3.empty()){
            if(nums2.empty()){
                nums1[p--] = nums3.back();
                nums3.pop_back();
            }
            else if(nums3.empty()){
                nums1[p--] = nums2.back();
                nums2.pop_back();
            }
            else if(nums2.back() > nums3.back()){
                nums1[p--] = nums2.back();
                nums2.pop_back();
            }
            else{
                nums1[p--] = nums3.back();
                nums3.pop_back();
            }
        }
    }
};

LeetCode 87. Scramble String

Aug 18, 2016

题目描述:

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

1
2
3
4
5
6
7
8
    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

1
2
3
4
5
6
7
8
    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

1
2
3
4
5
6
7
8
    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

看完这道题, 首先想到的是使用递归, 但是思维惯性让我觉得递归可能超时, 所以按照tag中的动态规划方法来做, 我是使用了三维数组来进行动态规划, 有四重循环, 所以可能还有优化空间. dp[i][j][k]表示s1[i]和s2[j]开始的长度为k的子串是不是scramble的, 最后要返回的结果是dp[0][0][s1.length()], 所以i和j要从大到小遍历.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    bool isScramble(string s1, string s2) {
        if(s1.length() != s2.length()) return false;
        int len = s1.length();
        vector<vector<vector<int>>> dp(len, vector<vector<int>>(len, vector<int>(len + 1, 0)));
        
        for(int i = 0; i < len; i++){
            for(int j = 0; j < len; j++){
                if(s1[i] == s2[j]){
                    dp[i][j][1] = 1;
                }
            }
        }
        
        for(int i = len - 1; i >= 0; i--){
            for(int j = len - 1; j >= 0; j--){
                for(int k = 2; i + k <= len && j + k <= len; k++){
                    for(int r = 1; r < k && !dp[i][j][k]; r++){
                        dp[i][j][k] = (dp[i][j][r] && dp[i + r][j + r][k - r]) || (dp[i][j + k - r][r] && dp[i + r][j][k - r]);
                    }
                }
            }
        }

        return dp[0][0][len];
    }
};

但是这个方法速度并不是很理想, 比较快的方法反而是递归+剪枝, 在递归前先判断字符串中字母数量是不是相同, 如果不相同则可以直接返回false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool isScramble(string s1, string s2) {
        if(s1.length() != s2.length()) return false;
        return isScrambleImpl(s1, s2, 0, 0, s1.length());
    }
    
    bool isScrambleImpl(string &s1, string &s2, int start1, int start2, int len){
        vector<int> charTimes(26, 0);
        for(int i = start1; i < start1 + len; i++){
            charTimes[s1[i] - 'a']++;
        }
        int flag  = true;
        for(int i = start2; i < start2 + len; i++){
            charTimes[s2[i] - 'a']--;
            if(charTimes[s2[i] - 'a'] < 0){
                flag = false;
                break;
            }
        }
        if(!flag) return false;
        if(len == 1 && len == 1) return true; // 只有一个字母并且相同
        for(int i = 1; i < len; i++){
            if((isScrambleImpl(s1, s2, start1, start2, i) && isScrambleImpl(s1, s2, start1 + i, start2 + i, len - i))
                || (isScrambleImpl(s1, s2, start1, start2 + len - i, i) && isScrambleImpl(s1, s2, start1 + i, start2, len - i))){
                    return true;
                }
        }
        return false;
    }
};

LeetCode 86. Partition List

Aug 17, 2016

题目描述:

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.

使用两个临时的链表分别保存小于x和大于等于x的值, 最后再把它们连接到一起.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *less = new ListNode(0), *greater = new ListNode(0), *p1 = less, *p2 = greater, *p = head;
        while(p){
            if(p->val < x){
                p1->next = new ListNode(p->val);
                p1 = p1->next;
            }
            else{
                p2->next = new ListNode(p->val);
                p2 = p2->next;
            }
            p = p->next;
        }
        p1->next = greater->next;
        return less->next;
    }
};