茉莉Python

voidqueens@hotmail.com

0%

LeetCode-18-搜索和排序

33. 搜索旋转排序数组

链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

给你一个整数数组 nums ,和一个整数 target 。

该整数数组原本是按升序排列,但输入时在预先未知的某个点上进行了旋转。(例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。


示例 1:

输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
示例 2:

输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:

输入:nums = [1], target = 0
输出:-1

提示:

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
nums 肯定会在某个点上旋转
-10^4 <= target <= 10^4

题解一|二分查找:

时间复杂度:O(logn),其中 n 为 nums数组的大小。整个算法时间复杂度即为二分搜索的时间复杂度 O(logn)。

空间复杂度:O(1) 我们只需要常数级别的空间存放变量。

注意:if中很多等号的判断

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        left,right=0,len(nums)-1
        while left<=right:
            mid=left+(right-left)//2
            if nums[mid]==target:
                return mid
            elif nums[0]<=nums[mid] : # 此处加=号,解决case[3,1]和1
                if nums[0]<=target<nums[mid]: # 此处加=号,解决case[1,3,5]和1
                    right=mid-1
                else:
                    left=mid+1
            else:
                if nums[mid]<target<=nums[len(nums)-1]: # 此处加=号,解决case[1,3]和3
                    left=mid+1
                else:
                    right=mid-1
        return -1

34. 在排序数组中查找元素的第一个和最后一个位置

链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值,返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

题解一:

时间复杂度: O(n)
空间复杂度: O(1)

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        res=[-1,-1]
        for i in range(len(nums)):
            if nums[i]==target:
                res[0]=i
                break
        if res[0]==-1:
            return res
        for i in range(len(nums)-1,-1,-1):
            if nums[i]==target:
                res[1]=i
                break
        return res

题解二|二分查找:

时间复杂度: O(logn)
空间复杂度: O(1)

    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
            return [-1,-1]
        left,right=0,len(nums)-1
        while left=target:
                right=mid
            else:
                left=mid+1
        if nums[left]!=target:
            return [-1,-1]
        start=left

        left,right=0,len(nums)-1
        while left

75. 颜色分类

链接:https://leetcode-cn.com/problems/sort-colors/

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶:

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗?

题解一|重写数组:

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        c0,c1,c2=0,0,0
        for i in nums:
            if i==0:
                c0+=1
            elif i==1:
                c1+=1
            elif i==2:
                c2+=1
        for i in range(len(nums)):
            if c0:
                nums[i]=0
                c0-=1
            elif c1:
                nums[i]=1
                c1-=1
            elif c2:
                nums[i]=2
                c2-=1

题解二|单指针:

时间复杂度:O(n),其中 n 是数组 nums 的长度。
空间复杂度:O(1)。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n=len(nums)
        ptr=0
        for i in range(n):
            if nums[i]==0:
                nums[i],nums[ptr]=nums[ptr],nums[i]
                ptr+=1
        for i in range(ptr,n):
            if nums[i]==1:
                nums[i],nums[ptr]=nums[ptr],nums[i]
                ptr+=1

题解三|双指针:

时间复杂度:O(n),其中 n 是数组 nums 的长度。
空间复杂度:O(1)。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n=len(nums)
        p0=p1=0
        for i in range(n):
            if nums[i]==1:
                nums[i],nums[p1]=nums[p1],nums[i]
                p1+=1
            elif nums[i]==0:
                nums[i],nums[p0]=nums[p0],nums[i]
                if p0 < p1:
                    nums[i],nums[p1]=nums[p1],nums[i]
                p0+=1
                p1+=1
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n=len(nums)
        p0,p2=0,n-1
        i=0
        while i<=p2:
            while i<=p2 and nums[i]==2:
                nums[i],nums[p2]=nums[p2],nums[i]
                p2-=1
            if nums[i]==0:
                nums[i],nums[p0]=nums[p0],nums[i]
                p0+=1
            i+=1

162. 寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。

数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

示例 1:

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素,你的函数应该返回其索引 2。
示例 2:

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5 
解释: 你的函数可以返回索引 1,其峰值元素为 2;
     或者返回索引 5, 其峰值元素为 6。
说明:

你的解法应该是 O(logN) 时间复杂度的。

题解一|线性扫描:

1、一直上坡
2、一直下坡
3、上坡和下坡

时间复杂度 : O(n)。 我们对长度为 n 的数组 nums 只进行一次遍历。
空间复杂度 : O(1)。 只使用了常数空间。

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(len(nums)-1):
            if nums[i]>nums[i+1]:
                return i
        return len(nums)-1

题解二|递归|二分查找:
时间复杂度 : O(logn)。每一步都将搜索空间减半。因此,总的搜索空间只需要 log(n) 步。其中 n 为 nums 数组的长度。
空间复杂度: O(logn)。每一步都将搜索空间减半。因此,总的搜索空间只需要 log(n) 步。于是,递归树的深度为 log(n)。

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return self.binarySearch(nums,0,len(nums)-1)
    def binarySearch(self,nums,left,right):
        if left==right:
            return left
        mid=left+(right-left)//2
        if nums[mid]>nums[mid+1]:
            return self.binarySearch(nums,left,mid)
        return self.binarySearch(nums,mid+1,right)

题解三|迭代|二分查找:

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left,right=0,len(nums)-1
        while left<right:
            mid=left+(right-left)//2
            if nums[mid]>nums[mid+1]:
                right=mid
            else:
                left=mid+1
        return left

179. 最大数

链接:https://leetcode-cn.com/problems/largest-number/

给定一组非负整数 nums,重新排列它们每个数字的顺序(每个数字不可拆分)使之组成一个最大的整数。

注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。

示例 1:

输入:nums = [10,2]
输出:"210"
示例 2:

输入:nums = [3,30,34,5,9]
输出:"9534330"
示例 3:

输入:nums = [1]
输出:"1"
示例 4:

输入:nums = [10]
输出:"10"


提示:

1 <= nums.length <= 100
0 <= nums[i] <= 109

题解一|重载运算符:

class StrLt(str):
    def __lt__(x,y):
        # 1、比较 ab 与 ba的大小,按降序排列;
        # 2、将数组转化为字符串。
        return x+y>y+x

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        tostr=[str(i) for i in nums]
        tostr.sort(key=StrLt)
        return ''.join(tostr) if tostr[0] != '0' else '0'

215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

题解一|小顶堆:

class Solution(object):
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        self.buildHeap(nums[:k])
        # print(self.heapList)
        for i in range(k,len(nums)):
            if nums[i]>self.heapList[1]:
                self.heapList[1]=nums[i]
                self.percDown(1)
        return self.heapList[1]
    def percDown(self,i):
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
                # self.heapList[i],self.heapList[mc]=self.heapList[mc],self.heapList[i]
            i = mc

    def minChild(self,i):
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i*2] < self.heapList[i*2+1]:
                return i * 2
            else:
                return i * 2 + 1

    def delMin(self):
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval

    def buildHeap(self,alist):
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            self.percDown(i)
            i = i - 1

240. 搜索二维矩阵 II

链接:https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1:

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出:true
示例 2:

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出:false

提示:

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109

题解一|暴力:

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        for row in matrix:
            if target in row:
                return True
        return False

题解二|二分查找:

时间复杂度:O(mlogn)
空间复杂度:O(1)

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        for i in range(len(matrix)):
            if self.binarySearch(matrix,i,target):
                return True
        return False

    def binarySearch(self,matrix,i,target):
        left,right=0,len(matrix[0])-1
        while left<=right:
            mid=left+(right-left)//2
            if target > matrix[i][mid]:
                left=mid+1
            elif target < matrix[i][mid]:
                right=mid-1
            elif target == matrix[i][mid]:
                return True
        return False

题解三|规律:

时间复杂度:O(m+n)
空间复杂度:O(1)

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        left,right=0,len(matrix[0])-1
        while left<len(matrix) and right>=0:
            if matrix[left][right]>target:
                right-=1
            elif matrix[left][right]<target:
                left+=1
            elif matrix[left][right]==target:
                return True
        return False

278. 第一个错误的版本

链接:https://leetcode-cn.com/problems/first-bad-version/

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5,并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以,4 是第一个错误的版本。 

题解一|二分查找:

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left,right=1,n
        while left<=right: # 注意是小于等于
            mid=left+(right-left)//2
            if isBadVersion(mid):
                right=mid-1
            else:
                left=mid+1
        return left

347. 前 K 个高频元素

链接:https://leetcode-cn.com/problems/top-k-frequent-elements/

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]


提示:

你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

题解一|小根堆:

import collections 
class Solution(object):
    def __init__(self):
        self.size=0
        self.heap=[(0,0)]

    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        hash={}
        for i in nums:
            hash[i]=hash.get(i,0)+1
        hashlist=[[key,value] for key,value in hash.items()]
        self.buildHeap(hashlist[:k]) # 建立基于次数的小根堆
        for i in range(k,len(hashlist)):
            if self.heap[1][1]<=hashlist[i][1]:
                self.heap[1]=hashlist[i]
                self.percDown(1)
        return [self.heap[i][0] for i in range(1,k+1)]

    def percDown(self,i):
        while (i * 2) <= self.size:
            mc = self.minChild(i)
            if self.heap[i][1] > self.heap[mc][1]: # 注意,基于次数
                self.heap[i],self.heap[mc]=self.heap[mc],self.heap[i]
            i = mc

    def minChild(self,i):
        if i * 2 + 1 > self.size:
            return i * 2
        else:
            if self.heap[i*2][1] < self.heap[i*2+1][1]: # 注意此处比较的是次数,而不是self.heap[i*2] < self.heap[i*2+1]
                return i * 2
            else:
                return i * 2 + 1
    def buildHeap(self,arr):
        i=len(arr)//2
        self.size=len(arr)
        self.heap=[(0,0)]+arr[:]
        while i>0:
            self.percDown(i)
            i-=1

451. 根据字符出现频率排序

链接:https://leetcode-cn.com/problems/sort-characters-by-frequency/

给定一个字符串,请将字符串里的字符按照出现的频率降序排列。

示例 1:

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次,'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外,"eetr"也是一个有效的答案。
示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外,"aaaccc"也是有效的答案。
注意"cacaca"是不正确的,因为相同的字母必须放在一起。
示例 3:

输入:
"Aabb"

输出:
"bbAa"

解释:
此外,"bbaA"也是一个有效的答案,但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

题解一|小根堆:

class Solution(object):
    def __init__(self):
        self.size=0
        self.heap=[['0',0]]
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        hash={}
        for i in s:
            if i not in hash:
                hash[i]=1
            else:
                hash[i]+=1
        hashlist=[[key,value] for key,value in hash.items()]
        self.buildHeap(hashlist)

        for i in range(len(hashlist),0,-1): 不要写成self.size,和下面self.size-=1不好区分。
        # for i in range(self.size,0,-1):
            self.heap[1],self.heap[i]=self.heap[i],self.heap[1]
            self.size-=1 # 关键点,减1后避免和最后一个元素再交换回去。
            self.percDown(1)
        result=''
        for i in range(1,len(self.heap)):
            result+=str(self.heap[i][0]*self.heap[i][1])
        return result
    def percDown(self,i):
        while (i*2)<=self.size:
            mc=self.minChild(i)
            if self.heap[i][1]>self.heap[mc][1]:
                self.heap[i],self.heap[mc]=self.heap[mc],self.heap[i]
            i=mc
    def minChild(self,i):
        if i*2+1>self.size:
            return i*2
        else:
            if self.heap[i*2][1]<self.heap[i*2+1][1]:
                return i*2
            else:
                return i*2+1
    def buildHeap(self,arr):
        i=len(arr)//2
        self.size=len(arr)
        self.heap=[['0',0]]+arr
        while i>0:
            self.percDown(i)
            i-=1

973. 最接近原点的 K 个点

链接:https://leetcode-cn.com/problems/k-closest-points-to-origin/

我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。

(这里,平面上两点之间的距离是欧几里德距离。)

你可以按任何顺序返回答案。除了点坐标的顺序之外,答案确保是唯一的。

示例 1:

输入:points = [[1,3],[-2,2]], K = 1
输出:[[-2,2]]
解释: 
(1, 3) 和原点之间的距离为 sqrt(10),
(-2, 2) 和原点之间的距离为 sqrt(8),
由于 sqrt(8) < sqrt(10),(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点,所以答案就是 [[-2,2]]。
示例 2:

输入:points = [[3,3],[5,-1],[-2,4]], K = 2
输出:[[3,3],[-2,4]]
(答案 [[-2,4],[3,3]] 也会被接受。)


提示:

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

题解一|大根堆:

import math
class Solution(object):
    def __init__(self):
        self.size=0
        self.heap=[[0,0]]
    def kClosest(self, points, K):
        """
        :type points: List[List[int]]
        :type K: int
        :rtype: List[List[int]]
        """
        self.buildHeap(points[:K])
        for i in range(K,len(points)):
            if self.cal(self.heap[1]) > self.cal(points[i]):
                self.heap[1]=points[i]
                self.percDown(1)
        return [self.heap[i] for i in range(1,K+1)]

    def percDown(self,i):
        while i*2<=self.size:
            mc=self.maxChild(i)
            if self.cal(self.heap[i])<self.cal(self.heap[mc]):
                self.heap[i],self.heap[mc]=self.heap[mc],self.heap[i]
            i=mc
    def maxChild(self,i):
        if (i*2+1)>self.size:
            return i*2
        else:
            if self.cal(self.heap[i*2])>self.cal(self.heap[i*2+1]):
                return i*2
            else:
                return i*2+1
    def buildHeap(self,arr):
        i=len(arr)//2
        self.heap=[[0,0]]+arr
        self.size=len(arr)
        while i>0:
            self.percDown(i)
            i-=1

    def cal(self,point):
        return math.sqrt(point[0]**2+point[1]**2)