当前位置：首页 > 编程日记 > 正文

刻意练习：LeetCode实战 -- Task26.判断子序列

编程日记 2024-09-25 20:10:00

背景

本篇图文是LSGO软件技术团队组织的第二期基础算法（Leetcode）刻意练习训练营的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了三个简单、两个中等、一个困难等级的题目，共计三十道题，利用三十天的时间完成这组刻意练习。

本次任务的知识点：贪心算法

贪心算法（greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

题目

题号：392
难度：简单
https://leetcode-cn.com/problems/is-subsequence/

给定字符串s和t，判断s是否为t的子序列。

你可以认为s和t中仅包含英文小写字母。字符串t可能会很长（长度 ~= 500,000），而s是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1:

s = "abc", t = "ahbgdc"返回 true.

示例 2:

s = "axc", t = "ahbgdc"返回 false.

示例 3:

s = "", t = "ahbgdc"返回 true.

后续挑战:

如果有大量输入的S，称作S1, S2, ... , Sk 其中k >= 10亿，你需要依次检查它们是否为T的子序列。在这种情况下，你会怎样改变代码？

实现

第一种：贪心算法

贪心算法必须具备后无效性，也就是不必考虑前面的影响，只需考虑当前的状态。

若s = "abc", t = "ahbgdc" 要判断字符串s和t的排序是否一致，我们这样构造贪心策略：

取s中的第一个字符a，判断t中是否存在字符a
若存在，则判断t中字符a之后的剩余字符串是否存在第二个字符b
依次类推

用一句通俗的话就是剩余字符串中是否存在下一个字符，利用贪心算法的概念就是局部是否存在最优解。

执行结果：通过
执行用时：116 ms, 在所有 C# 提交中击败了 42.17% 的用户
内存消耗：43 MB, 在所有 C# 提交中击败了 7.41% 的用户

public class Solution
{public bool IsSubsequence(string s, string t){for (int i = 0; i < s.Length; i++){int j = t.IndexOf(s[i]);if (j == -1)return false;t = t.Substring(j + 1);}return true;}
}

第二种：双指针法

利用两个变量i,j来记录搜索的位置，i记录搜索到t的位置，j记录搜索到s的位置，一旦j==s.Length表示s的字符全部搜索完成，即s是t的子序列，返回true即可。

执行结果：通过
执行用时：112 ms, 在所有 C# 提交中击败了 56.63% 的用户
内存消耗：38 MB, 在所有 C# 提交中击败了 25.93% 的用户

public class Solution
{public bool IsSubsequence(string s, string t){if (string.IsNullOrEmpty(s))return true;int j = 0;for (int i = 0; i < t.Length; i++){if (t[i] == s[j]){j++;}if (j == s.Length)return true;}return false;}
}

Python 语言

执行结果：通过
执行用时：268 ms, 在所有 Python3 提交中击败了 35.49% 的用户
内存消耗：18 MB, 在所有 Python3 提交中击败了 8.35% 的用户

class Solution:def isSubsequence(self, s: str, t: str) -> bool:if len(s) == 0:return Truej = 0for i in range(0, len(t)):if t[i] == s[j]:j += 1if j == len(s):return Truereturn False

往期活动

LSGO软件技术团队会定期开展提升编程技能的刻意练习活动，希望大家能够参与进来一起刻意练习，一起学习进步！

Python基础刻意练习活动即将开启，你参加吗？
Task01：变量、运算符与数据类型
Task02：条件与循环
Task03：列表与元组
Task04：字符串与序列
Task05：函数与Lambda表达式
Task06：字典与集合
Task07：文件与文件系统
Task08：异常处理
Task09：else 与 with 语句
Task10：类与对象
Task11：魔法方法
Task12：模块

我是终身学习者“老马”，一个长期践行“结伴式学习”理念的 中年大叔。

我崇尚分享，渴望成长，于2010年创立了“LSGO软件技术团队”，并加入了国内著名的开源组织“Datawhale”，也是“Dre@mtech”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。

愿我们一起学习，一起进步，相互陪伴，共同成长。

后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：

https://www.dkcj.cn/info/20317.html

刻意练习：LeetCode实战 -- Task26.判断子序列

背景

题目

实现

相关文章：

spring @component的作用

使用JavaScript变量需要注意哪些语法细节?

手把手教你搭建一个学习Python好看的 Jupyter 环境

刻意练习：LeetCode实战 -- Task27.分发饼干

祝贺《WCF邮件通信系统》在高阳市场研究汇编第五期发表

学软件测试有前途吗

Active Directory 账号迁移配置介绍

VIM命令快速记忆（转自杰哥）

刻意练习：LeetCode实战 -- Task28.跳跃游戏

类操作是什么意思?jQuery的类操作教程

刻意练习：LeetCode实战 -- Task29. 加油站

C#从SQL server数据库中读取l图片和存入图片

linux下查看内存使用情况

现在转行学习UI设计好不好就业

刻意练习：LeetCode实战 -- Task30.通配符匹配

iOS 11 安全区域适配总结

(广州)软件开发定制服务,工作流引擎 OA 库存管理系统

Java类加载机制详解【java面试题】

C#获取文件的当前路径

c# ThreadPool 判断子线程全部执行完毕的四种方法

腾讯精选练习 50 题（Leetcode）笔记 PDF下载！

Python培训：try-except语句与else子句联合使用处理可能出现的程序异常

Backup Exec 2012 备份和还原活动目录(非授权还原)

hdu3368 Reversi

有符号整型的数据范围为什么负数比正数多一个？

UI设计培训：UI构思创意技巧和方法

博客园 cnblogs博客添加Google Analytics统计

技术图文：Python 位运算防坑指南

聊聊nginx报错499问题

UI设计需要报培训班学习吗