<small id='hI7czYB20x'></small> <noframes id='yWT7uNJ'>

  • <tfoot id='Gnbl1'></tfoot>

      <legend id='vetN'><style id='DyeirfYzt'><dir id='0U6FMo'><q id='68DPL'></q></dir></style></legend>
      <i id='j9BfyCQaTL'><tr id='5hIk0'><dt id='1QnaSj'><q id='6GxoNq'><span id='tX52HkcIz'><b id='DdtTGUrRw'><form id='RqOXKxSU'><ins id='kMWHNOo'></ins><ul id='3JKuZCHUj'></ul><sub id='JOl0ZTpj2K'></sub></form><legend id='xXw76N3j'></legend><bdo id='SvAOyJd'><pre id='Ulvk'><center id='6LlfBK'></center></pre></bdo></b><th id='Js5Uo'></th></span></q></dt></tr></i><div id='IQTEPbv'><tfoot id='MPw1D5fy2B'></tfoot><dl id='4vRraA9h'><fieldset id='XAU5h'></fieldset></dl></div>

          <bdo id='Ike2dnp36O'></bdo><ul id='aUY9PC'></ul>

          1. <li id='xq8vYC'></li>
            登陆

            LeetCode根底算法题第164篇:判别子序列

            admin 2019-11-06 265人围观 ,发现0个评论

            技能进步是一个按部就班的进程,所以我讲的leetcode算法题从最简略的level开端写的,然后到中级难度,最后到hard难度悉数完。现在我挑选C言语,Python和Java作为完成言语,由于这三种言语仍是比较典型的。由于篇幅和精力有限,其他言语的完成有爱好的朋友请自己测验。

            假如有任何问题能够在文章后谈论或许私信给我。

            假如有朋友期望我讲些其他论题,请在谈论区留言或许私信给我。

            持续共享,敬请重视。

            LLeetCode根底算法题第164篇:判别子序列eetCode 392. 判别子序列(Is Subsequence)

            问题描绘:

            给定两个字符串 s 和 t ,LeetCode根底算法题第164篇:判别子序列判别 s 是否为 t 的子序列。

            假定 s 和 t 仅包括英文小写字母。字符串 t 可能会一个十分上的字符串(长度能够到达500,000),而 s 是个比较短的字符串(长度 <=100)。

            字符串的子序列是指经过删去一些(也可不删去)原始字符串中的某些字符,可是不会调整剩余字符的相对方位,这样构成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

            拓宽问题:

            假如有许多输入 S,记作S1, S2, ... , Sk 其间 k >= 10亿,你需求顺次查看它们是否为 T 的子序列。这种状况,怎么改进你的代码?

            ( 这个扩展题,我会鄙人一个文章中讲,咱们无妨考虑一下,提示一下,关于许多的输入,咱们应该尽量削减查看时刻,以使得整体耗时最短,空间开支往往不那么重要。)

            示例:

            C言语完成:

            这道题LeetCode根底算法题第164篇:判别子序列也是一个很简略的标题。

            清楚明了的解法是:一起遍历s和t,一查看s中的每一个字符是否在t中有序存在。

            这儿需求留意的是,标题给定的条件,t是一个十分长的字符串,而s是比较短的,所以我觉得这道题考的应该是你是以哪个字符串作为遍历目标。

            假如以t为遍历条件的话,假如在遍历的时分不加以判别,会导致遍历完这个t,哪怕s的长度是1。

            遇到这种状况,明显字符串短的LeetCode根底算法题第164篇:判别子序列比较合适作为遍历目标,由于短的遍历完毕后,整个程序也就完毕了,哪怕t还剩余许多没有遍历。

            咱们遍历s中的每一个字符c,然后查看c是否在t中“有序”存在,留意我说的“有序”,假如用下标来描绘的话,便是:假如s是t的子串,那么s中每个字符c的下标应该是肯定递加的。换句话说,跟着s的遍历,字符c在t中的方位是不断向后的。

            在t中查找c的时分,咱们先界说一个变量i来保存开端查找方位LeetCode根底算法题第164篇:判别子序列。

            C言语,咱们用strchr函数,JAVA咱们用indexOf办法,python咱们用find办法,这些函数或许办法,都能够指定查找的开端方位,咱们将i传递给它们。

            假如找不到c,会回来空或许-1。这个时分咱们直接god回来false就能够了。

            假如找到c,回来其下标,将这个回来值从头赋值给i,以使得,下次从这个方位持续查找下去。这儿要留意,实际上的开端方位应该是,从该下标的后一个字符开端。这便是为什么咱们初始化i为-1的原因。

            具体代码如下:

            Java言语完成:

            Java 的完成和C言语的完成共同,不再撰述。

            代码如下:

            Python言语完成:

            Python 的完成和CLeetCode根底算法题第164篇:判别子序列言语的完成共同,不再撰述。

            代码如下:


            请关注微信公众号
            微信二维码
            不容错过
            Powered By Z-BlogPHP