内容

1. 排序 - order by
   1. 升序 - asc (默认)
   2. 降序 - desc
2. 分组 - group by

排序

格式如下：

1

SELECT * FROM tablename ORDER BY 字段1,字段2,... [ASC(default) | DESC];

其中，ORDER BY后面的条件是优先级规则。先比照字段1，若相同则比照字段2，以此类推；其次，后面的ASC表示升序排列，是默认选项，如果欲按照降序排列则需指明DESC。

排序查询性能分析

1
2

SELECT * FROM user ORDER BY age;
EXPLAIN SELECT * FROM user ORDER BY age;

explain之后发现rows=5，如果单纯地进行排序而不加任何条件，将会进行整表查询。

type为ALL，意为整表查询，以前我们用带索引的查询此处为const，表示常量时间，此处的ALL则代表复杂度较高；Extra为Using filesort，这个标志意味着，此查询涉及到磁盘IO和外排序，将严重影响性能。

外排序的意思就是，有时磁盘的数据量很大，无法全部装到内存中处理，一般会采用n路归并排序思想，这将会涉及很多磁盘IO，效率低下。

再来看一个。

1

EXPLAIN SELECT * FROM user ORDER BY name;

explain发现即使按照字段name排序，结果还是与上面的效果一致。

再来一个。

1

EXPLAIN SELECT name FROM user ORDER BY name;

这次我们没有查按name排序结果后的所有字段，而是只查了字段name。

explain发现，变化显著。

首先type变为index；key变为name；最后，Extra变为Using index。

再试一个。

1

EXPLAIN SELECT age FROM user ORDER BY age;

explain发现，并不是说按啥排序并且只查啥的话性能就高。我们发现按age排序，只查age的话Extra仍是Using filesort。

结论就是：order by的性能不仅与待排序的字段是否有索引有关，还与select选择的列字段有关系。这与主索引树、辅助索引树有关，也就是聚集索引和非聚集索引的搜索过程有关，也涉及到回表问题。

分组

按照字段分组，字段内容相同的放在一组。

1

SELECT * FROM user;

1

SELECT DISTINCT age FROM user;

1

SELECT age FROM user GROUP BY age;

常用语句

分组并显示该组记录的条数

1

SELECT age,COUNT(age) AS number FROM user GROUP BY age;#AS可省略

分组后条件筛选 - HAVING

1

SELECT age,COUNT(age) number FROM user GROUP BY age HAVING age>20;

也可以分组前条件筛选 - where

1

SELECT age,COUNT(age) number FROM user WHERE age>20 GROUP BY age;

多字段分组

1

SELECT age,sex FROM user GROUP BY age,sex;

这个语句将会把age和sex同时一样的记录分组。

1

SELECT age,sex,COUNT(*) FROM user GROUP BY age,sex;

count(*)相当于求的是记录的行数。

与排序结合

1

SELECT age,sex,COUNT(*) FROM user GROUP BY age,sex ORDER BY age;

性能分析

首先我们先确定一下此表的结构属性。再用Explain进行性能分析。

1
2

DESC user;
EXPLAIN SELECT age FROM user GROUP BY age;

desc发现，id有主键索引，name有唯一性索引。其他的age、sex无索引。

explain发现，Extra中为Using temporary; Using filesort。说明此分组查询需要：产生临时表+使用外排序。效率极差。

实际上group by也会进行类似order by的排序。分组查询是先把分组以后的数据放到临时表中，然后在临时表中进行排序。由于age没有索引，所以需要使用外排序。

试试按name分组。

1

EXPLAIN SELECT name FROM user GROUP BY name;

explain发现，Extra为Using index。变化是很显著的。所以GROUP BY后面加索引也是非常有必要的。

练习

某银行代缴话费主流水表（bank_bill）结构：

题目：1）统计表中缴费的总笔数和总金额；2）给出一个SQL，按网点和日期统计每个网点每天的营业额，并按照营业额进行倒序排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

CREATE TABLE bank_bill(
    serno BIGINT UNSIGNED PRIMARY KEY NOT NULL AUTO_INCREMENT,
    date DATE NOT NULL,
    accno VARCHAR(100) NOT NULL,
    name VARCHAR(50) NOT NULL,
    amount DECIMAL(10,1) NOT NULL,
    brno VARCHAR(150) NOT NULL
);
INSERT INTO bank_bill VALUES
('101000','2022-3-1','111','zhang',100,'高新区支行'),
('101001','2022-3-1','222','liu',200,'碑林区支行'),
('101002','2022-3-1','333','gao',300,'高新区支行'),
('101003','2022-3-1','444','lian',150,'雁塔区支行'),
('101004','2022-3-1','555','lan',360,'雁塔区支行'),
('101005','2022-3-1','666','wang',300,'碑林区支行'),
('101006','2022-3-2','777','wei',500,'碑林区支行'),
('101007','2022-3-2','888','yao',50,'碑林区支行'),
('101008','2022-3-2','111','zhang',100,'高新区支行'),
('101009','2022-3-2','222','liu',200,'雁塔区支行'),
('101010','2022-3-3','333','gao',300,'高新区支行'),
('101011','2022-3-3','444','lian',150,'雁塔区支行'),
('101012','2022-3-3','555','lan',360,'雁塔区支行'),
('101013','2022-3-3','666','wang',300,'碑林区支行');

1）总笔数、总金额：

1

SELECT COUNT(serno),SUM(amount) FROM bank_bill;

2）按网点和日期统计每天营业额，倒序。

1

SELECT brno,date,sum(amount) AS total FROM bank_bill GROUP BY brno,date ORDER BY brno,total DESC;

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

1
2
3
4

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

1
2
3
4
5

输入：[2,7,9,3,1]
输出：12
解释：
    偷窃1号房屋(金额=2),偷窃3号房屋(金额=9)，接着偷窃5号房屋(金额=1)。
    偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

1
2

1 <= nums.length <= 100
0 <= nums[i] <= 400

代码

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

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> ar;
        ar.reserve(nums.size()+1);
        ar[0] = 0;
        ar[1] = nums[0];
        int max = ar[1];
        for(int i = 2; i<=nums.size(); ++i)
        {
            ar[i] = std::max(ar[i-2]+nums[i-1],ar[i-1]);
            if(ar[i]>max)max = ar[i];
        }
        return max;
    }
};

打家劫舍2

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

1
2
3

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

1
2
3
4

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

1
2

输入：nums = [1,2,3]
输出：3

提示：

1
2

1 <= nums.length <= 100
0 <= nums[i] <= 1000

题解

这道题是打家劫舍的进阶，和初级版的不同之处是，这道题中的房屋是首尾相连的，第一间房屋和最后一间房屋相邻，因此第一间房屋和最后一间房屋不能在同一晚上偷窃。

和其相似，这道题也可以使用动态规划解决。建议首先了解动态规划的思想。

首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。

注意到当房屋数量不超过两间时，最多只能偷窃一间房屋，因此不需要考虑首尾相连的问题。如果房屋数量大于两间，就必须考虑首尾相连的问题，第一间房屋和最后一间房屋不能同时偷窃。

如何才能保证第一间房屋和最后一间房屋不同时偷窃呢？如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。

假设数组$nums$的长度为$n$。如果不偷窃最后一间房屋，则偷窃房屋的下标范围是$[0, n-2]$；如果不偷窃第一间房屋，则偷窃房屋的下标范围是$[1,n−1]$。在确定偷窃房屋的下标范围之后，即可用第1题的方法解决。对于两段下标范围分别计算可以偷窃到的最高总金额，其中的最大值即为在$n$间房屋中可以偷窃到的最高总金额。

假设偷窃房屋的下标范围是$[start,end]$，用$dp[i]$表示在下标范围$[start,i]$内可以偷窃到的最高总金额，那么就有如下的状态转移方程：

$dp[i]=max(dp[i−2]+nums[i],dp[i−1])$

边界条件为：

$$\begin{cases} \textit{dp}[\textit{start}] = \textit{nums}[\textit{start}] & 只有一间房屋，则偷窃该房屋 \\ \textit{dp}[\textit{start}+1] = \max(\textit{nums}[\textit{start}], \textit{nums}[\textit{start}+1]) & 只有两间房屋，偷窃其中金额较高的房屋 \end{cases}$$

计算得到$dp[end]$即为下标范围$[start,end]$内可以偷窃到的最高总金额。

分别取$(start,end)=(0,n−2)$和$(start,end)=(1,n−1)$进行计算，取两个$dp[end]$中的最大值，即可得到最终结果。

根据上述思路，可以得到时间复杂度$O(n)$和空间复杂度$O(n)$的实现。

考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额，将空间复杂度降到$O(1)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int robRange(vector<int>& nums, int start, int end) {
        int first = nums[start], second = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

    int rob(vector<int>& nums) {
        int length = nums.size();
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return max(nums[0], nums[1]);
        }
        return max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }
};

打家劫舍3

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为root。

除了root之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

给定二叉树的root。返回在不触动警报的情况下，小偷能够盗取的最高金额 。

示例 1:

1
2
3

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

1
2
3

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

• 树的节点数在 [1, 104] 范围内
• 0 <= Node.val <= 104

题解

思路与算法

简化一下这个问题：一棵二叉树，树上的每个点都有对应的权值，每个点有两种状态（选中和不选中），问在不能同时选中有父子关系的点的情况下，能选中的点的最大权值和是多少。

我们可以用$f(o)$表示选择$o$节点的情况下，$o$节点的子树上被选择的节点的最大权值和；$g(o)$表示不选择$o$节点的情况下，$o$节点的子树上被选择的节点的最大权值和；$l$和$r$代表$o$的左右孩子。

• 当$o$被选中时，$o$的左右孩子都不能被选中，故$o$被选中情况下子树上被选中点的最大权值和为$l$和$r$不被选中的最大权值和相加，即$f(o)=g(l)+g(r)$。
• 当$o$不被选中时，$o$的左右孩子可以被选中，也可以不被选中。对于$o$的某个具体的孩子$x$，它对$o$的贡献是$x$被选中和不被选中情况下权值和的较大值。故$g(o)=max\{f(l),g(l)\}+max\{f(r),g(r)\}$。

至此，我们可以用哈希表来存$f$和$g$的函数值，用深度优先搜索的办法后序遍历这棵二叉树，我们就可以得到每一个节点的$f$和$g$。根节点的$f$和$g$的最大值就是我们要找的答案。

我们不难给出这样的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    unordered_map <TreeNode*, int> f, g;

    void dfs(TreeNode* node) {
        if (!node) {
            return;
        }
        dfs(node->left);
        dfs(node->right);
        f[node] = node->val + g[node->left] + g[node->right];
        g[node] = max(f[node->left], g[node->left]) + max(f[node->right], g[node->right]);
    }

    int rob(TreeNode* root) {
        dfs(root);
        return max(f[root], g[root]);
    }
};

假设二叉树的节点个数为$n$。

我们可以看出，以上的算法对二叉树做了一次后序遍历，时间复杂度是$O(n)$；由于递归会使用到栈空间，空间代价是$O(n)$，哈希表的空间代价也是$O(n)$，故空间复杂度也是$O(n)$。

我们可以做一个小小的优化，我们发现无论是$f(o)$还是$g(o)$，他们最终的值只和$f(l)$、$g(l)$、$f(r)$、$g(r)$有关，所以对于每个节点，我们只关心它的孩子节点们的$f$和$g$是多少。我们可以设计一个结构，表示某个节点的$f$和$g$值，在每次递归返回的时候，都把这个点对应的$f$和$g$返回给上一级调用，这样可以省去哈希表的空间。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

struct SubtreeStatus {
    int selected;
    int notSelected;
};

class Solution {
public:
    SubtreeStatus dfs(TreeNode* node) {
        if (!node) {
            return {0, 0};
        }
        auto l = dfs(node->left);
        auto r = dfs(node->right);
        int selected = node->val + l.notSelected + r.notSelected;
        int notSelected = max(l.selected, l.notSelected) + max(r.selected, r.notSelected);
        return {selected, notSelected};
    }

    int rob(TreeNode* root) {
        auto rootStatus = dfs(root);
        return max(rootStatus.selected, rootStatus.notSelected);
    }
};

复杂度分析

时间复杂度：$O(n)$。上文中已分析。

空间复杂度：$O(n)$。虽然优化过的版本省去了哈希表的空间，但是栈空间的使用代价依旧是$O(n)$，故空间复杂度不变。