代码随想录训练营 Day09 - 字符串(下)

简介: 代码随想录训练营 Day09 - 字符串(下)

概念


KMP 算法,战略性放弃,等到周末再研究研究 。


作业题


28. 找出字符串中第一个匹配项的下标

https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

class Solution {
    /**
     * 基于窗口滑动的算法
     * <p>
     * 时间复杂度:O(m*n)
     * 空间复杂度:O(1)
     * 注:n为haystack的长度,m为needle的长度
     */
    public int strStr(String haystack, String needle) {
        int m = needle.length();
        // 当 needle 是空字符串时我们应当返回 0
        if (m == 0) {
            return 0;
        }
        int n = haystack.length();
        if (n < m) {
            return -1;
        }
        int i = 0;
        int j = 0;
        while (i < n - m + 1) {
            // 找到首字母相等
            while (i < n && haystack.charAt(i) != needle.charAt(j)) {
                i++;
            }
            if (i == n) {// 没有首字母相等的
                return -1;
            }
            // 遍历后续字符,判断是否相等
            i++;
            j++;
            while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            }
            if (j == m) {// 找到
                return i - j;
            } else {// 未找到
                i -= j - 1;
                j = 0;
            }
        }
        return -1;
    }
}


总结


字符串


  • 如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数;
    如果库函数仅仅是 解题过程中的一小部分,并且自己已经很清楚这个库函数的内部实现原理的话,可以考虑使用库函数。


双指针


  • 数组、链表、字符串等题型中的常客
  • 反转字符串
  • 替换空格
  • 移除元素
  • 删除冗余空格
  • 反转字符串
  • KMP

目录
相关文章
|
11月前
|
编解码 数据可视化 前端开发
如何使用 D3.js 创建一个交互式的地图可视化?
如何使用 D3.js 创建一个交互式的地图可视化?
|
机器学习/深度学习 运维 Prometheus
构建高效运维体系:从自动化部署到智能监控的全方位实践
在当今数字化时代,企业对运维效率和稳定性的要求越来越高。本文将探讨如何构建一个高效的运维体系,从自动化部署、持续集成与持续交付(CI/CD)、智能监控、故障管理以及数据驱动决策等方面进行深入分析和实践指导。通过这些方法,企业可以实现更快速、更可靠的软件发布和问题解决,提升整体运营效率。
|
自然语言处理 Python
python基于百度,哈工大等停用表进行的中文分词
python基于百度,哈工大等停用表进行的中文分词
|
SQL 存储 关系型数据库
精通MySQL:从基础到高级应用与最佳实践
第一章:MySQL基础入门 1.1 MySQL概述 介绍MySQL的历史、发展、优势以及应用领域
|
前端开发
在react项目中如何引入国际化
在react项目中如何引入国际化
533 0
|
Dart 前端开发 JavaScript
Syntax Error: TypeError: this.getOptions is not a function
Syntax Error: TypeError: this.getOptions is not a function
720 0
Syntax Error: TypeError: this.getOptions is not a function
|
运维 安全 网络安全
带你读《网络安全等级保护2.0定级测评实施与运维》——1.1 等保 2.0 时代网络安全形势
带你读《网络安全等级保护2.0定级测评实施与运维》——1.1 等保 2.0 时代网络安全形势
|
Android开发 数据安全/隐私保护 iOS开发
一日一技 | 只需两步,把你的电脑变成局域网文件共享中心
一日一技 | 只需两步,把你的电脑变成局域网文件共享中心
714 0
|
前端开发 API Go
golang ES From size 分页查询 和 Scroll 分页查询 demo
golang ES From size 分页查询 和 Scroll 分页查询 demo
|
XML 编解码 安全
Android Studio 项目目录结构
Android 平台的主要组件 R.java 资源目录(res) drawable和mipmap的区别: 清单文件AndroidMainfest.xml Android Units 单位 Android 中支持 5 种单位类型
479 0
Android Studio 项目目录结构