移除元素与定位子串——LeetCode 第 27、28 题记
移除元素与定位子串——LeetCode 第 27、28 题记
今天负能量满满、累到爆炸，唯一值得欣慰的是要刷的两道题都是简单题目，而且还都能取巧（虽然取巧便违背了题目的初衷）。
题目一
第 27 题：移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例一：
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
示例二：
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
#来源：力扣（LeetCode）
#链接：https://leetcode-cn.com/problems/remove-element尝试思路
对于这道题目，我最初解法是违规的：先复制一份列表用来控制遍历循环过程，在循环中看列表元素与输入的数值是否相等，若相等，删除原列表该元素一次。因为复制了列表要占用额外数组空间，此法不通。
那我们对原列表遍历，若检测到元素与输入数字相等，我们记录下次数，遍历完，执行等次数的删除该元素操作。
代码实现
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
# 记录次数的变量
count = 0
# 对列表遍历循环记录与 val 相同次数
for i in nums:
if i == val:
count+=1
# 执行对应次数的删除元素操作
for j in range(count):
nums.remove(val)
return len(nums)提交测试表现：
执行用时 : 44 ms, 在所有 Python3 提交中击败了 41.00% 的用户
内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 7.14%的用户我也不知道这个解法是否符合“仅使用 O(1) 额外空间并原地修改输入数组”的标准，因为这个 lst.remove(value) 函数每次会自动删除第一次出现的 value 值，这就已经不是最基础的删除元素操作了。
我们先去看看推荐题解找找启发。
观摩题解
看到一份 Java 和 JavaScript 提交的题解，言简意赅地阐述了“拷贝覆盖”算法，我们用 Python 来实现。
我们在对原列表遍历时，如果该位与 val 不同，我们就在原列表中保留它；但如果它与 val 相同，我们就把这位跳过、或者说遗弃它，那么最终经过一次循环我们即可拿到结果：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
# count 变量控制新储存的列表的索引值
count = 0
¥ 对列表遍历
for i in range(len(nums)):
# 元素值不同于 val 时
if nums[i]!=val:
# 将元素值重新存到对应的 count 索引处
nums[count] = nums[i]
# 索引标自增
count+=1
# 最终只返回前 count 位
return len(nums[:count])相当于遍历过程中，我们在原列表中复制保留与 val 值不同的元素，跳过相同元素，即可产生删除元素效果。
测试表现与之前相同，但明显这个会更符合题意要求。
第 28 题：实现 strStr()
实现 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说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
尝试思路
strStr() 是 C 语言函数，即返回字符串中首次出现子串的地址。习惯了 Python 中的判断 if a in b, 所以先用这个来判断下子串是否在字符串中，若不存在直接返回 -1。若存在，则遍历字符串，当判断以该位开始可以匹配子串时，返回坐标。
题目要求不多，索性就这么蒙混过关吧！
代码实现
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
# 根据其说明，空子串返回 0
if needle=="":
return 0
# 若子串不在字符串中，返回 -1
if needle not in haystack:
return -1
# 取子串长度
l = len(needle)
# 遍历字符
for i in range(len(haystack)):
# 如果字符开始可以匹配子串
if haystack[i:l+i]==needle:
# 返回此时索引
return i
# 遍历完仍没有，则返回-1
return -1提交测试表现：
执行用时 : 36 ms, 在所有 Python3 提交中击败了 82.85% 的用户
内存消耗 : 13.8 MB, 在所有 Python3 提交中击败了 6.67% 的用户表现还挺好，翻看下题解借鉴下。
观摩题解
果然，遇到了惊喜。接着我们刚的算法来看，如果第一位匹配不上，我们会移到第二位，取与子串等长的片段来做匹配；若还不行，我们移动到第三位。这个过程是逐位检测的，匹配成功之前，每一位都会参与完整检测过程。这时，可以采用 Sunday 算法来跳过些不必要节点的检测。
Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是：在匹配过程中，模式串发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。 百度百科：Sunday 算法
有点类似于之前回文串时遇到的“马拉车算法”，比那个稍微简单些（简单完仍旧很烧脑），本想搬运些图片或例子来演示的，推演了会放弃了，不搞学术、实在不想做这烧脑算法题玩了。
题解区算法讲解链接：https://leetcode-cn.com/problems/implement-strstr/solution/python3-sundayjie-fa-9996-by-tes/
百度百科算法讲解链接：https://baike.baidu.com/item/sunday%20%E7%AE%97%E6%B3%95/1816405除了 Sunday 算法，还有 KMP 算法等的实现，真佩服研究出这些算法的数学家们。
因为这算法的优化本质上是对多情况下的分析讨论，避开不必要的节点，从而达到更高效的目的，那付出的就是代码中对边界情况的阐述，故而代码会看着弯弯绕绕比较复杂，反倒将代码题生生转化成数学题了。
结论
今天明明是两道简单题目，没想到还能记录这么些内容，也间接导致了昨天遗留的算法分析要推迟了，还好香港明天放假，绝对有时间来整理了，今天鸽一下也不打紧，反正也没多少人看。
最近的刷题算是打个先锋，探一探众题目深浅以及熟悉下套路，所以可能记录的内容更偏现有知识的即时反应，对于要坚持多久、刷多少道也是且行且看，闲了就多刷刷，毕竟题库里现在有 1625 道、可能还在增多中。同时也要提高写题记的效率和质量，算是给自己的一个小要求吧。