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啦
- 确定dp数组(dp table)以及下标的含义
dp[i][j]就是三角形的第i行第j列的最小路径和 - 确定递推公式
不在三角形的腰上时,路径和由上一行的两个路径和中选更小的
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] - dp数组如何初始化
三角形的两个腰上的值是只能由上一行的腰上的值决定
dp[0][0]=c[0][0] - 确定遍历顺序
从上到小从左到右 - 举例推导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. 求根节点到叶节点数字之和
深度搜索,前序遍历
从根节点开始,遍历每个节点,如果遇到叶子节点,则获得该路径的数字。如果当前节点不是叶子节点,则计算其子节点对应的数字,然后对子节点递归遍历,获得该节点对应的所有路径的数字之和。
- 参数及返回值
因为要用到当前路径到达父节点组成的值,所以参数不仅要当前节点,也需要父节点组成的值presum
返回值是当前节点到叶节点的数字之和,整型 - 终止条件
当前节点为根节点的时候,返回当前值
if(root->left==nullptr&&root->right==nullptr)
return sum;
因为左右节点是空的时候已经判断了,那么整个树的root节点是空的时候,返回0
if(root==nullptr)
return 0; - 单层逻辑
首先计算当前节点对应的数字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 ,请你统计并返回 该数组中和为 k k k 的子数组的个数 。子数组是数组中元素的连续非空序列。 输入:nums [1,2,3], k 3 输出:2 前缀和 1.2如何使用 前缀和的…...
C语言入门教程,C语言学习教程(第一部分:编程基础 )一
C语言是一门面向过程的编译型语言,它的运行速度极快,仅次于汇编语言。C语言是计算机产业的核心语言,操作系统、硬件驱动、关键组件、数据库等都离不开C语言;不学习C语言,就不能了解计算机底层。 这套「C语言入门教程」…...
uniapp微信小程序投票系统实战 (SpringBoot2+vue3.2+element plus ) -用户信息修改实现
锋哥原创的uniapp微信小程序投票系统实战: uniapp微信小程序投票系统实战课程 (SpringBoot2vue3.2element plus ) ( 火爆连载更新中... )_哔哩哔哩_bilibiliuniapp微信小程序投票系统实战课程 (SpringBoot2vue3.2element plus ) ( 火爆连载更新中... )共计21条视频…...
C语言PDF编程书籍下载
[C.Primer.Plus(第6版)中文版].(美)普拉达.扫描版.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 如果是使用的是校园网,可以不连接 2…...
46 WAF绕过-信息收集之反爬虫延时代理池技术
目录 简要本章具体内容和安排缘由简要本课具体内容和讲课思路简要本课简要知识点和具体说明演示案例:Safedog-默认拦截机制分析绕过-未开CCSafedog-默认拦截机制分析绕过-开启CC总结: Aliyun_os-默认拦截机制分析绕过-简要界面BT(防火墙插件)-默认拦截机制分析绕过-…...
[Markdown] Markdown常用快捷键分类汇总
文章目录 Markdown1、标题2、列表3、强调4、链接和图片5、代码和公式6、表格和任务列表7、引用8、分割线9、脚注10、目录11、注释12、定义 Markdown Markdown是一种轻量级的标记语言,可以让你用简单的语法来编写格式丰富的文档。 Markdown编辑器是一种专门用于编辑…...
uniapp自定义封装只有时分秒的组件,时分秒范围选择
说实话,uniapp和uview的关于只有时分秒的组件实在是不行。全是日历,但是实际根本就不需要日历这玩意。百度了下,终于看到了一个只有时分秒的组件。原地址:原地址,如若侵犯请联系我删除 <template><view clas…...
SpringBoot 中 @Transactional 注解的使用
一、基本介绍 事务管理是应用系统开发中必不可少的一部分。Spring 为事务管理提供了丰富的功能支持。Spring 事务管理分为编程式和声明式的两种方式。本篇只说明声明式注解。 1、在 spring 项目中, Transactional 注解默认会回滚运行时异常及其子类,其它范…...
【还不了解 Dockerfile 的同学不是好测试人】
近年来 Docker 非常火,想要玩好 Docker 的话 Dockerfile 是绕不开的,这就好比想要玩好 Linux 服务器绕不开 shell 道理是一样的。 今天我们就来聊一聊 Dockerfile 怎么写,那些指令到底是什么意思。 前言 一、先来看一个简单的 Dockerfile #这…...
新手一键重装系统Win10步骤教程
如果我们发现电脑上的操作系统出现很严重的问题,不能通过简单的操作解决,这时候就可以选择重新安装电脑系统,快速解决问题。但是,新手用户不具备专业的装机知识,不知道重装Win10系统要怎么操作?那么可以按照…...
Ceph源码分析-在C++中,符号““和“*“有不同的用法。
在C中,符号"&"和"*"有不同的用法。 "&"符号: 在变量声明时,"&"用于定义引用类型。例如:int a 10; int& ref a; 这里的"ref"是一个引用,它引用了…...
Azure AI 内容安全Content Safety Studio实战
Azure AI Content Safety 检测应用程序和服务中用户生成和 AI 生成的有害内容。 Azure AI 内容安全包括文本和图像 API,可用于检测有害材料。 交互式 Content Safety Studio,可用于查看、浏览和试用用于检测不同形式的有害内容的示例代码。 关注TechLead…...
计算机网络学习笔记(四)
文章目录 1.介绍一下HTTPS的流程。2.介绍一下HTTP的失败码。3.说一说你知道的http状态码。4. 301和302有什么区别?5.302和304有什么区别?6. 请描述一次完整的HTTP请求的过程。7.什么是重定向?8. 重定向和请求转发有什么区别?9.介绍…...
typora导出html添加目录
typora导出html添加目录 使用方法 首先要从typora导出html文件,之后用记事本编辑器html文件 找到文档最后面,如图: 用文字编辑类工具打开sideBar.txt,复制其中所有内容【内容在下面】 在如上图的位置插入所复制的内容 打开修改…...
vue3 封装一个按钮组件(可自定义按钮样式)
效果图 鼠标悬浮有对应的文字提示,且图标出现背景色和颜色 实现 目前提供五个固定样式的图标及三个用户自定义的图标,可根据需要补充 组件代码 <script setup lang"ts"> import { onMounted, PropType, reactive, ref, watch } from v…...
Docker 中使用超级用户
在docker中安装keytool产生的问题: 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
场景:某次git代码发布后定版记录,将发版所在的commit时候代码打上tag记录,方便后期切换到对应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,版本是C00,也就是V12.0.0。...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
