zkkKillua's Blog
0%

发表于 更新于 分类于

预备知识

首先需要了解“各组得分最高的员工”要如何求解，参考这篇文章：
如何查找各组得分最高的员工？以“部门工资最高的员工”为例。

类比”184.部门工资最高的员工“，可以考虑找出每个分组的工资前三高的值，然后通过子查询或者是连接这个临时表找出各组工资前三高的员工。

但实际上，各组前三高的工资并不能像各组最高的工资一样直接group by就能求出，所以这个方法并没有想象中那么简单。

前N高的含义

阅读全文 »

发表于 分类于

1. 递归+回溯

类似于求各种组合，选择->递归选择之后的元素->回溯。
为了避免重复计算，在每次递归时将数组加入答案中即可，不需要每个数组都是从头开始计算。
时间O(n*2^n)，空间O(n)递归栈。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);

        return ans;
    }
private:
    void dfs(vector<int>& nums, int begin) {
        ans.push_back(subAns);

        int n = nums.size();
        for (int i = begin; i < n; i++) {
            subAns.push_back(nums[i]);
            dfs(nums, i + 1);
            subAns.pop_back();
        }
    }
    vector<int> subAns;
    vector<vector<int>> ans;
};

2. 迭代

首先记录空集，然后在此基础上每次向后追加新元素。
如：[] -> [], [1] -> [], [1], [2], [1,2] -> [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]

阅读全文 »

发表于 更新于 分类于

预备知识

首先需要掌握的是查找所有人中得分最高的员工。

如果只查最高分的话，select max(score) from table就足够了。而如果还需要查出相关人员的信息，则需要进行一定的调整。

1. 子查询

一种查询方式是使用子查询，首先查找出所有人中最高的得分，然后扫描整个表，查找分数等于最高分的人。

阅读全文 »

发表于 分类于

1. salary >

通过子查询找出员工的老板，然后select出salary高的员工。
这个方法的缺点是对于每个员工，都要执行一次子查询，速度慢。 

1
2
3
select Name as Employee
from Employee as e
where e.Salary > (select Salary from Employee where Id = e.ManagerId);

2. 内连接

根据Id和ManagerId相等进行自身的内连接，另外还可以附加上salary高的条件。

阅读全文 »

发表于 分类于

名次实际上就是计算比当前元素大的值的个数，要求名次之间没有间隔，加个distinct即可。
灵活使用as重命名。 

1
2
3
select Score, (select count(distinct Score) from Scores where Score >= s.Score) as `Rank`
from Score as s
order by Score desc;

发表于 分类于

1. 找出最大值，再从小于最大值的值中找出最大值

1
2
3
select max(Salary) as SecondHighestSalary
from Employee
where Salary < (select max(Salary) from Employee)

这种方法的优点是如果存在第二大的，则一定能返回；如果不存在，则会返回null。
缺点是难以处理第3, 4, 5…大的数据。

2. limit与offset

limit可以限制结果的条数，offset是跟limit连用的，可以限制limit开始的位置。
如数据为1,2,3,4,5，limit 2获得的是1,2，而如果limit 2 offset 1返回的就是2，3，开始limit的位置向后偏移了1位。
另外，limit m offset n可以写成limit n, m
如果offset超出了数据范围，则不会报错，结果会得到空集，代表0条记录，而不是结果为null。

阅读全文 »

发表于 分类于

1. 递归

递归求解左叶子的和，直接在最小的树（2层）中定位到左叶子，而不是递归到只剩一个节点，因为这样无法判断左右。
时间O(n)，空间O(n). 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == nullptr)
            return 0;
        else if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr)
            return root->left->val + sumOfLeftLeaves(root->right);
        else
            return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
};

2. 迭代

使用层次遍历，逐个判断是否为左叶子。
时间O(n)，空间O(n)。

阅读全文 »

发表于 分类于

1. 回溯

类似的题目是46.全排列，数组中不包含可重复数字，所以直接对于每一位遍历每一个，选择然后回溯不选择。
而这道题目的数组中包含重复数字，因此如果按照上述方法，会出现重复排列。
如： 

1
2
3
4
5
6
   /   |   \  
  1    1    2      位置1 
 /\   /\    /\  
1  2  1 2   1 1    位置2  
|  |  | |   | |  
2  1  2 1   1 1    位置3

出现重复排列的原因是，对于当前位置，已经选择过的数字在之后又被重新选择了（但选择的不是同一个元素，只是它们的值相等）
因此避免重复的方法就是，在当前位置，避免选择之前已经选择过的数字。

想象在当前位置，第一次选择某个数字，则这个数字一定是所有相等的数字中，第一个在数组中未被选择的，选择它并置vis为true。
在获得当前位置为这个数字得到的所有排列之后，当前位置的数字被重新选择，并将之前元素的vis置为false。
如果选择到的元素还是相等的数字，则之后的排列一定是已经获得过的，并且可以发现它不是数组的相等数字中第一个未被选择的。
因此算法是，先将数组排序，将相等的元素放在一起，然后dfs，选择元素时只选择前一个相等元素被选择过的。
时间O(n*n!)，空间O(n)。

阅读全文 »

发表于 更新于 分类于

1. 递归

先交换左右子节点，然后再递归反转左右子树。
时间O(n)，空间O(n)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root != nullptr) {
            TreeNode* temp = root->left;
            root->left = root->right;
            root->right = temp;
            invertTree(root->left);
            invertTree(root->right);
        }
        
        return root;
    }
};

发表于 更新于 分类于

相关

  1. 二叉树的前序遍历：144
  2. 二叉树的中序遍历：94
  3. N叉树的前序遍历：589
  4. N叉树的后序遍历：590

1. 递归

左右根
时间O(n)，空间O(n)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        postorderTraversal(ans, root);
        return ans;
    }
private:
    void postorderTraversal(vector<int>& ans, TreeNode* root) {
        if (root == nullptr)
            return;
        postorderTraversal(ans, root->left);
        postorderTraversal(ans, root->right);
        ans.push_back(root->val);
    }
};
阅读全文 »