leetcode-数组一

发表于 | 分类于 ， | 页面访问量 次
字数统计: 2.3k 字 | 阅读时长 ≈ 10 分钟

总结：本来以为数组题很简单，结果碰到好多问题。引出回溯法，和堆排序。做个专题练习一下。任重道远啊，差的太多了。

31. 下一个排列（B+）

分析：一道数组题竟然卡了好久。为什么没有思路呢。关键在于，题意理解，还有细化问题。倒叙从小到大，比较。找到前一个大于后一个，这时交换。再从后往前遍历，确保交换的是最小一个大于i-1的数。然后将i-1之后的所有数从小到大排序。也就是倒序。

转换思维一时间没有转换过来。感觉又误入歧途了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums)-1, -1, -1):
            if i-1 >=0 and nums[i] > nums[i-1]:
                for j in reversed(range(i,len(nums))):
                    if nums[j] > nums[i-1]:
                        nums[i-1], nums[j] = nums[j], nums[i-1]
                        break
                nums[i:] = nums[i:][::-1]
                break
            else:
                nums = nums.reverse()

第二种。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums)-1, 0, -1):
            if nums[i] > nums[i-1]:
                for j in range(len(nums)-1, i-1, -1):
                    if nums[j] > nums[i-1]:
                        nums[j], nums[i-1] = nums[i-1], nums[j]
                        nums[i:] = list(reversed(nums[i:]))
                        return		#稍微有点问题，题干说不返回return
        for i in range(len(nums)//2):	#优化只遍历一半，第一个与最后一个交换。
            nums[i], nums[-i-1] = nums[-i-1], nums[i]

33. 搜索旋转排序数组（B-）

分析：注意要求！你的算法时间复杂度必须是 O(log n) 级别。想到二分法。

先膜拜一下大神的代码

在用 for..in.. 迭代对象时，如果对象没有实现 __iter__ __next__ 迭代器协议，Python的解释器就会去寻找__getitem__ 来迭代对象，如果连__getitem__ 都没有定义，这解释器就会报对象不是迭代器的错误.

实例调用__class__属性时会指向该实例对应的类，然后可以再去调用其它类属性，毕竟类属性还是由类调用会比较好

bisect 其目的在于查找该数值将会插入的位置并返回，而不会插入。

bisect_left 和 bisect_right 函数，该函数用入处理将会插入重复数值的情况，返回将会插入的位置：

1
2
3
4
5
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        self.__class__.__getitem__ = lambda self, m: not(target <nums[0] <= nums[m] or nums[0] <= nums[m] < target or nums[m] < target <= nums[-1])
        i = bisect.bisect_left(self, True, 0, len(nums))
        return i if target in nums[i:i+1] else -1

第二种

一看到题目要求时间复杂度O(log n) 级别，就应该想到应该是用二分法了。但这题难就难在它并不是一个严格意义上的递增序列，而是两段递增序列组成的。那第一步就应该先用二分法找出分界点。然后对两段用二分法查找出index。相当于用了两次二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def search(self, nums: List[int], target: int) -> int:       
        #先找到两个第二个升序数组的第一项的
        l = 0
        r = len(nums) - 1
        while l < r:
            mid = (l + r) // 2
            if nums[mid] > nums[r]:
                l = mid + 1
            else:
                r = mid
        pol = l
        ans = self.binary_search(target, nums[:pol])
        if ans == -1:
            ans = self.binary_search(target, nums[pol:])
            if ans != -1:
                ans += len(nums[:pol])
                
        return ans
 
    # 二分查找index值函数   
    def binary_search(self, target, nums):
        index = -1
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = (l+r)//2
            if nums[mid] < target:
                l = mid + 1
            elif nums[mid] > target:
                r = mid - 1
            else:
                index = mid 
                break
        return index

第三种。直接对target位置进行细分比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1
        if len(nums) == 0:
            return -1
        while l <= r:
            m = (l+r)//2
            if target == nums[m]:
                return m
            elif target == nums[r]:
                return r
            elif target == nums[l]:
                return l
            else:
                if nums[m] < nums[r]:
                    if target > nums[m] and target < nums[r]:
                        l = m + 1
                    else:
                        r = m - 1
                else:
                    if target < nums[m] and target > nums[l]:
                        r = m - 1
                    else:
                        l = m + 1
        return -1

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

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

经过上一题的洗礼，这道题就显得简单很多了。先二分，找到元素。然后，往前往后循环找到第一个，和最后一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = l + (r-l) // 2
            if nums[mid] < target:
                l = mid + 1
                continue
            if nums[mid] > target:
                r = mid -1
                continue
            if nums[mid] == target:
                l = mid
                r = mid
                while l > 0 and nums[l-1] == nums[l]:
                    l = l - 1
                while r < len(nums)-1 and nums[r] == nums[r+1]:
                    r = r + 1
                return [l,r]
        return [-1, -1]

35. 搜索插入位置（D-）

分析：很简单的一道题。二分法并没有快反而变慢了，大概是用例问题。

1
2
3
4
5
6
7
8
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target in nums:
            return nums.index(target)
        else:
            nums.append(target)
            nums.sort()
            return nums.index(target)

二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) - 1
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        return low

39. 组合总和（A-）中二

分析：想用dp做但是感觉不太对。看了别人的答案，觉得步骤很巧妙。这种自迭代加上过滤，匿名函数综合运用。有点厉害。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if target == 0:
            return [[]]
        elif not candidates or target < min(candidates):
            return []
        res = []
        for i in candidates:
            # 以下过滤器可避免出现排列不同的重复答案且免排序，x>=i和x<=i都行
            for j in self.combinationSum(list(filter(lambda x: x <= i, candidates)), target - i):
                res.append([i] + j)
        return res

filter() 函数用于过滤序列，过滤掉不符合条件的元素，返回由符合条件元素组成的新列表。

该接收两个参数，第一个为函数，第二个为序列，序列的每个元素作为参数传递给函数进行判，然后返回 True 或 False，最后将返回 True 的元素放到新列表中。

第二种。

分支界限法，使用递归函数做到自然剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        mylist = []
        for i in range(len(candidates)):
            if target - candidates[i] == 0:
                mylist.append([candidates[i]])
            elif target - candidates[i] > 0:
                result = self.combinationSum(candidates[i:], target - candidates[i])
                if result:
                    for ll in result:
                        ll.insert(0, candidates[i])
                    mylist += result
        return mylist

第三种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        cand = sorted(candidates)
        
        def dfs(remain, stack):
            if remain == 0:
                ans.append(stack)
                return
            for i in cand:
                if i > remain:
                    break
                if stack and stack[-1] > i:#这个条件为了答案不重复
                    continue
                else:
                    dfs(remain - i, stack + [i])
        dfs(target, [])
        return ans

40. 组合总和 II（A-）

分析：和上一题差不多的方法。

回溯法。不是很清楚。明天开个专题。训练一下。答案贴出来，暂且不表。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        return self.dfs(candidates, target, [], [])
    
    def dfs(self, candidates, target, tmp, res):
        if sum(tmp) == target and sorted(tmp) not in res:
            res.append(sorted(tmp))
        elif sum(tmp) < target:
            for i in range(len(candidates)):
                self.dfs(candidates[i + 1:], target, tmp + candidates[i:i + 1], res)
        return res

第二种。用时短了不少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        len_nums = len(candidates)
        self.X = []
        self.func(0,target,[],candidates,len_nums)
        return self.X
    def func(self,index,target,x,nums,len_nums):
        if target==0:
            self.X.append(x[:])
        for i in range(index, len_nums):
            # 去重,如【1，1，7】--->【1，7】
            if i > index and nums[i]==nums[i-1]:
                    continue
            if target - nums[i]>=0:
                self.func(i+1,target-nums[i],x+[nums[i]],nums,len_nums)

41. 缺失的第一个正数（B+）

分析：

注意：你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

（1）首先把数组内，范围在 ( 0, n ] 元素x，放到nums[x - 1]，类似桶排序中的找位置。
（2）放好之后，进行遍历，找第一个 i + 1 != nums[i]，返回 i + 1，就是结果，如果没有就返回 n + 1。

（3）所以，最小的正整数很重要，如果是第一个没出现的数，就不能这样做了。

桶排序~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0
        while i < n:
            if nums[i] >= 1 and nums[i] <= n and nums[i] != i + 1:  # nums[i] != i + 1 如果相等或者是本身就没必要替换了，避免死循环
                if nums[nums[i] - 1] == nums[i]:  # 获取当前位置的数据，减去1是为了得到 在list要插入的位置
                    i += 1
                else:
                    nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
            else:
                i += 1
        
        for i in range(1, n + 1):
            if i != nums[i - 1]:
                return i
        return n + 1

第二种。取巧，不过是不是不满足常数空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        if not nums:
            return 1
        
        min_,max_ = min(nums), max(nums)
        
        if min_ >1:
            return 1
        else:
            for i in range(1, max_):
                if i not in nums:
                    return i
            return max(1,max_+1)

第三种 ~~ 二。plus

1
2


0%
undefined