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。...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
在 Spring Boot 项目里,MYSQL中json类型字段使用
前言: 因为程序特殊需求导致,需要mysql数据库存储json类型数据,因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...
