【题解】—— LeetCode一周小结53

devtools/2025/1/12 6:53:03/

🌟欢迎来到 我的博客 —— 探索技术的无限可能!


🌟博客的简介(文章目录)

在这里插入图片描述


【题解】—— 每日一道题目栏


上接:【题解】—— LeetCode一周小结52

30.二叉树中的链表

题目链接:1367. 二叉树中的链表

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中,存在一条一直向下的路径,且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值,那么请你返回 True ,否则返回 False 。

一直向下的路径的意思是:从树中某个节点开始,一直连续向下的路径。

示例 1:

在这里插入图片描述

输入:head = [4,2,8], root =
[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

输出:true

解释:树中蓝色的节点构成了与链表对应的子路径。

示例 2:

在这里插入图片描述

输入:head = [1,4,2,6], root =
[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

输出:true

示例 3:

输入:head = [1,4,2,6,8], root =
[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

输出:false

解释:二叉树中不存在一一对应链表的路径。

提示:

二叉树和链表中的每个节点的值都满足 1 <= node.val <= 100 。

链表包含的节点数目在 1 到 100 之间。

二叉树包含的节点数目在 1 到 2500 之间。

题解:
方法:暴力匹配
        

class Solution {private ListNode head;public boolean isSubPath(ListNode head, TreeNode root) {this.head = head;return dfs(head, root);}private boolean dfs(ListNode s, TreeNode t) {if (s == null) { // 整个链表匹配完毕return true;}// 否则需要继续匹配if (t == null) { // 无法继续匹配return false;}// 节点值相同则继续匹配,否则从 head 开始重新匹配return s.val == t.val && (dfs(s.next, t.left) || dfs(s.next, t.right)) ||s == head && (dfs(head, t.left) || dfs(head, t.right));}
} 

31.切蛋糕的最小总开销 II

题目链接:3219. 切蛋糕的最小总开销 II

有一个 m x n 大小的矩形蛋糕,需要切成 1 x 1 的小块。

给你整数 m ,n 和两个数组:

horizontalCut 的大小为 m - 1 ,其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。
verticalCut 的大小为 n - 1 ,其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。
一次操作中,你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一:

沿着水平线 i 切开蛋糕,开销为 horizontalCut[i] 。
沿着垂直线 j 切开蛋糕,开销为 verticalCut[j] 。
每次操作后,这块蛋糕都被切成两个独立的小蛋糕。

每次操作的开销都为最开始对应切割线的开销,并且不会改变。

请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。

示例 1:

输入:m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]

输出:13

解释:

在这里插入图片描述

沿着垂直线 0 切开蛋糕,开销为 5 。

沿着水平线 0 切开 3 x 1 的蛋糕块,开销为 1 。

沿着水平线 0 切开 3 x 1 的蛋糕块,开销为 1 。

沿着水平线 1 切开 2 x 1 的蛋糕块,开销为 3 。

沿着水平线 1 切开 2 x 1 的蛋糕块,开销为 3 。

总开销为 5 + 1 + 1 + 3 + 3 = 13 。

示例 2:

输入:m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

输出:15

解释:

沿着水平线 0 切开蛋糕,开销为 7 。

沿着垂直线 0 切开 1 x 2 的蛋糕块,开销为 4 。

沿着垂直线 0 切开 1 x 2 的蛋糕块,开销为 4 。

总开销为 7 + 4 + 4 = 15 。

提示:

1 <= m, n <= 105

horizontalCut.length == m - 1

verticalCut.length == n - 1

1 <= horizontalCut[i], verticalCut[i] <= 103

题解:
方法:最小生成树
        

class Solution {public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {Arrays.sort(horizontalCut); // 下面倒序遍历Arrays.sort(verticalCut);long ans = 0;int i = 0;int j = 0;while (i < m - 1 || j < n - 1) {if (j == n - 1 || i < m - 1 && horizontalCut[i] < verticalCut[j]) {ans += horizontalCut[i++] * (n - j); // 上下连边} else {ans += verticalCut[j++] * (m - i); // 左右连边}}return ans;}
} 

未完待续


http://www.ppmy.cn/devtools/149811.html

相关文章

【云计算】OpenStack云计算平台

OpenStack云计算平台框架搭建 1.先换源 先换成阿里源: curl -o /etc/yum.repos.d/CentOS-Base.repo http://mirrors.aliyun.com/repo/Centos-7.repo 2.安装框架 yum -y install centos-release-openstack-train 3.安装客户端 yum -y install python-openstackclient 但…

C# 告别FirstOrDefault

一、开篇&#xff1a;FirstOrDefault 的 “江湖地位” 在 C# 编程的世界里&#xff0c;FirstOrDefault 可谓是一位 “常客”&#xff0c;被广大开发者频繁地运用在各种项目场景之中。无论是 Windows 窗体应用程序&#xff0c;需要从数据集中检索第一条记录&#xff0c;或是满足…

UE5 打包项目

UE5 打包项目 flyfish 通过 “文件”->“打开项目”&#xff0c;然后在弹出的对话框中选择项目文件&#xff08;通常是以.uproject为后缀的文件&#xff09; 选择目标平台&#xff1a; 在 UE5 主界面中&#xff0c;找到 “平台”&#xff08;Platforms&#xff09;。根据…

Flutter:吸顶效果

在分页中&#xff0c;实现tab吸顶。 TDNavBar的screenAdaptation: true, 开启屏幕适配。 该属性已自动对不同手机状态栏高度进行适配。我们只需关注如何实现吸顶。 view import package:ducafe_ui_core/ducafe_ui_core.dart; import package:flutter/material.dart; import p…

Shader->LinearGradient线性渐变着色器详解

XML文件 <com.example.myapplication.MyViewxmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_gravity"center"android:layout_height"400dp"/>自定义View代码 c…

鸿蒙UI(ArkUI-方舟UI框架)

参考&#xff1a;https://developer.huawei.com/consumer/cn/doc/harmonyos-guides-V13/arkts-layout-development-overview-V13 ArkUI简介 ArkUI&#xff08;方舟UI框架&#xff09;为应用的UI开发提供了完整的基础设施&#xff0c;包括简洁的UI语法、丰富的UI功能&#xff…

hive在大数据体系里面起到什么作用

数据存储与管理方面 核心作用&#xff1a;Hive 是基于 Hadoop 的数据仓库工具&#xff0c;它提供了一种将结构化数据存储在分布式文件系统&#xff08;如 HDFS&#xff09;中的方式。在大数据体系中&#xff0c;数据量往往非常庞大&#xff0c;传统的数据库系统很难有效存储和管…

ip归属地和手机号是一个地址吗

IP归属地和手机号是两个常被提及但本质上截然不同的概念。它们各自代表着不同的信息&#xff0c;反映了不同的技术和应用场景。本文将从定义、原理、应用场景以及两者之间的关系等方面&#xff0c;详细探讨IP归属地和手机号是否是一个地址的问题。 一、IP归属地和手机号的定义 …