LeetCode 117. Populating Next Right Pointers in Each Node II

Sep 9, 2016

题目描述:

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
6
     1
   /  \
  2    3
 / \    \
4   5    7

After calling your function, the tree should look like:

1
2
3
4
5
     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \    \
4-> 5 -> 7 -> NULL

这个问题仍然沿用上一题的思路, 先对一个节点是父节点的左节点还是右节点分类. 然后再细分接下来的情况.

  • 一个节点是父节点的左孩子:
    • 如果父节点有右孩子, 那么next就是右孩子
    • 如果父节点没有右孩子并且next为null, 那么该节点的next也为null
    • 如果父节点next不为null, 那么遍历父节点接下来的每一个next节点, 直到找到一个节点有孩子节点, 这个孩子节点是该节点的next. 如果找不到, 该节点的next节点为null
  • 一个节点是父节点的右孩子
    • 父节点的next为null, 则该节点的next为null
    • 如果父节点next不为null, 那么遍历父节点接下来的每一个next节点, 直到找到一个节点有孩子节点, 这个孩子节点是该节点的next. 如果找不到, 该节点的next节点为null

由于对于每一层节点都是从左往右遍历的, 所以每一个父节点的所有后续next节点在处理孩子节点的时候都必须固定下来, 所以要采取从上到下, 从右到左的顺序来遍历二叉树.

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
/**
 * 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, TreeLinkNode *parent = NULL) {
        if(root == NULL)return;
        if(parent != NULL){
            if(root == parent->left){
                if(parent->right) root->next = parent->right;
                else if(!parent->next){
                    root->next = nullptr;
                }
                else{
                    TreeLinkNode* t = parent->next;
                    while(t && !(t->left || t->right)) t = t->next;
                    if(!t) root->next = nullptr;
                    else root->next = (t->left ? t->left : t->right);
                }
            }else if(root == parent->right){
                if(!parent->next){
                    root->next = nullptr;
                }
                else{
                    TreeLinkNode* t = parent->next;
                    while(t && !(t->left || t->right)) t = t->next;
                    if(!t) root->next = nullptr;
                    else root->next = (t->left ? t->left : t->right);
                }
            }
        }
        connect(root->right, root);
        connect(root->left, root);
    }
};

LeetCode 116. Populating Next Right Pointers in Each Node

Sep 9, 2016

题目描述:

Given a binary tree

1
2
3
4
5
6
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
     1
   /  \
  2    3
 / \  / \
4  5  6  7

After calling your function, the tree should look like:

1
2
3
4
5
     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

给一颗完全二叉树的每一个节点确定它同层中的下一个节点. 规则比较简单:

  • 如果一个节点是父节点的左孩子, 那么它的next就是父节点的右孩子
  • 如果一个节点是父节点的右孩子, 那么分两种情况:
    • 父节点的next为null, 则该节点的next为null
    • 父节点的next不为null, 则该节点的next为父节点next节点的左孩子

为了知道一个节点的父节点, 在函数参数中要同时把节点的父节点传入.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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, TreeLinkNode *parent = NULL) { // 与题目提供的函数原型略有不同S
        if(root == NULL)return;
        if(parent != NULL){
            if(root == parent->left){
                root->next = parent->right;
            }else if(root == parent->right){
                if(parent->next != NULL)root->next = parent->next->left;
                else root->next = NULL;
            }
        }
        connect(root->left, root);
        connect(root->right, root);
    }
};

LeetCode 115. Distinct Subsequences

Sep 8, 2016

题目描述:

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.

这道题第一反应是动态规划, 使用dp[i][j]表示从s[0]到s[i](含, 以下用s[0:i]表示)这个字符串中包含多少个t[0:j]字符串. 但是递推公式不太好想, 所以我先把例子中给出的"rabbbit"和"rabbit"的dp数组写出来:

1
2
3
4
5
6
7
8
  r a b b i t
r 1 0 0 0 0 0
a 1 1 0 0 0 0
b 1 1 1 0 0 0
b 1 1 2 1 0 0
b 1 1 3 3 0 0
i 1 1 3 3 3 0
t 1 1 3 3 3 3

通过观察这个数组我们可以发现, 递推公式可能为:

1
dp[i][j] = (s[i] == t[j]) ? dp[i - 1][j - 1] + dp[i - 1][j] : dp[i - 1][j]

那么为什么会是这个公式呢? 首先, 如果s[i]与t[j]不相等, 那么说明没有增加新的子串, 所以s[0:i]中包含的t[0:j]数量与s[0:i-1]相同. 而如果s[i] == t[j], 那么说明增加了新的子串, 就要在s[0:i-1]中包含t[0:j]的基础上加上s[0:i-1]中包含t[0:j-1]的数量.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<int>> dp(s.length(), vector<int>(t.length(), 0));
        if(s.empty() || t.empty()) return 0;
        if(s[0] == t[0]) dp[0][0] = 1;
        for(int i = 1; i < s.length(); i++){ //初始化第一列
            if(s[i] == t[0]) dp[i][0] = dp[i - 1][0] + 1;
            else dp[i][0] = dp[i - 1][0];
        }
        for(int j = 1; j < t.length(); j++){
            for(int i = j; i < s.length(); i++){ // s的长度一定大于等于t的长度
                if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[s.length() - 1][t.length() - 1];
    }
};

以上的代码的运行效率有问题, 大家都知道受到Cache命中的影响, 遍历二维数组时, 按行列比按列行的效率更高, 所以把行列代表的含义交换一下, 得到按行列遍历的数组. 同时进行一些剪枝和dp初始化的优化.

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
class Solution {
public:
    int numDistinct(string s, string t) {
        // s的长度应该大于等于t长度
        if(s.empty() || t.empty() || s.length() < t.length()) return 0;
        int dp[t.length()][s.length()];
        memset(dp, 0, sizeof(dp));
        if(s[0] == t[0]) dp[0][0] = 1;
        // 记录t中是否有s中不存在的元素
        vector<int> chars(128, 0);
        chars[s[0]]++;
        for(int i = 1; i < s.length(); i++){
            if(s[i] == t[0]) dp[0][i] = dp[0][i - 1] + 1;
            else dp[0][i] = dp[0][i - 1];
            chars[s[i]]++;
        }
        for(int i = 0; i < t.length(); i++){
            // 如果t中含有s中不存在的元素则直接返回0
            if(--chars[t[i]] < 0) return 0;
        }
        
        for(int i = 1; i < t.length(); i++){
            for(int j = i; j < s.length(); j++){
                if(s[j] == t[i]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
                }
                else dp[i][j] = dp[i][j - 1];
            }
        }
        return dp[t.length() - 1][s.length() - 1];
    }
};

LeetCode 114. Flatten Binary Tree to Linked List

Sep 8, 2016

题目描述:

Given a binary tree, flatten it to a linked list in-place.

For example, Given

1
2
3
4
5
6
    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
2
3
4
5
6
7
8
9
10
11
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

题目中其实并没有说清楚怎么flatten的, 但是观察给的例子后可以发现是把一个节点的左子树插到右子树之前, 原来的右子树放到左子树的最右端叶子节点的右子树位置.

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode *p = root;
        while(p){
            if(p->left){
                TreeNode *right = p->right;
                p->right = p->left;
                p->left = nullptr;
                leftNode(p)->right = right;
            }
            p = p->right;
        }
    }
    
    TreeNode* leftNode(TreeNode *root){
        if(!root) return nullptr;
        TreeNode *p = root;
        while(p->right){
            p = p->right;
        }
        return p;
    }
};

LeetCode 113. Path Sum II

Sep 7, 2016

题目描述:

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:

Given the below binary tree and

1
sum = 22

,

1
2
3
4
5
6
7
8
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

return

1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]

与上一题类似, 只不过在DFS的过程中维护一个路径path, 保存从根节点到当前节点的值, 抵达叶子节点并且path中元素的和与sum相等时就把它加到结果中.

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    vector<vector<int>> ret;
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<int> path;
        DFS(root, 0, sum, path);
        return ret;
    }
    
    void DFS(TreeNode *node, int n, int sum, vector<int> &path){
        if(!node){
            return;
        }
        path.push_back(node->val);
        if(!node->left && !node->right){
            if(n + node->val == sum){
                ret.push_back(path);
            }
        }
        else if(!node->left && node->right){
            DFS(node->right, node->val + n, sum, path);
        }
        else if(node->left && !node->right){
            DFS(node->left, node->val + n, sum, path);
        }
        else{
            DFS(node->left, node->val + n, sum, path);
            DFS(node->right, node->val + n, sum, path);
        }
        path.pop_back();
    }
};

LeetCode 112. Path Sum

Sep 7, 2016

题目描述:

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:

Given the below binary tree and

1
sum = 22

,

1
2
3
4
5
6
7
8
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

深度优先搜索就可以了.

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        return DFS(root, 0, sum);
    }
    
    bool DFS(TreeNode *node, int n, int sum){
        if(!node){
            return false;
        }
        if(!node->left && !node->right){
            if(n + node->val == sum)
                return true;
            else
                return false;
        }
        if(!node->left && node->right){
            return DFS(node->right, node->val + n, sum);
        }
        if(node->left && !node->right){
            return DFS(node->left, node->val + n, sum);
        }
        if(node->left && node->right){
            return DFS(node->left, node->val + n, sum) || DFS(node->right, node->val + n, sum);
        }
    }
};

LeetCode 111. Minimum Depth of Binary Tree

Sep 7, 2016

题目描述:

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

DFS/BFS都可以, 但是我觉得大概BFS会快一点, 因为在最坏的情况下DFS需要遍历完所有节点才能知道最短的高度.

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> BFS;
        queue<int> depth;
        BFS.push(root);
        depth.push(1);
        while(!BFS.empty()){
            TreeNode *p = BFS.front();
            int d = depth.front();
            if(!p->left && !p->right){
                return d;
            }
            if(p->left){
                BFS.push(p->left);
                depth.push(d + 1);
            }
            if(p->right){
                BFS.push(p->right);
                depth.push(d + 1);
            }
            BFS.pop();
            depth.pop();
        }
    }
};

LeetCode 110. Balanced Binary Tree

Sep 6, 2016

题目描述:

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

题目中二叉树平衡的定义为: 每个节点的左右子树的高度相差都不超过1. 因此可以用递归的方式依次遍历每个节点同时计算每个节点左右子树的高度. 用一个bool变量来保存是否出现了不平衡的节点.

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        bool re = true;
        height(root, re);
        return re;
    }
    
    int height(TreeNode *node, bool &re){
        if(node == nullptr) return 0;
        int leftHeight = height(node->left, re), rightHeight = height(node->right, re);
        if(abs(leftHeight - rightHeight) > 1) re = false;
        return max(leftHeight, rightHeight) + 1;
    }
};

LeetCode 395. Longest Substring with At Least K Repeating Characters

Sep 6, 2016

题目描述:

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

1
2
3
4
5
6
7
8
Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

1
2
3
4
5
6
7
Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

第一眼看到这道题我是想用动态规划的, 可是凭我的弱鸡DP功底做不出来. 第二眼我又想用双指针, 可是又觉得有超时的危险(暴力双循环必然超时, 我写的双指针复杂度降低不多). 所以我最后采用了分治+递归的方法.

总体思想如下

  1. 先遍历一遍字符串, 记录每个字符的出现次数, 在这一步中同时记录出现大于等于k次的字母个数, 如果根本就没有大于等于k次的字母, 那么可以直接返回0.
  2. 通过出现次数不足k次的字母来把字符串分割成多个子串, 因为在原字符串中出现次数不足k次的字母必然不会出现在结果串中.
  3. 递归的处理每个子串. 递归结束条件为字符串长度不足k.
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
class Solution {
public:
    int longestSubstring(string s, int k) {
        return longestSubstringImpl(s, k, 0, s.length());
    }
    
    int longestSubstringImpl(string &s, int k, int start, int end){
        if(end - start < k) return 0; // 递归结束条件
        vector<int> letters(26, 0);
        int biggerThanK = 0;
        for(int i = start; i < end; i++){ // 记录每个字母出现的次数
            if(++letters[s[i] - 'a'] >= k) biggerThanK++;
        }
        if(biggerThanK == 0) return 0; // 没有出现达到k次的字母
        int l = start, r = l, maxLen = 0;
        while(r < end){
            while(r < end && letters[s[r] - 'a'] >= k){ // 跳过出现次数达到k次的字母
                r++;
            }
            if(r == l){ // r == l说明第一个字母就没有到达k次, 所以处理下一个字母
                l++;
                r++;
            }
            else if(r == end && l == start){
                // 这里比较重要, 如果不单独处理整个字符串都符合
                // 要求的情况的话, 就会出现无穷递归.
                maxLen = max(maxLen, r - l);
            }
            else{
                // 递归处理子串
                maxLen = max(maxLen, longestSubstringImpl(s, k, l, r));
                l = r;
            }
        }
        return maxLen;
    }
};

LeetCode 394. Decode String

Sep 5, 2016

题目描述:

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that kis guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or2[4].

Examples:

1
2
3
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

对一个字符串进行解码, 该字符串的编码规则是这样的重复次数[重复内容], 由于有可能出现嵌套, 所以我使用递归来处理这个字符串.

对于括号匹配来说, 使用栈来确定与相应左括号匹配的右括号. 要注意可能会出现不重复的串, 这时要直接把它加到返回串的后面而不处理重复次数.

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
52
53
54
55
56
57
58
59
class Solution {
	string s;
public:
	string decodeString(string str) {
		s = str;
		return decodeStringImpl(0, s.length());
	}

	string decodeStringImpl(int start, int end) {
		string ret;
		int index = start;
		while(index < end && !isDigit(s[index]) && s[index] != ']'){
		    index++;
		}
		ret += s.substr(start, index - start);
		while (index < end) {
		    if(!isDigit(s[index])){
		        int j = index;
		        while(j < end && !isDigit(s[j])) j++;
		        ret += s.substr(index, j - index);
		        index = j;
		    }
		    else{
    			int leftBracket = getInt(index);
    			int repeat = stoi(s.substr(index, leftBracket - index));
    			int rightBracket = findRightBracket(leftBracket);
    			string s = decodeStringImpl(leftBracket + 1, rightBracket);
    			for (int i = 0; i < repeat; i++) {
    				ret += s;
    			}
    			index = rightBracket + 1;
		    }
		}
		return ret;
	}

	int findRightBracket(int index) {
		vector<int> st;
		st.push_back(index);
		int i = index;
		while (!st.empty() && i < s.length() - 1) {
			i++;
			if (s[i] == '[') st.push_back(i);
			else if (s[i] == ']') st.pop_back();
		}
		return i;
	}

	int getInt(int index) {
		while (index < s.length() && isDigit(s[index])) {
			index++;
		}
		return index;
	}
	
	bool isDigit(char ch){
	    return ch <= '9' && ch >= '0';
	}
};