[算法]实现strStr()
算法 实现 strstr
2023-09-11 14:16:50 时间
题目
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/implement-strstr
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
两种解法。
第一种:暴力直接求解,时间复杂度是O(n^2)。
第二种:Rabin-Karp算法。
时间复杂度O(m + n)。
代码
代码1
class Solution { public int strStr(String haystack, String needle) { if(haystack == null || needle == null) return -1; for(int i=0; i < haystack.length() - needle.length() + 1; i++){ int j = 0; for(; j < needle.length(); j++){ if(haystack.charAt(i + j) != needle.charAt(j)) break; } if(j == needle.length()) return i; } return -1; } }
代码2
class Solution { static final int BASE = 1000000; public int strStr(String haystack, String needle) { if(haystack == null || needle == null) return -1; if(needle.length() == 0) return 0; int m = needle.length(); //31 ^ m int power = 1; for (int i = 0; i < m; i++) { power = (power * 31) % BASE; } int targetCode = 0; for (int i = 0; i < m; i++) { targetCode = (targetCode * 31 + needle.charAt(i)) % BASE; } int hashCode = 0; for (int i = 0; i < haystack.length(); i++) { hashCode = (hashCode * 31 + haystack.charAt(i)) % BASE; if(i < m - 1){ continue; } //减去开始的数 abcd - a if(i >= m) { hashCode = hashCode - (haystack.charAt(i - m) * power) % BASE; if(hashCode < 0){ hashCode += BASE; } } //双重校验 if(hashCode == targetCode){ if(haystack.substring(i - m + 1, i + 1).equals(needle)){ return i - m + 1; } } } return -1; } }
相关文章
- 文本相似度-bm25算法原理及实现
- 非阻塞算法(Lock-Free)的实现
- Google Earth Engine 实现 LandTrendr 光谱-时间分割算法的指南( LT-GEE获取信息)
- AES算法及实现
- 激光雷达、摄像头、毫米波雷达多传感器融合及融合动态分配(DWD)算法编译运行
- 朴素贝叶斯算法简介及python代码实现分析
- 使用 Python 实现电梯调度的核心算法【100010451】
- java 实现 DES加密 解密算法
- Python实现的粒子群优化算法
- 算法与计算--算法的本质是表达解决问题的逻辑
- 机器学习算法: 基于逻辑回归的分类预测Python实现
- 《数据结构与算法 C语言版》—— 2.3线性表的链式表示与实现
- Java_一致性哈希算法与Java实现
- 常见数据结构和算法 的可视化
- 算法基础复盘笔记Day10【动态规划】—— 线性DP
- 华为OD机试 - 投篮大赛(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 网上商城优惠活动(一)(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- stm32工程和算法分享(11)--74HC595驱动数码管之按键加减显示
- 续前篇---数据挖掘之聚类算法k-mediod(PAM)原理及实现
- 数据结构与算法——优先队列类的C++实现(二叉堆)
- KNN算法基本原理与sklearn实现
- 分布式服务器框架之Servers.Core库实现 DES对称加密算法;SHA1信息摘要算法;MD5信息摘要算法
- leetcode算法225.用队列实现栈
- leetcode算法13.罗马数字转整数