LeetCode selected questions

1. Sequence zigzag traversal of binary tree

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

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

The return zigzag hierarchy traversal is as follows:

[
  [3],
  [20,9],
  [15,7]
]

thinking

To put it bluntly, it's just sequence traversal and stratigraphic inversion.

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();
            n++;//Number of control layers
            for(int i=0;i<len;i++)
            {
                fz=q.front();
                b.push_back(fz->val);
                if(fz->left!=NULL) q.push(fz->left);
                if(fz->right!=NULL) q.push(fz->right);
                q.pop();
            } 
            if((n&1)==1)
            {
                a.push_back(b);
            }
            else
            {
                reverse(b.begin(),b.end());
                a.push_back(b);
            }
            b.clear();
        } 
        return a;
    }

2. Constructing binary tree from preorder traversal and inorder traversal of binary tree

According to the preorder traversal and inorder traversal of a tree, a binary tree is constructed.

be careful:
You can assume that there are no duplicate elements in the tree.

For example, give

preorder = [3,9,20,15,7]
Middle order traversal inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

thinking

For any tree, the form of preorder traversal is always

[root node, [preorder traversal result of left subtree], [preorder traversal result of right subtree]]

That is, the root node is always the first node in the preorder traversal. The form of 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 order traversal, we can know the number of nodes in the left subtree and the right subtree respectively. Since the lengths of preorder traversal and middle order traversal of the same subtree are obviously the same, we can locate all the left and right parentheses in the above form corresponding to the results of preorder traversal.

In this way, we know the pre order traversal and middle order traversal results of the left subtree and the pre order traversal and middle order traversal results of the right subtree. We can recursively construct the left subtree and right subtree, 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 preorder traversal is the root node
        int preorder_root = preorder_left;
        // Locate the root node in the middle order traversal
        int inorder_root = index[preorder[preorder_root]];
        
        // First establish 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;
        // The left subtree is constructed recursively and connected to the root node
        // The elements "size_left_subtree starting from the left boundary + 1" in the preorder traversal correspond to the elements "from the left boundary to the root node location - 1" in the inorder traversal
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // The right subtree is constructed recursively and connected to the root node
        // The element "starting from the left boundary + 1 + number of left subtree nodes to the right boundary" in the preorder traversal corresponds to the element "locating from the root node + 1 to the right boundary" in the preorder traversal
        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();
        // Construct hash mapping 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);
    }
};

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 down or right one step at a time. The robot attempts to reach the lower right corner of the grid (marked "Finish" in the figure below).

How many different paths are there altogether?

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

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
Starting from the upper left corner, there are three paths to the lower right corner.

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

Example 2:

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

Tips:

1 <= m, n <= 100
 The question data ensures that the answer is less than or equal to 2 * 10 ^ 9

Links

[tricks] take different paths on the map

4. Find the K-th smallest element in the binary tree

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

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

Example 1:

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

   3
  / \
 1   4
  \
   2

Output: 1

Example 2:

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

      5
      / \
     3   6
    / \
   2   4
  /
 1

Output: 3

Advanced:
If the binary search tree is often modified (insert / delete operations) and you need to frequently find the k-th smallest value, how would you optimize the kthSmallest function?

Idea:

Traverse the binary tree in middle order and output the K-th value.

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;
    }

5. Search rotation array

Suppose that the array sorted in ascending order rotates at a previously unknown point.

(for example, the array [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2]).

If the given target index exists, it returns a value of - 1.

You can assume that there are no duplicate elements in the array.

The time complexity of your algorithm must be O(log n) level.

Example 1:

Input: num = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: num = [4,5,6,7,0,1,2], target = 3
Output: - 1

Idea:

The problem requires that the time complexity of the algorithm must be O(logn), which suggests that we can use the binary search method.

However, the array itself is not ordered. After rotation, only the parts of the array are ordered. Can we carry out binary search? The answer is yes.

It can be found that when we divide the array into left and right parts from the middle, some of the arrays must be orderly. Take an example. After we separate from the position of 6, the array becomes two parts [4, 5, 6] and [7, 0, 1, 2]. Among them, the array of the left part [4, 5, 6] is orderly, and so are others.

This enlightens us that we can check which part [l, mid] and [mid + 1, r] of the two parts [l, mid] and [mid + 1, r] divided by the current mid are ordered during the conventional binary search, and determine how to change the upper and lower bounds of the binary search according to the ordered part, because we can judge whether the target is in this part according to the ordered part:

If [l, mid - 1] Is an ordered array, and target The size of is satisfied [nums[l],nums[mid]),Then we should narrow the search to [l, mid - 1],Otherwise in [mid + 1, r] Look in the.
If [mid, r] Is an ordered array, and target The size of is satisfied (nums[mid+1],nums[r]],Then we should narrow the search to [mid + 1, r],Otherwise in [l, mid - 1] Look in the.

Code implementation:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = (int)nums.size();
        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;
    }
};

6. Delete the penultimate node of the linked list

Solution: fast move 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 move n first
            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;
}

7. Ring linked list to find the entry point

When the fast and slow pointers meet, put another slow pointer at the head node, and then let the slow pointer in the ring continue to walk, and then meet again, which is the entry point.
prove:

At the first encounter, there is an equation:
2(D+S1) = D+nS2+(n+1)S1
->D+S1 = n(S1+S2)
->D = (n-1)(S1+S2)+S2

In other words, when the fast and slow pointers meet, put another slow pointer at the head node, and then let the slow pointer in the ring continue to walk, and then meet again, that is, the entry point.

8. Symmetric binary tree

The original space complexity of recursion is also O(n). I thought recursion didn't consume space.

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

For example, a binary tree [1,2,2,3,4,4,3] is symmetric.

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

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

    1
   / \
  2   2
   \   \
   3    3

Idea:

If the left subtree and the right subtree of a tree are mirror symmetrical, then the tree is symmetrical.
Therefore, the problem can be transformed into: under what circumstances are two trees mirror each other?

If the following conditions are met at the same time, the two trees mirror each other:
Their two root nodes have the same value
The right subtree of each tree is mirrored and symmetrical with the left subtree of another tree

We can implement such a recursive function to traverse the tree by "synchronously moving" two pointers. At first, the p pointer and q pointer point to the root of the tree, and then when p moves right, q moves left, and when p moves left, q moves right. Check whether the values of the current p and q nodes are equal each time. If they are equal, judge whether the left and right subtrees are symmetrical.

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);
    }
};

Suppose there are n nodes in the tree.

Time complexity: this tree is traversed here, and the progressive time complexity is O(n). 
Space complexity: the space complexity here is related to the stack space used by recursion. The number of recursion layers here does not exceed n,Therefore, the complexity of progressive space is O(n). 

9. The best time to buy and sell stocks

Given an array, its i-th element is the price of a given stock on day I.

If you are allowed to complete only one transaction at most (i.e. buy and sell a stock once), design an algorithm to calculate the maximum profit you can make.

Note: you cannot sell stocks before you buy them.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6). Maximum profit = 6-1 = 5.
Note that the profit cannot be 7-1 = 6, because the selling price needs to be greater than the buying price; At the same time, you can't sell stocks before buying.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: in this case, no transaction is completed, so the maximum profit is 0.

Idea: C + + uses sentry to maintain a monotonous stack.

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

Here we maintain a monotonically increasing stack
Adding a sentinel at the end of the price array (that is, a small element, set to 0 here) is equivalent to marking the closing of the stock market (its role will be clear later)
If the stack is empty or the element on the stack is larger than the element on the top of the stack, directly put it on the stack
If the stack element is smaller than the top element, the stack will be bounced repeatedly until the stack element is larger than the top element or the stack is empty
In each pop-up, we take the difference between the value and the bought value (that is, the bottom of the stack) to maintain a maximum value.

(gray marked as scanned)
① Step 1: the stack is empty. The scan is 7. We can directly enter the stack.

② Step 2: the stack element is 1, which is smaller than the top element. In order to maintain this monotonous stack, we pop up 7. Because it is both the bottom and the top of the stack, we don't need to update our maximum value. Because it is empty after pop-up, we put 1 directly into the stack and we put it directly into the stack.

③ Step 3: the stack element is 5, which is larger than the top element of the stack. We directly stack it

④ Step 4: the stack entry element is 3, which is larger than the top element 5. We directly pop the stack and subtract the bottom element 1 from it (this is the most important. It simulates the transaction, because 5 meets 3 smaller than it. Therefore, even if it encounters a larger element C later, there is C − 3 > C − 5, so it is useless. Pop it up after calculation

⑤ Step 5: the stack element is 6, which is larger than the top element of the stack.

⑥ Step 6: the input element is 4, which is smaller than the top element 6. According to our theory just now, the maximum profit of 6 has been determined after encountering 4. No matter what appreciation happens later, the profit of buying at 4 is obviously higher, so we pop up 6, make a difference with the bottom of the stack (that is, the value we buy), compare it with the maximum value we maintained before, and then update it.

⑦ Step 7: now the role of the sentry is very clear. If there is no sentry, there are still residual elements in our monotone stack that have not been judged (for example, when the price array increases monotonically, max=0 will occur without sentry). Therefore, the role of the sentry is to ensure that every element in the monotone stack is judged. 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); \\ sentry👨‍✈️
        for (int i = 0; i < prices.size(); ++ i){
            while (!St.empty() && St.back() > prices[i]){ \\ Maintain monotone stack📈
                ans = std::max(ans, St.back() - St.front()); \\ Maintenance maximum
                St.pop_back();
            }
            St.emplace_back(prices[i]);
        }

        return ans;
    }
};

10. Count prime

Count the number of all prime numbers less than 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.

Idea:

Optimization: zero the array every time you eliminate it.

Code implementation:

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

    for (int i = 2; i < n; i++) 
        if (isPrim[i]) 
            // The multiple of i can't 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;
}

11. Longest substring without repeated characters (sliding window)

Given a string, please find the length of the longest substring that does not contain duplicate characters.

Example 1:
Enter: "abcabcbb"
Output: 3
Explanation: because the longest substring without repeated characters is "abc", its length is 3.

Example 2:
Enter: "bbbbb"
Output: 1
Explanation: because the longest substring without repeated characters is "b", its length is 1.

Example 3:
Input: "pwwkew"
Output: 3
Explanation: because the longest substring without repeated characters is "wke", its length is 3.
Please note that your answer must be the length of the substring, "pwke" is a substring, not a substring.

Idea:

The main idea of this problem is: sliding window
What is a sliding window?
In fact, it is a queue, such as abcabcbb in the example. Entering this queue (window) meets the requirements for abc. When entering a again, the queue becomes abca, which does not meet the requirements. So, we're going to move this queue!

How to move?
We just need to move out the elements on the left of the queue until the requirements of the topic are met!
Always maintain such a queue, find out the longest length of the queue and 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(); i++){
            while (lookup.find(s[i]) != lookup.end()){
                lookup.erase(s[left]);
                left ++;
            }
            maxStr = max(maxStr,i-left+1);
            lookup.insert(s[i]);
    		}
        return maxStr;
    }
};

12. Color classification

Given an array of n elements including red, white and blue, sort them in place so that the elements of the same color are adjacent and arranged in the order of red, white and blue.
In this question, we use integers 0, 1 and 2 to represent red, white and blue respectively.
be careful:
The sorting function in the code base cannot be used to solve this problem.
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Advanced:
An intuitive solution is to use the two pass scanning algorithm of count sorting.
First, iteratively calculate the number of 0, 1 and 2 elements, and then rewrite the current array according to the order of 0, 1 and 2.
Can you think of a one pass scan algorithm that uses only constant space?

This problem is called the Dutch flag problem
, originally proposed by Edsger W. Dijkstra.
The main idea is to set a color for each number and adjust it according to the order of the colors of the Dutch flag.

We use three pointers (p0, p2 and curr) to track the rightmost boundary of 0, the leftmost boundary of 2 and the currently considered element respectively.

The idea of this solution is to move the curr pointer along the array. If num [curr] = 0, it will be exchanged with num [P0]; If num [curr] = 2, it is interchangeable with num [P2].

class Solution {
public:
/*
Solution to the problem of Dutch tricolor flag
*/
void sortColors(vector& nums) {
//For all IDX < P0: num [IDX < P0] = 0
//curr is the subscript of the currently considered element
int p0 = 0, curr = 0;
//For all IDX > P2: num [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++;
}

}
};

Tags: Algorithm

Posted by rdoylelmt on Mon, 23 May 2022 10:16:49 +0300