当前位置: 首页 > 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。...

纯前端上传word,xlsx,ppt,在前端预览并下载成图片(预览效果可以,下载图片效果不太理想)

纯前端上传word,xlsx,ppt,在前端预览并下载成图片&#xff08;预览效果可以&#xff0c;下载图片效果不太理想&#xff09; 一.安装依赖二、主要代码 预览效果链接: https://github.com/501351981/vue-office 插件文档链接: https://501351981.github.io/vue-office/examples/d…...

WPS Office找回丢失的工作文件

WPS office恢复办公文件方法有两种. 1.通过备份中心可以查看近期编辑 office 历史版本进行恢复. 2.缓存备份目录可以查看编辑过的 office 文件的历史版本&#xff0c;新版本 WPS 可以在配置工具-备份清理找到&#xff0c;2019 年旧版本 WPS 可以在新建任意 office 文件-文件-选…...

【MATLAB源码-第106期】基于matlab的SAR雷达系统仿真,实现雷达目标跟踪功能,使用卡尔曼滤波算法。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 1. 雷达系统参数设定&#xff1a; - 工作频率&#xff1a;选择一个适合的工作频率&#xff0c;例如X波段&#xff08;8-12 GHz&#xff09;。 - 脉冲重复频率&#xff08;PRF&#xff09;&#xff1a;设定一个适当的PR…...

【机器学习】scikit-learn机器学习中随机数种子的应用与重现

随机数种子是为了能重现某一次实验生成的随机数而设立的&#xff0c;相同的随机数种子下&#xff0c;生成的随机数序列一样 一、随机数种子基础应用 在python中简单运用随机数种子 import random random.seed(1) a random.sample(range(0,100),10) random.seed(2) b random.…...

欧洲编程语言四巨头

从左往右&#xff0c;依次是 尼克劳斯沃斯 (Niklaus Wirth)&#xff0c;迪杰斯特拉&#xff08;Edsger Dijkstra&#xff09;&#xff0c;霍尔&#xff08;Tony Hoare&#xff09; 尼克劳斯沃斯 (Niklaus Wirth) 瑞士人&#xff0c;一生发明了8种编程语言&#xff0c;其中最著…...

检查密码(字符串)

本题要求你帮助某网站的用户注册模块写一个密码合法性检查的小功能。该网站要求用户设置的密码必须由不少于6个字符组成&#xff0c;并且只能有英文字母、数字和小数点 .&#xff0c;还必须既有字母也有数字。 输入格式&#xff1a; 输入第一行给出一个正整数 N&#xff08;≤…...

Pointnet++改进注意力机制系列:全网首发LSKAttention大核卷积注意力机制 |即插即用,实现有效涨点

简介:1.该教程提供大量的首发改进的方式,降低上手难度,多种结构改进,助力寻找创新点!2.本篇文章对Pointnet++特征提取模块进行改进,加入LSKAttention注意力机制,提升性能。3.专栏持续更新,紧随最新的研究内容。 目录 1.理论介绍 2.修改步骤 2.1 步骤一 2.2 步骤二...

C++常用库函数大小写转换

在我们在编写代码时大小写转换是基础知识&#xff0c;这篇博客将通过介绍C常用库函数来回顾和学习一种不一样的大小写转换 目录 一、islower/isupper函数二、tolower/toupper函数三、ASCLL码 一、islower/isupper函数 islower和isupper函数是C标准库中的字符分类函数&#xff…...

基于springboot+html的汽车销售管理系统设计与实现

基于springboothtml的汽车销售管理系统 &#x1f345; 作者主页 央顺技术团队 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; 前言 随着汽车市场的快速发展&#xff0c;汽车销售企业面临着越来越大的管理…...

pyside6 界面美化库的使用

使用qt_material库&#xff0c;在库中进行导入后&#xff0c;直接使用库提供的皮肤即可非常简单 example&#xff1a; # -*- coding: utf-8 -*- # 使用例子 import sys # from PySide6 import QtWidgets # from PySide2 import QtWidgets from PySide6 import QtWidgets from…...