查找

35. 搜寻插入地位

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按程序插入的地位。

你能够假如数组中无反复元素。

示例 1:

输出: [1,3,5,6], 5
输入: 2

示例 2:

输出: [1,3,5,6], 2
输入: 1

示例 3:

输出: [1,3,5,6], 7
输入: 4

示例 4:

输出: [1,3,5,6], 0
输入: 0

首先来回顾一下二分搜寻的代码

def search(nums -> list[int], target -> int) -> int:
    """
    Params:
        nums(list): sorted array
        
        target(int): int 
    """
    # 如果数组为空
    if not nums:
        return -1
    
    def helper(left -> int, right -> int):
        # 循环完结条件: left = right + 1
        while left <= right:
            
            # 防止数值过大导致溢出
            mid = left + (right - left) // 2

            # 向左膨胀
            if nums[mid] < target:
                right = mid -1
        
            # 向右膨胀
            elif nums[mid] > target:
                left = mid + 1
            
            # 找到了, 间接返回
            elif nums[mid] == target:
                return mid
            
    n = len(nums)
    idx = helper(0, n-1)
    return idx if idx else -1

def searchInsert(nums -> list[int], target -> int) -> int:
    if not nums:
        return 0

    def helper(left, right):
        while left <= right:
            mid = (left + right) // 2
            
            if nums[mid] < target:
                left = mid + 1
                
            elif nums[mid] > target:
                right = mid - 1
                
            elif nums[mid] == target:
                right = right - 1
                
        return left
    
    return helper(0, len(nums)-1)

202. 高兴数

编写一个算法来判断一个数 n 是不是高兴数。

「高兴数」定义为：对于一个正整数，每一次将该数替换为它每个地位上的数字的平方和，而后反复这个过程直到这个数变为 1，也可能是 有限循环 但始终变不到 1。如果 能够变为 1，那么这个数就是高兴数。

如果 n 是高兴数就返回 True；不是，则返回 False。

示例：

输出：19
输入：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

这道题的关键在于当数 n 不是高兴数时, 如何跳出循环, 一个简略的思路是, 应用字典来保留每次变换的后果

def isHappy(n):
    if n == 1:
        return True
    
    dicts = {}
    while n != 1:
        
        # 如果字典中已存在变换的后果, 则间接返回 False
        if n in dicts:
            return False
        
        ans = 0
        while n > 0:
            ans += (n % 10) * (n % 10)
            n //= 10
            
        n = ans
        
    # 如果能够跳出循环
    return True

复杂度剖析

内层的复杂度 $log(n)$,

思路 2

快慢指针, 起始该题中隐含着一个链表, 而咱们须要做的就是判断该链表中是否有环

def isHappy(n):
    if n == 1:
        return True
    
    def helper(num):
        ans = 0
        while n > 0:
            ans += (n % 10) * (n % 10)
            n //= 10
        return ans
    
    # 慢指针
    slow = n
    # 快指针
    fast = helper(n)

    # 如果快慢指针不相等, 直至它们相等
    while slow != fast:
        slow = helper(slow)
        fast = helper(helper(fast))
        
    return slow == 1

205. 同构字符串

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符能够被替换失去 t，那么这两个字符串是同构的。

所有呈现的字符都必须用另一个字符替换，同时保留字符的程序。两个字符不能映射到同一个字符上，但字符能够映射本人自身。

示例 1:

输出: s = “egg”, t = “add”
输入: true

示例 2:

输出: s = “foo”, t = “bar”
输入: false

示例 3:

输出: s = “paper”, t = “title”
输入: true

def isIsomorphic(s -> str, t -> str):
    if not s and not s:
        return False
    
    if not s or not t or len(s) != len(t):
        return True
    
    dicts = {}
    
    for i, c in enumerate(s):
        if c in dicts:
            if dicts != t[i]:
                return False
            
        dicts = t[i]
        
    return len(dicts) == len(set(dicts.values()))
        

工夫复杂度为 $O(n)$, 空间复杂度为 $O(1)$, 因为字典最多蕴含 128 个元素

242. 无效的字母异位词

给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输出: s = "anagram", t = "nagaram"
输入: true

示例 2:

输出: s = "rat", t = "car"
输入: false

阐明:

你能够假如字符串只蕴含小写字母。

进阶:

如果输出字符串蕴含 unicode 字符怎么办？你是否调整你的解法来应答这种状况？

思路 1

排序, 如果两个字符串是字母异位词, 则排序后的字符串将雷同

def isAnagram(s: str, t: str) -> bool:
    if not s and not t:
        return True
    
    if not s or not t or len(s) != len(t):
        return False
    
    # 排序
    s = sorted(s)
    
    t = sorted(t)
    
    # 如果两个字符串是字母异位词
    return s == t

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

思路 2

哈希表来记录每个字母呈现的次数, 因为只蕴含小写字母, 咱们能够应用固定大小的数组来实现哈希表

def isAnagram(s: str, t: str) -> bool:
    if not s and not t:
        return True
    
    if not s or not t or len(s) != len(t):
        return False
    
    # 记录每个字母呈现次数
    arr = [0] * 26
    
    for i, c in enumerate(s):
        arr[ord(c) - ord('a')] += 1
        arr[ord(t[i]) - ord('a')] -= 1
        
    # 如果某个地位的元素小于 0, 则能够间接返回 False
    for i in range(26):
        if arr[i] < 0:
            return False
        
    # 
    return sum(arr) == 0

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

如果蕴含 Unicode 字符, 则须要应用字典来记录每个字符呈现的次数, 思路雷同

290. 单词法则

给定一种法则 pattern 和一个字符串 str，判断 str 是否遵循雷同的法则。

这里的 遵循 指齐全匹配，例如，pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连贯的对应法则。

示例 1:

输出: pattern = “abba”, str = “dog cat cat dog”
输入: true

示例 2:

输出:pattern = “abba”, str = “dog cat cat fish”
输入: false

示例 3:

输出: pattern = “aaaa”, str = “dog cat cat dog”
输入: false

示例 4:

输出: pattern = “abba”, str = “dog dog dog dog”
输入: false

阐明:

你能够假如 pattern 只蕴含小写字母，str 蕴含了由单个空格分隔的小写字母。

这题和 205 题的思路是一样的, 同样借助了字典

def wordPattern(pattern: str, str: str) -> bool:
    if not pattern or not str:
        return False
    
    split_str = str.split()
    
    if len(pattern) != len(split_str):
        return False
    
    dicts = {}
    for i, c in enumerate(pattern):
        if c in dicts:
            if dicts != split_str[i]:
                return False
            
        dicts = split_str[i]
        
    return len(dicts) == len(set(dicts.values()))

349. 两个数组的交加

给定两个数组，编写一个函数来计算它们的交加。

示例 1：

输出：nums1 = [1,2,2,1], nums2 = [2,2]
输入：[2]

示例 2：

输出：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输入：[9,4]

阐明：

输入后果中的每个元素肯定是惟一的。
咱们能够不思考输入后果的程序。

去重 + 查找

def intersection(nums1: List[int], nums2: List[int]) -> List[int]:
    if not nums1 or not nums2:
        return []
    
    # 去重
    nums1 = set(nums1)
    nums2 = set(nums2)

    m = len(nums1)
    
    # 查找
    res = [i for i in nums1 if i in nums2]

    return res

工夫复杂度为 $O(m+n)$, set操作的工夫复杂度为 $O(n)$, in/contain. 空间复杂度为 $O(1)$

350. 两个数组的交加 II

给定两个数组，编写一个函数来计算它们的交加。

示例 1：

输出：nums1 = [1,2,2,1], nums2 = [2,2]
输入：[2,2]

示例 2:

输出：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输入：[4,9]

阐明：

输入后果中每个元素呈现的次数，应与元素在两个数组中呈现次数的最小值统一。
咱们能够不思考输入后果的程序。

进阶：

如果给定的数组曾经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种办法更优？
如果 nums2 的元素存储在磁盘上，内存是无限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

def intersect(nums1: List[int], nums2: List[int]) -> List[int]:
    if not nums1 or not nums2:
        return []
    
    m, n = len(nums1), len(nums2)
    res = []
    
    dicts = {}
    # 应用字典记录每个数呈现的次数
    for i in nums1:
        dicts[i] = dicts.get(i, 0) + 1
        
    for i in nums2:
        # 如果 i 在字典中并且它的值大于 0
        if i in dicts and dicts[i] > 0:
            res.append(i)
            dicts[i] -= 1
            
    return res

工夫复杂度为 $O(n+m)$, 空间复杂度为 $O(m)$ 或者 $O(n)$

如果 nums2 的元素存储在磁盘上，内存是无限的，并且你不能一次加载所有的元素到内存中, 则能够应用并行的形式进行读取.

410. 宰割数组的最大值

给定一个非负整数数组和一个整数 m，你须要将这个数组分成 m 个非空的间断子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

留神:
数组长度 n 满足以下条件:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)

示例:

输出:
nums = [7,2,5,10,8]
m = 2

输入:
18

解释:

一共有四种办法将 nums 宰割为 2 个子数组。
其中最好的形式是将其分为 [7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为 18，在所有状况中最小。

二分查找 + 贪婪

「使……最大值尽可能小」是二分搜寻题目常见的问法。

本题中，咱们留神到：当咱们选定一个值 xx，咱们能够线性地验证是否存在一种宰割计划，满足其最大宰割子数组和不超过 xx。策略如下：

def splitArray(nums: List[int], m: int) -> int:
    def check(x: int) -> bool:
        total, cnt = 0, 1
        for num in nums:
            if total + num > x:
                cnt += 1
                total = num
            else:
                total += num
        return cnt <= m


    left = max(nums)
    right = sum(nums)
    while left < right:
        mid = (left + right) // 2
        if check(mid):
            right = mid
        else:
            left = mid + 1

    return left
    

451. 依据字符呈现频率排序

给定一个字符串，请将字符串里的字符依照呈现的频率降序排列。

示例 1:

输出:
“tree”

输入:
“eert”

解释:
‘e’ 呈现两次，’r’ 和 ’t’ 都只呈现一次。
因而 ’e’ 必须呈现在 ’r’ 和 ’t’ 之前。此外，”eetr” 也是一个无效的答案。

示例 2:

输出:
“cccaaa”

输入:
“cccaaa”

解释:
‘c’ 和 ’a’ 都呈现三次。此外，”aaaccc” 也是无效的答案。
留神 ”cacaca” 是不正确的，因为雷同的字母必须放在一起。

示例 3:

输出:
“Aabb”

输入:
“bbAa”

解释:

此外，”bbaA” 也是一个无效的答案，但 ”Aabb” 是不正确的。
留神 ’A’ 和 ’a’ 被认为是两种不同的字符。

哈希表 + 排序

def frequencySort(s: str) -> str:
    if not s or len(s) < 2:
        return s
    
    dicts = {}
    res = ''
    
    # 统计每个字符呈现的次数
    for c in s:
        dicts = dicts.get(c, 0) + 1
        
    # 依照呈现次数对字符进行排序
    dicts = sorted(dicts.items(), lambda x: x[1], reverse=True)
    
    for k, v in dicts.items():
        res += k * v
    return res

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

更简洁的办法

def frequencySort(s: str) -> str:
    if not s or len(s) < 2:
        return s
    
    from collections import Counter
    
    # Counter(s) : 返回一个元素统计字典
    # most_common() : 依照元素呈现次数进行降序排序
    return ''.join(k * v for k, v in Counter(s).most_common())

540. 有序数组中的繁多元素

给定一个只蕴含整数的有序数组，每个元素都会呈现两次，唯有一个数只会呈现一次，找出这个数。

示例 1:

输出: [1,1,2,3,3,4,4,8,8]
输入: 2

示例 2:

输出: [3,3,7,7,10,11,11]
输入: 10
留神: 您的计划应该在 O(log n)工夫复杂度和 O(1)空间复杂度中运行。

思路 1

暴力算法

遍历整个数组

def singleNonDuplicate(nums: List[int]) -> int:
    n = len(nums)
    i = 0
    while i < n - 1:
        if nums[i] != nums[i+1]:
            return nums[i]
        
    return nums[n-1]
    

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

思路 2

位运算

def singleNonDuplicate(nums: List[int]) -> int:
    
    res = nums[0]
    
    for i in nums[1:]:
        res = res & i
        
    return res
    

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

思路 3

二分搜寻

def singleNonDuplicate(nums: List[int]) -> int:
    n = len(nums)

    left, right = 0, n - 1

    while left <= right:

        mid = (left + right) // 2

        if mid + 1 < n and mid % 2 == 0:
            # mid 为奇数, 阐明 mid 之前的局部和之后的局部均为偶数
            # 阐明这个数在 mid 右侧
            if nums[mid] == nums[mid + 1]:
                left = mid + 2
            # 
            else:
                right = mid - 1

        elif mid + 1 < n and mid % 2:
            # mid 为奇数, 阐明 mid 之前的局部和之后的局部均为奇数
            if nums[mid] == nums[mid + 1]:
                right = mid - 1
            # 
            else:
                left = mid + 1

        else:
            return nums[mid]

    return nums[left]

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