乐趣区

关于leetcode:Leetcode-搜索2

1. 两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你能够假如每种输出只会对应一个答案。然而,数组中同一个元素不能应用两遍。

 

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]


def twoSum(nums: List[int], target: int) -> List[int]:
    if not nums or len(nums) < 2:
        return
    prefix_sum = {}
    
    n = len(nums)
    
    for i in range(n):
        if nums[i] in prefix_sum:
            return [prefix_sum[nums[i]], i]
            
        prefix_sum[target-nums[i]] = i

工夫复杂度为 $O(n)$, 工夫复杂度为 $O(n)$

15. 三数之和

给你一个蕴含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c,使得 a + b + c = 0?请你找出所有满足条件且不反复的三元组。

留神:答案中不能够蕴含反复的三元组。

 
示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组汇合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

def threeSum(nums: List[int]) -> List[List[int]]:
    if not nums or len(nums) < 3:
       return []
    nums.sort()
    n = len(nums)
    res = []

    if nums[0] > 0 or nums[-1] < 0:
        return res

    for i in range(n-2):
        p1 = i + 1
        p2 = n - 1

        if i - 1 >= 0 and nums[i] == nums[i-1]:
            continue
        while p1 < p2:
            
            if nums[p1] + nums[p2] + nums[i] < 0:
                # while p1 < n-1 and nums[p1] == nums[p1+1]:
                #     p1 += 1 
                p1 += 1
            elif nums[p1] + nums[p2] + nums[i] > 0:
                # while p2 > 0 and nums[p2] == nums[p2-1]:
                #     p2 -= 1
                p2 -= 1
            elif nums[p1] + nums[p2] + nums[i] == 0:
                res.append([nums[i], nums[p1], nums[p2]])
                # print('done')
                p1 += 1
                p2 -= 1
                
    return res

工夫复杂度为 $O(n^2)$, 工夫复杂度为 $O(1)$

16. 最靠近的三数之和

给定一个包含 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最靠近。返回这三个数的和。假设每组输出只存在惟一答案。
示例:

输出:nums = [-1,2,1,-4], target = 1
输入:2
解释:与 target 最靠近的和是 2 (-1 + 2 + 1 = 2)。
 

def threeSumClosest(nums: List[int], target: int) -> int:
    if not nums or len(nums) < 3:
        return 
        
    n = len(nums)
    nums.sort()
    res = []
    nearest_sum = sum(nums[:3])
    if nums[0] >= target:
        return sum(nums[:3])
        
    if nums[-1] <= target:
        return sum(nums[-3:])
        
    for i in range(n-2):
        p1 = i + 1
        p2 = n - 1
        
        while p1 < p2:
            temp = nums[i] + nums[p1] + nums[p2]
            # print(temp)
            if abs(temp - target) < abs(nearest_sum - target):
                # res = [nums[i], nums[p1], nums[p2]]
                nearest_sum = temp
                
            if temp < target:
                p1 += 1
            elif temp > target:
                p2 -= 1
            else:
                return target
                
    return nearest_sum

工夫复杂度为 $O(n^2)$, 工夫复杂度为 $O(1)$

18. 四数之和

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

留神:

答案中不能够蕴含反复的四元组。

示例:

给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。
满足要求的四元组汇合为:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
    if not nums or len(nums) < 4:
        return []

    n = len(nums)

    nums.sort()
    res = []
    for i in range(n-3):
        # 保障 nums[i]扭转了
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i+1, n-2):
            # 保障 nums[j]扭转了
            if j > i + 1 and nums[j] == nums[j-1]:
                continue
            
            h = j + 1
            k = n - 1

            while h < k:
                four_sum = nums[i] + nums[j] + nums[h] + nums[k]

                if four_sum > target:
                    k -= 1
                elif four_sum < target:
                    h += 1

                else:
                    res.append([nums[i], nums[j], nums[h], nums[k]])
                    while h < k and nums[h] == nums[h+1]:
                        h += 1

                    while h < k and nums[k] == nums[k-1]:
                        k -= 1
                    k -= 1
                    h += 1
    return res

工夫复杂度为 $O(n^3)$, 空间复杂度为 $O(1)$

49. 字母异位词分组

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母雷同,但排列不同的字符串。

示例:

输出: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输入:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]

阐明:

所有输出均为小写字母。
不思考答案输入的程序。

思路 1: 暴力解法

两两进行比拟, 判断其是否为异位词

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    if not strs: 
        return []    
    if len(strs) < 2:
        return [strs]
    
    # 判断两个词是否为异位词
    def isAnagram(s1, s2):
        if not s1 and not s2:
            return True
        if not s1 or not s2 or len(s1) != len(s2):
            return False
        
        return sorted(s1) == sorted(s2)
    
    dicts = {}
    
    for s in strs:
        
        flag = False
        for w in dicts.keys():
            if isAnagram(s, w):
                dicts[w].append(s)
                flag = True
        if not flag:
            dicts[s] = [s]
            
    return list(dicts.values())

工夫复杂度为 $O(n^2klogk)$, 空间复杂度为 $O(nk)$

因为工夫简单度过高并未通过测试

思路 2

排序 + 哈希表

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    if not strs: 
        return []    
    
    dicts = {}
    # 异位词排序之后雷同
    
    for s in strs:
        sorted_s = ''.join(sorted(s))
        if sorted_s in dicts:
            dicts[sorted_s].append(s)
        eles:
            dicts[sorted_s] = [s]
            
    return list(dicts.values())

工夫复杂度为 $O(nklogk)$, 空间复杂度为 $O(nk)$

思路 3

计数 + 哈希表

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    if not strs: 
        return []    
    
    # 
    from collections import defaultdict
    dicts = collections.defaultdict(list)
    for s in strs:
        
        # 统计每个字符呈现的个数
        arr = [0] * 26
        for c in s:
            arr[ord(c) - ord('a')] += 1
        
        # 异位词只是单词程序产生扭转, 每个单词的计数并未变动
        dicts[tuple(arr)].append(s)

    return list(dicts.values())

219. 存在反复元素 II

给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的 绝对值 至少为 k。

示例 1:

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

示例 2:

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

示例 3:

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

哈希表记录每个元素呈现的右边界

def containsNearbyDuplicate(nums: List[int], k: int) -> bool:
    if not nums:
        return False
    
    dicts = {}
    n = len(nums)
    flag = False
    
    for i in range(n):
        if nums[i] in dicts:
            if i - dicts[nums[i]] <= k:
                # 只有存在就为真
                return True
                
        # 不论 nums[i] 是否在字典中, 都须要更新右边界
        dicts[nums[i]] = i
    return False

工夫复杂度为 $O(n)$, 空间复杂度为 $O(n)$

220. 存在反复元素 III

在整数数组 nums 中,是否存在两个下标 i 和 j,使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t,且满足 i 和 j 的差的绝对值也小于等于 ķ。

如果存在则返回 true,不存在返回 false。

示例 1:

输出: nums = [1,2,3,1], k = 3, t = 0
输入: true

示例 2:

输出: nums = [1,0,1,1], k = 1, t = 2
输入: true

示例 3:

输出: nums = [1,5,9,1,5,9], k = 2, t = 3
输入: false

依据题目, $m, n \in [i, i+k]$ 范畴内的元素, 只有存在 abs(nums[m] – nums[n]) <= t 即可

对于数组 [0, 5, 1, 9, 3, 4], t = 3, 设置桶的大小为 4 , 依照 nums[i] // 4 来构建桶

0, 1, 3 位于同一个桶

4, 5 位于同一个桶

9 位于同一个桶

这样保障每一个桶内的元素都相差不会超过t, 先不思考 k 的限度, 存在以下两种状况

  1. 一个桶中蕴含多个元素
  2. 如果以后元素与相邻桶中的元素相差小于t

另外, 思考 k 的限度, 能够应用一个滑动窗口

咱们应用字典来示意桶, 键为桶号, 值为处于该桶的元素

def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
    if not nums:
        return False
    
    bucket = {}
    n = len(nums)
    
    bucket_size = t + 1
    for i in range(n):
        num = nums[i] // bucket_size
        
        # 如果该桶不为空, 则间接返回 True
        # 每个桶只蕴含一个元素
        if num in bucket:
            return True
        
        # 将元素放入桶中
        bucket[num] = nums[i]
        
        # 查看前一个桶
        if num - 1 in bucket and abs(bucket[num - 1] - nums[i]) <= t:
            return True
        
        # 查看后一个桶
        if num + 1 in bucket and abs(bucket[num + 1] - nums[i]) <= t:
            return True
        
        
        # 对索引进行了限度, 保障所有桶内的元素都处于 (i-k, i], 相当于一个固定大小的滑动窗口
        if i >= k:
            bucket.pop(nums[i-k] // bucket_size)
            
            
    return False

447. 盘旋镖的数量

给定立体上 n 对不同的点,“盘旋镖”是由点示意的元组 (i, j, k),其中 i 和 j 之间的间隔和 i 和 k 之间的间隔相等(须要思考元组的程序)。

找到所有盘旋镖的数量。你能够假如 n 最大为 500,所有点的坐标在闭区间 [-10000, 10000] 中。

示例:

输出:
[[0,0],[1,0],[2,0]]

输入:
2

解释:
两个盘旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

思路 1

哈希表

顺次以数组中的每个元素作为i, 计算残余元素与之的间隔, 并对不同间隔进行计数, 应用字典进行保留

def numberOfBoomerangs(points: List[List[int]]) -> int:
    if not points or len(points) < 3:
        return 0
    
    n = len(points)
    
    def dist(p1, p2):
        return (p1[0] - p2[0]) * (p1[0] - p2[0])  + (p1[1] - p2[1]) * (p1[1] - p2[1])

    
    res = 0
    for i in range(n):
        dicts = {}
        for j in range(n):
            if j == i:
                continue
                
            dis = dist(points[i], points[j])
            dicts[dis] = dicts.get(dis, 0) + 1
            
        for _, v in dicts.items():
            if v > 1:
                res += v * (v - 1)
        
    return res

工夫复杂度为 $O(n^2)$, 空间复杂度为 $O(n)$

149. 直线上最多的点数

给定一个二维立体,立体上有 n 个点,求最多有多少个点在同一条直线上。

示例 1:

输出: [[1,1],[2,2],[3,3]]
输入: 3
解释:
^
|
| o
| o
| o
+————->
0 1 2 3 4

示例 2:

输出: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输入: 4
解释:
^
|
| o
| o o
| o
| o o
+——————->
0 1 2 3 4 5 6

上一题中应用字典对不同间隔进行计数, 这题应用字典对不同斜率进行计数

固定两点,

def maxPoints(points: List[List[int]]) -> int:
    if not points:
        return 0
    if len(points) < 3:
        return len(points)
    
    n = len(points)
    def slope(p1, p2):
        if p1[0] == p2[0]:
            return float('inf')
            
        return (p1[1] - p2[1]) / (p1[0] - p2[0])
        
    from  collections import Counter
    
    for p in points:
        repeated_cnt = sum([1 for point in points if point == p])
        
        counter = Counter([slope(p, point) for point in points if point != p])
        
        temp = counter.most_common(1)[0][1] + repeated_cnt
        
        res = max(res, temp + repeated_cnt)
            
    return res
    

454. 四数相加 II

给定四个蕴含整数的数组列表 A , B , C , D , 计算有多少个元组 (i, j, k, l),使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化,所有的 A, B, C, D 具备雷同的长度 N,且 0 ≤ N ≤ 500。所有整数的范畴在 -228 到 228 – 1 之间,最终后果不会超过 231 – 1。

例如:

输出:
A = [1, 2]
B = [-2,-1]
C = [-1, 2]
D = [0, 2]

输入:
2

解释:
两个元组如下:

  1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
    if not A:
        return 0
    
    dicts = {}
    
    for a in A:
        for b in B:
            # 应用字典保留 a + b, 对两数之和进行计数
            dicts[a+b] = dicts.get(a+b, 0) + 1
            
    res = 0
    for c in C:
        for d in D:
            if -(c + d) in dicts:
                res += dicts[-(c + d)]
    return res

工夫复杂度为 $O(n^2)$, 空间复杂度为 $O(n)$

该问题能够同样扩大到 n 个数相加的问题, 联合二分的思路, 同样能够不便的求解

退出移动版