每日Leetcode—算法（4）

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。

算法：

def removeElement(self, nums: List[int], val: int) -> int:
    if len(nums)=0:
        return 0
    count=0
    for i in range(0,len(nums):
        if nums[count]==val:
            nums.pop(count)
        else:
            count+=1
    return len(nums)

分析：直接使用上一题的思路，在原地对元素进行删减。有算法给出while，但是需要额外创建两个空间，本算法只创造了一个额外空间。另外：pop()函数比del函数快很多。

28. 实现strStr()

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例：
输入: haystack = "hello", needle = "ll"，输出: 2
输入: haystack = "aaaaa", needle = "bba"，输出: -1

算法一：

def strStr(self, haystack: str, needle: str) -> int:
    if len(needle)==0:
        return 0
    if len(needle)>len(haystack):
        return -1
    l = len(haystack)
    for i in range(len(haystack)):
        if hastack[i:i+l] == needle:
            return i
    return -1

算法二：

if needle not in haystack:
    return -1
return haystack.find(needle)