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

日拱一卒(18)——leetcode学习记录:二叉树中的伪回文路径

一、题目

给你一棵二叉树,每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的,当它满足:路径经过的所有节点值的排列中,存在一个回文序列。

请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。

二、思路

  1. 理解伪回文路径的概念

    • 首先,我们要明白什么是伪回文路径。对于一条从根节点到叶节点的路径,这条路径上的节点值组成一个序列。如果这个序列可以通过重新排列,变成一个回文序列,那么这条路径就是伪回文路径。
    • 回文序列就是正读和反读都一样的序列,比如 "aba" 或 "aabb"。对于我们的问题,节点值范围是 1 到 9,所以我们只需要关注这些数字出现的次数。
    • 对于一个序列要成为伪回文序列,其中最多只能有一个数字出现的次数是奇数,其他数字出现的次数都必须是偶数。例如,对于序列 "121",数字 1 出现两次(偶数次),数字 2 出现一次(奇数次),可以重新排列成 "112" 形成回文,所以是伪回文序列;对于序列 "123",三个数字都只出现一次,不满足最多一个数字出现奇数次,所以不是伪回文序列。
  2. 使用深度优先搜索(DFS)遍历二叉树

    • 我们要遍历二叉树从根节点到所有叶节点的路径。这就像走迷宫一样,从起点(根节点)出发,每次选择一个分支(左子节点或右子节点)走,直到走到终点(叶节点)。
    • 在走的过程中,我们要记录下经过的节点值。
    • 当到达叶节点时,检查这条路径是否是伪回文路径。
  3. 记录节点值的出现次数

    • 我们可以使用一个列表(或数组)来记录每个数字(1 到 9)出现的次数。开始时,列表中所有数字的计数都是 0。
    • 当我们经过一个节点时,就把该节点值对应的计数加 1。
    • 当我们回溯(从叶节点往回走)时,要把这个计数减 1,因为我们要检查其他可能的路径。
  4. 检查是否是伪回文路径

    • 当到达叶节点时,我们检查记录节点值出现次数的列表。
    • 计算列表中出现奇数次的数字的数量。如果这个数量小于等于 1,那么这条路径就是伪回文路径。

具体步骤:

  1. 开始 DFS 遍历

    • 从根节点开始,将根节点的值对应的计数加 1。
    • 然后递归地对左子节点和右子节点进行 DFS 遍历。
    • 每次递归调用时,会重复上述加计数的操作。
  2. 到达叶节点

    • 当到达叶节点时,检查列表中出现奇数次的数字的数量。
    • 如果这个数量小于等于 1,说明这条路径是伪回文路径,我们可以将结果加 1。
  3. 回溯操作

    • 在从叶节点往回走时,要把当前节点值对应的计数减 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学习记录:二叉树中的伪回文路径

一、题目 给你一棵二叉树&#xff0c;每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的&#xff0c;当它满足&#xff1a;路径经过的所有节点值的排列中&#xff0c;存在一个回文序列。 请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。 二、思路 …...

hive—炸裂函数explode/posexplode

1、Explode炸裂函数 将hive某列一行中复杂的 array 或 map 结构拆分成多行&#xff08;只能输入array或map&#xff09; 语法&#xff1a; select explode(字段) as 字段命名 from 表名; 举例&#xff1a; 1&#xff09;explode(array)使得结果中将array列表里的每个元素生…...

SpringBoot 新特性

优质博文&#xff1a;IT-BLOG-CN 2.1.0新特性最低支持jdk8,支持tomcat9 对响应式编程的支持&#xff0c;spring-boot-starter-webflux starter POM可以快速开始使用Spring WebFlux&#xff0c;它由嵌入式Netty服务器支持 1.5.8 2.1.0/2.7.0/3.0.0 Configuration propertie…...

鸿蒙app封装 axios post请求失败问题

这个问题是我的一个疏忽大意&#xff0c;在这里记录一下。如果有相同问题的朋友&#xff0c;可以借鉴。 当我 ohpm install ohos/axios 后&#xff0c;进行简单post请求验证&#xff0c;可以请求成功。 然后&#xff0c;我对axios 进行了封装。对axios 添加请求拦截器/添加响…...

消息队列 Kafka 架构组件及其特性

Kafka 人们通常有时会将 Kafka 中的 Topic 比作队列&#xff1b; 在 Kafka 中&#xff0c;数据是以主题&#xff08;Topic&#xff09;的形式组织的&#xff0c;每个 Topic 可以被分为多个分区&#xff08;Partition&#xff09;。每个 Partition 是一个有序的、不可变的消息…...

网络攻击与防范

目录 选填 第一章 1、三种网络模式 2、几种创建网络拓扑结构 NAT模式 VPN模式 软路由模式1 软路由模式2 3、Linux网络配置常用指令 4、常见网络服务配置 DHCP DNS Web服务与FTP服务 FTP用户隔离 第二章 DNS信息收集&#xff08;dnsenum、dnsmap&#xff09; 路…...

文献研读|基于像素语义层面图像重建的AI生成图像检测

前言&#xff1a;本篇文章主要对基于重建的AI生成图像检测的四篇相关工作进行介绍&#xff0c;分别为基于像素层面重建的检测方法 DIRE 和 Aeroblade&#xff0c;以及基于语义层面重建的检测方法 SimGIR 和 Zerofake&#xff1b;并对相应方法进行比较。 相关文章&#xff1a;论…...

【操作系统】为什么需要架构裁剪?

为什么需要架构裁剪&#xff1f; 原因 减小核心大小提高架构初始化速度降低内存占用提高系统性能移除不需要的功能&#xff0c;增加安全性 裁剪方法 初始化配置设置功能模块化移除不需要的驱动底层 一般裁剪对象&#xff08;以操作系统为例&#xff09; 文件系统的支持网…...

LSTM长短期记忆网络

LSTM&#xff08;长短期记忆网络&#xff09;数学原理 LSTM&#xff08;Long Short-Term Memory&#xff09;是一种特殊的递归神经网络&#xff08;RNN&#xff09;&#xff0c;解决了标准RNN中存在的梯度消失&#xff08;Vanishing Gradient&#xff09; 和**梯度爆炸&#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 电…...

数据结构与算法:稀疏数组

前言 此文以整型元素的二维数组为例&#xff0c;阐述稀疏数组的思想。其他类型或许有更适合压缩算法或者其他结构的稀疏数组&#xff0c;此文暂不扩展。 稀疏数组的定义 在一个二维数据数组里&#xff0c;由于大量的元素的值为同一个值&#xff0c;比如 0或者其他已知的默认值…...

Meta重磅发布Llama 3.3 70B:开源AI模型的新里程碑

在人工智能领域&#xff0c;Meta的最新动作再次引起了全球的关注。今天&#xff0c;我们见证了Meta发布的Llama 3.3 70B模型&#xff0c;这是一个开源的人工智能模型&#xff0c;它不仅令人印象深刻&#xff0c;而且在性能上达到了一个新的高度。 一&#xff0c;技术突破&#…...

VSCode中的Black Formatter没有生效的解决办法

说明 如果正常按照配置进行的话&#xff0c;理论上是可以生效的。 "[python]": {"editor.defaultFormatter": "ms-python.black-formatter","editor.formatOnSave": true }但我在一种情况下发现不能生效&#xff0c;应为其本身的bug…...

【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题

目录 背包问题简介 问题描述 输入&#xff1a; 输出&#xff1a; 动态规划解法 动态规划状态转移 代码实现 代码解释 动态规划的时间复杂度 例子解析 输出&#xff1a; 总结 作者我蓝桥杯&#xff1a;2023第十四届蓝桥杯国赛C/C大学B组一等奖&#xff0c;所以请听我…...

Odoo:免费开源ERP的AI技术赋能出海企业电子商务应用介绍

概述 伴随电子商务的持续演进&#xff0c;客户对于便利性、速度以及个性化服务的期许急剧攀升。企业务必要探寻创新之途径&#xff0c;以强化自身运营&#xff0c;并优化购物体验。达成此目标的最为行之有效的方式之一&#xff0c;便是将 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 中&#xff0c;如果你在 CASE 表达式中定义了多个 WHEN 子句&#xff0c;并且这些条件有重叠&#xff0c;那么 CASE 表达式的执行顺序遵循以下规则&#xff1a; &#xff08;1&#xff09;从上到下&#xff1a;SQL 引擎会按照 CASE …...

压力测试Jmeter简介

前提条件&#xff1a;要安装JDK 若不需要了解&#xff0c;请直接定位到左侧目录的安装环节。 1.引言 在现代软件开发中&#xff0c;性能和稳定性是衡量系统质量的重要指标。为了确保应用程序在高负载情况下仍能正常运行&#xff0c;压力测试变得尤为重要。Apache JMeter 是一…...

cesium 与 threejs 对比

Cesium 和 Three.js 都是用于在 Web 浏览器中创建和渲染 3D 图形的强大 JavaScript 库&#xff0c;但它们有显著的不同之处&#xff0c;主要体现在应用领域、功能集和使用场景上。 以下是两者之间的对比&#xff1a; 1. 应用场景 Three.js: 适用于广泛的 3D 图形应用&#xff…...

探索QScreen的信号与槽:动态响应屏幕变化

在处理屏幕显示和多显示器环境时&#xff0c;QScreen 提供了一些特有的信号&#xff0c;这些信号可以在屏幕的变化时通知应用程序&#xff0c;帮助我们动态地适配和响应显示设备的变化。今天&#xff0c;我们将深入探讨如何使用 QScreen 的信号与槽&#xff0c;并展示适用的使用…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...

UE5 音效系统

一.音效管理 音乐一般都是WAV,创建一个背景音乐类SoudClass,一个音效类SoundClass。所有的音乐都分为这两个类。再创建一个总音乐类&#xff0c;将上述两个作为它的子类。 接着我们创建一个音乐混合类SoundMix&#xff0c;将上述三个类翻入其中&#xff0c;通过它管理每个音乐…...