Leetcode分类刷题_leetcode分类刷题python

 

Array

27. Remove Element #Array #TwoPointers

题目考点 

•  in-place with O(1) extra memory

• The order of elements can be changed. It doesn't matter what you leave beyond the new length.

解题思路

• O(1) 说明算法不会涉及到排序以及暴力遍历，是用swap or 几个temp + replace，此题中有赘余元素，故用replace就好
• 说明最后返回的不要求改变array，只是把赘余的element换到后面去，返回前面的有效长度，所以需要两个位置参数
• 对于array检查为空和只有一个元素的情况
• 注意out of index的问题

代码

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

判断语句处可从swap改为replace，增加效率 

 if nums[i] != val:
    nums[l] = nums[i]
    l += 1

加一句判空，如果题目不要求返回任何值，直接写return

if not nums:
    return 0

总结

• 循环不变量l代表了有效数组最后一项的后一项的索引，同时也代表了返回的有效数组的长度，取值范围为0到l
• 对于空的list可以直接不进入循环，对于这种不进入后面所有语句的特殊情况，直接在开头返回

 

26. Remove Duplicates from Sorted Array #Array #TwoPointers

题目考点 

• Given a sorted array nums
•  in-place with O(1) extra memory

解题思路

• swap or replace in-place with O(1) problem
• 这道题就要考虑空array
• 与1题的区别是要与前一项比较

代码

def removeDuplicates(self, A):
    if not A:
        return 0
    l = 0
    for i in range(1, len(A)):
        if A[i] != A[l]:
            A[l+1] = A[i]
            l += 1
    return l + 1

循环从1开始是因为要从第一项跟l，即有效数组的最后一项比较，相当于check i - 1项

总结

• 循环不变量l代表了有效数组最后一项的索引，所以最后要返回l+1
• 从进循环方面：要求数组有二项，所以要判空和判1；从题目角度出发，len为0和1的情况就直接返回就好了

 

80. Remove Duplicates from Sorted Array2 #Array #TwoPointers

题目考点 

• modifying the input array in-place with O(1) extra memory
• Given a sorted array nums

解题思路

• 需要check是不是在2次以下，方法1：需要一个count，且每一次到新的数都要置为0；方法2，check i - 2 项
• 注意这里要从0开始，因为count会被开头的项影响
• 一些不用跑循环的特殊情况(0/1/2)，在开头就返回避免不必要的运行

代码

解法1

def removeDuplicates(self, nums: List[int]) -> int:
    if len(nums) < 3:
        return len(nums)       
    l = 0
    count = 0        
    for cur in range(1, len(nums)):            
        if nums[cur] != nums[l] :
            count = 0                                   
            nums[l + 1] = nums[cur]             
            l += 1
        else:
            count += 1
            if count < 2:
                nums[l + 1] = nums[cur] 
                l += 1                
    return l + 1

• 逻辑清晰，每次if只进去一次，但看起来不太工整、有重复语句

def removeDuplicates(self, nums: List[int]) -> int:
    if len(nums) <= 2:
        return len(nums)         
    l = 0
    count = 0        
    for i in range(1,len(nums)):
        if nums[l] != nums[i] : 
            count = 0                 
        if nums[l] == nums[i] : 
            count += 1                 
        if (nums[l] != nums[i]) or (nums[l] == nums[i] and count == 1):
            nums[l + 1] = nums[i]
            l += 1                
    return l + 1

解法2

• 分步的逻辑清楚，写法工整、没有重复语句，但存在进两个if的情况且if判断较长 
• 判断条件尽量不要用闭区间

def removeDuplicates(self, nums: List[int]) -> int:
    i = 0
    for n in nums:
        if i < 2 or n > nums[i-2]:
            nums[i] = n
            i += 1
    return i

总结 

• 方法1的循环不变量l代表了有效数组最后一项的索引，故返回l+1；循环不变量count代表了复制的数量
• 设定了参数后，要考虑每个参数该怎么推进。代表的意义、取值范围
• 方法1中因为同样的原因要判空、1
• 方法2是思考了题目的本质（？）后，循环不变量为i，代表有效数组的最后一项的后一项

 

189. Rotate Array #Array

题目考点 

•  in-place with O(1) extra memory

解题思路

• swap or replace in-place with O(1) problem
• 很明显这道题所有的元素都是有效的，一定是swap
• swap分一块的（次序不影响）以及单个的，一块的会比单个的多用O(k-1)
• 想象成齿轮的话，并没有类似的数据结构，但可以用同样的array拼接成“齿轮”

代码

解法1 O(n) + O(k) 整块swap

def rotate(self, nums: List[int], k: int) -> None:
    l = len(nums)
    k = k % l   
    temp = nums[l - k : l] #extra