当前位置：首页 > article >正文

LeetCode刷题-Top100-技巧题目

article 2024/10/21 9:32:02

本期给大家带来的是LeetCode的Top100热题中的技巧题目

一.[136] 只出现一次的数字（简单）

在这里插入图片描述
这道题其实很简单。我们最该想到的思路就是每当出现一个数字加上这个值，再次出现时减去这个值，最后留下的数便是答案。但是由于本题规定使用常量的额外空间，所以意味着我们需要用O(1)的空间复杂度来写这道题。我们可以初始化一个变量为0，然后和每个元素异或。
在这里插入图片描述
所以相同的数字会相互抵消，而留下来的就是只出现一次的数。
代码如下（不用转换为二进制数，直接在十进制数上操作即可）：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        length = len(nums)
        result = 0
        for i in range(length):
            result = result^nums[i]
        return result

二.[169] 只出现一次的数字（简单）

在这里插入图片描述
我们不妨直接尝试进阶版本：本题最大的题点在于这个元素的出现次数会大于n/2。那么我们就把这个元素当成“正派”，把剩下的所有元素当做“反派”（可以想象是复仇者联盟和灭霸hh）。那么只要出现反派，我们就对计数器count（初始为0）加1，而出现正派我们就加1，我们用计数器作为评判标准，当计数器为0时，我们把当前元素作为“候选者”，可以认为，当count为0时，意味着前面所有正派反派同归于尽了，所以当前的新元素作为新的开始。务必要注意的是，只有当count为0时，才会指定新的“候选者”。

代码如下：

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

三.[75] 颜色分类（中等）

在这里插入图片描述
这道题如果不考虑进阶版本的话，非常简单，只需要记录出每个颜色出现的次数，然后最后赋值即可（相信你们有更简单的方法）：

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zero_count = 0
        one_count = 0
        two_count = 0
        length = len(nums)
        for i in range(length):
            if nums[i]==0:
                zero_count+=1
            elif nums[i]==1:
                one_count+=1
            else:
                two_count+=1
        for z in range(zero_count):
            nums[z] = 0
        for o in range(one_count):
            nums[zero_count+o] = 1
        for t in range(two_count):
            nums[zero_count+one_count+t]=2
        return

但是，如果我们考虑一下进阶版本呢？
如果想要用一个额外空间来完成这道题，那么这个额外空间一定是用来交换的temp。
所以这道题用到一种稍微不太常见的技术——三指针技术（low,mid,high），最初分别指向0,0，length-1的位置（length是数组的长度）。我们要保证low的左边始终为0，high的右边始终是2，然后用mid不断完成遍历更新，具体代码逻辑如下：

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        low,mid,high = 0,0,length-1 #low始终指向0的下一个数，而high始终指向2的前一个数，用mid作为探针不断推进
        while(mid<=high):#只要mid小于等于high
            if nums[mid] == 0:
                tmp = nums[mid]
                nums[mid] = nums[low]
                nums[low] = tmp
                mid += 1
                low += 1
            elif nums[mid]==1:
                mid+=1
            else: #当探索到2的时候，这个时候需要把2这个元素赋给当前high指针指的地方，同时mid不能移动，因为它不知道换过来的元素的值是什么
                tmp = nums[high]
                nums[high] = nums[mid]
                nums[mid] = tmp
                high -= 1
        return #我们全局只使用了tmp这一个额外空间

四.[31] 下一个排列（中等）

在这里插入图片描述
这道题我只讲一下我的思路吧，最核心的想法还是从后往前遍历，因为后面的数字调换位置最有可能出现临近值。（其实这道题就是找下一个稍微大一点的临近值）。我们不妨找到第一个升序排列的二元组(i,j)，为什么要找这个二元组呢，因为一旦找到升序排列的二元组，意味着我们具备了对换的能力，我们就可以找到下一个临近值了（比如说56就是一个升序二元组，那么65就比它大）。但是我们仍然需要检查一下这个二元组的右边是否有其他数字，然后找到有没有比j更合适替换掉i的数字，比如说75936542,我们找到升序二元组(3,6)，那么除了6能替换掉3，其实还存在着后面的4也可以替换掉3的情况，那么就变成了75946532，那么既然3变成了4，那么我们就需要把后面的6542从小到大排序（这里不再解释，为了让整个子排序最小）。最后得到75942356。希望这个例子能帮到你
代码如下：

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        if length==1:
            return
        pointer = length-2
        while(pointer>=0 and nums[pointer]>=nums[pointer+1]):
            pointer-=1
        if pointer>=0:
            tail = length-1
            while(tail>=pointer and nums[tail]<=nums[pointer]):
                tail-=1
            nums[pointer],nums[tail] = nums[tail],nums[pointer]
        low = pointer+1
        high = length-1
        while(low<=high):
            nums[low],nums[high] = nums[high],nums[low]
            low+=1
            high-=1
        return

五.[287] 寻找重复数（中等）

在这里插入图片描述
进阶情况是使用时间复杂度为O（N）的算法进行解答。
这个题说实话我没想到特别好的方法，看了一眼提示，发现数组中元素值的范围是[1,n]，所以这些数字本身就可以充当索引。那么必然有两个数相等的情况下，意味着这两个数的值（也就是索引）指向数组中的同一个位置（我们暂且叫他交点）。那么就意味着有两个不同的位置可以跳到这个交点，这样是不是就形成一个闭环呢？有索引，有闭环的情况下，第一个想到的应该是指针。

思路如下：

我们要设置一个快指针、一个慢指针。目的是什么？我们要找到这个交点，也就是入口处。（如下图中的4），但是快指针和慢指针不一定非得在入口处相遇，也可能是在环图里相遇。（这个可以自己证明），但是我们最起码知道它们走过的路径中必然包含入口处。
现在我们找到这个交点了，在下图中交点为4。（这里入口其实也是4），所以我们只需要找到哪两个位置（索引）可以调到这个入口即可。一个是在环外，另一个在环内。我们假设从原点到交点一共是m步，从交点到交点（闭环路径）为n步。那么由快慢指针我们可以知道m+k1n = (m+k2n)/2,可以得到的是m = (k2-k1)*n，其中k1是慢指针在闭环中走的圈数，k2是快指针在闭环中走的圈数，k2一定比k1大。可以得到m是n的整数倍。
所以如果我们设置一个从原点出发的正常指针和一个从交点出发的正常指针,那么它们必然会在指向交点的前一个位置处含有相同的变量。而这个位置所在的值就是我们想要的答案。

代码如下：

class Solution:     
    def findDuplicate(self, nums: List[int]) -> int:
        slow = 0
        quick = 0
        while(1):
            quick = nums[nums[quick]]
            slow = nums[slow]
            if quick==slow:
                break
        #拥有相同元素的应该是环的入口
        begin = 0
        while (begin!=slow):
            begin = nums[begin]
            slow = nums[slow]
        return begin