题目1概览

题解

因为是树的层序遍历，考虑使用广度优先搜索配合队列的使用，每层都打印一行，将本层的全部节点打印到一行，并将下一层全部节点都加入队列，跳出循环的条件是队列变成空，以此类推，就可以分为多行的打印。

算法流程：

• 特例处理：根节点root为空的时候，返回空列表[]；
• 初始化：打印结果res = []，包含根节点的队列queue = [root]
• BFS循环：当队列为空的时候跳出
• • 大小：计算队列的大小也就是当前所在的根节点有多少个左右孩子节点；
• • 新建一个临时列表tmp，用于存储当前层的打印结果；
• • 当前层打印循环：循环次数为当前层的节点个数，也即是队列的长度，也即是上一根节点的左右孩子树；
• • • 出队：队首元素先出，记作node；
• • • 打印：将node->val 添加至 tmp 的尾部；
• • • 添加子节点：若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
• • 将当前层结果 tmp 假如 res，push_back() 即可实现。
• 返回值：返回res即可。

Code

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        /* 根据函数返回值定义存储结果的变量 */
        vector<vector<int>> result;
        /* 定义一个队列用于存储节点的数据 */
        queue<TreeNode*> que;
        /* 判空 */
        if(root != NULL) que.push(root);

        /* 开始层序遍历 */
        while(!que.empty()) {
            /* 计算队列的大小也即有多少个孩子 */
            int size = que.size();
            /* 定义一个临时vector 存储每一层 */
            vector<int> vec;
            /* 层序遍历 */
            for(int i = 0; i < size; i++) {
                /* 获取第一个节点数据 */
                TreeNode* node = que.front();
                que.pop();

                vec.push_back(node->val);
                if(node->left != NULL) que.push(node->left);
                if(node->right != NULL) que.push(node->right);
            }
            /* 将一层的数据保存 */
            result.push_back(vec);
        }
        return result;
    }
};

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

结果

题目2概览

题解

换句话说，就是寻找众数，找众数的几种方法：

1. 哈希表统计法：遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出众数。此方法时间和空间复杂度均为 $O(N)$。
2. 数组排序法：直接用sort()进行排序，排序后，数组的中点就是众数。
3. 摩尔投票法：采用票数正负抵消的思想，为众数，票数+1；不为众数，票数-1；指定当前num为众数，然后进行遍历，遍历到最后的，票数为正的数为众数。

Code

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = 0, votes = 0, count = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        // 验证 x 是否为众数
        for(int num : nums)
            if(num == x) count++;
        return count > nums.size() / 2 ? x : 0; // 当无众数时返回 0
    }
};

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

//找中点法
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort (nums.begin(), nums.end());
        int size = nums.size();
        return nums[size/2];
    }
};
1
2
3
4
5
6
7
8
9

结果

题目3概览

题解

采用快速排序暴力破解。

Code

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 最后一个参数表示我们要找的是下标为k-1的数
        return quickSearch(arr, 0, arr.length - 1, k - 1);
    }

    private int[] quickSearch(int[] nums, int lo, int hi, int k) {
        // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
        int j = partition(nums, lo, hi);
        if (j == k) {
            return Arrays.copyOf(nums, j + 1);
        }
        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
        return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
    }

    // 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
    private int partition(int[] nums, int lo, int hi) {
        int v = nums[lo];
        int i = lo, j = hi + 1;
        while (true) {
            while (++i <= hi && nums[i] < v);
            while (--j >= lo && nums[j] > v);
            if (i >= j) {
                break;
            }
            int t = nums[j];
            nums[j] = nums[i];
            nums[i] = t;
        }
        nums[lo] = nums[j];
        nums[j] = v;
        return j;
    }
}
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
34
35
36
37
38

结果