概念
KMP 算法,战略性放弃,等到周末再研究研究 。
作业题
28. 找出字符串中第一个匹配项的下标
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