1所有可能的路径
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
示例 1：
输入：graph = [[1,2],[3],[3],[]] 输出：[[0,1,3],[0,2,3]] 解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
示例 2：
输入：graph = [[4,3,1],[3,2,4],[3],[4],[]] 输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
提示：
n == graph.length2 <= n <= 150 <= graph[i][j] < ngraph[i][j] != i（即不存在自环）graph[i]中的所有元素 互不相同- 保证输入为 有向无环图（DAG）
深度搜索思路：
深度搜索过程：
- 首先从起始节点开始，将起始节点加入当前路径中，然后进行深度优先搜索。
- 在搜索的过程中，不断向下探索下一个邻居节点，将其加入当前路径并继续递归搜索。
- 当搜索到最后一个节点时，将当前路径加入结果中，表示找到了一条从起始节点到最后一个节点的路径。
- 接着进行回溯操作，将最后一个节点从路径中移除，然后继续搜索其他可能的分支。
- 重复以上步骤，直到搜索完所有可能的路径，最终得到所有从起始节点到最后一个节点的路径集合。
所以我们可以使用深度优先搜索的方式求出所有可能的路径。具体地，我们从0号点出发，使用栈记录路径上的点。每次我们遍历到点 n−1，就将栈中记录的路径加入到答案中。
- 首先定义了一个类Solution，其中包含了一个二维vector result 用来存放所有路径的结果，一个一维vector path 用来表示当前遍历的路径。
- 接着有了一个dfs函数，用来进行深度优先搜索。在dfs函数中，首先判断当前节点是否为最后一个节点，如果是则将当前路径加入结果中；否则就遍历当前节点的邻居节点。
- 在遍历邻居节点的过程中，将邻居节点加入当前路径中，然后继续深度优先搜索下一个节点。搜索完毕后进行回溯操作，将当前节点从路径中移除，以便继续搜索其他分支。
- 最后，在allPathsSourceTarget函数中，将起始节点0加入路径中，然后调用dfs函数开始进行深度优先搜索，最终返回结果中存储的所有从起始节点到最后一个节点的路径。
代码：
class Solution {
public:
vector<vector<int>> result; // 存放所有路径的结果
vector<int> path; // 当前遍历的路径
void dfs(vector<vector<int>>& graph, int x){
// 当遍历到最后一个节点时，将当前路径加入结果中
if(x==graph.size()-1){
result.push_back(path);
return;
}
// 遍历当前节点的邻居节点
for(int i=0;i<graph[x].size();i++){
// 将邻居节点加入当前路径中
path.push_back(graph[x][i]);
// 继续深度优先搜索
dfs(graph,graph[x][i]);
// 回溯，将当前节点从路径中移除
path.pop_back();
}
}
// 找到从0到最后一个节点的所有路径
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
path.push_back(0); // 起始节点为0
dfs(graph,0);
return result;
}
};2岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1
示例 2：
输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1
思路：
这道题的解题思路是利用深度优先搜索（DFS）来遍历地图中的岛屿。首先定义一个帮助函数numIslandsHelper，用于递归地标记岛屿及其连通的岛屿。然后，在主函数numIslands中遍历整个地图，如果发现未被访问过的岛屿，则调用numIslandsHelper进行标记，并同时将真实岛屿数量加一。最后返回真实岛屿数量。
具体解题步骤如下：
- 遍历整个地图，对每个未被访问过的岛屿（即值为’1’的位置）调用
numIslandsHelper函数。 - 在
numIslandsHelper函数中，将当前岛屿标记为已访问，然后递归地向该岛屿的四个方向（上、下、左、右）进行搜索，将连通的岛屿都标记为相同的字符（这里使用字符’2’)。 - 每次成功标记一个岛屿后，真实岛屿数量加一。
- 最后返回真实岛屿数量。
代码：
class Solution {
public:
void numIslandsHelper(vector<vector<char>>& grid, int i, int j, char& num)
{
/* 帮助函数：深度优先搜索遍历并标记岛屿 */
/* 参数说明：
grid: 二维字符数组，表示地图
i: 当前元素行坐标
j: 当前元素列坐标
num: 当前标记号
*/
// 先将当前位置标记为已访问
grid[i][j] = num;
// 向右递归
if (j + 1 < grid[0].size() && grid[i][j + 1] == '1')
{
numIslandsHelper(grid, i, j + 1, num);
}
// 向左递归
if (j - 1 >= 0 && grid[i][j - 1] == '1')
{
numIslandsHelper(grid, i, j - 1, num);
}
// 向上递归
if (i - 1 >= 0 && grid[i - 1][j] == '1')
{
numIslandsHelper(grid, i - 1, j, num);
}
// 向下递归
if (i + 1 < grid.size() && grid[i + 1][j] == '1')
{
numIslandsHelper(grid, i + 1, j, num);
}
//cout<<"num=" << num<<endl;
}
int numIslands(vector<vector<char>>& grid)
{
/* 主函数：计算岛屿数量 */
/* 参数说明：
grid: 二维字符数组，表示地图
*/
char num = '2'; // 起始标记号
int real_num = 0; // 真实岛屿数量
// 遍历地图元素
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[0].size(); j++)
{
if (grid[i][j] == '1')
{
numIslandsHelper(grid, i, j, num); // 调用帮助函数标记岛屿
real_num++; // 岛屿数量加一
}
}
}
return real_num; // 返回岛屿数量
}
};3N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：[["Q"]]
提示：
1 <= n <= 9
思路：
首先来看一下皇后们的约束条件：
- 不能同行
- 不能同列
- 不能同斜线
确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。
只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。
回溯三部曲的具体应用在N皇后问题中可以分解如下：
-
递归函数参数：
int n：棋盘大小，也即皇后数量int row：当前处理的行数vector<string>& chessBoard：当前棋盘状态
-
递归终止条件：
- 当
row == n时，说明找到了一组解，将其加入结果集合并返回。
- 当
-
单层搜索的逻辑：
- 遍历当前行的每一列，尝试将皇后放置在该位置。
- 调用
isValid函数判断当前位置是否有效，即是否与之前的皇后位置产生冲突。 -
isValid函数的作用是判断当前位置是否有效，即判断放置皇后在当前位置是否会与之前已经放置的皇后位置产生冲突。具体而言，isValid函数可以通过以下方式来检查当前位置是否安全： - 检查同一列是否有皇后：遍历之前的每一行，检查当前列上是否已经放置了皇后，如果有则表示当前位置不安全。
- 检查左对角线是否有皇后：遍历之前的每一行，检查当前位置的左对角线上是否存在皇后，即行号之差与列号之差的绝对值相等表示在同一左对角线上。
- 检查右对角线是否有皇后：遍历之前的每一行，检查当前位置的右对角线上是否存在皇后，即行号之和与列号之差的绝对值相等表示在同一右对角线上。
- 若有效，则在当前位置放置皇后，继续递归处理下一行。
- 如果下一行无解，则回溯到当前位置，继续遍历下一个列。
- 最终找到所有合法的解并存储到结果集中。
代码：
class Solution {
private:
vector<vector<string>> result; // 存储最终结果的变量
void backtracking(int n, int row, vector<string>& chessBoard) {
// 回溯函数：用于解决N皇后问题
// 参数说明：
// n: 棋盘大小
// row: 当前行数
// chessBoard: 当前棋盘状态
// 如果当前行数等于棋盘大小，说明找到了一组解，将其加入结果集合并返回
if (row == n) {
result.push_back(chessBoard);
return;
}
// 遍历当前行的每一个列
for (int col = 0; col < n; col++) {
// 判断当前位置是否可以放置皇后
if (isValid(row, col, chessBoard, n)) {
// 如果可以放置皇后，则在当前位置放置一个皇后，继续对下一行进行递归
chessBoard[row][col] = 'Q';
backtracking(n, row + 1, chessBoard);
// 回溯，将当前位置复原
chessBoard[row][col] = '.';
}
}
}
bool isValid(int row, int col, vector<string>& chessBoard, int n) {
// 判断当前位置是否可以放置皇后
// 参数说明：
// row: 当前行数
// col: 当前列数
// chessBoard: 当前棋盘状态
// n: 棋盘大小
// 遍历之前的行，判断是否同一列有皇后
for (int i = 0; i < row; i++) {
if (chessBoard[i][col] == 'Q') return false;
}
// 检查左上方对角线
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chessBoard[i][j] == 'Q') return false;
}
// 检查右上方对角线
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (chessBoard[i][j] == 'Q') return false;
}
return true; // 可以放置皇后
}
public:
vector<vector<string>> solveNQueens(int n) {
// 初始化一个n*n的棋盘，全部填充为'.'表示空格
vector<string> chessBoard(n, string(n, '.'));
// 从第0行开始回溯求解
backtracking(n, 0, chessBoard);
return result; // 返回所有解
}
};4最后一个能进入巴士的人
表: Queue
+-------------+---------+ | Column Name | Type | +-------------+---------+ | person_id | int | | person_name | varchar | | weight | int | | turn | int | +-------------+---------+ person_id 是这个表具有唯一值的列。 该表展示了所有候车乘客的信息。 表中 person_id 和 turn 列将包含从 1 到 n 的所有数字，其中 n 是表中的行数。 turn 决定了候车乘客上巴士的顺序，其中 turn=1 表示第一个上巴士，turn=n 表示最后一个上巴士。 weight 表示候车乘客的体重，以千克为单位。
有一队乘客在等着上巴士。然而，巴士有1000 千克 的重量限制，所以其中一部分乘客可能无法上巴士。
编写解决方案找出 最后一个 上巴士且不超过重量限制的乘客，并报告 person_name 。题目测试用例确保顺位第一的人可以上巴士且不会超重。
返回结果格式如下所示。
示例 1：
输入： Queue 表 +-----------+-------------+--------+------+ | person_id | person_name | weight | turn | +-----------+-------------+--------+------+ | 5 | Alice | 250 | 1 | | 4 | Bob | 175 | 5 | | 3 | Alex | 350 | 2 | | 6 | John Cena | 400 | 3 | | 1 | Winston | 500 | 6 | | 2 | Marie | 200 | 4 | +-----------+-------------+--------+------+ 输出： +-------------+ | person_name | +-------------+ | John Cena | +-------------+ 解释： 为了简化，Queue 表按 turn 列由小到大排序。 +------+----+-----------+--------+--------------+ | Turn | ID | Name | Weight | Total Weight | +------+----+-----------+--------+--------------+ | 1 | 5 | Alice | 250 | 250 | | 2 | 3 | Alex | 350 | 600 | | 3 | 6 | John Cena | 400 | 1000 | (最后一个上巴士) | 4 | 2 | Marie | 200 | 1200 | (无法上巴士) | 5 | 4 | Bob | 175 | ___ | | 6 | 1 | Winston | 500 | ___ | +------+----+-----------+--------+-----
思路：我们需要根据 turn 排序， 并累加 weight，找到最后一个使得总和小于等于 1000 的 person_name。
我们只需要计算出每个人进去后的总和，找到总和小于等于 1000 的最后一个人即可
代码：
select person_name
from(select *,
sum(weight) over (order by turn) as sum_weight
from Queue) a
where sum_weight<=1000
order by sum_weight desc
limit 1;5 平均售价
表：Prices
+---------------+---------+ | Column Name | Type | +---------------+---------+ | product_id | int | | start_date | date | | end_date | date | | price | int | +---------------+---------+ (product_id，start_date，end_date) 是prices表的主键（具有唯一值的列的组合）。prices表的每一行表示的是某个产品在一段时期内的价格。 每个产品的对应时间段是不会重叠的，这也意味着同一个产品的价格时段不会出现交叉。
表：UnitsSold
+---------------+---------+ | Column Name | Type | +---------------+---------+ | product_id | int | | purchase_date | date | | units | int | +---------------+---------+ 该表可能包含重复数据。 该表的每一行表示的是每种产品的出售日期，单位和产品 id。
编写解决方案以查找每种产品的平均售价。average_price 应该 四舍五入到小数点后两位。
返回结果表 无顺序要求 。
结果格式如下例所示。
示例 1：
输入： Prices table: +------------+------------+------------+--------+ | product_id | start_date | end_date | price | +------------+------------+------------+--------+ | 1 | 2019-02-17 | 2019-02-28 | 5 | | 1 | 2019-03-01 | 2019-03-22 | 20 | | 2 | 2019-02-01 | 2019-02-20 | 15 | | 2 | 2019-02-21 | 2019-03-31 | 30 | +------------+------------+------------+--------+ UnitsSold table: +------------+---------------+-------+ | product_id | purchase_date | units | +------------+---------------+-------+ | 1 | 2019-02-25 | 100 | | 1 | 2019-03-01 | 15 | | 2 | 2019-02-10 | 200 | | 2 | 2019-03-22 | 30 | +------------+---------------+-------+ 输出： +------------+---------------+ | product_id | average_price | +------------+---------------+ | 1 | 6.96 | | 2 | 16.96 | +------------+---------------+ 解释： 平均售价 = 产品总价 / 销售的产品数量。 产品 1 的平均售价 = ((100 * 5)+(15 * 20) )/ 115 = 6.96 产品 2 的平均售价 = ((200 * 15)+(30 * 30) )/ 230 = 16.96
思路：首先通过左连接将价格表和单位销售表按产品ID进行连接，然后根据条件筛选符合购买日期在有效日期范围内的数据。接着按产品ID分组统计数据，计算每个产品的平均价格，如果单位销售表中没有对应的数据，则平均价格为0，否则计算平均价格并四舍五入保留两位小数。最终得到每个产品的平均价格。
代码：
select
prices.product_id, -- 选择价格表中的产品id
ifnull(round(sum(price * units) / sum(units), 2), 0) as average_price -- 如果单位销售表中没有对应的数据，则平均价格为0；否则计算平均价格并四舍五入保留两位小数
from
prices
left join unitssold
on prices.product_id = unitssold.product_id -- 使用产品id连接价格表和单位销售表
and start_date <= purchase_date and purchase_date <= end_date -- 筛选符合购买日期在有效日期范围内的数据
group by product_id -- 按产品id分组统计数据
![[网络安全] apt攻击是什么？](https://img-blog.csdnimg.cn/direct/99b9e93268444ee19623fe03fd3d43b9.jpeg#pic_center)
