移除元素
给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。
提示：
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
思考：
删除val值的元素，然后返回其他数值个数。初步来看，就是循环、删除、计数？不过要求原地删除……唔，python里列表用del可以删除，似乎没有什么难的。
emmm……实际发现，直接使用del会导致列表长度变化，然后容易导致循环报错，虽然，虽然也能够约束，但是效果不太稳定。不如直接替换，然后就搞出来了一个双指针法啥的。
实现：
class Solution:
def removeElement(self, nums, val):
k = 0
for i in range(len(nums)):
if nums[i] != val:
nums[k] = nums[i]
k += 1
return k
class Solution2:
def removeElement(self, nums, val):
while val in nums:
nums.remove(val)
return len(nums)
test1 = Solution()
print(test1.removeElement([3,2,2,3],3))找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
提示：
1 <= haystack.length, needle.length <= 104haystack和needle仅由小写英文字符组成
思考：
粗暴思路，for循环，然后遇到符合首字母的就进入判断，成功就返回。似乎也没有啥太有效的方法了，这样只要循环一遍，然后判断需要些许循环……
万恶的循环，靠，各种报错，各种打补丁，真的烦。能搞定，但是需要补充很多的if，看着都头疼。哦，gpt建议可以直接使用切片，省了很多循环。
不过看了下其他人的题解，提到一个KMP（Knuth-Morris-Pratt）解法，然后python的find函数里似乎还有个更好一些的Boyer-Moore算法。
KMP叽里咕噜讲一大堆，看的头都炸了……什么吊毛前缀后缀，就TMD扯淡，其实就是找needle里面的重复字符串。
KMP分为两个步骤，一个是处理needle字符串的规律（构建next数组，可以理解为这个数组记录的数据就是用于后续匹配过程中可以跨越的步长），一个是匹配的过程。 （1）next数组构建 为了方便理解，这儿我直接拍一些对子，大家对着代码看一看就明白了（可以先把j = next_arr[j – 1]理解为j=0）。
aaaab-[0,1,2,3,0]、ababc-[0,0,1,2,0]、sababc-[0,0,0,0,0,0]、llmmll-[0,1,0,0,1,2] 比如aaaab，首字符是a，然后第二个字符是a，重复了，那next[1]=0+1；然后再往后看，第二个字符是a，第三个字符也是a，重复了，那next[2]=0+1+1；再往后看，第三个字符是a，第四个字符也是a，那next[3]=0+1+1+1……
但是为什么j = next_arr[j – 1]，而不是直接让j=0，回到初始位置，毕竟看起来多数情况下j=0和j=next_arr[j-1]类似。这儿就是这个算法的巧妙之处了。 这儿我们举个例子，aabaaa，如果是j=0的话，我们会发现next数组是[0,1,0,1,2,1]，而如果j = next_arr[j – 1]，就会得到[0,1,0,1,2,2]，换句话来说，就是j = next_arr[j – 1]能够更好的复用已有经验，会回到上一个匹配上的位置上，而不是直接回到j=0这么初始的位置。我举个更为复杂的例子，大家就能看到差异了。
“aabcaaabcaaaabcef”,如果用j=0，可得到[0, 1, 0, 0, 1, 2, 1, 0, 0, 1, 2, 1, 2, 3, 4, 0, 0]，而如果采用j=next_arr[j-1]则会得到[0, 1, 0, 0, 1, 2, 2, 3, 4, 5, 6, 7, 2, 3, 4, 0, 0] 很显然，j=0会忽略很多有用的信息，比如中间这段aaabc明眼人一下就看出来后四位aabc和前面首四个字符重复，但是j=0让程序变成了蠢逼，傻傻的对比完前面的aaa发现匹配不上后就直接往后匹配abc了，忽略了aabc的关联。 （2）匹配的过程 匹配的过程和上述数组构建过程高度类似，其实本身也差不多。 不考虑任何算法，常规匹配过程就是匹配完发现对不上，就只能进入i的下一个循环，让j从0重新开始。现在有了next数组，我们可以告诉程序，你不用从0开始，你可以基于已有的规律，比如next数组里是2，j就可以从2开始。 这儿比较巧妙地是同样是j = next_arr[j – 1]，但是在构建next数组和匹配过程中，所代表的含义却略有不同。
实现：
class Solution:
def strStr(self, haystack, needle):
for i in range(len(haystack)):
if haystack[i] == needle[0]:
for j in range(len(needle)):
if i+j>=len(haystack):
j = 0
break
if haystack[i+j] != needle[j]:
j = 0
break
if j == len(needle)-1:
return i
return -1
class Solution2:
def strStr(self, haystack, needle):
m, n = len(haystack), len(needle)
for i in range(m - n + 1): # 保证不会越界
if haystack[i:i+n] == needle:
return i
return -1
class Solution3:
def strStr(self, haystack, needle):
if not needle:
return 0
n, m = len(haystack), len(needle)
# 构建 next 数组（最长公共前后缀长度）
next_arr = [0] * m
j = 0 # 当前匹配的前缀长度
for i in range(1, m):
while j > 0 and needle[i] != needle[j]:
j = next_arr[j - 1]
if needle[i] == needle[j]:
j += 1
next_arr[i] = j
# KMP 匹配
j = 0 # needle 的指针
for i in range(n):
while j > 0 and haystack[i] != needle[j]:
j = next_arr[j - 1] # 利用 next 数组跳过已匹配部分
if haystack[i] == needle[j]:
j += 1
if j == m: # 完全匹配
return i - m + 1
return -1
test1 = Solution3()
print(test1.strStr("sadbutsad", "sad"))
print(test1.strStr("leetcode", "leeto"))
print(test1.strStr("hello", "sababc"))
print(test1.strStr("aaaaaaaabaaa", "aabaaa"))
print(test1.strStr("abababababababc", "ababaca")) # [0,0,1,2,3,0,1]