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

力扣小题，力扣113.路径总和II力扣.111二叉树的最小深度力扣.221最大正方形力扣5.最长回文子串更加优秀的算法:中心扩展算法

news 来源：原创 2025/6/28 9:04:05

力扣113.路径总和II

力扣.111二叉树的最小深度

力扣.221最大正方形

力扣5.最长回文子串

更加优秀的算法:中心扩展算法

力扣113.路径总和II

这道题，让我明白回溯了到底啥意思

之前我找的时候，我一直在想，如果可以，请你对比一下这个代码和下面那个代码

我们这个相当于自动回溯，因为他是引用传递，所以说就不用维护了

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public  List<List<Integer>>ret=new LinkedList<>();public  List<Integer>res=new LinkedList();int targetSum=0;public  List<List<Integer>> pathSum(TreeNode root, int _targetSum) {targetSum=_targetSum;dfs(root,0);return ret;}public  void dfs(TreeNode root,int count){  if(root==null)return;count+=root.val;res.add(root.val);if(count==targetSum&&root.left==null&&root.right==null){ret.add(new LinkedList<>(res));}dfs(root.left,count);dfs(root.right,count);res.removeLast();}
}

这个是错误代码，为什么这个是错误的，上面确实正确的呢，是因为

下面这个我们无法回溯，你回溯要有一个计数器那种，怎么维护这个计数器是关键，我假如使用下面的这个，我们回溯，减法的话，怎么减去呢，我如果使用减法回溯计数器，我就要知道他回溯前的节点是什么，可是我们无法知道回溯前的节点是啥，所以下面这个错误

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public static List<List<Integer>>ret=new LinkedList<>();public static List<Integer>res=new LinkedList();static int count=0;static int targetSum=0;public static List<List<Integer>> pathSum(TreeNode root, int _targetSum) {targetSum=_targetSum;dfs(root);return ret;}public static void dfs(TreeNode root){  if(root==null)return;count+=root.val;res.add(root.val);if(count==targetSum&&root.left==null&&root.right==null){ret.add((List<Integer>) res);}dfs(root.left);dfs(root.right);res.removeLast();}
}

力扣.111二叉树的最小深度

这个正常情况好想，你假如剪枝的话，就不是很好想了，看代码分析，

他的剪枝分在两个地方，第一个到了叶子结点，不再往后遍历，第二个是当前最大深度已经比最小的深度大了，就直接放弃就好了
class Solution {int ans = Integer.MAX_VALUE;public int minDepth(TreeNode root) {if(root == null) {return 0;}dfs(root, 0);return ans;}private void dfs(TreeNode root, int cnt) {if(root == null) {return;}//记录每一层cnt++;if(cnt > ans) {//比最小值大，直接排除return;}//这一步可能就是假如左右端点都为空，那么我就不去遍历了。减去叶子结点的下面（因为我已经到达最下面的节点了。）if(root.left == root.right) {ans = Math.min(ans, cnt);return;}dfs(root.left, cnt);dfs(root.right, cnt);}
}

力扣.221最大正方形

太久没写动规了，回顾一下

我们只需要会一个，也是最难的状态定义

这里定义i,j位置为以i,j为右下角的最大正方形边长

那么初始化这件事不知道你能不能想出来，右下角的话你的最左边一行，和最上边一行是不是都要初始化为1，假如哪个原先位置字符是1的话，你想一下，右下角，你怎么可以拿最左边和最上边为右下角呢

然后他的边长，我是这么想的，你看这个图，假如想要边长变大，是不是，你的左边，上面，以及你的对角线那个位置都要是1，不然你不可能是正方形(或者说，正方形的边长，那么dp[][]这些位置，肯定都要有值

class Solution {public int maximalSquare(char[][] matrix) {int n=matrix.length;int m=matrix[0].length;//dp[i][j] 在i,j位置，包含1的最大正方形,int[][]dp=new int[n][m];for(int i=0;i<n;i++){    if(matrix[i][0]=='1'){dp[i][0]=1;}}for(int j=0;j<m;j++){if(matrix[0][j]=='1'){dp[0][j]=1;}}int maxSide=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(matrix[i][j]=='1'&&(i!=0&&j!=0)){dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;   }maxSide=Math.max(maxSide,dp[i][j]);}}return maxSide*maxSide;}
}

力扣5.最长回文子串

这个题，你首先明确状态转移方程

boolean[][]dp 他是i位置开头，j位置结尾，那我问你，我两边相等，我是不是要检查中间，然后后面就这么些，前面的判断是因为，一个字符，或者两个字符，我可以直接给他判定为回文

  public static String longestPalindrome(String s) {int n=s.length();//dp[i][j]:设置以i位置开头，j位置结尾的dpint len=1;int begin=0;//判断i位置开头，j位置结尾的dp。boolean[][]dp=new boolean[n][n];//检查，从后往前找，因为 [i,j] =[i+1][j-1]for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s.charAt(i)==s.charAt(j)){if(i==j||i+1==j){//a ,aa 两个字符或者一个字符的情况  babaddp[i][j]=true;}else{//中间有字符，接下来看看i+1和j-1这个位置看看，为啥要到这个位置看，我今天才搞明白，// 是因为我需要看你里面是不是回文字符串，假如他俩下标不挨着，那么就看看中间有没有不是回文的//换句话说，计算机思路先检查外面，再检查里面。dp[i][j]=dp[i+1][j-1];}}//假如发现当前i,j位置是true,就说明是回文if(dp[i][j]==true&&j-i+1>len){//随时更新开始值和最长长度len=j-i+1;begin=i;}}}return s.substring(begin,begin+len);}

更加优秀的算法:中心扩展算法

以每个点作为中心去计算他的回文数。

class Solution {public String longestPalindrome(String s) {//中心拓展算法int n=s.length();char[]a=s.toCharArray();String c="";int max=0;for(int i=0;i<n;i++){int left=i-1;int right=i+1;while(left>=0&&right<n){if(a[left]==a[right]){left--;right++; }else{break;}}if(right-left-1>max){c=s.substring(left+1,right);max=right-left-1;}left=i;right=i+1;while(left>=0&&right<n){if(a[left]==a[right]){left--;right++; }else{break;}}if(right-left-1>max){c=s.substring(left+1,right);max=right-left-1;}}return c;}
}

差距不大，算法一致，快了10ms差不多

class Solution {public String longestPalindrome(String s) {//中心拓展算法int n=s.length();char[]a=s.toCharArray();String c="";int max=0;for(int i=0;i<n;i++){int left=i-1;int right=i+1;//我直接 aba 这种while(left>=0&&right<n){//两个相等就不变指针if(a[left]==a[right]){left--;right++; }else{//不等就退出循环break;}}//因为出来的话俩个都是不等，所以   kabac   left=k    right=c 你减一下if(right-left-1>max){c=s.substring(left+1,right);max=right-left-1;}//aa这种left=i;right=i+1;while(left>=0&&right<n){if(a[left]==a[right]){left--;right++; }else{break;}}if(right-left-1>max){c=s.substring(left+1,right);max=right-left-1;}}return c;}
}

力扣小题，力扣113.路径总和II力扣.111二叉树的最小深度力扣.221最大正方形力扣5.最长回文子串更加优秀的算法:中心扩展算法

目录力扣113.路径总和II 力扣.111二叉树的最小深度力扣.221最大正方形力扣5.最长回文子串更加优秀的算法:中心扩展算法力扣113.路径总和II 这道题，让我明白回溯了到底啥意思之前我找的时候，我一直在想，如果可以，请你对比…...

编程日记 2025/6/28 9:04:05

力扣-无重复字符的最长子串

1.题目描述 2.题目链接 LCR 016. 无重复字符的最长子串 - 力扣（LeetCode） 3.题目解析本题中我们还是使用滑动窗口来解决。那么为什么使用滑动窗口来解决呢？ 对于这样一个数组，我们定义双指针都指向数组第一个元素。left表示…...

编程日记 2025/6/26 16:46:20

华为2025年校招笔试真题手撕教程（一）

一、题目输入： 第一行为记录的版本迭代关系个数N，范围是[1，100000]; 第二行到第N1行：每行包含两个字符串，第一个字符串为当前版本，第二个字符串为前序版本，用空格隔开。字符串包含字符个数为…...

编程日记 2025/6/26 17:28:02

VUE 文件下载，流形式的文件下载，判断返回的是流还是JSON；获取下载名称

在前端中，有很多下载文件的情况，在大多数情况下，后端是以流的形式把需要的数据返回给前端，这就有接口报错的情况在里面，如果接口报错，有的后端则会返回一个带有错误信息的JSON给我们，比如下面这…...

编程日记 2025/6/25 3:59:20

Starrocks的CBO基石--统计信息的来源 StatisticAutoCollector

背景本文来从底层代码的实现来分析一下Starrocks怎么获取统计信息，这些统计信息在后续基于CBO的代价计算的时候有着重要的作用本文基于Starrrocks 3.3.5 结论 Starrocks的统计信息的收集是通过周期性的运行一系列的SQL（以分区为维度，如果…...

编程日记 2025/6/27 14:31:14

这个证书可配置么，这个配置不是需要在API里面配置吧，AT指令应该是不支持的吧

AT 固件里调这个 CA_ID 只能填 0，也就是说 AT 命令目前并不支持在线下发或替换 CA 证书。ESP-AT 的做法是：在编译/烧录阶段就把 CA 根证书刷入到 Flash（或 SPIFFS/WL）里的固定分区里，CA_ID 永远指向那一套证书&#xf…...

编程日记 2025/6/27 14:06:09

Python训练打卡Day31

文件的规范拆分和写法知识点回顾规范的文件命名规范的文件夹管理机器学习项目的拆分编码格式和类型注解把一个文件，拆分成多个具有着独立功能的文件，然后通过import的方式，来调用这些文件。 1. 可以让项目文件变得更加规范和清晰 2. 可以让…...

编程日记 2025/6/26 14:21:01

前端性能优化的秘密武器：Preload 与 Prefetch 的深度解析

前端性能优化的秘密武器：Preload 与 Prefetch 的深度解析在前端开发中，页面加载速度直接影响用户体验和业务转化率。而“资源预加载”技术，正是优化加载性能的核心手段之一。本文将深入浅出地讲解 Preload 与 Prefetch 这两项技术&#xff…...

编程日记 2025/6/25 7:05:30

DAY8字典的简单介绍

字典的简单介绍字典就是键值对标签编码实现映射操作 import pandas as pd data pd.read_csv(data.csv) data data["Home Ownership"].value_counts() # 定义映射字典 mapping {"Own Home": 1,"Rent": 0,"Have Mortgage": 2,&…...

编程日记 2025/6/27 2:46:42

VPLC (VPLCnext) K8S

前序在接触Virtual PLCnext Control的时候，我想过好几次如何将它运行在k8s上，由于对k8s的熟悉程度不够，跌跌撞撞尝试了很久，终于把vPLC部署在单机版的k8s上了。（此教程仅为demo阶段，此教程仅为demo阶段&a…...

编程日记 2025/6/25 5:26:07

鸿蒙App开发学习路径

以下是一份系统的鸿蒙（HarmonyOS）App开发学习路径，适合从零开始逐步掌握相关技能： 1. 基础知识储备 1.1 理解鸿蒙系统鸿蒙核心特性：分布式能力、一次开发多端部署、原子化服务、ArkUI框架。与Android/iOS的区别&…...

编程日记 2025/6/27 22:47:17

【Java多态】：灵活编程的核心

🎁个人主页：User_芊芊君子 🎉欢迎大家点赞👍评论📝收藏⭐文章 🔍系列专栏：【Java】内容概括【前言】在Java面向对象编程的世界中，多（Polymorphism） 是一个核…...

编程日记 2025/6/27 23:34:15

k8s容器入门（1）有状态服务 vs 无状态服务核心区别

本质区别维度有状态服务 (Stateful)无状态服务 (Stateless)数据存储服务内部维护持久化数据不保存客户端会话数据请求关联性后续请求依赖之前请求的状态每个请求独立处理典型示例数据库/消息队列/文件存储Web API/计算服务/负载均衡技术实现对比 #mermaid-svg-hoKO2gnZ8Gvms…...

编程日记 2025/6/27 23:18:13

BERT框架：自然语言处理的革命性突破

引言在自然语言处理（NLP）领域，2018年Google推出的BERT（Bidirectional Encoder Representations from Transformers）框架无疑是一场革命。作为基于Transformer架构的双向编码器表示模型，BERT通过预训练学习…...

编程日记 2025/6/27 23:02:59

基于FPGA控制电容阵列与最小反射算法的差分探头优化设计

在现代高速数字系统测试中，差分探头的信号完整性直接影响测量精度。传统探头存在阻抗失配导致的信号反射问题，本文提出一种通过FPGA动态控制电容阵列，结合最小反射算法的优化方案，可实时调整探头等效容抗，将信号反射损…...

编程日记 2025/6/27 16:02:47

珠宝课程小程序源码介绍

这款珠宝课程小程序源码，基于ThinkPHPFastAdminUniApp开发，功能丰富且实用。ThinkPHP提供稳定高效的后台服务，保障数据安全与处理速度；FastAdmin助力快速搭建管理后台，提升开发效率；UniApp则让小程序能多端…...

编程日记 2025/6/27 22:47:24

DAY33

简单的神经网络 PyTorch和cuda的安装查看显卡信息的命令行命令（cmd中使用） cuda的检查简单神经网络的流程 1.数据预处理（归一化、转换成张量） 2.模型的定义 1.继承nn.Module类 2.定…...

编程日记 2025/6/27 23:25:54

AI相关的笔记

推荐视频： https://www.bilibili.com/video/BV1aeLqzUE6L/?share_sourcecopy_web&vd_source3d0a14a267c9cbda8f2a6184dd8c564d AI Agent AI Agent（人工智能代理） AI Agent 是一种具备自主决策和执行能力的智能程序，能够像…...

编程日记 2025/6/27 3:02:10

Python训练营---Day33

知识点回顾： PyTorch和cuda的安装查看显卡信息的命令行命令（cmd中使用）cuda的检查简单神经网络的流程数据预处理（归一化、转换成张量）模型的定义继承nn.Module类定义每一个层定义前向传播流程定义损失函数和优化器定…...

编程日记 2025/6/27 23:00:55

window 显示驱动开发-指定 GDI 硬件加速渲染操作

调用 DxgkDdiRenderKm 函数时，操作系统指定要通过 pRenderKmArgs 参数执行的 GDI 硬件加速呈现操作的类型。 DirectX 图形内核子系统的显示端口驱动程序 (Dxgkrnl.sys) 将 pRenderKmArgs-pCommand> 成员设置为指向包含可变大小DXGK_RENDERKM_COMMAND结构数组的命…...

编程日记 2025/6/27 22:47:18

什么是VR展馆？VR展馆的实用价值有哪些？

VR展馆，重塑展览体验。在数字化时代浪潮的推动下，传统的实体展馆经历前所未有的变革。作为变革的先锋，VR展馆以无限的潜力，成为展览行业的新宠。 VR展馆，即虚拟现实展馆，是基于VR（Virtual Real…...

编程日记 2025/6/27 23:28:06

uniapp实现H5、APP、微信小程序播放.m3u8监控视频

目录 1.APP播放.m3u8监控视频 2.H5播放.m3u8监控视频 3.微信小程序播放.m3u8监控视频最近在写一个uniapp实现h5、app、微信小程序兼容三端的播放监控视频功能，我原本以为一套代码多处运行，但事实并非如此，h5可以运行，微信小程…...

编程日记 2025/6/27 23:12:57

CAD如何导出PDF？PDF如何转CAD？详细教程来了

浩辰CAD看图王是一款功能强大的CAD图纸查看与编辑工具，其核心功能之一便是支持CAD与PDF格式的互转。下面是CAD看图王输出PDF和PDF转CAD功能的详细介绍及操作步骤： 一、输出PDF功能看图王可以将CAD图纸转换为PDF格式，是文件在不同的设备上显…...

编程日记 2025/6/27 23:15:09

微信小程序学习基础：从入门到精通

文章目录第一章：微信小程序概述1.1 什么是微信小程序1.2 小程序与原生APP、H5的区别1.3 小程序的发展历程与现状第二章：开发环境搭建2.1 注册小程序账号2.2 安装开发者工具2.3 开发者工具界面介绍2.4 第一个小程序项目第三章：小程序框架与…...

编程日记 2025/6/27 23:17:05

[免费]微信小程序宠物医院管理系统(uni-app+SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好，我是java1234_小锋老师，看到一个不错的微信小程序宠物医院管理系统(uni-appSpringBoot后端Vue管理端)，分享下哈。项目视频演示【免费】微信小程序宠物医院管理系统(uni-appSpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibi…...

编程日记 2025/6/27 22:47:19

乘最多水的容器 | 算法 | 给定一个整数数组。有n条垂线。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

在我们日常生活中，蓄水似乎是一个极为朴素的物理行为：两堵墙之间，注入水，看谁能装得更多。可如果换个角度，从算法的视角去看这个问题，它会变得怎样？你是否意识到，这样一个简单的问题…...

编程日记 2025/6/27 8:52:54

英伟达有意入股 PsiQuantum，释放战略转向量子计算的重要信号

内容来源：量子前哨（ID：Qforepost） 文丨浪味仙排版丨浪味仙行业动向：1800字丨5分钟阅读 “十五年太早，三十年又太晚，但如果说二十年，我想很多人都会相信。” emmmm&#xff0c…...

编程日记 2025/6/27 15:31:22

【Ubuntu修改串口延时(Latency Timer)为1毫秒(设备拔插或系统重启后自动生效)】

Ubuntu修改串口延时Latency Timer为1毫秒-设备拔插或系统重启后自动生效在Ubuntu系统中，串口设备的延时参数(latency_timer)可以通过udev规则永久修改。以下是完整步骤： 创建udev规则文件 sudo vim /etc/udev/rules.d/99-ftdi-low-latency.rules添加以…...

编程日记 2025/6/27 23:40:38

《量子计算实战》PDF下载

内容简介在加密、科学建模、制造物流、金融建模和人工智能等领域，量子计算可以极大提升解决问题的效率。量子系统正变得越来越强大，逐渐可用于生产环境。本书介绍了量子计算的思路与应用，在简要说明与量子相关的科学原理之后，指…...

编程日记 2025/6/27 23:27:18

Win 系统 conda 如何配置镜像源

通过命令添加镜像源（推荐） 以清华源为例，依次执行以下命令： # 添加主镜像源 conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/main # 添加免费开源镜像源 conda config --add channels http…...

编程日记 2025/6/27 23:32:27

[密码学实战]使用C语言实现TCP服务端（二十九）

[密码学实战]使用C语言实现TCP服务端（二十九）引言 TCP（传输控制协议）是互联网通信中最核心的协议之一，它提供可靠的、面向连接的数据传输服务。通过C语言的标准Socket API，开发者可以灵活地实现TCP客户端和服务端程序。本文将详细讲解TCP通信的原理，并提供完整的代码…...

编程日记 2025/6/27 0:28:20

打卡Day34

问题： 背景： 剩余时长总时长 - 必须的计算时长（3秒）。记录间隔、记录次数和剩余时长的关系需要进一步分析。数据观察： 当总epoch为20000时，不同记录间隔对应的记录次数和剩余时长如下： 记…...

编程日记 2025/6/27 11:40:58

谷歌开源医疗领域AI语言模型速递：medgemma-27b-text-it

一、模型概述 MedGemma 是由谷歌开发的一个医疗领域 AI 模型系列，基于 Gemma 3 架构，旨在加速医疗保健相关 AI 应用的开发。该模型系列包含两个主要变体：4B 多模态版本（支持文本和图像理解）以及 27B 纯文本版本&#…...

编程日记 2025/6/27 22:58:27

C++ JSON解析技术详解

一、JSON基础与解析流程 1.1 JSON数据结构 JSON包含两种核心结构（）： 对象：{}包裹的键值对集合数组：[]包裹的值序列 1.2 解析流程 flowchart TDA[加载JSON数据] --> B{数据来源}B -->|字符串…...

编程日记 2025/6/27 23:27:40

多维应用场景的落地实践的智慧园区开源了

智慧园区场景视频监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒，省去繁琐重复的适配流程，实现芯片、算法、应用的全流程组合，从而大大减少企业级应用约95%的开发成本。用户只需在界…...

编程日记 2025/6/27 22:47:23

本次参数 llamafactory-cli train \ --stage sft \ --do_train True \ --model_name_or_path /home/qhyz/zxy/LLaMA-Factory/model \ --preprocessing_num_workers 16 \ --finetuning_type lora \ --template deepseek3 \ --flash_attn fa2 \ --dataset_dir data \ --dataset …...

编程日记 2025/6/27 7:43:36

力扣113.路径总和II

力扣.111二叉树的最小深度

力扣.221最大正方形

力扣5.最长回文子串

更加优秀的算法:中心扩展算法

相关文章：