查找
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 -1def 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 == 1205. 同构字符串
给定两个字符串 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[c] != t[i]: return False dicts[c] = 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[c] != split_str[i]: return False dicts[c] = 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[c] = 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)$