练习题（2024/4/13）

1长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续

子数组

 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

思路1暴力两层for循环：暴力循环的思路是通过遍历所有可能的子数组来找到和大于或等于目标值 target 的最小子数组。具体的做法是对于数组的每一个元素，以它为起始，计算所有可能的子数组和，并找到满足条件的最小子数组。

代码：

class Solution {
public:
    int minSubArrayLen(int s, std::vector<int>& nums) {
        int result = INT32_MAX; // 最终的结果
        int sum = 0; // 子序列的数值之和
        int subLength = 0; // 子序列的长度
        for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
            sum = 0;
            for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                sum += nums[j];
                if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                    subLength = j - i + 1; // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

滑动窗口思路2：

滑动窗口是一种经典的解决连续子数组或子字符串问题的方法。其基本思想是维护一个窗口，通过移动窗口的起始位置和结束位置来寻找满足特定条件的子数组或子字符串。

在解决给定数组和目标值的问题中，可以使用滑动窗口的思想来找到满足条件的最小长度子数组。

具体步骤如下：

1. 初始化窗口的左右边界，初始时窗口不包含任何元素，长度为0。
2. 移动右边界，直到满足窗口内元素的和大于等于目标值，同时记录当前窗口的长度。
3. 缩小窗口，移动左边界，尽量减小窗口的长度，直到不满足条件为止。在此过程中，记录满足条件的最小长度。
4. 重复步骤2和3，直到遍历完整个数组。

代码：

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

2螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

思路：

1. 初始化一个空的 n x n 矩阵，用于存放结果。
2. 定义四个变量，分别表示当前要填入的元素值、当前填入元素的行、当前填入元素的列、以及当前层的边界。
3. 不断循环，直到所有位置都填满为止：
   • 从左到右填充当前层的上边界，行不变，列递增。
   • 从上到下填充当前层的右边界，列不变，行递增。
   • 从右到左填充当前层的下边界，行不变，列递减。
   • 从下到上填充当前层的左边界，列不变，行递减。
   • 每完成一圈，缩小边界范围。
4. 返回生成的矩阵。

代码：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        // 初始化结果矩阵
        vector<vector<int>> res(n, vector<int>(n, 0));

        // 定义边界
        int up = 0, down = n - 1;
        int left = 0, right = n - 1;

        int num = 1; // 用于填充矩阵的数字

        // 填充矩阵
        while (num <= n * n) {
            // 从左到右填充上边界
            for (int j = left; j <= right; j++)
                res[up][j] = num++;
            up++; // 上边界向下移动一行

            // 从上到下填充右边界
            for (int j = up; j <= down; j++)
                res[j][right] = num++;
            right--; // 右边界向左移动一列

            // 从右到左填充下边界
            for (int j = right; j >= left; j--)
                res[down][j] = num++;
            down--; // 下边界向上移动一行

            // 从下到上填充左边界
            for (int j = down; j >= up; j--)
                res[j][left] = num++;
            left++; // 左边界向右移动一列
        }

        return res;
    }
};

3 产品销售分析 III

销售表 Sales：

+-------------+-------+
| Column Name | Type  |
+-------------+-------+
| sale_id     | int   |
| product_id  | int   |
| year        | int   |
| quantity    | int   |
| price       | int   |
+-------------+-------+
(sale_id, year) 是这张表的主键（具有唯一值的列的组合）。
product_id 是产品表的外键（reference 列）。
这张表的每一行都表示：编号 product_id 的产品在某一年的销售额。
请注意，价格是按每单位计的。

产品表 Product：

+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| product_id   | int     |
| product_name | varchar |
+--------------+---------+
product_id 是这张表的主键（具有唯一值的列）。
这张表的每一行都标识：每个产品的 id 和 产品名称。

编写解决方案，选出每个售出过的产品 第一年 销售的 产品 id、年份、数量 和 价格。

结果表中的条目可以按 任意顺序 排列。

结果格式如下例所示：

示例 1：

输入：
Sales 表：
+---------+------------+------+----------+-------+
| sale_id | product_id | year | quantity | price |
+---------+------------+------+----------+-------+ 
| 1       | 100        | 2008 | 10       | 5000  |
| 2       | 100        | 2009 | 12       | 5000  |
| 7       | 200        | 2011 | 15       | 9000  |
+---------+------------+------+----------+-------+
Product 表：
+------------+--------------+
| product_id | product_name |
+------------+--------------+
| 100        | Nokia        |
| 200        | Apple        |
| 300        | Samsung      |
+------------+--------------+
输出：
+------------+------------+----------+-------+
| product_id | first_year | quantity | price |
+------------+------------+----------+-------+ 
| 100        | 2008       | 10       | 5000  |
| 200        | 2011       | 15       | 9000  |
+------------+------------+----------+-------+

思路：使用子查询来选择每个产品的第一年销售数据，并通过将产品 ID 和年份作为子查询结果的筛选条件来检索相应的销售数量和价格。在子查询中找到每个产品的第一年销售数据（即最小年份），然后将其与销售表 Sales 进行连接。连接条件是销售表中的 product_id 和 year 必须与子查询中的 product_id 和 first_sale_year 匹配，以检索出相应的产品 ID、第一年、销售数量和价格信息。

代码：

select 
    product_id, 
    year as first_year, 
    quantity, 
    price
from sales
where (product_id, year) in
(select product_id, min(year)
from sales 
group by product_id)

4项目员工 I

项目表 Project： 

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| project_id  | int     |
| employee_id | int     |
+-------------+---------+
主键为 (project_id, employee_id)。
employee_id 是员工表 Employee 表的外键。

员工表 Employee：

+------------------+---------+
| Column Name      | Type    |
+------------------+---------+
| employee_id      | int     |
| name             | varchar |
| experience_years | int     |
+------------------+---------+
主键是 employee_id。

请写一个 SQL 语句，查询每一个项目中员工的 平均 工作年限，精确到小数点后两位。

查询结果的格式如下：

Project 表：
+-------------+-------------+
| project_id  | employee_id |
+-------------+-------------+
| 1           | 1           |
| 1           | 2           |
| 1           | 3           |
| 2           | 1           |
| 2           | 4           |
+-------------+-------------+

Employee 表：
+-------------+--------+------------------+
| employee_id | name   | experience_years |
+-------------+--------+------------------+
| 1           | Khaled | 3                |
| 2           | Ali    | 2                |
| 3           | John   | 1                |
| 4           | Doe    | 2                |
+-------------+--------+------------------+

Result 表：
+-------------+---------------+
| project_id  | average_years |
+-------------+---------------+
| 1           | 2.00          |
| 2           | 2.50          |
+-------------+---------------+
第一个项目中，员工的平均工作年限是 (3 + 2 + 1) / 3 = 2.00；第二个项目中，员工的平均工作年限是 (3 + 2) / 2 = 2.50

思路：

例如：

1. 从项目表（Project）和员工表（Employee）中选择所需的列。
2. 使用left join将项目表和员工表连接起来，以便从两个表中获取所需的信息。
3. 使用AVG函数计算每个项目的平均工作经验，并使用round函数将结果保留两位小数。
4. 使用group by子句按照项目ID（project_id）对结果进行分组，以便获得每个项目的平均工作经验。

5. round函数用于将数值四舍五入为指定的小数位数。它的语法通常为：

   ROUND(number, decimal_places)
   

6. number 是要四舍五入的数值。
7. decimal_places 是要保留的小数位数，可以是正数、负数或零。正数表示要保留的小数位数，负数表示要四舍五入到小数点左侧的位数，零表示四舍五入到整数。
8. ROUND(3.14159, 2) 将会返回 3.14。
9. ROUND(123.456, -1) 将会返回 120。
10. ROUND(10.678, 0) 将会返回 11。

代码：

-- 选择每个项目的平均工作经验
select
    project_id,  -- 项目ID
    round(avg(e.experience_years),2)  as average_years  -- 平均工作年限
from
    Project as p  -- 项目表别名为 p
left join
    Employee as e  -- 员工表别名为 e
on
    p.employee_id = e.employee_id  -- 根据员工ID连接项目和员工表
group by
    p.project_id  -- 按项目ID分组