Haiyang Yu's Blog

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

1
2
3

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

1
2
3

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

1
2

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

解法完全与 leetcode 105 相同

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() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        unordered_map<int, vector<int>::iterator> mp;
        for(vector<int>::iterator it = inorder.begin(); it != inorder.end(); ++it)
            mp.insert({*it,it});
        return buildTree(mp, postorder.begin(), postorder.end(), inorder.begin(), inorder.end());
    }
private:
    TreeNode* buildTree(const unordered_map<int, vector<int>::iterator>& mp, vector<int>::iterator postorder_begin, vector<int>::iterator postorder_end, vector<int>::iterator inorder_begin, vector<int>::iterator inorder_end)
    {
        if(postorder_begin == postorder_end || inorder_begin == inorder_end)
            return nullptr;
        vector<int>::iterator inorder_parentNode= mp.find(*(postorder_end - 1)) -> second;
        int leftTreeNums = inorder_parentNode - inorder_begin;
        int rightTreeNums = inorder_end - inorder_parentNode - 1;
        TreeNode* res = new TreeNode(*inorder_parentNode);
        res->left = buildTree(mp, postorder_begin, postorder_begin + leftTreeNums, inorder_begin, inorder_parentNode);
        res->right = buildTree(mp, postorder_end - 1 - rightTreeNums, postorder_end - 1, inorder_parentNode + 1, inorder_end);
        return res;
    }
};

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

1
2

Input: 123
Output: 321

Example 2:

1
2

Input: -123
Output: -321

Example 3:

1
2

Input: 120
Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

1
2

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

1
2

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Follow up:

• This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
• Would this affect the run-time complexity? How and why?

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

1
2
3
4
5

Given nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

1
2

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

• A rather straight forward solution is a two-pass algorithm using counting sort.
  First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
• Could you come up with a one-pass algorithm using only constant space?

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

Note:

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

Example:

1
2
3
4
5

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

Constraints:

• -10^9 <= nums1[i], nums2[i] <= 10^9
• nums1.length == m + n
• nums2.length == n

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.

Example 1:

1
2
3
4
5
6
7
8
9
10
11

Input:
matrix = [
  [1,2,3,4],
  [5,1,2,3],
  [9,5,1,2]
]
Output: True
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

Example 2:

1
2
3
4
5
6
7
8

Input:
matrix = [
  [1,2],
  [2,2]
]
Output: False
Explanation:
The diagonal "[1, 2]" has different elements.

Note:

1. matrix will be a 2D array of integers.
2. matrix will have a number of rows and columns in range [1, 20].
3. matrix[i][j] will be integers in range [0, 99].

Follow up:

1. What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
2. What if the matrix is so large that you can only load up a partial row into the memory at once?

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

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

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

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

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Follow up:

• A straight forward solution using O(m**n) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?