Is Subsequence

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

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

Example 1:
s = “abc”, t = “ahbgdc”

Return true.

Example 2:
s = “axc”, t = “ahbgdc”

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Overtime

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) return true;
        
                for (int i = 0; i < t.length() - s.length(); i++) {
                    int res = 0;
                    int cur = i;
                    while (cur < t.length() && res < s.length()) {
                        if (t.charAt(cur) == s.charAt(res)) res++;
        
                        cur++;
        
                        if (res == s.length()) return true;
                    }
                }
        
                return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public boolean isSubsequence(String s, String t) {
        int res = -1;
        for (int i = 0; i < s.length(); i++) {
            res = t.indexOf(s.charAt(i), res + 1);
            if (res == -1) return false;
        }
        return true;
    }
}
/*
执行用时 :1 ms, 在所有 Java 提交中击败了90.09%的用户
内存消耗 :44.2 MB, 在所有 Java 提交中击败了100.00%的用户
*/

Reference
https://leetcode-cn.com/problems/is-subsequence

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 (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int maxProfit(int[] prices) {
        int[] dp = new int[2];

        dp[1] = Integer.MIN_VALUE;

        for (int price : prices) {
            dp[0] = Math.max(dp[0], dp[1] + price);
            dp[1] = Math.max(dp[1], dp[0] - price);
        }
        
        return dp[0];
    }

/*
执行用时 :2 ms, 在所有 Java 提交中击败了26.28%的用户
内存消耗 :42.5 MB, 在所有 Java 提交中击败了5.04%的用户
*/
}

Reference
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/submissions

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

1
/
3

2

Output: [3,1,null,null,2]

3
/
1

2
Example 2:

Input: [3,1,4,null,null,2]

3
/
1 4
/
2

Output: [2,1,4,null,null,3]

2
/
1 4
/
3
Follow up:

A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?

Unsolved

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

class Solution {
  public void inorder(TreeNode root, List<Integer> nums) {
    if (root == null) return;
    inorder(root.left, nums);
    nums.add(root.val);
    inorder(root.right, nums);
  }

  public int[] findTwoSwapped(List<Integer> nums) {
    int n = nums.size();
    int x = -1, y = -1;
    for(int i = 0; i < n - 1; ++i) {
      if (nums.get(i + 1) < nums.get(i)) {
        y = nums.get(i + 1);
        // first swap occurence
        if (x == -1) x = nums.get(i);
        // second swap occurence
        else break;
      }
    }
    return new int[]{x, y};
  }

  public void recover(TreeNode r, int count, int x, int y) {
    if (r != null) {
      if (r.val == x || r.val == y) {
        r.val = r.val == x ? y : x;
        if (--count == 0) return;
      }
      recover(r.left, count, x, y);
      recover(r.right, count, x, y);
    }
  }

  public void recoverTree(TreeNode root) {
    List<Integer> nums = new ArrayList();
    inorder(root, nums);
    int[] swapped = findTwoSwapped(nums);
    recover(root, 2, swapped[0], swapped[1]);
  }
}

Reference
https://leetcode-cn.com/problems/recover-binary-search-tree

不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

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

Unsolved

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

class Solution {
    public List<TreeNode> generateTrees(int n) {

        if (n == 0) return new ArrayList<>();
        return helper(1, n);

    }

    private List<TreeNode> helper(int start, int end) {
        List<TreeNode> res = new ArrayList<>();
        if (start > end) {
            res.add(null);
            return res;
        }
        for (int val = start; val <= end; val++) {
            List<TreeNode> left = helper(start, val - 1);
            List<TreeNode> right = helper(val + 1, end);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(val);
                    root.left = l;
                    root.right = r;
                    res.add(root);
                }
            }
        }
        return res;
    }
}

Reference
https://leetcode-cn.com/problems/unique-binary-search-trees-ii

Binary Tree Inorder Traversal

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

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?

Old

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> stack;
        vector<int> vector;

        while (root != nullptr || !stack.empty()) {
            while (root != nullptr) {
                stack.push(root);
                root = root->left;
            }
            if (!stack.empty()) {
                root = stack.top();
                stack.pop();
                vector.push_back(root->val);
                root = root->right;
            }
        }
        
        return vector;
    }
}

Reference
https://leetcode-cn.com/problems/binary-tree-inorder-traversal