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

模拟算法(4)_外观数列

个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

模拟算法(4)_外观数列

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌

目录

1. 题目链接 :

2. 题目描述 :

3. 解法(模拟 + 双指针) :

    题目分析:

    算法思路 :

    代码展示 :

    结果分析 :


1. 题目链接 :

OJ链接 : 外观数列

2. 题目描述 :

「外观数列」是一个数位字符串序列,由递归公式定义:

  • countAndSay(1) = "1"
  • countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。

行程长度编码(RLE)是一种字符串压缩方法,其工作原理是通过将连续相同字符(重复两次或更多次)替换为字符重复次数(运行长度)和字符的串联。例如,要压缩字符串 "3322251" ,我们将 "33" 用 "23" 替换,将 "222" 用 "32" 替换,将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"

给定一个整数 n ,返回 外观数列 的第 n 个元素。

示例 1:

输入:n = 4

输出:"1211"

解释:

countAndSay(1) = "1"

countAndSay(2) = "1" 的行程长度编码 = "11"

countAndSay(3) = "11" 的行程长度编码 = "21"

countAndSay(4) = "21" 的行程长度编码 = "1211"

示例 2:

输入:n = 1

输出:"1"

解释:

这是基本情况。

提示:

  • 1 <= n <= 30

3. 解法(模拟 + 双指针) :

    题目分析:

countAndSay(n) 是对 countAndSay(n - 1) 的描述,然后转换成另⼀个数字字符串。
前五项如下:
1. 1
2. 11
3. 21
4. 1211
5. 111221
第⼀项是数字 1
描述前⼀项,这个数是 1 即 “ ⼀ 个 1 ”,记作 "11"
描述前⼀项,这个数是 11 即 “ ⼆ 个 1 ” ,记作 "21"
描述前⼀项,这个数是 21 即 “ ⼀ 个 2 + ⼀ 个 1 ” ,记作 "1211"
描述前⼀项,这个数是 1211 即 “ ⼀ 个 1 + ⼀ 个 2 + ⼆ 个 1 ” ,记作 "111221"

    算法思路 :

1. 初始化:

        先将 ret 初始化为 "1",这是 * *"count and say" * *序列的第一项。
2. 迭代构建序列 :

        使用一个外层循环 for (int i = 1; i < n; i++),这个循环会执行 n - 1 次,因为我们已经有了第一项。每次迭代都会根据当前项生成下一项。
3. 内部逻辑 :

        在每次迭代中,首先定义一个空字符串 tmp,用于存储下一项的内容。
        len 存储当前字符串 ret 的长度,以便在后续处理中使用。
4. 双指针扫描 :

        使用两个指针 left 和 right,初始都指向字符串的开始位置。目的是扫描字符串并统计相邻相同字符的数量。
        内层循环:while(right < len && ret[left] == ret[right]) 用来找到从 left 开始的相同字符的连续个数。right 会向右移动,直到遇到不同的字符或到达字符串末尾。
        一旦 right 指向了不同的字符(或者到达了字符串的末尾),就可以得知从 left 到 right 的字符是相同的,且数量为 right - left。
5. 生成下一项 :

        使用 tmp += to_string(right - left) + ret[left]; 将当前相同字符的数量和字符本身拼接到 tmp 中。例如,如果遇到 "11",就会在 tmp 中添加 "21"(表示有两个1)。
        更新 left 为 right,准备处理下一个不同的字符。
6. 更新当前项 :

        在内层循环完成后,将 tmp 赋值给 ret,这就构成了新的 * *"count and say" * *项。
7. 返回结果 :

        当外层循环完成后,返回最终构建好的字符串 ret,即为 * *"count and say" * *序列的第 n 项。

    代码展示 :

class Solution {
public:string countAndSay(int n) {//最基本的情况string ret = "1";for(int i = 1; i < n; i++)//解释n - 1次ret即可{string tmp;int len = ret.size();for(int left = 0, right = 0; right < len;){while(right < len && ret[left] == ret[right]) right++;//"11" -> 2个1 -> "21" //to_string是将不同类型的数据变成字符串 tmp += to_string(right - left) + ret[left];left = right;}ret = tmp;}return ret;}
};

    结果分析 :

1. 每次迭代的过程都是对当前字符串的描述,并将描述生成的字符串用于下一次迭代。
2. 时间复杂度 : 虽然每一项的描述可能导致字符串长度的增加,但由于字符的重复性,时间复杂度为 O(2 ^ n),也就是说随着 n 的增大,生成过程的复杂度会迅速增加。
3. 这个算法的实现既高效又简单,利用了字符串的基本操作和简单的逻辑判断,能够有效生成** "count and say" * *序列。

相关文章:

模拟算法(4)_外观数列

个人主页&#xff1a;C忠实粉丝 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 C忠实粉丝 原创 模拟算法(4)_外观数列 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记&#xff0c;欢迎大家在评论区交流讨论&#x1f48c; 目录 1. 题目链…...

vsomeip用到的socket

概述&#xff1a; ​ vsomeip用到的socket的代码全部都在implementation\endpoints目录下面&#xff0c;主要分布在下面六个endpoint类中&#xff1a; local_client_endpoint_impl // 本地客户端socket&#xff08;UDS Socket或者127.0.0.1的socket&#xff09;local_server…...

MFC有三个选项:MFC ActiveX控件、MFC应用程序、MFC DLL,如何选择?

深耕AI&#xff1a;互联网行业 算法研发工程师 ​ 目录 MFC ActiveX 控件 控件的类型 标准控件 自定义控件 ActiveX控件 MFC ActiveX控件 标准/自定义控件 MFC ActiveX控件分类 3种MFC如何选择&#xff1f; MFC ActiveX控件 MFC 应用程序 MFC DLL 总结 举例说明…...

边缘概率 | 条件概率

关于什么是边缘概率分布和条件概率分布&#xff0c;在理论上&#xff0c;我自己也还没有理解&#xff0c;那么现在就根据我学习到的理解方式来记录一下&#xff0c;有错误指出&#xff0c;请大家指正&#xff01;&#xff01;&#xff01; 例如&#xff0c;一个箱子里有十个乒乓…...

深入浅出:现代JavaScript开发者必知必会的Web性能优化技巧

亲爱的读者们&#xff0c;欢迎来到本期博客。今天&#xff0c;我们将深入探讨JavaScript开发者在日常工作中如何提升Web性能。在快节奏的Web开发世界中&#xff0c;性能优化至关重要。本文将分享一些实用技巧&#xff0c;帮助你构建快速、高效的Web应用。 1. 使用CDN加速资源加…...

【S32K3 RTD LLD篇5】K344 ADC SW+HW trigger

【S32K3 RTD LLD篇5】K344 ADC SWHW trigger 一&#xff0c;文档简介二&#xff0c;ADC SW HW 触发2.1 软硬件平台2.2 SWADC 软件触发2.3 SWBCTUADC 软件BCTU触发2.4 PITTRIGMUXADC 硬件PIT TRIGUMX触发2.5 EMIOSBCTUHWADC硬件EMIOS BCTU触发2.6 EMIOSBCTUHW LISTADC硬件EMIOS …...

TransFormer 视频笔记

TransFormer BasicsAttention单头注意力 single head attentionQ&#xff1a; query 查寻矩阵 128*12288K key matrix 128*12288SoftMax 归一 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/19e3cf1ea28442eca60d5fc1303921f4.png)Value matrix 12288*12288 MLP Bas…...

前端的混合全栈之路Meteor篇(三):发布订阅示例代码及如何将Meteor的响应数据映射到vue3的reactive系统

Meteor 3.0 是一个功能强大的全栈 JavaScript 框架&#xff0c;特别适合实时应用程序的开发。它的核心机制之一就包括发布-订阅&#xff08;Publish-Subscribe&#xff09;模型&#xff0c;它允许服务器端发布数据&#xff0c;客户端订阅并实时更新。本文将介绍如何在 Meteor 3…...

自动驾驶系列—颠覆未来驾驶:深入解析自动驾驶线控转向系统技术

&#x1f31f;&#x1f31f; 欢迎来到我的技术小筑&#xff0c;一个专为技术探索者打造的交流空间。在这里&#xff0c;我们不仅分享代码的智慧&#xff0c;还探讨技术的深度与广度。无论您是资深开发者还是技术新手&#xff0c;这里都有一片属于您的天空。让我们在知识的海洋中…...

Webstorm 中对 Node.js 后端项目进行断点调试

首先&#xff0c;肯定需要有一个启动服务器的命令脚本。 然后&#xff0c;写一个 debug 的配置&#xff1a; 然后&#xff0c;debug 模式 启动项目和 启动调试服务&#xff1a; 最后&#xff0c;发送请求&#xff0c;即可调试&#xff1a; 这几个关键按钮含义&#xff1a; 重启…...

VUE前后端分离毕业设计题目项目有哪些,VUE程序开发常见毕业论文设计推荐

目录 0 为什么选择Vue.js 1 Vue.js 的主要特点 2 前后端分离毕业设计项目推荐 3 后端推荐 4 总结 0 为什么选择Vue.js 使用Vue.js开发计算机毕业设计是一个很好的选择&#xff0c;因为它不仅具有现代前端框架的所有优点&#xff0c;还能让你专注于构建高性能、高可用性的W…...

一、Spring Boot集成Spring Security之自动装配

Spring Boot集成Spring Security之自动装配介绍 一、实现功能及软件版本说明二、创建Spring Boot项目三、查看自动装配配置类四、自动装配配置类之SecurityAutoConfiguration1、SecurityAutoConfiguration部分源码2、主要作用3、SpringBootWebSecurityConfiguration3.1、Spring…...

计数相关的题 Python 力扣

2284. 最多单词数的发件人 给你一个聊天记录&#xff0c;共包含 n 条信息。给你两个字符串数组 messages 和 senders &#xff0c;其中 messages[i] 是 senders[i] 发出的一条 信息 。 一条 信息 是若干用单个空格连接的 单词 &#xff0c;信息开头和结尾不会有多余空格。发件…...

Express内置的中间件(express.json和express.urlencoded)格式的请求体数据

目录 Express内置的中间件 express.json 中间件的使用 express.urlencoded 中间件的使用 express.urlencoded([options]) 解析req.body的兼容写法 Express内置的中间件 自 Express 4.16.0 版本开始&#xff0c;Express 内置了 3 个常用的中间件&#xff0c;极大的提高了 …...

cmakelist加载Qt模块

Qt编程中&#xff0c;cmakelist会自动添加Core&#xff0c;Gui&#xff0c;Widgets模块&#xff0c;有时需要添加新的Qt的模块。在命令find_package中搜索要新增的模块&#xff0c;在命令target_link_libraries中添加要新增的模块。 比如要使用QUiLoader类&#xff0c;要增加对…...

8-2.Android 任务之 CountDownTimer 编码模板(开启计时器、取消计时器)

一、CountDownTimer 1、概述 CountDownTimer 是 Android 中一个用于执行定时操作的类 CountDownTimer 主要应用于在指定时间段内完成某项任务&#xff0c;或者每隔一段时间触发某项任务 2、使用步骤 创建 CountDownTimer&#xff1a;创建 CountDownTimer 就是创建它的匿名…...

Servlet的生命周期及用户提交表单页面的实现(实验报告)

一、实验目的、要求 1. 掌握Servlet的定义&#xff0c;即Servlet是运行在服务器端的Java程序&#xff0c;用于扩展服务器的功能。 2. 学习和掌握在开发环境中搭建Servlet应用所需的工具&#xff0c;如Tomcat服务器、IDEA等。 二、实验内容 根据本章所学知识&#xff0c;实验…...

【Router】路由功能之IP过滤(IP Filter)功能(基于端口)介绍及实现

IP过滤(IP Filter) IP Filter是一种通过对网络数据包中的 IP 地址进行分析和筛选,以实现对网络流量的控制和管理的技术。 IP过滤(IP Filter)作用 安全防护 可以阻止来自特定 IP 地址或 IP 地址范围的恶意攻击、非法访问等,增强网络的安全性。 流量管理 根据不同的 IP …...

数据结构_2.2、顺序表插入删除查找

1、线性表的顺序存储表示定义&#xff1a; 线性表&#xff1a;是具有相同数据类型的n &#xff08;n≥0&#xff09;个数据元素的有限序列 顺序表&#xff1a;用顺序存储的方式实现线性表 顺序存储&#xff1a;把逻辑上相邻的元素存储在物理 位置上也相邻的存储单元中&#…...

嵌入式C语言自我修养:编译链接

源文件生成可执行文件的过程&#xff1f; 源文件经过预处理、编译、汇编、链接生成一个可执行的目标文件。 编译器驱动程序&#xff0c;包括预处理器、编译器、汇编器和链接器。Linux用户可以调用GCC驱动程序来完成整个编译流程。 使用GCC驱动程序将示例程序从ASCII码源文件转换…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

结构化文件管理实战:实现目录自动创建与归类

手动操作容易因疲劳或疏忽导致命名错误、路径混乱等问题&#xff0c;进而引发后续程序异常。使用工具进行标准化操作&#xff0c;能有效降低出错概率。 需要快速整理大量文件的技术用户而言&#xff0c;这款工具提供了一种轻便高效的解决方案。程序体积仅有 156KB&#xff0c;…...

写一个shell脚本,把局域网内,把能ping通的IP和不能ping通的IP分类,并保存到两个文本文件里

写一个shell脚本&#xff0c;把局域网内&#xff0c;把能ping通的IP和不能ping通的IP分类&#xff0c;并保存到两个文本文件里 脚本1 #!/bin/bash #定义变量 ip10.1.1 #循环去ping主机的IP for ((i1;i<10;i)) doping -c1 $ip.$i &>/dev/null[ $? -eq 0 ] &&am…...