当前位置: 首页 > news >正文

408算法题leetcode--第23天

236. 二叉树的最近公共祖先

  • 236. 二叉树的最近公共祖先\
  • 思路:递归,如注释
  • 时间和空间:O(n)
/*** 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 最近公共祖先:root的两侧分别为p, q;root = p, 且q在左/右子树中,同理root = q, 且p在左右子树中// dfs: 1. 确定参数类型和返回类型,TreeNode*, bool// 2. 终止条件:空节点,null; root == q/p, root// 3. 递归逻辑:后序遍历,如果左右儿子都为空,返回null,如果其中一个不是空,即目标节点if(root == nullptr || root == q || root == p) return root;TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);if(!left && !right) return nullptr;if(left && !right) return left;if(!left && right) return right;return root;}
};

234. 回文链表

  • 234. 回文链表
  • 思路1:如注释
  • 时间和空间:O(n)
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {// 思路1:转换为数组,然后再判断回文vector<int>v;while(head){v.push_back(head->val);head = head->next;}// 判断回文int size = v.size();for(int i = 0; i < size / 2; i++){if(v[i] != v[size - 1 - i]){return false;}}return true;}
};
  • 思路2:快慢指针找到链表中点,后一段链表翻转,然后比较两个链表是否相同
  • 时间:O(n),空间:O(1)
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* findMiddle(ListNode* head){// 快慢指针ListNode* fast = head, *slow = head;while(fast->next && fast->next->next){fast = fast->next->next;slow = slow->next;}return slow;}ListNode* reverseList(ListNode* head){// 翻转链表ListNode* pre = nullptr, *cur = head, *next = nullptr;while(cur){next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;}bool isPalindrome(ListNode* head) {// 快慢指针找到链表中点,后一段链表翻转,然后比较两个链表是否相同if(head == nullptr) return true;// 找中点,奇数个节点时,中间节点放到左边的链表中ListNode* middle = findMiddle(head);// 翻转右边的链表ListNode* right = reverseList(middle->next);// 比较ListNode* p = head, *q = right;while(p && q){if(p->val != q->val){return false;}p = p->next;q = q->next;}// 最好比较完,还原链表return true;}
};

141. 环形链表

  • 141. 环形链表
  • 思路:如注释
  • 时间:O(n);空间:O(1)
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {// 思路1:哈希表:如果某个值出现2次,则有环// 思路2:快慢指针,快指针走2,慢指针走1,如果相等则有环if(head == nullptr || head->next == nullptr) return false;ListNode* p = head, *q = head;while(q && q->next){p = p->next;q = q->next->next;if(q == p){return true;}}return false;}
};

相关文章:

408算法题leetcode--第23天

236. 二叉树的最近公共祖先 236. 二叉树的最近公共祖先\思路&#xff1a;递归&#xff0c;如注释时间和空间&#xff1a;O(n) /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) …...

帝国CMS系统开启https后,无法登陆后台的原因和解决方法

今天本地配置好了帝国CMS7.5&#xff0c;传去服务器后&#xff0c;使用http访问一切正常。但是当开启了https&#xff08;SSL&#xff09;后&#xff0c;后台竟然无法登陆进去了。 输入账号密码后&#xff0c;点击登陆&#xff0c;跳转到/e/admin/ecmsadmin.php就变成页面一片…...

根据视频id查询播放量

声明&#xff1a;文章仅用于学习交流,如有侵权请联系删除 如何根据视频ID查询视频的播放数量 在数字化时代&#xff0c;视频内容的消费已成为人们日常生活的重要组成部分。无论是社交媒体平台上的短视频&#xff0c;还是视频分享网站上的长视频&#xff0c;了解视频的播放数量…...

初始爬虫11

1.斗鱼selenium爬取 # -*- coding: utf-8 -*- from selenium import webdriver from selenium.webdriver.common.by import By import timeclass Douyu(object):def __init__(self):self.url https://www.douyu.com/directory/allself.driver webdriver.Chrome()self.driver…...

SSY20241002提高组T4题解__纯数论

题面 题目描述 有一天 p e o p 1 e peop1e peop1e 学长梦到了一个丑陋的式子&#xff1a; ∑ i 1 n ( ∑ m 1 R F m ) ! i ! ∑ l 0 i ∑ j 0 ∑ t 1 R F t { K i − l } l ! { i ∑ w 1 R F w − j } j ! \sum_{i1}^n (\sum_{m1}^R F_m)!\times i!\times \sum_{l…...

Python:lambda 函数详解 以及使用

一、lambda 语法 lambda 函数的语法只包含一个语句&#xff0c;表现形式如下&#xff1a; lambda [arg1 [,arg2,.....argn]]:expression 其中&#xff0c;lambda 是 Python 预留的关键字&#xff0c;[arg…] 和 expression 由用户自定义。 具体如下: [arg…] 是参数列表&#…...

【C++】空指针和野指针

文章目录 1.空指针2.野指针总结 1.空指针 概念&#xff1a;指针变量指向内存中编号为0的空间。 用途&#xff1a;初始化指针变量。 注意&#xff1a;空指针指向的内存是不可以访问的。 示例&#xff1a; int main(){//指针变量p指向内存地址编号为0的空间int *PNULL&#…...

大模型提示词

纯输入版提示工程词 输出一个九九乘法口诀表 当然可以&#xff01;以下是九九乘法口诀表&#xff1a; 1 x 1 1 1 x 2 2 2 x 2 4 1 x 3 3 2 x 3 6 3 x 3 9 1 x 4 4 2 x 4 8 3 x 4 12 4 x 4 16 1 x 5 5 2 x 5 10 3 x 5 15 4 x 5 20 5 …...

在线css像素px到Em的转换器

具体请前往&#xff1a;在线Px转Em工具--将绝对像素(px)长度单位转换为相对长度em...

回溯算法解决排列组合及子集问题

216. 组合总和 III39. 组合总和40. 组合总和 II46. 全排列47. 全排列 II77. 组合 78. 子集 90. 子集 II 以上是力扣设计相关问题的题目。排列组合还是子集问题无非就是从序列 nums 中以给定规则取若干元素&#xff0c;主要有以下几类&#xff1a; 元素无重不可复选&#xff0…...

Unity中Mesh多种网格绘制模式使用方法参考

Unity中MeshFilter中的Mesh默认情况下使用MeshTopology.Trigangles类型绘制网格&#xff0c;就是通常的绘制三角形网格&#xff0c;实际上Mesh有五种绘制模式&#xff0c;对应MeshTopology的枚举&#xff0c;分别是 Triangles网格由三角形构成。Quads网格由四边形构成。Lines网…...

【Spring Security】基于SpringBoot3.3.4版本②如何配置免鉴权Path

基于Spring Boot 3.3.4,详细说明Spring Security 6.3.3的使用 摘要本地开发环境说明SecurityFilterChain介绍application.ymlWen3SecurityProperties.java修改DemoWen3Security修改SecurityFilterChainIgnoredPathController.javaIgnoredPathController2.java启动工程测试测试…...

信息学奥赛复赛复习11-CSP-J2020-04方格取数-动态规划、斐波那契数列、最优子结构、重叠子问题、无后效性

PDF文档回复:20241004 1 P7074 [CSP-J2020] 方格取数 [题目描述] 设有 nm 的方格图&#xff0c;每个方格中都有一个整数。现有一只小熊&#xff0c;想从图的左上角走到右下角&#xff0c;每一步只能向上、向下或向右走一格&#xff0c;并且不能重复经过已经走过的方格&#x…...

Hive数仓操作(十二)

一、Hive 中的行列转换 1. 行转列&#xff1a; collect_list() collect_list() 函数用于将一个列中的数据收集成一个数组。 示例数据文件 假设有一个名为 orders.txt 的文件&#xff0c;内容如下&#xff1a; 1,101 1,101 1,103 2,104 2,105导入数据到 Hive 表 首先&…...

计算机毕业设计 基于SpringBoot和Vue的课程教学平台的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…...

有状态(Session) VS 无状态(Token)

目录 概念 JWT Token在项目中使用 概念 有状态和无状态服务是两种不同的服务架构&#xff0c;两者的不同之处在于对于服务状态的处理。 1、有状态服务 是指程序在执行过程中生成的中间数据&#xff0c;服务器端一般都要保存请求的相关信息&#xff0c;每个请求可以默认地使…...

天坑!Spark+Hive+Paimon+Dolphinscheduler

背景: 数据中台项目使用Spark+Hive+Paimon做湖仓底层,调度任务使用的是基于Dolphinscheduler进行二开。在做离线脚本任务开发时,在Paimon库下执行非查询类SQL报错。 INSERT报错 DELETE报错 现状: 原始逻辑为数据中台中选择的Paimon数据源,实际上在Dolphinscheduler中是…...

JAVA——IO框架

目录 一、框架 二、导入框架步骤 三、测试 一、框架 框架就是为了解决某类问题&#xff0c;编写的一套类、接口等。大多数框架都是第三方研发的 好处: 在框架的基础上开发&#xff0c;提高开发效率 框架的形式&#xff1a;一般是把类、接口编译成class形式&#xff0c;再…...

项目管理系统如何实现项目申报流程自动化?

传统的项目申报流程往往繁琐复杂&#xff0c;涉及众多环节和部门间的协作&#xff0c;不仅耗时费力&#xff0c;还容易因人为疏忽而导致错误或延误。随着信息技术的飞速发展&#xff0c;项目管理系统的出现为项目申报流程的自动化提供了可能&#xff0c;极大地提升了申报效率和…...

ndb9300public-ndb2excel简介

1 引言 ndb9300是一个自己定义的机载导航数据库劳作&#xff08;不敢称为项目&#xff09;代号&#xff0c;其中3表示是第3种数据库。 多年前&#xff0c;对在役民航客机中的某型机载导航数据库的二进制文件进行分析&#xff0c;弄明白它的数据结构后做了几个工具&#xff0c…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...