Weakly Contest 169

题目

Weakly Contest 169

题目一

5295. Find N Unique Integers Sum up to Zero

Given an integer n, return any array containing n unique integers such that they add up to 0.

Example 1:

Input: n = 5
Output: [-7,-1,1,3,4]
Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].

Example 2:

Input: n = 3
Output: [-1,0,1]
Example 3:

Input: n = 1
Output: [0]

Constraints:

1 <= n <= 1000

解题报告

理解题意

• 这是一道简单题
• 给定一个数，求数组
• 要求数组的所有元素和位0

思路

• 给的数有可能为奇数、也有可能为偶数
• 如果是奇数：从0开始向左右拓展，最后加上0即可
• 如果为偶数：从0开始向左右拓展

代码

class Solution {
public:
    vector<int> sumZero(int n) {
        vector<int> ans;
        if (n % 2 != 0) ans.push_back(0);
        for (int i = 1; i <= n / 2; i++) {
            ans.push_back(i);
            ans.push_back(-i);
        }
        return ans;
    }
};

题目二

5296. All Elements in Two Binary Search Trees My SubmissionsBack to Contest

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]
Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]
Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]
Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]
Example 5:


Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]


Constraints:

Each tree has at most 5000 nodes.
Each node's value is between [-10^5, 10^5].

解题报告

理解题意

• 这是一道中档难度题
• 给定两个二叉排序树，要求返回一个包含所有元素并且是递增顺序的列表

思路

• 给定的两个二叉搜索树有可能为空
• 二叉搜索树中序遍历即为递增排序
• 遍历两个二叉搜索树，然后对归并排序，时间复杂度为 \(\mathcal{O(max(m,n))}\)

代码

class Solution {
public:
  vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
    function<void(TreeNode*, vector<int>&)> inorder = [&](TreeNode* root, vector<int>& t) {
      if (!root) return;
      inorder(root->left, t);
      t.push_back(root->val);
      inorder(root->right, t);
    };
    vector<int> t1;
    vector<int> t2;
    inorder(root1, t1);
    inorder(root2, t2);
    vector<int> m;
    std::merge(begin(t1), end(t1), begin(t2),end(t2), std::back_inserter(m));
    return m;
  }
};