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

涂色不踩雷：如何优雅解决 LeetCode 栅栏涂色问题

news 来源：原创 2025/6/18 8:54:41

在这里插入图片描述

文章目录

- 摘要
- 描述
- - 例子：
- 题解答案（Swift）
- 题解代码分析
- - 动态规划核心思路
  - 初始条件
- 示例测试及结果
- - 示例 1：
  - 示例 2：
  - 示例 3：
- 时间复杂度
- 空间复杂度
- 总结
- 实际场景联系

摘要

在用户体验和界面设计中，颜色搭配是个绕不开的核心问题。而在 LeetCode 的一道经典题目「栅栏涂色」中，系统地将这个看似简单的“上色”问题转化为一道有趣的动态规划挑战。今天我们就用 Swift 带你一探这个问题背后的“涂色学”，并分析它的数学规律、代码实现以及实际意义。

描述

题目大意很简单：你要给一排 n 根栅栏涂色。你一共有 k 种颜色可以选择，但有一个限制条件：不能有超过两根相邻的栅栏使用同一种颜色。

你需要返回总共有多少种不同的涂色方法。

例子：

输入: n = 3, k = 2
输出: 6
解释:
可能的涂色方式如下：
1. 红 红 蓝
2. 红 蓝 红
3. 红 蓝 蓝
4. 蓝 蓝 红
5. 蓝 红 蓝
6. 蓝 红 红

题解答案（Swift）

这个题目是动态规划的典型题，我们需要考虑状态转移和子问题的划分。简单来说，我们要区分两种情况：

same: 最后两根栅栏颜色相同
diff: 最后两根栅栏颜色不同

根据这两个状态，我们可以构造出一个高效的递推公式。

func numWays(_ n: Int, _ k: Int) -> Int {if n == 0 { return 0 }if n == 1 { return k }var same = 0var diff = kvar total = same + difffor _ in 2...n {same = diffdiff = total * (k - 1)total = same + diff}return total
}

题解代码分析

动态规划核心思路

我们用 same 表示前两根栅栏颜色相同的方案数，diff 表示前两根颜色不同的方案数。总方案数就是这两者之和。

递推关系如下：

当前的 same = diff（因为如果前一轮是不同色的，当前这一轮就可以延续相同颜色）
当前的 diff = total * (k - 1)（从上一个状态的所有组合中选择不同的颜色）

我们每轮都更新这两个变量，直到涂完 n 根栅栏。

初始条件

当 n = 1，只有 k 种可能。
当 n = 2，我们可以有：
- 相同颜色：k（比如红红、蓝蓝）
- 不同颜色：k * (k - 1)（比如红蓝、蓝红）

示例测试及结果

示例 1：

let result = numWays(3, 2)
print(result)  // 输出: 6

这个结果就跟题目中的例子一致，一共 6 种组合。

示例 2：

let result = numWays(1, 3)
print(result)  // 输出: 3

只有一根栅栏，那就直接从三种颜色里选一种。

示例 3：

let result = numWays(4, 3)
print(result)  // 输出: 66

解释较复杂，但动态规划会自动帮你计算出来所有组合。

时间复杂度

O(n)
我们遍历一遍从 2 到 n，所以时间复杂度是线性的。

空间复杂度

O(1)
我们只用了几个变量，没有额外数组存储，空间复杂度为常数级。

总结

这个问题虽然看起来像是简单的排列组合，但真正下手的时候会发现，不加限制的排列很容易，但加了“不能超过两个相同颜色”的规则后就变得有点挑战性了。

动态规划的好处就是可以把问题拆成更小的部分，一步步向目标推进。在这题中，理解 same 和 diff 这两个状态是关键。

实际场景联系

想象你是个装修师傅，客户让你刷墙，说每面墙可以选择多种颜色，但不希望连续三面墙刷成一样的颜色（太单调了）。你要怎么安排？其实就是这道题！

或者你是个前端开发者，在设计界面时，需要生成用户界面卡片颜色的方案，同样不能让相邻部分颜色一致。解决方法也就是应用这种动态递推模型。

涂色不踩雷：如何优雅解决 LeetCode 栅栏涂色问题

文章目录摘要描述例子： 题解答案（Swift）题解代码分析动态规划核心思路初始条件示例测试及结果示例 1：示例 2：示例 3： 时间复杂度空间复杂度总结实际场景联系摘要在用户体验和界面设计中，颜…...

编程日记 2025/5/29 12:06:27

WL-G4048 Multi-Port PCIe 4.0 Switch

系列文章目录文章目录系列文章目录《WL-G4048 Multi-Port PCIe 4.0 Switch数据手册》总结一、芯片介绍二、芯片规格介绍（一）功能指标（二）管理调试和监控（三）参考时钟（四）系统复位 …...

编程日记 2025/6/2 3:47:24

基于Huber函数和最大相关熵的抗差滤波算法

最大熵滤波（Maximum Entropy Filtering）常用于信号处理中的谱估计和噪声抑制，尤其适用于短数据序列的高分辨率谱分析。一、最大熵滤波算法原理核心思想：在满足已知自相关函数约束的条件下，使信号的熵最大化。数学形…...

编程日记 2025/5/28 7:53:22

力扣-39.组合总和

题目描述给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合 ，并以列表形式返回。你可以按任意顺序返回这些组合。 candidates 中的同一个数字可以无限制重复被…...

编程日记 2025/5/27 7:45:21

医学图像分析中的大规模基准测试与增强迁移学习|文献速递-深度学习医疗AI最新文献

Title 题目 Large-scale benchmarking and boosting transfer learning for medical imageanalysis 医学图像分析中的大规模基准测试与增强迁移学习 01 文献速递介绍将在大规模摄影数据集（如ImageNet）上预训练的模型微调至医学图像领域&#xff08…...

编程日记 2025/5/29 20:00:55

深入浅出横向联邦学习、纵向联邦学习、联邦迁移学习

深入浅出解析横向联邦学习（Horizontal Federated Learning）、纵向联邦学习（Vertical Federated Learning）和联邦迁移学习（Federated Transfer Learning） 有多个机构（比如几家不同的银行&#x…...

编程日记 2025/5/29 12:46:14

vue复杂数据类型多层嵌套的监听

vue复杂数据类型多层嵌套的监听本来看前辈的做法是watch的嵌套，遇到这种复杂的数据结构还是不多，分享一下前辈的做法 let stopChildWatchList [] // 用于存放每个子监听器watch(() > data,(val) > {// 清除旧监听stopChildWatchList.forEach(…...

编程日记 2025/5/27 7:50:31

windows系统中下载好node无法使用npm

原因是 Windows PowerShell禁用导致的npm无法正常使用解决方法管理员打开Windows PowerShell 输入Set-ExecutionPolicy -Scope CurrentUser RemoteSigned 按Y 确认就解决了...

编程日记 2025/5/29 15:58:33

使用 Docker 部署 React + Nginx 应用教程

目录 1. 创建react项目结构2. 创建 .dockerignore3. 创建 Dockerfile4. 创建 nginx.conf5. 构建和运行6. 常用命令 1. 创建react项目结构 2. 创建 .dockerignore # 依赖目录 node_modules npm-debug.log# 构建输出 dist build# 开发环境文件 .git .gitignore .env .env.local …...

编程日记 2025/5/29 12:49:44

顶层设计-IM系统架构

一、系统总体架构概览即时通讯（IM）系统的核心目标，是让用户可以随时随地稳定地发送和接收消息。为了支撑成千上万用户同时在线交流，我们需要将整个系统划分成多个专职模块，每个模块只负责一件事情，彼此协同…...

编程日记 2025/5/29 17:52:46

Maven Deploy的依赖与引用方的依赖不同

提供的依赖：dependency:tree - com.alibaba.csp:sentinel-springboot-starter:jar:3.0.1-SNAPSHOT:compile [INFO] | - com.alibaba.csp:sentinel-datasource-nacos:jar:3.0.1:compile [INFO] | - com.alibaba.csp:sentinel-datasource-extension:jar:3.0.1:compil…...

编程日记 2025/5/27 17:37:22

如何让 Google 收录 Github Pages 个人博客

版权归作者所有，如有转发，请注明文章出处：https://cyrus-studio.github.io/blog/ 如何确认自己的网站有没有被 google 收录假设网址是：https://cyrus-studio.github.io/blog 搜索：site:https://cyrus-studio.github…...

编程日记 2025/5/28 14:44:00

物体雅克比、空间雅克比、解析雅克比、几何雅克比

在机器人学中，雅可比矩阵是连接广义坐标速度与末端执行器速度的关键工具。根据应用场景和参考系的不同，雅可比矩阵可分为物体雅可比（Body Jacobian）、空间雅可比（Space Jacobian）、解析雅可比（A…...

编程日记 2025/5/29 17:28:53

PCL PolygonMesh 与 TextureMesh 源码阅读与简单测试

Title: PCL PolygonMesh 与 TextureMesh 源码阅读与简单测试文章目录 I . PolygonMesh1. PolygonMesh 结构体2. Vertices 结构体与点云索引3. 测试 PolygonMesh II. TextureMesh1. TextureMesh 结构体2. TexMaterial 结构体3. 纹理坐标与纹理坐标索引4. 测试 TextureMesh 以下…...

编程日记 2025/5/27 5:24:23

CSS面试题汇总

在前端开发领域，CSS 是一项不可或缺的技术。无论是页面布局、样式设计还是动画效果，CSS 都扮演着重要的角色。因此，在前端面试中，CSS 相关的知识点往往是面试官重点考察的内容。为了帮助大家更好地准备面试，本文汇总了…...

编程日记 2025/5/29 16:49:00

光谱相机的空间分辨率和时间分辨率

一、空间分辨率 ‌定义与参数‌ ‌概念‌：指单个像素对应实际地物的最小尺寸，常用地面采样距离（GSD，单位：米）或像素大小（单位：微米）表示。 ‌分类‌： 高空…...

编程日记 2025/5/29 9:39:30

【研0学习计划表】

前言以下学习计划并不固定： 1.若当前阶段的学习任务学习结束，对下一阶段的学习计划进行适当调整，提前进入下一阶段学习任务。若当前阶段学习任务未完成，则根据每一阶段的学习情况，进行学习总结，然后对下…...

编程日记 2025/5/28 16:13:59

还没用过智能文档编辑器吗?带有AI插件的ONLYOFFICE介绍

在当今激烈的数字化竞争中，文档处理效率直接影响企业的决策与响应速度。然而，许多办公平台仅支持基础流程，查阅、批注和修改仍需借助外部工具，增加了操作复杂性和沟通成本。本文将探讨如何在自己的网站、平台、系统或者服务中集成…...

编程日记 2025/5/27 6:49:29

机器学习前言2

1.机器学习 2.机器学习模型 3.模型评价方法 4.如何选择合适的模型介绍机器学习（Machine Learning, ML）是人工智能（AI）的核心分支，致力于通过数据和算法让计算机系统自动“学习”并改进性能，而无需显式编…...

编程日记 2025/5/27 7:46:49

在多个SpringBoot程序中./相对路径下隐患、文件覆盖问题

概述两个 Spring Boot 应用生成的配置文件被覆盖，是因为相对路径的解析依赖于当前工作目录（Working Directory），而你可能在运行应用时未正确设置各自的工作目录。以下是具体原因和解决方案： 原因分析相对路径…...

编程日记 2025/5/29 15:01:24

弦理论的额外维度指的是什么，宇宙中有何依据

弦理论中的额外维度是解释微观世界与宏观宇宙矛盾的关键假设之一。它们并非科幻中的平行宇宙，而是通过严谨的数学框架提出，并可能留下可观测的宇宙学痕迹。以下是具体解析： 一、弦理论为何需要额外维度？ 数学自洽性要求弦理论中…...

编程日记 2025/6/1 9:12:24

FC7300 GPT MCAL 配置引导

一、配置约束 FCPIT：仅FC7240型号芯片支持。如果GPT模块与PWM/ICU/OCU模块使用相同的FTU实例，配置工具将报告一个错误。如果GPT通道使用FTU，时钟源来自PCC，则GptFtuChannelClkSrc必须选择GPT_FTU_BUS_CLK。二、MCU 组件 - 配置WDG采用的定时器时钟 Examle:WDG选用AONTIMER…...

编程日记 2025/5/28 8:02:32

LangFlow技术深度解析：可视化编排LangChain应用的新范式 -（2）流编辑器系统

Flow Editor System | langflow-ai/langflow | DeepWiki 流编辑器系统相关源文件流编辑器系统是 Langflow 的核心交互式组件，允许用户直观地创建、编辑和管理 LLM 驱动的应用程序。它提供了一个直观的画布，用户可以在其中添加节点、将其与边缘连接并…...

编程日记 2025/5/28 16:45:10

okcc呼叫中心系统搭建的方案方式

传统企业呼叫中心多采用 PC和手机软件，很难与客户保持良好的沟通。因此，需要建设一套呼叫中心系统来实现与客户实时有效沟通。那么，呼叫中心搭建的方案方式有哪些呢?下面详细介绍一下。呼叫中心系统的搭建方式需根据企业规模、预算和业务需…...

编程日记 2025/5/29 14:35:46

asp.net IHttpHandler 对分块传输编码的支持,IIs web服务器后端技术

IHttpHandler，不支持分块传输编码（Chunked Transfer）吧？ IHttpHandler 对分块传输编码的支持实际上，IHttpHandler 完全支持分块传输编码（Chunked Transfer Encoding），但具体行为取…...

编程日记 2025/5/27 8:29:51

芍药BAHD酰基转移酶-文献精读128

PoDPBT, a BAHD acyltransferase, catalyses the benzoylation in paeoniflorin biosynthesis in Paeonia ostii PoDPBT，一种BAHD酰基转移酶，在芍药（Paeonia ostii）中催化芍药苷生物合成中的苯甲酰化反应。摘要 PoDPBT是属于BA…...

编程日记 2025/5/31 3:06:16

GTS-400 系列运动控制器板卡介绍（三十三）---运动程序单线程累加求和

运动控制器函数库的使用运动控制器驱动程序、dll 文件、例程、Demo 等相关文件请通过固高科技官网下载，网址为：www.googoltech.com.cn/pro_view-3.html 1 Windows 系统下动态链接库的使用在 Windows 系统下使用运动控制器，首先要安装驱动程序。在安装前需要提前下载运动…...

编程日记 2025/5/29 8:49:30

C# 面向对象构造函数带参无参细节解析

继承类构造时会先调用基类构造函数，不显式调用基类构造函数时，默认调用基类无参构造函数，但如果基类没有写无参构造函数，会无法调用从而报错；此时，要么显式的调用基类构造函数，并按其格式带上参…...

编程日记 2025/5/27 7:49:56

数字化工厂升级引擎：Modbus TCP转Profinet网关助力打造柔性生产系统

在当今的工业自动化领域，通信协议扮演着至关重要的角色。Modbus TCP和Profinet是两种广泛使用的工业通信协议，它们分别在不同的应用场景中发挥着重要作用。然而，有时我们可能需要将这两种协议进行转换，以实现不同设备之间的无缝通…...

编程日记 2025/5/27 7:16:43

【编译原理】词法分析器

//简单实现，伪代码 int code,value; strToken :" "; //置strToken为空串 GetChar();GetBC(); if(IsLetter()) beginwhile(IsLetter() or IsDigit())beginConcat();GetChar();endRetract();code:Reserve();if(code0)beginvalue:InsertId(strToken);retu…...

编程日记 2025/5/31 1:44:27

记录一次vue项目页面内嵌iframe页面实现跨域上传和下载附件的功能

功能背景：项目部署在外网，然后其中有一个功能需要上传下载附件，附件是上传到华为云对象存储服务OBS中（私有云），所以采用iframe嵌套页面的方式解决跨域问题。实现思路： 1、父窗口封装一个组件专…...

编程日记 2025/5/27 8:09:54

【Win32 API】 lstrcpyA()

作用将字符串复制到指定的字符串缓冲区。函数 LPSTR lstrcpyA(LPSTR lpString1, LPCSTR lpString2); 参数 lpString1 类型：LPTSTR 一个缓冲区，用于接收由 lpString2 参数指向的字符串的内容。缓冲区必须足够大才能包含字符串，包括终止…...

编程日记 2025/6/1 9:18:09

报表控件stimulsoft教程：如何在报表和仪表板中创建热图

Stimulsoft Ultimate （原Stimulsoft Reports.Ultimate）是用于创建报表和仪表板的通用工具集。该产品包括用于WinForms、ASP.NET、.NET Core、JavaScript、WPF、PHP、Java和其他环境的完整工具集。无需比较产品功能，Stimulsoft Ultimate包含了…...

编程日记 2025/5/28 0:38:16

Axure疑难杂症：剖析面包屑导航“用户不迷路”（玩转导航）

亲爱的小伙伴，在您浏览之前，烦请关注一下，在此深表感谢！ Axure产品经理精品视频课已登录CSDN可点击学习https://edu.csdn.net/course/detail/40420 课程主题：剖析面包屑导航“用户不迷路” 主要内容：面包屑导航各种做法应用场景：页面导航、页面路径、用户选择路径、…...

编程日记 2025/5/29 15:38:16

中exec()函数因$imagePath参数导致的命令注入漏洞

exec(zbarimg -q . $imagePath, $barcodeList, $returnVar); 针对PHP中exec()函数因$imagePath参数导致的命令注入漏洞，以下是安全解决方案和最佳实践： 一、漏洞原理分析直接拼接用户输入$imagePath到系统命令中，攻击者可通过注入特殊字…...

编程日记 2025/5/29 17:07:08

HTML常用标签用法全解析：构建语义化网页的核心指南

HTML作为网页开发的基石，其标签的合理使用直接影响页面的可读性、SEO效果及维护性。本文系统梳理HTML核心标签的用法，结合语义化设计原则与实战示例，助你构建规范、高效的网页结构。一、基础结构与排版标签 1.1 文档结构 <!DOCTYPE htm…...

编程日记 2025/5/29 11:45:50

【Linux】动静态库链接原理

📝前言： 这篇文章我们来讲讲Linux——动静态库链接原理 🎬个人简介：努力学习ing 📋个人专栏：Linux 🎀CSDN主页愚润求学 🌄其他专栏：C学习笔记，C语言入门基础…...

编程日记 2025/5/29 12:57:27

Axure设计的“广东省网络信息化大数据平台”数据可视化大屏

在数据驱动决策的时代，数据可视化大屏成为了展示数据、洞察趋势的重要工具。今天，让我们一同深入了解由Axure设计的“广东省网络信息化大数据平台”数据可视化大屏，看看它如何通过精心的布局和丰富的图表类型，将复杂的数据以直观易…...

编程日记 2025/5/29 21:32:02

linux安装宝塔面板到数据盘

操作很简单，假如数据盘挂载在cipan1，在数据盘新建目录www，为了方便对应。执行一下命令，创建软连接 ln -s /cipan1/www www 此时，根目录就出现了www文件夹下面正常安装宝塔即可...

编程日记 2025/5/29 11:42:07

数学实验（Matlab编程基础）

一、函数文件 Matlab编程基础 Matlab作为一种广泛应用于科学计算的工具软件，不仅具有强大的数值计算、符号计算、矩阵运算能力和丰富的绘图功能，同时也具有和C、FORTRAN等高级语言一样进行程序设计利用Matlab的程序控制功能，可以将有关Ma…...

编程日记 2025/5/29 8:49:51

不同坐标系下MATLAB绘制阵列的方向图

不同坐标系下MATLAB绘制阵列的方向图球坐标系，极坐标系、直角坐标系文章目录前言一、极坐标系二、球坐标系三、直角坐标系总结前言 \;\;\;\;\; 在阵列信号处理和天线设计中，方向图（Pattern）是描述波束形成性能的关键工具&…...

编程日记 2025/5/31 4:37:54

python可视化：北方省市人口流动与春运数据综合分析5

python可视化：北方省市人口流动与春运数据综合分析5 一、北方省市常住人口数据及变化趋势（2023-2024第一季度） 1. 主要城市常住人口数据（按城市等级分类） 城市类型2023Q1常住人口(万)2024Q1常住人口(万)变化量(万)变…...

编程日记 2025/5/28 7:35:59

Java并发编程-线程池（四）

文章目录线程池实现原理WorkerWorker 核心设计总结 runWorker(Worker w)总结线程池实现原理上一篇我们看了 addWork 方法，那接下来就让我们详细看看内部类Worker。 Worker private final class Workerextends AbstractQueuedSynchronizerimplements Runnable …...

编程日记 2025/5/29 13:37:10