双指针应用--快慢指针

1、给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

算法思路：准备重置数组nums[0.....l]

def removeElement(nums,val):
    #想象一个新数组nums[0....l]，其索引从0...l。
    l=0
    #遍历现数组，找出不等于val的数，然后赋值给新数组。
    for r in range(len(nums)):
        if nums[r]!=val:
            #赋值.
            nums[l]=nums[r]
            l+=1
    return l

nums = [0,1,2,2,3,0,4,2]
val=2
print(removeElement(nums,val))

2、给定一个二进制数组，计算其中最大连续1的个数。输入: [1,1,0,1,1,1] 输出: 3。

算法思路：初始化count=0用于记录1的个数，初始化res=0用来记录连续1的个数。指针 i 用于遍历数组，遇到1，count自增。遇到 0,count归零。res=max(res,count)。

def findMaxConsecutiveOnes(nums):
    if 1 not in nums:
        return 0
    else:
        n=len(nums)
        count=0
        res=0
        for i in range(len(nums)):
            if nums[i]!=0:
                count+=1
                res=max(res,count)
            if nums[i]==0:
                count=0
        return res


nums=[1,1,0,1,1,1]
print(findMaxConsecutiveOnes(nums))

3、给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

输入: "Let's take LeetCode contest" 输出: "s'teL ekat edoCteeL tsetnoc"
算法思路：将字符串转换成列表。想象一个新的列表，索引 0....j。遍历现列表，翻转其中的元素，然后赋值给新列表。

def reverseWords(s):
    s=s.split()
    n=len(s)
    j=0
    for i in range(n):
        s[j]=s[i][::-1]
        j+=1
    return " ".join(s)
    
s="Let's take LeetCode contest"
print(reverseWords(s))

4、给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

给定数组 nums = [1,1,2]  函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2.
算法思路： 初始化慢指针 j=0.快指针 i 用于遍历。当指针 i，j 指代的元素不等时，指针j+=1.然后赋值：nums[j]=nums[i]。完成对数组nums的修改。

def f(nums):
    n=len(nums)
    j=0
    for i in range(n):
        if nums[j]!=nums[i]:
            j+=1
            nums[j]=nums[i]
    return j+1

nums = [0,0,1,1,1,2,2,3,3,4]
print(f(nums))

5、给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。给定 nums = [1,1,1,2,2,3], 函数应返回新长度 length = 5,

并且原数组的前五个元素被修改为 1, 1, 2, 2, 3算法思路：j指针指向数组元素的位置，i指针遍历现数组。然后把复合要求的i所指代的值赋给j，

完成对数组nums的修改。因为每个元素可以出现2次，那么只需要从数组nums第二个数开始 修改即可，即 j 的初始值为 1.

def f(nums):
    j=1
    count=1
    n=len(nums)
    for i in range(1,n):
        if nums[i]==nums[i-1]:
            count+=1
        else:
            count=1
        if count<=2:
            nums[j]=nums[i]
            j+=1
    return j
nums = [1,1,1,2,2,3]
print(f(nums))

6、给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

输入: [0,1,0,3,12] 输出: [1,3,12,0,0]

算法思路：设置慢指针 j用来指代非零元素且设定初始值 j=0。快指针 i 用来遍历数组，找出非零元素、然后赋值给 j 所指代的元素。即 nums【j】=nums[i]，

完成一次赋值后，慢指针 j 移动到下一个元素，即 j+=1.然后再次赋值。当 i 针遍历结束后，前 j 个元素军重置为该数组的非零元素。接下来只需把后续的元素归零即可。

def moveZeroes(nums):
    n=len(nums)
    j=0
    for i in range(n):
        if nums[i]!=0:
            nums[j]=nums[i]
            j+=1
    for k in range(j,n):
        nums[k]=0
    return nums


nums=[0,1,0,3,12]
print(moveZeroes(nums))