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

leetcode每日一题43

116. 填充每个节点的下一个右侧节点指针

层序遍历嘛

/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}Node(int _val, Node* _left, Node* _right, Node* _next): val(_val), left(_left), right(_right), next(_next) {}
};
*/class Solution {
public:Node* levelOder(Node* root){queue<Node*> que;if(root==NULL){return root;}que.push(root);while(!que.empty()){int size = que.size();for(int i=0;i<size;i++){Node* node = que.front();que.pop();if(i<size-1)node->next=que.front();if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return root;}Node* connect(Node* root) {return levelOder(root);}
};

120. 三角形最小路径和

其实就是DP啦

  1. 确定dp数组(dp table)以及下标的含义
    dp[i][j]就是三角形的第i行第j列的最小路径和
  2. 确定递推公式
    不在三角形的腰上时,路径和由上一行的两个路径和中选更小的
    dp[i][j]=min(dp[i-1][j-1], dp[i-1][j]) + c[i][j]
    c[i][j]为三角形第i行第j列的值
    三角形的两个腰上的值是只能由上一行的腰上的值决定
    dp[i][0]=c[i][0]+dp[i-1][0]
    dp[i][i]=c[i][i]+dp[i-1][i-1]
  3. dp数组如何初始化
    三角形的两个腰上的值是只能由上一行的腰上的值决定
    dp[0][0]=c[0][0]
  4. 确定遍历顺序
    从上到小从左到右
  5. 举例推导dp数组
class Solution {
public:int minimumTotal(vector<vector<int>>& triangle) {int size = triangle.size();vector<vector<int>> dp(size, vector<int>(size));dp[0][0]=triangle[0][0];for(int i=1;i<size;i++){dp[i][0] = triangle[i][0] + dp[i-1][0];for(int j=1;j<i;j++){dp[i][j]=min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];}dp[i][i] = triangle[i][i]+dp[i-1][i-1];}int min = dp[size-1][0];for(int i =1;i<size;i++){if(min>dp[size-1][i])min = dp[size-1][i];}return min;}
};

128. 最长连续序列

直接用sort()的话是O(nlogn)
题目要求O(n)
所以我们使用一个哈希表对于数据进行快速的查找
当前数字nums[i]是序列的第一个数据的条件是找不到nums[i]-1
找到第一个数据后,递增,找下一个数据在不在哈希表里,若在,当前序列长度++

class Solution {
public:int longestConsecutive(vector<int>& nums) {int res_len = 0;unordered_set<int> num_set(nums.begin(), nums.end());  int cur_len;for(int i=0;i<nums.size();i++){int cur = nums[i];if(!num_set.count(cur-1)){cur_len = 1;while(num_set.count(++cur))cur_len++;res_len = max(res_len,cur_len);}}return res_len;}
};

为什么代码里for里套了while还是O(n)呢

如果所有数字都是连续的,那么只有第一个数字会去走while,其他数字无法通过if判断,那么每个数字都只处理一次。如果所有数字都是不连续的,每个数字都去走while,但是while只会处理这个数字,相当于还是每个数字只处理一次。不是说for里面套了while就一定是平方级别的复杂度,关键在于看数组中每个元素的处理次数。

就酱

129. 求根节点到叶节点数字之和

深度搜索,前序遍历
从根节点开始,遍历每个节点,如果遇到叶子节点,则获得该路径的数字。如果当前节点不是叶子节点,则计算其子节点对应的数字,然后对子节点递归遍历,获得该节点对应的所有路径的数字之和。

  1. 参数及返回值
    因为要用到当前路径到达父节点组成的值,所以参数不仅要当前节点,也需要父节点组成的值presum
    返回值是当前节点到叶节点的数字之和,整型
  2. 终止条件
    当前节点为根节点的时候,返回当前值
    if(root->left==nullptr&&root->right==nullptr)
    return sum;
    因为左右节点是空的时候已经判断了,那么整个树的root节点是空的时候,返回0
    if(root==nullptr)
    return 0;
  3. 单层逻辑
    首先计算当前节点对应的数字int sum=preSum*10+root->val;
    然后深度遍历,获得左右节点的值之和
int leftSum=0;
int rightSum=0;
if(root->left)leftSum=preOrder(root->left,sum);
if(root->right)rightSum=preOrder(root->right,sum);

最后将左右节点对应的路径的数字之和再求和,就是当前节点所在的所有路径的数字之和

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int preOrder(TreeNode* root, int preSum){if(root==nullptr)return 0;int sum=preSum*10+root->val;if(root->left==nullptr&&root->right==nullptr)return sum;int leftSum=0;int rightSum=0;if(root->left)leftSum=preOrder(root->left,sum);if(root->right)rightSum=preOrder(root->right,sum);return leftSum+rightSum;}int sumNumbers(TreeNode* root) {return preOrder(root,0);}
};

相关文章:

leetcode每日一题43

116. 填充每个节点的下一个右侧节点指针 层序遍历嘛 /* // Definition for a Node. class Node { public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(N…...

每天刷两道题——第十天

1.1和为k的子数组 给你一个整数数组 n u m s nums nums 和一个整数 k k k &#xff0c;请你统计并返回 该数组中和为 k k k 的子数组的个数 。子数组是数组中元素的连续非空序列。 输入&#xff1a;nums [1,2,3], k 3 输出&#xff1a;2 前缀和 1.2如何使用 前缀和的…...

C语言入门教程,C语言学习教程(第一部分:编程基础 )一

C语言是一门面向过程的编译型语言&#xff0c;它的运行速度极快&#xff0c;仅次于汇编语言。C语言是计算机产业的核心语言&#xff0c;操作系统、硬件驱动、关键组件、数据库等都离不开C语言&#xff1b;不学习C语言&#xff0c;就不能了解计算机底层。 这套「C语言入门教程」…...

uniapp微信小程序投票系统实战 (SpringBoot2+vue3.2+element plus ) -用户信息修改实现

锋哥原创的uniapp微信小程序投票系统实战&#xff1a; uniapp微信小程序投票系统实战课程 (SpringBoot2vue3.2element plus ) ( 火爆连载更新中... )_哔哩哔哩_bilibiliuniapp微信小程序投票系统实战课程 (SpringBoot2vue3.2element plus ) ( 火爆连载更新中... )共计21条视频…...

C语言PDF编程书籍下载

[C.Primer.Plus&#xff08;第6版&#xff09;中文版].&#xff08;美&#xff09;普拉达.扫描版.pdf 链接: https://pan.baidu.com/s/1difCyykkBdLqgLu32PgYLw 密码: tv05 C语言程序设计教程_基于Visual.Cpp.6.0环境.pdf 链接: https://pan.baidu.com/s/1q3nRrRJyUd4H3Yp_PgA…...

VScode/Xshell连接学校服务器

vscode连学校服务器 1.连接atrust VPN2.Xshell连接服务器2.1创建一个自己的用户 3.xftp传文件4.vscode连接服务器4.1下载remote-ssh4.2连接服务器4.3激活conda环境4.4运行代码 5. pytorch版本不兼容解决方案 1.连接atrust VPN 如果是使用的是校园网&#xff0c;可以不连接 2…...

46 WAF绕过-信息收集之反爬虫延时代理池技术

目录 简要本章具体内容和安排缘由简要本课具体内容和讲课思路简要本课简要知识点和具体说明演示案例:Safedog-默认拦截机制分析绕过-未开CCSafedog-默认拦截机制分析绕过-开启CC总结&#xff1a; Aliyun_os-默认拦截机制分析绕过-简要界面BT(防火墙插件)-默认拦截机制分析绕过-…...

[Markdown] Markdown常用快捷键分类汇总

文章目录 Markdown1、标题2、列表3、强调4、链接和图片5、代码和公式6、表格和任务列表7、引用8、分割线9、脚注10、目录11、注释12、定义 Markdown Markdown是一种轻量级的标记语言&#xff0c;可以让你用简单的语法来编写格式丰富的文档。 Markdown编辑器是一种专门用于编辑…...

uniapp自定义封装只有时分秒的组件,时分秒范围选择

说实话&#xff0c;uniapp和uview的关于只有时分秒的组件实在是不行。全是日历&#xff0c;但是实际根本就不需要日历这玩意。百度了下&#xff0c;终于看到了一个只有时分秒的组件。原地址&#xff1a;原地址&#xff0c;如若侵犯请联系我删除 <template><view clas…...

SpringBoot 中 @Transactional 注解的使用

一、基本介绍 事务管理是应用系统开发中必不可少的一部分。Spring 为事务管理提供了丰富的功能支持。Spring 事务管理分为编程式和声明式的两种方式。本篇只说明声明式注解。 1、在 spring 项目中, Transactional 注解默认会回滚运行时异常及其子类&#xff0c;其它范…...

【还不了解 Dockerfile 的同学不是好测试人】

近年来 Docker 非常火&#xff0c;想要玩好 Docker 的话 Dockerfile 是绕不开的&#xff0c;这就好比想要玩好 Linux 服务器绕不开 shell 道理是一样的。 今天我们就来聊一聊 Dockerfile 怎么写&#xff0c;那些指令到底是什么意思。 前言 一、先来看一个简单的 Dockerfile #这…...

新手一键重装系统Win10步骤教程

如果我们发现电脑上的操作系统出现很严重的问题&#xff0c;不能通过简单的操作解决&#xff0c;这时候就可以选择重新安装电脑系统&#xff0c;快速解决问题。但是&#xff0c;新手用户不具备专业的装机知识&#xff0c;不知道重装Win10系统要怎么操作&#xff1f;那么可以按照…...

Ceph源码分析-在C++中,符号““和“*“有不同的用法。

在C中&#xff0c;符号"&"和"*"有不同的用法。 "&"符号&#xff1a; 在变量声明时&#xff0c;"&"用于定义引用类型。例如&#xff1a;int a 10; int& ref a; 这里的"ref"是一个引用&#xff0c;它引用了…...

Azure AI 内容安全Content Safety Studio实战

Azure AI Content Safety 检测应用程序和服务中用户生成和 AI 生成的有害内容。 Azure AI 内容安全包括文本和图像 API&#xff0c;可用于检测有害材料。 交互式 Content Safety Studio&#xff0c;可用于查看、浏览和试用用于检测不同形式的有害内容的示例代码。 关注TechLead…...

计算机网络学习笔记(四)

文章目录 1.介绍一下HTTPS的流程。2.介绍一下HTTP的失败码。3.说一说你知道的http状态码。4. 301和302有什么区别&#xff1f;5.302和304有什么区别&#xff1f;6. 请描述一次完整的HTTP请求的过程。7.什么是重定向&#xff1f;8. 重定向和请求转发有什么区别&#xff1f;9.介绍…...

typora导出html添加目录

typora导出html添加目录 使用方法 首先要从typora导出html文件&#xff0c;之后用记事本编辑器html文件 找到文档最后面&#xff0c;如图&#xff1a; 用文字编辑类工具打开sideBar.txt&#xff0c;复制其中所有内容【内容在下面】 在如上图的位置插入所复制的内容 打开修改…...

vue3 封装一个按钮组件(可自定义按钮样式)

效果图 鼠标悬浮有对应的文字提示&#xff0c;且图标出现背景色和颜色 实现 目前提供五个固定样式的图标及三个用户自定义的图标&#xff0c;可根据需要补充 组件代码 <script setup lang"ts"> import { onMounted, PropType, reactive, ref, watch } from v…...

Docker 中使用超级用户

在docker中安装keytool产生的问题&#xff1a; sudo apt-get install openjdk-8-jre-headless bash: sudo: command not found elasticsearchd989639e3cb4:~/config/certs$ apt-get install openjdk-8-jre-headless E: Could not open lock file /var/lib/dpkg/lock-frontend …...

git打tag以及拉取tag

场景&#xff1a;某次git代码发布后定版记录&#xff0c;将发版所在的commit时候代码打上tag记录&#xff0c;方便后期切换到对应tag代码位置。 查看所有tag名 git tag// 1.1.0 // 1.0.0查看tag和描述 git tag -l -n//1.0.0 云监管一期项目完结 //1.1.0 …...

TS 36.212 V12.0.0-信道编码、复用和交织(1)-通用过程

本文的内容主要涉及TS 36.212&#xff0c;版本是C00&#xff0c;也就是V12.0.0。...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7

在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤&#xff1a; 第一步&#xff1a; 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为&#xff1a; // 改为 v…...