日拱一卒(18)——leetcode学习记录:二叉树中的伪回文路径
一、题目
给你一棵二叉树,每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的,当它满足:路径经过的所有节点值的排列中,存在一个回文序列。
请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
二、思路
-
理解伪回文路径的概念:
- 首先,我们要明白什么是伪回文路径。对于一条从根节点到叶节点的路径,这条路径上的节点值组成一个序列。如果这个序列可以通过重新排列,变成一个回文序列,那么这条路径就是伪回文路径。
- 回文序列就是正读和反读都一样的序列,比如 "aba" 或 "aabb"。对于我们的问题,节点值范围是 1 到 9,所以我们只需要关注这些数字出现的次数。
- 对于一个序列要成为伪回文序列,其中最多只能有一个数字出现的次数是奇数,其他数字出现的次数都必须是偶数。例如,对于序列 "121",数字 1 出现两次(偶数次),数字 2 出现一次(奇数次),可以重新排列成 "112" 形成回文,所以是伪回文序列;对于序列 "123",三个数字都只出现一次,不满足最多一个数字出现奇数次,所以不是伪回文序列。
-
使用深度优先搜索(DFS)遍历二叉树:
- 我们要遍历二叉树从根节点到所有叶节点的路径。这就像走迷宫一样,从起点(根节点)出发,每次选择一个分支(左子节点或右子节点)走,直到走到终点(叶节点)。
- 在走的过程中,我们要记录下经过的节点值。
- 当到达叶节点时,检查这条路径是否是伪回文路径。
-
记录节点值的出现次数:
- 我们可以使用一个列表(或数组)来记录每个数字(1 到 9)出现的次数。开始时,列表中所有数字的计数都是 0。
- 当我们经过一个节点时,就把该节点值对应的计数加 1。
- 当我们回溯(从叶节点往回走)时,要把这个计数减 1,因为我们要检查其他可能的路径。
-
检查是否是伪回文路径:
- 当到达叶节点时,我们检查记录节点值出现次数的列表。
- 计算列表中出现奇数次的数字的数量。如果这个数量小于等于 1,那么这条路径就是伪回文路径。
具体步骤:
-
开始 DFS 遍历:
- 从根节点开始,将根节点的值对应的计数加 1。
- 然后递归地对左子节点和右子节点进行 DFS 遍历。
- 每次递归调用时,会重复上述加计数的操作。
-
到达叶节点:
- 当到达叶节点时,检查列表中出现奇数次的数字的数量。
- 如果这个数量小于等于 1,说明这条路径是伪回文路径,我们可以将结果加 1。
-
回溯操作:
- 在从叶节点往回走时,要把当前节点值对应的计数减 1,这样可以继续检查其他可能的路径。
三、题解
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
mylist = [0]*10
return self.dfs(mylist,root)
# 递归
def dfs(self,mylist,root):
ans = 0
# 初始条件
if not root:
return 0
mylist[root.val] += 1
if not root.left and not root.right:
ans = int(self.isPalindromic(mylist))
else:
ans = self.dfs(mylist,root.left) + self.dfs(mylist,root.right)
mylist[root.val] -= 1
return ans
def isPalindromic(self,mylist):
odd = 0
for value in mylist:
if value%2 == 1:
odd += 1
return odd <= 1
相关文章:
日拱一卒(18)——leetcode学习记录:二叉树中的伪回文路径
一、题目 给你一棵二叉树,每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的,当它满足:路径经过的所有节点值的排列中,存在一个回文序列。 请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。 二、思路 …...
hive—炸裂函数explode/posexplode
1、Explode炸裂函数 将hive某列一行中复杂的 array 或 map 结构拆分成多行(只能输入array或map) 语法: select explode(字段) as 字段命名 from 表名; 举例: 1)explode(array)使得结果中将array列表里的每个元素生…...
SpringBoot 新特性
优质博文:IT-BLOG-CN 2.1.0新特性最低支持jdk8,支持tomcat9 对响应式编程的支持,spring-boot-starter-webflux starter POM可以快速开始使用Spring WebFlux,它由嵌入式Netty服务器支持 1.5.8 2.1.0/2.7.0/3.0.0 Configuration propertie…...
鸿蒙app封装 axios post请求失败问题
这个问题是我的一个疏忽大意,在这里记录一下。如果有相同问题的朋友,可以借鉴。 当我 ohpm install ohos/axios 后,进行简单post请求验证,可以请求成功。 然后,我对axios 进行了封装。对axios 添加请求拦截器/添加响…...
消息队列 Kafka 架构组件及其特性
Kafka 人们通常有时会将 Kafka 中的 Topic 比作队列; 在 Kafka 中,数据是以主题(Topic)的形式组织的,每个 Topic 可以被分为多个分区(Partition)。每个 Partition 是一个有序的、不可变的消息…...
网络攻击与防范
目录 选填 第一章 1、三种网络模式 2、几种创建网络拓扑结构 NAT模式 VPN模式 软路由模式1 软路由模式2 3、Linux网络配置常用指令 4、常见网络服务配置 DHCP DNS Web服务与FTP服务 FTP用户隔离 第二章 DNS信息收集(dnsenum、dnsmap) 路…...
文献研读|基于像素语义层面图像重建的AI生成图像检测
前言:本篇文章主要对基于重建的AI生成图像检测的四篇相关工作进行介绍,分别为基于像素层面重建的检测方法 DIRE 和 Aeroblade,以及基于语义层面重建的检测方法 SimGIR 和 Zerofake;并对相应方法进行比较。 相关文章:论…...
【操作系统】为什么需要架构裁剪?
为什么需要架构裁剪? 原因 减小核心大小提高架构初始化速度降低内存占用提高系统性能移除不需要的功能,增加安全性 裁剪方法 初始化配置设置功能模块化移除不需要的驱动底层 一般裁剪对象(以操作系统为例) 文件系统的支持网…...
LSTM长短期记忆网络
LSTM(长短期记忆网络)数学原理 LSTM(Long Short-Term Memory)是一种特殊的递归神经网络(RNN),解决了标准RNN中存在的梯度消失(Vanishing Gradient) 和**梯度爆炸&#x…...
基于前端技术UniApp和后端技术Node.js的电影购票系统
文章目录 摘要Abstruct第一章 绪论1.1 研究背景与意义1.2 国内外研究现状 第二章 需求分析2.1 功能需求分析2.2 非功能性需求分析 第二章系统设计3.1 系统架构设计3.1.1 总体架构3.1.2 技术选型 3.2 功能架构 第四章 系统实现4.1 用户端系统实现4.1.1 用户认证模块实现4.1.2 电…...
数据结构与算法:稀疏数组
前言 此文以整型元素的二维数组为例,阐述稀疏数组的思想。其他类型或许有更适合压缩算法或者其他结构的稀疏数组,此文暂不扩展。 稀疏数组的定义 在一个二维数据数组里,由于大量的元素的值为同一个值,比如 0或者其他已知的默认值…...
Meta重磅发布Llama 3.3 70B:开源AI模型的新里程碑
在人工智能领域,Meta的最新动作再次引起了全球的关注。今天,我们见证了Meta发布的Llama 3.3 70B模型,这是一个开源的人工智能模型,它不仅令人印象深刻,而且在性能上达到了一个新的高度。 一,技术突破&#…...
VSCode中的Black Formatter没有生效的解决办法
说明 如果正常按照配置进行的话,理论上是可以生效的。 "[python]": {"editor.defaultFormatter": "ms-python.black-formatter","editor.formatOnSave": true }但我在一种情况下发现不能生效,应为其本身的bug…...
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
目录 背包问题简介 问题描述 输入: 输出: 动态规划解法 动态规划状态转移 代码实现 代码解释 动态规划的时间复杂度 例子解析 输出: 总结 作者我蓝桥杯:2023第十四届蓝桥杯国赛C/C大学B组一等奖,所以请听我…...
Odoo:免费开源ERP的AI技术赋能出海企业电子商务应用介绍
概述 伴随电子商务的持续演进,客户对于便利性、速度以及个性化服务的期许急剧攀升。企业务必要探寻创新之途径,以强化自身运营,并优化购物体验。达成此目标的最为行之有效的方式之一,便是将 AI 呼叫助手融入您的电子商务平台。我们…...
微信小程序苹果手机自带的数字键盘老是弹出收起,影响用户体验,100%解决
文章目录 1、index.wxml2、index.js3、index.wxss1、index.wxml <!--index.wxml--> <view class="container"><view class="code-input-container"><view class="code-input-boxes"><!-- <block wx:for="{{…...
sql中case when若条件重复 执行的顺序
sql case when若条件重复 执行的顺序 在 SQL 中,如果你在 CASE 表达式中定义了多个 WHEN 子句,并且这些条件有重叠,那么 CASE 表达式的执行顺序遵循以下规则: (1)从上到下:SQL 引擎会按照 CASE …...
压力测试Jmeter简介
前提条件:要安装JDK 若不需要了解,请直接定位到左侧目录的安装环节。 1.引言 在现代软件开发中,性能和稳定性是衡量系统质量的重要指标。为了确保应用程序在高负载情况下仍能正常运行,压力测试变得尤为重要。Apache JMeter 是一…...
cesium 与 threejs 对比
Cesium 和 Three.js 都是用于在 Web 浏览器中创建和渲染 3D 图形的强大 JavaScript 库,但它们有显著的不同之处,主要体现在应用领域、功能集和使用场景上。 以下是两者之间的对比: 1. 应用场景 Three.js: 适用于广泛的 3D 图形应用ÿ…...
探索QScreen的信号与槽:动态响应屏幕变化
在处理屏幕显示和多显示器环境时,QScreen 提供了一些特有的信号,这些信号可以在屏幕的变化时通知应用程序,帮助我们动态地适配和响应显示设备的变化。今天,我们将深入探讨如何使用 QScreen 的信号与槽,并展示适用的使用…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
