LeetCode select good questions (5)

1, binary tree sequence zigzag traversal

Given a binary tree, return a zigzag hierarchy traversal of its node values. (that is, the next layer is traversed from left to right, then right to left, and so on, alternating between layers).

For example, given a binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns the zigzag hierarchy traversal as follows:

[[3],
  [20.9],
  [15.7]]Copy the code

Train of thought

Code implementation

vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        vector<vector<int> > a;
        if(root==NULL) return a;
        vector<int> b;
        queue<TreeNode*> q;
        q.push(root);
        int n=0;
        while(! q.empty())
        {
            TreeNode* fz;
            int len=q.size(a); n++;// Control the number of layers
            for(int i=0; i<len; i++) { fz=q.front(a); b.push_back(fz->val);
                if(fz->left! =NULL) q.push(fz->left);
                if(fz->right! =NULL) q.push(fz->right);
                q.pop(a); }if((n&1) = =1)
            {
                a.push_back(b);
            }
            else
            {
                reverse(b.begin(),b.end());
                a.push_back(b);
            }
            b.clear(a); }return a;
    }
Copy the code

2. Construct binary tree from preorder traversal and middle order traversal of binary tree

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Train of thought

For any tree, the form of the preceding traversal is always

[root node, [pre-traversal result of left subtree], [pre-traversal result of right subtree]]

That is, the root node is always the first node in the preceding traversal. And the middle order traversal is always

[[middle-order traversal result of left subtree], root node, [middle-order traversal result of right subtree]]

As long as we locate the root node in the middle traversal, we can know the number of nodes in the left and right subtrees respectively. Since the length of pre-order traversal and middle-order traversal of the same subtree is obviously the same, we can locate all the left and right parentheses in the above form in the result of pre-order traversal.

In this way, we know the results of pre-order traversal and middle-order traversal of the left subtree, as well as the results of pre-order traversal and middle-order traversal of the right subtree. We can construct the left and right subtrees recursively, and then connect the two subtrees to the left and right positions of the root node.

Code implementation

class Solution {
private:
    unordered_map<int.int> index;

public:
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
        
        // The first node in the forward traversal is the root node
        int preorder_root = preorder_left;
        // Locate the root node in the middle traversal
        int inorder_root = index[preorder[preorder_root]];
        
        // Create the root node
        TreeNode* root = new TreeNode(preorder[preorder_root]);
        // Get the number of nodes in the left subtree
        int size_left_subtree = inorder_root - inorder_left;
        // Recursively construct the left subtree and connect it to the root node
        // Size_left_subtree from left +1 corresponds to size_left_subtree from left to root -1
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // Construct the right subtree recursively and connect to the root node
        // Start from left +1+ number of left subtree nodes to right, which corresponds to start from root +1 to right
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size(a);// Construct a hash map to help us quickly locate the root node
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1.0, n - 1); }};Copy the code

3. Different paths

A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below).

The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).

How many different paths are there?

For example, the image above shows a 7 x 3 grid. How many possible paths are there?

Example 1:

Input: m = 3, n = 2 Output: 3 Description: There are three paths to the lower right corner starting from the upper left corner.

1. Right -> right -> down
2. Right -> down -> right
3. Down -> right -> right

Example 2:

Input: m = 7, n = 3 Output: 28

Tip:

1 <= m, n <= 100. The answer is guaranteed to be less than or equal to 2 times 10 to the ninthCopy the code

link

Find the KTH smallest element in the binary tree

Given a binary search tree, write a function kthSmallest to find the kthSmallest element in the tree.

Note: You can assume that k is always valid, 1 ≤ k ≤ the number of binary search tree elements.

Example 1:

Enter: root = [3,1,4,null,2], k = 1

   3
  / \
 1   4
  \
   2
Copy the code

Output: 1.

Example 2:

Enter: root = [5,3,6,2,4,null,null,1], k = 3

      5
      / \
     3   6
    / \
   2   4
  /
 1
Copy the code

Output: 3

Further: If the binary search tree is constantly modified (insert/delete operations) and you need to find the kthSmallest value frequently, how can you optimize kthSmallest function?

Ideas:

Code implementation:

void recursion(TreeNode* root,int& res,int& k)
    {
        if(! root)return;
        
        recursion(root->left,res,k);
        
        k--;
        if(k == 0)
        {
            res = root->val;
            return;
        }
            
        recursion(root->right,res,k);
    }
    
    int kthSmallest(TreeNode* root, int k) {
        int res;
        recursion(root,res,k);
        
        return res;
    }
Copy the code

5. Search the rotation array

Ideas:

The time complexity of the algorithm must be order (logn), which suggests that binary search can be used.

But the array itself is not ordered, the rotation only ensures that part of the array is ordered, this can still be binary search? The answer is yes.

What you can see is that when we split the array down the middle into the left and right, some of the array must be in order. For example, when we split from 6, the array becomes [4, 5, 6] and [7, 0, 1, 2]. The left [4, 5, 6] part of the array is ordered, as is the rest.

This enlightenment allows us to check which part of the two parts [L, mid] and [mid + 1, r] separated by mid is orderly in conventional binary search, and determine how to change the upper and lower bounds of binary search according to the ordered part. Because we can tell if Target is in this section from the ordered part:

If [l, mid-1] is an ordered array, and target size is [nums[L],nums[mid]), then we should narrow the search scope to [L, mid-1], If [mid, r] is an ordered array, and the target size is (nums[mid+1],nums[r]]), then we should narrow the search scope to [mid+1, r]. Otherwise look in [L, mid-1].Copy the code

Code implementation:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = (int)nums.size(a);if(! n)return - 1;
        if (n == 1) return nums[0] == target ? 0 : - 1;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1; }}else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1; }}}return - 1; }};Copy the code

6. Delete the penultimate node of the list

Solution: Fast moves n first

Code implementation

ListNode* removeNthFromEnd(ListNode* head, int n) {
       if(! head)return NULL;
        ListNode* new_head = new ListNode(0);
        new_head->next = head;
        ListNode* slow = new_head, *fast = new_head;
        for(int i = 0; i<n; ++i){//fast first move n
            fast = fast->next;
        }
        if(! fast)return new_head->next;
        while(fast->next){      // Move together
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return new_head->next;
}
Copy the code

7. Circular lists find entry points

Symmetric binary trees

It used to be O(n), so I thought recursion had no space cost.

Given a binary tree, check whether it is mirror – symmetric.

For example, binary trees [1,2,2,3,4,4,3] are symmetric.

    1
   / \
  2   2/ \ \3  4 4  3
Copy the code

But the following [1,2,2,null,3,null,3] is not mirror symmetric:

    1
   / \
  2   2
   \   \
   3    3
Copy the code

Ideas:

Code implementation:

class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        if(! p && ! q)return true;
        if(! p || ! q)return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root); }};Copy the code

Let’s say there are n nodes in the tree.

Time complexity: The tree is traversed here, and the asymptotic time complexity is O(n). Space complexity: The space complexity here is related to the stack space used for recursion, where the number of recursive layers does not exceed N, so the progressive space complexity is O(n).Copy the code

9. The best time to buy and sell stocks

C++ uses sentry to maintain a monotonous stack.

First of all, we need to make it clear that this is a time series, so we cannot simply solve the problem with the maximum and minimum. Here we solve the problem through a typical example: [7,1,5,3,6,4]

Here we maintain a monotonically increasing stack and add a sentinel (a very small element, set to 0 here) to the end of the Pricespricesprices array, which acts as a marker for the closing of the stock market. If the stack is empty or the element added to it is larger than the element at the top of the stack, If the pushed element is smaller than the top element, the stack pops until the pushed element is larger than the top element or empty. At each pop, we maintain a maximum value by taking the difference between the value we bought and the bottom of the stack.

(Gray marks scanned) ① : The first step, the stack is empty, the scanned is 7, we directly push the stack.

② : The second step is to push the element 1, which is smaller than the element at the top of the stack. In order to maintain the monotonous stack, we pop 7, and since it is both the bottom and the top of the stack, we do not need to update our maximum value, and since it is empty after the pop, we push 1 directly to the stack.

③ : Step 3, the push element is 5, which is larger than the top element of the stack, we directly push

(4) : the fourth step, into the stack elements of 3, he is bigger than top of stack elements 5, we directly play the stack, and take his minus 1 bottom of stack elements (this is the most important, to simulate the buying and selling, because 5 met its smaller 3, so even if the encounter greater elements of C, but there are C – 3 C – > 5, so it is useless, after calculating the pop-up it

⑤ : The fifth step, the stack element is 6, larger than the top of the stack element, the stack.

6: Step 6, into the stack elements of 4, 6 small than the top element, we just according to the theory of the after meet 4, 6 have identified the highest profit, because no matter how behind in appreciation, at the time of 4 purchase obviously higher profits So we pop up 6, and compared with the bottom of the stack (that is, we buy value) do bad, Compare it to the maximum we maintained before and update it.

7: The function of the sentry is now clear. If there is no sentry, there are still elements left in the monotone stack (for example, Max =0 if the pricespricesprices array increases monotonically without sentry). So the sentry’s job is to make sure that every element in the monotonic stack is evaluated. So the final image should look like this:

Code implementation:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        vector<int> St;
        prices.emplace_back(- 1); \ \ the sentinel 👨 ✈ ️for (int i = 0; i < prices.size(a); ++ i){while(! St.empty() && St.back() > prices[I]){📈 ans = STD ::max(ans, St.back() - St.front()); \\ Maintain maximum St.pop_back(a); } St.emplace_back(prices[i]);
        }

        returnans; }};Copy the code

10. Count primes

Count the number of primes less than the non-negative integer n.

Example:

Input: 10 Output: 4 Explanation: There are four prime numbers less than 10. They are 2, 3, 5, and 7.

Ideas:

Code implementation:

int countPrimes(int n) {
    boolean[] isPrim = new boolean[n];
    // Initialize all arrays to true
    Arrays.fill(isPrim, true);

    for (int i = 2; i < n; i++) 
        if (isPrim[i]) 
            // Multiples of I cannot be prime
            for (int j = 2 * i; j < n; j += i) 
                    isPrim[j] = false;
    
    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrim[i]) count++;
    
    return count;
}
Copy the code

11. The largest string without repeating characters (sliding window)

Ideas:

What is a sliding window? In fact, it is a queue, such as abCABcbb in our example. Entering this queue (window) satisfies the requirements of the problem. When entering A, the queue becomes ABCA, which does not satisfy the requirements. So, we’re going to move this queue!

How to move? We just have to move the left side of the queue out until we satisfy the problem! Always maintain this queue, find the maximum length of the queue, find the solution! Time complexity: O(n)

Code implementation:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() = =0) return 0;
        unordered_set<char> lookup;
        int maxStr = 0;
        int left = 0;
        for(int i = 0; i < s.size(a); i++){while (lookup.find(s[i]) ! = lookup.end()){
                lookup.erase(s[left]);
                left ++;
            }
            maxStr = max(maxStr,i-left+1);
            lookup.insert(s[i]);
    		}
        returnmaxStr; }};Copy the code

12. Color classification

Given an array of n red, white, and blue elements, sort them in place so that the elements of the same color are adjacent and sorted in red, white, and blue order. In this case, we used integers 0, 1, and 2 to represent red, white, and blue, respectively. Note: You cannot solve this problem using collation functions in the code base. Example: input: [2,0,2,1,1,0] output: [0,0,1,1,2,2] advanced: an intuitive solution is to use a counting sort two-pass scan algorithm. First, iterate over the number of 0, 1, and 2 elements, and then rewrite the current array in order of 0, 1, and 2. Can you come up with a one-pass scan algorithm that uses only constant space?

This question is known as the Dutch flag question and was first proposed by Edsger W. Dijkstra. The main idea is to give each number a color and adjust it in the order of the colors of the Dutch flag.

We use three Pointers (P0, P2, and curr) to track the right-most boundary of 0, the left-most boundary of 2, and the element under consideration, respectively.

If nums[curr] = 0, swap it with nums[p0]. If nums[curr] = 2, then nums[p2] is interchanged.

Class Solution {public: void sortColors(vector& nums) {// For all idx < p0: Int p0 = 0, curr = 0; nums[idx < p0] = 0; // for all idx > p2: nums[idx > p2] = 2 int p2 = nums.size() -1;

while (curr <= p2) {
  if (nums[curr] == 0) {
    swap(nums[curr++], nums[p0++]);
  }
  else if (nums[curr] == 2) {
    swap(nums[curr], nums[p2--]);
  }
  else curr++;
}
Copy the code

}};