练习题（2024/4/29）

 在深度优先遍历中：有三个顺序，前中后序遍历 这里前中后，其实指的就是中间节点的遍历顺序，只要记住 前中后序指的就是中间节点的位置就可以了。

如图

1二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

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

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100
递归思路：

递归是一种在算法中使用函数自身来解决问题的方法。在递归算法中，函数会重复调用自身来处理问题的每一步，直到达到某个终止条件为止。递归算法通常包括三个重要部分：

  1. 确定递归函数的参数和返回值：确定哪些参数是递归过程中需要处理的，以及每次递归的返回值是什么进而确定递归函数的返回类型。

  2. 确定终止条件：为了避免无限循环或栈溢出错误，在递归算法中必须定义递归终止的条件，当满足终止条件时递归停止。

  3. 确定单层递归的逻辑：确定每一层递归需要处理的信息，并实现递归过程。通常在单层递归的逻辑中包含当前节点的处理逻辑以及对子节点的递归调用。

在递归算法中，需要注意以下几点：

  1. 确定递归函数的参数和返回值：在这段代码中，递归函数的参数为当前节点指针和存储节点值的数组，返回类型为void。这样做可以处理当前节点的值并在递归过程中更新结果数组。

  2. 确定终止条件：在递归中，一定要有终止条件，否则会导致栈溢出错误。在这段代码中，终止条件是当前节点为空（cur == NULL），此时直接返回，结束当前递归。

  3. 确定单层递归的逻辑：在前序遍历中，需要先处理当前节点的值，然后递归遍历左子树，最后递归遍历右子树。这种顺序符合前序遍历的要求。

代码：

class Solution {
public:
    // 定义一个辅助函数，用来递归遍历二叉树并将节点值存入结果数组
    void traversal(TreeNode* cur, vector<int>& vec) {
        // 若当前节点为空，则返回
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中序遍历，将当前节点的值加入结果数组
        traversal(cur->left, vec);  // 递归遍历左子树
        traversal(cur->right, vec); // 递归遍历右子树
    }
    
    // 定义前序遍历函数，返回一个存储节点值的数组
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        // 从根节点开始遍历
        traversal(root, result); // 调用辅助函数，从根节点开始前序遍历
        return result;
    }
};
 迭代思路：

迭代的思想是通过循环重复执行某段代码来解决问题，而不是通过递归的方式调用函数自身。迭代通常通过循环结构来实现，每次循环迭代处理一部分信息，直到达到预定的终止条件为止。

栈的特点是一种后进先出（LIFO）的数据结构，即最后入栈的元素会最先出栈

前序遍历的迭代法思路是通过使用栈数据结构来模拟递归的过程。具体步骤如下：

  1. 创建一个栈（stack）用于存储节点指针和一个结果数组（result）用于存储节点值。

  2. 将根节点压入栈中。

  3. 循环执行以下操作，直到栈为空：
    a. 弹出栈顶节点（当前访问的节点）。
    b. 将节点值加入结果数组。
    c. 如果节点的右子节点不为空，则将右子节点压入栈中。
    d. 如果节点的左子节点不为空，则将左子节点压入栈中。

  4. 遍历结束后，返回结果数组作为前序遍历的结果。

代码：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;  // 定义栈用来存储节点指针
        vector<int> result;   // 定义结果数组
        if (root == NULL) return result;  // 如果根节点为空则直接返回空数组
        st.push(root);  // 将根节点压入栈中
        while (!st.empty()) {
            TreeNode* node = st.top();  // 获取栈顶节点
            st.pop();  // 弹出栈顶节点
            result.push_back(node->val);  // 将节点值加入结果数组
            if (node->right) st.push(node->right);  // 若右子节点不为空，则压入栈中
            if (node->left) st.push(node->left);  // 若左子节点不为空，则压入栈中
        }
        return result;  // 返回结果数组
    }
};

2二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：

输入：root = []
输出：[]

示例 3：

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

提示：

  • 树中节点的数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100
递归思路 代码:
class Solution {
public:
    // 定义一个辅助函数，用来递归遍历二叉树并将节点值存入结果数组（后序遍历）
    void traversal(TreeNode *cur, vector<int>& vec) {
        if (cur == nullptr) return;
        traversal(cur->left, vec);   // 递归遍历当前节点的左子树
        traversal(cur->right, vec);  // 递归遍历当前节点的右子树
        vec.push_back(cur->val);     // 将当前节点的值加入结果数组
    }

    // 定义后序遍历函数，返回一个存储节点值的数组
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);     // 开始后序遍历，将结果存入数组
        return result;
    }
};
迭代思路

  1. 栈的应用：题目要求实现二叉树的后序遍历，可以考虑使用栈来辅助实现。栈可以帮助我们模拟递归的过程，从而遍历树的节点。

  2. 迭代法的核心：迭代法的核心是通过循环结构不断处理节点，模拟递归的过程。在后序遍历中，节点的访问顺序是左子树、右子树、根节点，因此我们需要注意入栈的顺序。

  3. 遍历过程：从根节点开始，将根节点入栈。然后循环执行以下步骤：

    • 弹出栈顶节点，将其值加入结果数组。
    • 如果节点有右子节点，则将右子节点压入栈中。
    • 如果节点有左子节点，则将左子节点压入栈中。

  4. 结果反转：由于后序遍历的顺序是左子树、右子树、根节点，而我们入栈的顺序是根节点、右子节点、左子节点，因此得到的结果数组需要进行反转。

  5. 返回结果：最后返回反转后的结果数组即可。

代码：
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;  // 定义栈用来存储节点指针
        vector<int> result;   // 定义结果数组
        if (root == NULL) return result;  // 如果根节点为空则直接返回空数组
        st.push(root);  // 将根节点压入栈中
        while (!st.empty()) {
            TreeNode* node = st.top();  // 获取栈顶节点
            st.pop();  // 弹出栈顶节点
            result.push_back(node->val);  // 将节点值加入结果数组
            if (node->left) st.push(node->left);  // 若左子节点不为空，则压入栈中
            if (node->right) st.push(node->right);  // 若右子节点不为空，则压入栈中
        }
        reverse(result.begin(), result.end());  // 将结果数组反转，得到左右中的遍历顺序
        return result;  // 返回结果数组
    }
};

3二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

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

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100
递归思路 代码：
class Solution {
public:
    // 定义一个辅助函数，用来递归遍历二叉树并将节点值存入结果数组（中序遍历）
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == nullptr) return;
        traversal(cur->left, vec);      // 递归遍历当前节点的左子树
        vec.push_back(cur->val);        // 将当前节点的值加入结果数组
        traversal(cur->right, vec);     // 递归遍历当前节点的右子树
    }

    // 定义中序遍历函数，返回一个存储节点值的数组
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);        // 开始中序遍历，将结果存入数组
        return result;
    }
};
 迭代思路

  1. 栈的应用：使用栈来辅助实现中序遍历。栈可以帮助我们模拟递归的过程，从而遍历树的节点。

  2. 指针的运用：我们使用一个指针cur来遍历节点，初始时指向根节点。

  3. 循环遍历：我们使用一个while循环来遍历节点，直到当前节点为NULL且栈为空为止。在循环中，我们检查当前节点cur是否为空，以及栈是否为空。

  4. 处理当前节点：

    • 如果cur不为空，说明还有左子树未遍历完，此时我们将当前节点入栈，并将cur指向其左子节点，以便继续向左遍历。
    • 如果cur为空，说明左子树已经遍历完毕，我们从栈中取出节点进行处理。这个节点就是当前子树的根节点，我们将其值加入结果数组，并将cur指向当前节点的右子节点。

  5. 遍历过程：

    • 不断将左子节点入栈，直到到达最左侧节点。在入栈的过程中，保证了左、中、右的顺序。
    • 当一个节点的左子树全部处理完毕后，从栈中取出节点进行处理，然后转向处理右子树。

  6. 返回结果：最终返回中序遍历的结果数组。

代码：
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;  // 定义结果数组
        stack<TreeNode*> st;  // 定义栈用来存储节点指针
        TreeNode* cur = root;  // 初始化当前节点为根节点
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {  // 如果当前节点不为空
                st.push(cur);  // 将当前节点入栈
                cur = cur->left;  // 移动到左子节点
            } else {
                cur = st.top();  // 从栈中取出节点进行处理
                st.pop();  // 弹出栈顶节点
                result.push_back(cur->val);  // 将节点值加入结果数组
                cur = cur->right;  // 移动到右子节点
            }
        }
        return result;  // 返回结果数组
    }
};

4学生们参加各科测试的次数

学生表: Students

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| student_id    | int     |
| student_name  | varchar |
+---------------+---------+
在 SQL 中，主键为 student_id（学生ID）。
该表内的每一行都记录有学校一名学生的信息。

科目表: Subjects

+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| subject_name | varchar |
+--------------+---------+
在 SQL 中，主键为 subject_name（科目名称）。
每一行记录学校的一门科目名称。

考试表: Examinations

+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| student_id   | int     |
| subject_name | varchar |
+--------------+---------+
这个表可能包含重复数据（换句话说，在 SQL 中，这个表没有主键）。
学生表里的一个学生修读科目表里的每一门科目。
这张考试表的每一行记录就表示学生表里的某个学生参加了一次科目表里某门科目的测试。

查询出每个学生参加每一门科目测试的次数，结果按 student_id 和 subject_name 排序。

查询结构格式如下所示。

示例 1：

输入：
Students table:
+------------+--------------+
| student_id | student_name |
+------------+--------------+
| 1          | Alice        |
| 2          | Bob          |
| 13         | John         |
| 6          | Alex         |
+------------+--------------+
Subjects table:
+--------------+
| subject_name |
+--------------+
| Math         |
| Physics      |
| Programming  |
+--------------+
Examinations table:
+------------+--------------+
| student_id | subject_name |
+------------+--------------+
| 1          | Math         |
| 1          | Physics      |
| 1          | Programming  |
| 2          | Programming  |
| 1          | Physics      |
| 1          | Math         |
| 13         | Math         |
| 13         | Programming  |
| 13         | Physics      |
| 2          | Math         |
| 1          | Math         |
+------------+--------------+
输出：
+------------+--------------+--------------+----------------+
| student_id | student_name | subject_name | attended_exams |
+------------+--------------+--------------+----------------+
| 1          | Alice        | Math         | 3              |
| 1          | Alice        | Physics      | 2              |
| 1          | Alice        | Programming  | 1              |
| 2          | Bob          | Math         | 1              |
| 2          | Bob          | Physics      | 0              |
| 2          | Bob          | Programming  | 1              |
| 6          | Alex         | Math         | 0              |
| 6          | Alex         | Physics      | 0              |
| 6          | Alex         | Programming  | 0              |
| 13         | John         | Math         | 1              |
| 13         | John         | Physics      | 1              |
| 13         | John         | Programming  | 1              |
+------------+--------------+--------------+----------------+
解释：
结果表需包含所有学生和所有科目（即便测试次数为0）：
Alice 参加了 3 次数学测试, 2 次物理测试，以及 1 次编程测试；
Bob 参加了 1 次数学测试, 1 次编程测试，没有参加物理测试；
Alex 啥测试都没参加；
John  参加了数学、物理、编程测试各 1 次。

思路：

使用join语句将学生表 (students) 和课程表 (subjects) 进行连接，以获取学生和课程的相关信息。使用left join语句将考试表 (examinations) 与学生、课程表进行左连接，确保即使某些学生没有参加考试，也能包括在结果中。

在on子句中，通过学生ID和课程名进行连接条件的指定，以便获取正确的考试记录。

使用count()函数统计每位学生在每门课程上参加的考试次数，起别名为attended_exams。

使用group by子句按照学生ID和课程名进行分组，以便对每个学生每门课程进行统计。

最后使用order by子句按照学生ID和课程名进行排序，以便输出结果。

代码：

select st.student_id, st.student_name, su.subject_name, count(e.subject_name) as attended_exams
from Students as st
join Subjects as su  -- 连接学生表和课程表
left join Examinations as e  -- 左连接考试表
on st.student_id = e.student_id and e.subject_name = su.subject_name  -- 根据学生ID和课程名进行连接
group by st.student_id, su.subject_name  -- 按学生ID和课程名分组
order by st.student_id, su.subject_name;  -- 按学生ID和课程名排序

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/583843.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【项目】仿muduo库One Thread One Loop式主从Reactor模型实现高并发服务器（Http测试板块）

【项目】仿muduo库One Thread One Loop式主从Reactor模型实现高并发服务器（Http测试板块）

【项目】仿muduo库One Thread One Loop式主从Reactor模型实现高并发服务器&#xff08;Http测试板块&#xff09; 一、使用Http网页界面1、main.cc原码和index.html原码2、运行结果&#xff08;1&#xff09;测试结果1&#xff1a;用index.html内部的代码&#xff08;2&#xf…
阅读更多...
《HelloGitHub》第 97 期

《HelloGitHub》第 97 期

兴趣是最好的老师&#xff0c;HelloGitHub 让你对编程感兴趣&#xff01; 简介 HelloGitHub 分享 GitHub 上有趣、入门级的开源项目。 github.com/521xueweihan/HelloGitHub 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等&#xff0c;涵盖多种编程语言 Python、…
阅读更多...
win下vscode的vim切换模式的中英文切换

win下vscode的vim切换模式的中英文切换

问题描述 在vscode中安装vim插件后&#xff0c;如果insert模式下完成输入后&#xff0c;在中文输入方式下按esc会发生无效输入&#xff0c;需要手动切换到英文。 解决方法 下载完成vscode并在其中配置vim插件下载github—im-select.exe插件&#xff08;注意很多博文中的gitcod…
阅读更多...
Microsoft Threat Modeling Tool 使用(二)

Microsoft Threat Modeling Tool 使用(二)

主界面 翻译 详细描述 选择了 “SDL TM Knowledge Base (Core)” 模板并打开了一个新的威胁模型。这个界面主要用于绘制数据流图&#xff08;Data Flow Diagram, DFD&#xff09;&#xff0c;它帮助您可视化系统的组成部分和它们之间的交互。以下是界面中各个部分的功能介绍&a…
阅读更多...
软件设计师-重点的行为型设计模式

软件设计师-重点的行为型设计模式

一、命令模式&#xff08;Command&#xff09;&#xff1a; 意图&#xff1a;&#xff08;上午题&#xff09; 将一个请求封装为一个对象&#xff0c;从而使得可以用不同的请求对客户进行参数化&#xff1b;对请求排队或记录请求日志&#xff0c;以及支持可撤销的操作。 结构…
阅读更多...
Django-基础篇

Django-基础篇

Django是一个开放源代码的Web应用框架&#xff0c;由Python语言编写。它遵循MVC&#xff08;Model-View-Controller&#xff09;的软件设计模式&#xff0c;使开发者能够以高效、可扩展和安全的方式构建Web应用程序。 Django具有以下特点和优势&#xff1a; 强大的功能&#x…
阅读更多...
[技术小技巧] 可视化分析：在jupyter中使用d3可视化树形结构

[技术小技巧] 可视化分析：在jupyter中使用d3可视化树形结构

首先在python中定义一个字符串&#xff0c;记录d3.js绘制属性图的js脚本代码模版。其中{{data}}就是将来要被替换的内容。 d3_code_template """ // 创建树状结构数据 var treeData {{data}};// 创建d3树布局 var margin { top: 20, right: 90, bottom: 30,…
阅读更多...
行业推荐：数据防泄漏软件首先解决方案

行业推荐：数据防泄漏软件首先解决方案

随着信息时代的快速发展&#xff0c;数据安全已成为企业经营的关键之一。然而&#xff0c;数据泄漏事件时有发生&#xff0c;不仅可能导致巨大的经济损失&#xff0c;更会损害企业的声誉和客户信任。 为了帮助企业有效地保护数据安全&#xff0c;Ping32 数据防泄漏系统应运而生…
阅读更多...
【跟我学RISC-V】认识RISC-V指令集并搭建实验环境

【跟我学RISC-V】认识RISC-V指令集并搭建实验环境

写在前面 现在计算机的体系架构正是发展得如火如荼的时候&#xff0c;占领桌面端市场的x86架构、占领移动端市场的arm架构、在服务器市场仍有一定地位的mips架构、国产自研的指令集loongarch架构、还有我现在要讲到的新型开源开放的RISC-V指令集架构。 我先说一说我的学习经历…
阅读更多...
Facebook的语言学：社交媒体如何影响我们的沟通方式

Facebook的语言学：社交媒体如何影响我们的沟通方式

1. 引言 社交媒体已经成为人们日常生活中不可或缺的一部分&#xff0c;而Facebook作为其中最具影响力的平台之一&#xff0c;不仅改变了人们之间的社交方式&#xff0c;也对我们的语言学产生了深远的影响。本文将深入探讨Facebook的语言学特点&#xff0c;以及它如何塑造和改变…
阅读更多...
【C++题解】1608. 三位数运算

【C++题解】1608. 三位数运算

问题&#xff1a;1608. 三位数运算 类型&#xff1a;基本运算、拆位求解 题目描述&#xff1a; 小丽在编程课上学会了拆位运算&#xff0c;她已经可以拆出一个三位整数的百位、十位和个位了&#xff0c;她想知道这个整数的&#xff08;百位 十位&#xff09; / &#xff08;…
阅读更多...
Web3与智能合约：科技革新下的新金融时代

Web3与智能合约：科技革新下的新金融时代

在当今数字化时代&#xff0c;Web3和智能合约正在共同塑造着金融领域的未来。Web3作为下一代互联网的重要组成部分&#xff0c;以其去中心化、安全性和透明性为核心特点&#xff0c;正推动着金融行业向着数字化和去中心化的方向发展。而智能合约作为Web3技术的关键应用之一&…
阅读更多...
虚拟机网络桥接模式无法通信，获取到的ip为169.254.X.X

虚拟机网络桥接模式无法通信，获取到的ip为169.254.X.X

原因&#xff1a;VMware自动选择的网卡可能不对 解决&#xff1a;编辑-虚拟网络编辑器-更改桥接模式-选择宿主机物理网卡&#xff0c;断开虚拟机网络连接后重新连接即可
阅读更多...
Docker（Docker的安装和介绍，常用命令，镜像制作，服务编排，docker私服）

Docker（Docker的安装和介绍，常用命令，镜像制作，服务编排，docker私服）

目录 一、简介 1. docker简介 1 什么是docker 2 容器和虚拟机对比 2. 安装docker 1 docker相关概念 2 安装docker 1 安装docker 2 设置注册中心(仓库) 3. 小结 二、常用命令【重点】 1. 服务管理 2. 镜像管理 1 语法说明 2 使用练习 3. 容器管理 1 容器介绍 2…
阅读更多...
2024.4.25 LoadRunner 测试工具详解 —— Controller Analysis

2024.4.25 LoadRunner 测试工具详解 —— Controller Analysis

目录 Controller 的使用 创建场景 Controller 快捷方式创建场景 VUG 针对写好脚本创建场景 场景设计 设计初始化 设计启动机制 设计性能测试脚本的执行时间 设计虚拟用户退出机制 场景运行 添加监控指标至图标格区域 Analysis 的使用 汇总报告 测试报表 吞吐量图 …
阅读更多...
Dockerfile实战---构建SSH、Tomcat、MySQL、Nginx镜像

Dockerfile实战---构建SSH、Tomcat、MySQL、Nginx镜像

目录 引言 一、安装docker程序 二、构建SSH镜像 1.创建镜像 2.基于sshd镜像创建容器 三、构建tomcat镜像 1.创建镜像 2.基于tomcat镜像创建容器 四、构建MySQL镜像 1.创建镜像 2.基于mysqld镜像创建容器 五、构建nginx镜像 1.创建镜像 2.基于nginx镜像创建容器 引…
阅读更多...
用Stream流方式合并两个list集合（部分对象属性重合）

用Stream流方式合并两个list集合（部分对象属性重合）

一、合并出共有部分 package com.xu.demo.test;import java.util.Arrays; import java.util.List; import java.util.stream.Collectors;public class ListMergeTest1 {public static void main(String[] args) {List<User> list1 Arrays.asList(new User(1, "Alic…
阅读更多...
Linux学习之Tcp与Udp

Linux学习之Tcp与Udp

目录 UDP Udp协议的格式 UDP的传输特性 UDP的缓冲区 基于UDP的应用层协议 TCP协议 TCP的报文格式 1.ACK确认应答机制 2.超时重传 3.TCP的链接管理机制 为什么要三次握手呢&#xff1f; 理解TIME_WAIT状态 流量控制&#xff08;可靠性效率&#xff09; 滑动窗口 拥塞…
阅读更多...
Java8中的Stream流相关用法学习

Java8中的Stream流相关用法学习

目录 一、Stream是什么 二、创建Stream 三、中间操作 3.1 filter() 3.2 map() 3.3 flatMap() 3.4 distinct() 3.5 limit() 四、终端操作 4.1 findAny(), 和 orElse() 4.2 sorted() 4.3 forEach() 4.4 count() 4.5 collect() 4.6 groupingBy() 4.7 average() 4…
阅读更多...
RAG-Driver: 多模态大语言模型中具有检索增强上下文学习的通用驱动解释

RAG-Driver: 多模态大语言模型中具有检索增强上下文学习的通用驱动解释

RAG-Driver: 多模态大语言模型中具有检索增强上下文学习的通用驱动解释 摘要Introduction RAG-Driver: Generalisable Driving Explanations with Retrieval-Augmented In-Context Learning in Multi-Modal Large Language Model. 摘要 由“黑箱”模型驱动的机器人需要提供人类…
阅读更多...
最新文章

Copyright @ 2022~2023