Leetcode 刷题总结

Posted by Pelhans on February 22, 2019

线性表

数组

26. 删除排序数组中的重复项

问题:给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例: [1, 1, 2],返回 2

核心思想:用一个指针指向有用部分的末尾

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        index = 0
        for i in range(1, len(nums)):
            if nums[index] != nums[i]:
                index += 1
                nums[index] = nums[i]
        return index + 1

80. 删除排序数组中的重复项 II

问题:给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例:给定 nums = [1,1,1,2,2,3], 函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。

核心思想:加一个变量记录元素出现的次数,如果是没有排过序的则需要引入一个 hashmap

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        index = 0
        count = 1
        for i in range(1, len(nums)):
            if nums[index] == nums[i]:
                count += 1
                if count <= 2:
                    index += 1
                    nums[index] = nums[i]
            else:
                index += 1
                nums[index] = nums[i]
                count = 1
        return index + 1

33. 搜索旋转排序数组

题目描述:假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。

核心思想:二分查找,用 mid 确定一个有序部分,所有判断在有序范围内定

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        if not nums:
            return False
        start = 0
        end = len(nums)
        while start != end:
            mid = start + int((end - start)/2)
            if nums[mid] == target:
                return True
            if nums[start] < nums[mid]:
                if nums[start] <= target and nums[mid] > target:
                    end = mid
                else:
                    start = mid + 1
            elif nums[start] > nums[mid]:
                if nums[mid] < target and nums[end-1] >= target:
                    start = mid + 1
                else:
                    end = mid
            else:
                start += 1
        return False

81. 搜索旋转排序数组 II

问题描述:假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。

核心思想:在上一题的基础上,增加了数组中有重复数字的情况,如 [1,1,1,1,3],当旋转后为 [1,3,1,1,1] 时,nums[start] >= nums[mid] 不再符合判定该区间有序的条件,因此需要增加额外的判断。

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        if not nums:
            return False
        start = 0
        end = len(nums)
        while start != end:
            mid = start + int((end - start)/2)
            if nums[mid] == target:
                return True
            if nums[start] < nums[mid]:
                if nums[start] <= target and nums[mid] > target:
                    end = mid
                else:
                    start = mid + 1
            elif nums[start] > nums[mid]:
                if nums[mid] < target and nums[end-1] >= target:
                    start = mid + 1
                else:
                    end = mid
            else:
                start += 1
        return False

4. 查找两个排序数组的中位数

问题描述:给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。

核心思想:归并算法本质上还是 O(m+n)的,因此要满足要求,需要用二分法的思想,每次排除一半不满足要求的。此题可以扩展为查找任意指定位置的数。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if not nums1 and not nums2:
            return
        m = len(nums1)
        n = len(nums2)
        total = m + n
        if total%2 != 0:
            return find_kth(nums1, nums2, total/2 + 1)
        else:
            return (find_kth(nums1, nums2, total/2 ) + find_kth(nums1, nums2, total/2 + 1))/2
    
def find_kth(nums1, nums2, k):
    # list 1 is the smaller one
    k = int(k)
    size_1 = len(nums1)
    size_2 = len(nums2)
    if size_1 > size_2:
        return find_kth(nums2, nums1, k)
    if size_1 == 0: 
        return nums2[k-1]
    if k == 1: 
        return min(nums1[0], nums2[0])
    ia = int(min(k/2, size_1))
    ib = int(k - ia)
    if nums1[ia-1] < nums2[ib-1]:
        return find_kth(nums1[ia:], nums2, k-ia)
    elif nums1[ia-1] > nums2[ib-1]:
        return find_kth(nums1, nums2[ib:], k-ib)
    else:
        return nums1[ia-1]

128. 最长连续序列

问题描述:给定一个未排序的整数数组,找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。

核心思想:因为复杂度需求,采用哈希表记录每个元素是否使用,对每个元素,根据当前位置向两侧扩散,直到不连续为止。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        num_map = {i: False for i in nums}
        length = 1
        max_length = 1
        for num in num_map:
            # forward
            for i in range(1, len(nums)):
                if num + i in num_map and not num_map[num+i]:
                    num_map[num+i] = True
                    length += 1
                else:
                    break
            # backward
            for i in range(1, len(nums)):
                if num - i in num_map and not num_map[num-i]:
                    num_map[num-i] = True
                    length += 1
                else:
                    break
            if length > max_length:
                max_length = length
            length = 1
        return max_length

674. 最长连续递增序列

问题描述:给定一个未经排序的整数数组,找到最长且连续的的递增序列。

核心思想:单指针记录

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return 1
        length = 1
        max_length = 1
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                length += 1
                if max_length < length:
                    max_length = length
            else:
                length = 1
        return max_length

1. 两数之和

问题描述:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

核心思想:用 哈希表做

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if len(nums) < 2:
            return []
        num_map = {i:id for id, i in enumerate(nums)}
        for idx, num in enumerate(nums):
            dif = target - num 
            if dif in num_map and idx != num_map[dif]:
                return [idx, num_map[dif]]
        return []

15. 三数之和

问题描述:给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。注意:答案中不可以包含重复的三元组。

核心思想:双指针

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []
        nums = sorted(nums)
        res = []
        for idx in range(len(nums)-2):
            target = - nums[idx]
            if nums[idx] > 0:
                continue
            if nums[idx] == nums[idx-1] and idx > 0:
                continue
            start = idx + 1
            end = len(nums)-1
            while start < end:
                if nums[start] + nums[end] == target:
                    res.append([nums[idx], nums[start], nums[end]])
                    while start < end and nums[start] == nums[start+1]:
                        start += 1
                    while start < end and nums[end] == nums[end-1]:
                        end -= 1
                    start += 1
                    end -= 1
                elif nums[start] + nums[end] > target:
                    end -= 1
                else:
                    start += 1
        return res

16. 最接近的三数之和

问题描述:给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

核心思想:同样先排序然后左右逼近,只不过要记录最小距离

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if len(nums) < 3:
            return
        nums.sort()
        min_num = float('inf')
        sign = 1
        for idx in range(len(nums)):
            min_distance = float('inf')
            tmp_sign = 1
            start = idx + 1
            end = len(nums)-1
            while start < end:
                tmp_dis = nums[start] + nums[end] + nums[idx] - target
                tmp_abs_dis = abs(tmp_dis)
                if min_distance > tmp_abs_dis:
                    min_distance = tmp_abs_dis
                    tmp_sign = -1 if tmp_dis < 0 else 1
                if tmp_dis == 0:
                    return target
                elif tmp_dis <0 and start < end:                   
                    start += 1
                elif tmp_dis > 0 and start < end:
                    end -= 1
            if min_distance < min_num:
                min_num = min_distance
                sign = tmp_sign
        return min_num*sign + target

18. 四数之和

问题描述:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

核心思想:先拍戏,然后左右夹逼,复杂度 O(N3)

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        if len(nums) < 4:
            return []
        res = []
        nums.sort()
        end = len(nums)
        for a in range(len(nums)-3):
            for b in range(a+1, len(nums)-2):
                c = b + 1
                d = len(nums) -1 
                while c < d:
                    if nums[a] + nums[b] + nums[c] + nums[d] > target:
                        d -= 1
                    elif nums[a] + nums[b] + nums[c] + nums[d] < target:
                        c += 1
                    else:
                        tmp_res = [nums[a], nums[b], nums[c], nums[d]]
                        if tmp_res not in res:
                            res.append(tmp_res)
                        c += 1
                        d -= 1
        return res

27. 移除元素

问题描述: 给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

核心思想:双指针法

class Solution(object):
    def removeElement(self, nums, val):
        end = 0
        for i in range(0, len(nums)):
            if nums[i] != val:
                nums[end]= nums[i]
                end += 1
        return end

31. 下一个排列

问题描述:实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。必须原地修改,只允许使用额外常数空间。

核心思想:

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return []
        if len(nums) == 1:
            return nums
        if len(nums) == 2:
            nums[0], nums[1] = nums[1], nums[0]
            return nums

        pivot = len(nums) - 1
        for i in range(len(nums)-2, -1, -1):
            if nums[i] < nums[i+1]:
                pivot = i
                break
        if pivot == len(nums) - 1:
           nums = reverse(nums)
           return nums
        candi_idx = len(nums) - 1
        for i in range(len(nums)-1, -1, -1):
            if nums[i] > nums[pivot]:
                candi_idx = i
                break
        nums[pivot], nums[candi_idx] = nums[candi_idx], nums[pivot]
        nums[pivot+1:] = reverse(nums[pivot+1:])
        return nums

def reverse(nums):
    start = 0
    end = len(nums) - 1
    while start <= end:
        nums[start], nums[end] = nums[end], nums[start]
        start += 1
        end -= 1
    return nums

###