leetcode 11.02-11.08

2020-11-06

1356 根据数字二进制下1的数目排序
1305 两棵二叉搜索树的所有元素

1356. 根据数字二进制下1的数目排序

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：先算这个数字的二进制有多少个1，这个可以通过n&(n-1)算出来，之后按照要求排序即可，比较简单。

AC代码：

class Solution {
public:
    static int getOneCount(int n) {
        int count = 0;
        while (n) {
            n &= (n - 1);
            count++;
        }
        return count;
    }

    static bool cmp(const int &a, const int &b) {
        int acount = getOneCount(a);
        int bcount = getOneCount(b);
        if (acount == bcount) return a < b;
        else return acount < bcount;
    }

    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), cmp);
        return arr;
    }
};

python不知道怎么写，看了下题解里的代码

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        return sorted(arr, key=lambda x:(bin(x).count("1"), x))

作者：luanhz
链接：https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits/solution/python3-yong-sortednei-zhi-han-shu-by-luanhz/

1305. 两棵二叉搜索树的所有元素

给你 root1 和 root2 这两棵二叉搜索树。

请你返回一个列表，其中包含两棵树中的所有整数并按升序排序。.

示例 1：

输入：root1 = [2,1,4], root2 = [1,0,3]
输出：[0,1,1,2,3,4]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：先用中序遍历，得到两个搜索树的数组，这个数组已经是从小到大排好序的，之后再merge这两个有序数组即可。

AC代码：

class Solution {
public:
    void InOrder(TreeNode* root, vector<int>& vec) {
        if (!root) return;
        InOrder(root->left, vec);
        vec.push_back(root->val);
        InOrder(root->right, vec);
    }

    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> vec1, vec2;
        InOrder(root1, vec1);
        InOrder(root2, vec2);
        vector<int> ret;
        int i = 0, j = 0, len1 = vec1.size(), len2 = vec2.size();
        while (i < len1 && j < len2) {
            if (vec1[i] < vec2[j]) {
                ret.push_back(vec1[i]);
                i++;
            } else {
                ret.push_back(vec2[j]);
                j++;
            }
        }
        for (; i < len1; i++) {
            ret.push_back(vec1[i]);
        }
        for (; j < len2; j++) {
            ret.push_back(vec2[j]);
        }

        return ret;
    }
};