专栏首页java工会算法养成记:实现 strStr()

算法养成记:实现 strStr()

LeetCode28

Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"

Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"

Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

中文意思就是:

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

示例 1:

输入: haystack = "hello", needle = "ll"

输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"

输出: -1

说明:

当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

暴力破解!

  1. 遍历haystack的每一个字符
  2. 当某一位置i的字符和needle的第一个字符相等时,再依次判断下一个字符与needle的下一个字符是否相等
  3. 注意跳出循环的条件,当i+needle.length>haystack.length时,就意味着后面不可能相等了,所以可以提前跳出循环
  4. 当某循环的长度等于needle.length,就意味着已经找到了第一个相等的字符换,可以跳出循环。

所以代码如下:

用Java的话,偷个懒,用substring方法直接截取haystack和needle长度相同的字符串,依次比较;大于haystack.length-needle.length时,查找失败,跳出循环。

当我在查查别人还有没有什么好方法时,看到了一个说只用一行代码,执行0ms。还满怀期待的点了进去,然后我看到了如下触目惊心的代码!

当时好想抽那位仁兄一个大嘴瓜子,简直沙雕一般的存在,也是没救了的。

以下是JDK的源码:

从源码上看,首先是找了第一个相等的字符,找了之后,再依次找之后的字符,从思想上还是一样的。

在实际测试里

执行用时分别是:1ms,0ms,0ms

内存消耗分别是:38.2MB,37.9MB,38.3MB

本文分享自微信公众号 - java工会(javagonghui),作者:除却巫山

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 20个代码生成框架

    官方论坛:http://forum.codesmithtools.com/default.aspx

    三哥
  • 团队如何进行CodeReview

    三哥
  • 十个常用的java正则表达式

    三哥
  • Qt官方示例-速度仪表盘

    Qt君
  • Python3 与 C# 并发编程之~ 进程篇上

    上次说了很多Linux下进程相关知识,这边不再复述,下面来说说Python的并发编程,如有错误欢迎提出~

    逸鹏
  • Language issue for downloaded product category

    When you try to edit some downloaded product categories, you may meet with this ...

    Jerry Wang
  • Language issue for downloaded product category

    When you try to edit some downloaded product categories, you may meet with this ...

    Jerry Wang
  • 面试时,怎么介绍自己做过的项目?

    需求或机会--投资人在线上购买理财产品(平台代发布) 给借款人提供一个借款的渠道, 海尔(平台方)作为做一个监督方,从中抽取佣金; 第三方提供理财产品、保险、...

    张树臣
  • php 页面传递数组元素

    <form action="a.php"> <input type="text" name="books[]"/> <input type="tex...

    WindWant
  • 解决tensorflow 释放图,删除变量问题

    问题,在一个程序内构建好了一个图,运行完之后想重新使用这个图进行计算,或者想同时在train完的时候做test,就会提示***变量已存在。

    砸漏

扫码关注云+社区

领取腾讯云代金券