这里指的查找问题主要包括以下两类：
- 查找元素
a是否存在？ 一般采用集合 Set 来做。 - 查找元素
a出现了几次？ 一般采用字典 Dict 来做。
leetcode 349: 两个数组的交集
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Note:
Each element in the result must be unique.
The result can be in any order.
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))
leetcode 350: 两个数组的交集 2
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.
- 与上一题类似，但多了需要计数出现次数，之后比较两个counter并生成最后结果。
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
from collections import Counter
counter1 = Counter(nums1)
counter2 = Counter(nums2)
res = []
for key in counter1.keys():
c2 = counter2.get(key,0)
res.extend([key]*min(counter1[key],c2))
return res
leetcode 242: 有效的字母异位词
Given two strings s and t , write a function to determine if t is an anagram of s.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Note:
You may assume the string contains only lowercase alphabets.
- 同样是统计单词出现个数，然后直接比较就行
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
from collections import Counter
return Counter(t) == Counter(s)
leetcode 202: 快乐数
Write an algorithm to determine if a number is “happy”.
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example:
Input: 19
Output: true
Explanation:
- 若给定数为快乐数，则最终结果为 1，若不是则进入死循环。因此循环终止条件为 sum = 1；将每次 sum 值存入 val中，利用set去重，若出现重复，则 return False
class Solution:
def isHappy(self, n: int) -> bool:
res = set()
while 1:
val = 0
while n > 0:
digit = n % 10
val += digit ** 2
n = n // 10
n = val
if val == 1:
return True
if val in res:
return False
res.add(val)
- 优化：如果计算了太多次会导致set过大导致无法存储，因此可以使用快慢指针的思路，只要存在循环则两个指针相遇时说明不是快乐数。
- python里面没有do - while语法，使用while True和中止判断来代替。
class Solution:
def isHappy(self, n: int) -> bool:
def get_next(n):
n_sum = 0
while n > 0 :
digit = n % 10
n_sum += digit ** 2
n = n // 10
return n_sum
slow,fast = n,n
while True:
slow = get_next(slow)
fast = get_next(get_next(fast))
if slow == fast:
break
if slow == 1 or fast == 1:
return True
return True if slow == 1 or fast == 1 else False
leetcode 290: 单词规律
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Example 1:
Input: pattern = "abba", str = "dog cat cat dog"
Output: true
Example 2:
Input:pattern = "abba", str = "dog cat cat fish"
Output: false
Example 3:
Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false
Example 4:
Input: pattern = "abba", str = "dog dog dog dog"
Output: false
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.
- 核心思路 : 建立单词与pattern字符的一对一映射,单纯用dict来储存，以word或者pattern里的char做key都是行不通的，不是一对一的问题，遇到下面的场景会失效：
以pattern的字符作key： "abba" "dog dog dog dog"
以word作key： "abba" "dog cat cat fish"
-
相关python函数知识补充：
-
map(function, iterable, ...) map() 会根据提供的函数对指定序列做映射。 第一个参数 function 以参数序列中的每一个元素调用 function 函数，返回包含每次 function 函数返回值的迭代器。 #示例 >>> map(lambda x: x ** 2, [1, 2, 3, 4, 5]) # 使用 lambda 匿名函数 [1, 4, 9, 16, 25] str.index(str) : 类似于find，返回str第一次出现的位置，结合map和index对pattern和str中的字符分别建立两个对应的一对一映射，再进行比较。
class Solution:
def wordPattern(self, pattern: str, str: str) -> bool:
s = str.split()
return list(map(pattern.index,pattern)) == list(map(s.index,s))
leetcode 205: 同构字符串
Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
Example 1:
Input: s = "egg", t = "add"
Output: true
Example 2:
Input: s = "foo", t = "bar"
Output: false
Example 3:
Input: s = "paper", t = "title"
Output: true
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
return list(map(s.index,s)) == list(map(t.index,t))
leetcode 1: 两数之和
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
- hashmap储存值-索引。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
mapping = dict()
for i in range(len(nums)):
if target-nums[i] not in mapping:
mapping[nums[i]] = i
else:
return [mapping[target-nums[i]],i]
leetcode 447: 回旋镖的数量
Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).
Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).
Example:
Input:
[[0,0],[1,0],[2,0]]
Output:
2
Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]
题目中所谓的 “回旋镖” 就是指数组中存在两个点 B C 与点 A 的距离相等。 即 [A, B, C] 中 distance(A, B) == distance(A, C)， [A, B, C] 就是一个 “回旋镖” 题目中要求返回满足该条件的所有点的个数， 所以可以想到固定点 A， 并计算其它所有点到 A 的距离，并用counter储存距离-次数的键值对，如果同一个距离有两个或以上的点， 就可以说明存在 “回旋镖”,对每个点A，其存在的回旋镖个数为$C_N^2$
class Solution:
def numberOfBoomerangs(self, points: List[List[int]]) -> int:
from collections import Counter
res = 0
for point in points:
distances = []
for neighbor in points:
distances.append((point[0] - neighbor[0]) ** 2+(point[1] - neighbor[1]) ** 2)
freq = Counter(distances)
for dist,num in freq.items():
if num >= 2:
res += num * (num-1)
return res
leetcode 217:存在重复元素
Given an array of integers, find if the array contains any duplicates.
Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
Example 1:
Input: [1,2,3,1]
Output: true
Example 2:
Input: [1,2,3,4]
Output: false
Example 3:
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return len(nums) != len(set(nums))
leetcode 219: 存在重复元素2
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
- 使用dict存储每一个数字对应的最后位置，遇到相同的进行比较，只要有一组满足条件即为true。
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
mapping = {}
flag = False
for i in range(len(nums)):
if nums[i] not in mapping:
mapping[nums[i]] = i
else:
if abs(i-mapping[nums[i]]) <= k:
flag = True
mapping[nums[i]] = i
return flag
leetcode 451: 根据字符出现频率排序
Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
Input:
"tree"
Output:
"eert"
Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
- 先用counter计数，然后对dict依据value降序排序，然后输出。
#对dict的排序：先对items()转list，里面每个元素是一个元组，然后用sorted结合lambda表达式。
sorted(list(dict.items()),key=lambda x:-x[1])
class Solution:
def frequencySort(self, s: str) -> str:
from collections import Counter
freq = Counter(s)
freq_list = sorted(list(freq.items()),key=lambda x :-x[1])
return "".join([str(key)*val for key,val in freq_list])
*leetcode 15: 三数之和
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
- 三个点的和，选用一个指针cur作为遍历结点，然后设立mid和right两个指针，通过cur、mid和right之和来判断是否符合条件，mid和right做为滑动窗口，如果和大于一，说明右边大，right减一，小于一则mid加一。
- 要注意不能得到重复的结果，需要设定条件来排除。$O(N^{2})$
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3 or (len(set(nums))==0 and nums[0] !=0):
return []
res = []
nums.sort()
for i in range(len(nums)):
if nums[i] > 0 :
return res
#如果上一个值和这个一样 则会得到同样的结果 跳过
if(i>0 and nums[i]==nums[i-1]):
continue
mid = i+1
right = len(nums)-1
while mid < right :
if nums[i]+nums[mid]+nums[right] == 0:
res.append([nums[i],nums[mid],nums[right]])
#保证唯一性，相同值跳过去
while mid < right and nums[mid]==nums[mid+1]:
mid += 1
while mid < right and nums[right]==nums[right-1]:
right -= 1
mid += 1
right -= 1
elif nums[i]+nums[mid]+nums[right] < 0:
mid += 1
else:
right -= 1
return res
leetcode 16: 最接近的三数之和
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
- 思路和上一题一致，只是需要改变下循环里的判断条件
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
if len(nums) < 3:
return []
res = int(1e5)
nums.sort()
for cur in range(len(nums)):
if cur!=0 and nums[cur] == nums[cur-1]:
continue
mid , right = cur + 1,len(nums)-1
while mid < right:
cur_value = nums[cur]+nums[mid]+nums[right]
if cur_value == target:
return cur_value
#更新 距离最近的值
if abs(res-target) > abs(cur_value-target):
res = cur_value
if cur_value < target:
mid += 1
else:
right -= 1
return res
leetcode 454: 四数相加2
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of $-2^{28}$ to $2^{28} - 1 $and the result is guaranteed to be at most$ 2^{31} - 1$.
Example:
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output:
2
Explanation:
The two tuples are:
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
- 暴力法需要四次遍历，时间复杂度太高。一种可行的方案是将其中两组的和存入dict中，key为和的值，value为能加到这个值的pair对数，然后再对另外两组遍历，并计算0减去另外两组的值是否在dict中来判断，这样时间复杂度只有$O(N^{2})$
class Solution:
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
vals = {}
for i in A:
for j in B:
if i+j in vals:
vals[i+j] += 1
else:
vals[i+j] = 1
cnt = 0
for k in C:
for l in D:
if -(k+l) in vals:
cnt += vals[-(k+l)]
return cnt
leetcode 49: 字母异位词分组
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
- 思路：对字母异位词，可以通过排序来让其顺序一致。。然后用dict储存，key为排序后的字符串，value为原字符串的list。
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
vals = {}
for s in strs:
k = "".join(sorted(s))
vals[k] = vals.get(k,[])+[s]
return list(vals.values())
*leetcode 220:存在重复元素3
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
- 思路：对每一个元素val，需要检索它前面(或后面)的t个元素来判断是否满足条件，暴力法两重循环超时。
- 桶排序法：将数据分到 M 个桶中,每个数字nums[i] 都被我们分配到一个桶中,分配的依据就是 nums[i] // (t + 1),这样相邻桶内的数字最多相差2 * t + 1,同一个桶内的数字最多相差t.
- 因此如果命中同一个桶内，那么直接返回True
- 如果命中相邻桶，我们再判断一下是否满足 相差 <= t ,否则返回False
- 由于题目有索引相差k的要求，因此要维护一个大小为k的窗口，定期清除桶中过期的数字。
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
if t < 0 or k < 0:
return False
all_buckets = {}
# 桶的大小设成t+1更加方便
bucket_size = t + 1
for i in range(len(nums)):
# 放入哪个桶
bucket_num = nums[i] // bucket_size
# 桶中已经有元素了
if bucket_num in all_buckets:
return True
# 把nums[i]放入桶中
all_buckets[bucket_num] = nums[i]
# 检查前一个桶
if (bucket_num-1) in all_buckets and abs(all_buckets[bucket_num-1]-nums[i])<=t:
return True
# 检查后一个桶
if (bucket_num+1) in all_buckets and abs(all_buckets[bucket_num+1]-nums[i])<=t:
return True
# 如果不构成返回条件，那么当i >= k 的时候就要删除旧桶了，以维持桶中的元素索引跟下一个i+1索引只差不超过k
if i >= k:
all_buckets.pop(nums[i-k]//bucket_size)
return False
*leetcode 149: 直线上最多的点数
[困难]Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example 1:
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
Example 2:
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
- 首先对数组里的点进行去重操作，然后对每一个点进行遍历，计算斜率作为key存入dict中，value需要计算每个点重复的次数，进行累加。之后value最大的那个为同一条直线上最多的点。(需要加上之前对应重复的点个数)
- 去重时，点的list不能作为dict的键可以转化为tuple格式。
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
from collections import Counter
#统计唯一点和重复点
points_dict = Counter([tuple(point) for point in points])
unique_points = list(points_dict.keys())
unique_num = len(unique_points)
if unique_num == 1: return points_dict[unique_points[0]]
res = 0
for i in range(unique_num-1):
x1,y1 = unique_points[i][0],unique_points[i][1]
slopes = dict()
for j in range(i+1,unique_num):
x2,y2 = unique_points[j][0],unique_points[j][1]
dx,dy = x2-x1,y2-y1
slope = dy*1000 / dx if dx !=0 else '#'
slopes[slope] = slopes.get(slope,0)+points_dict[unique_points[j]]
cur_point_max = max(slopes.values()) + points_dict[unique_points[i]]
res = max(res,cur_point_max)
return res
- 注意点：第一个点遍历范围为倒数第二个结点
- 因为浮点数京都的问题，需要乘以1000，以区分特别接近的浮点数相除的结果
In [10]: a,b = 94911151,94911150
In [11]: c,d = 94911152,9491115
In [12]: b/a
Out[12]: 0.9999999894638303
In [13]: b*1000/a
Out[13]: 999.9999894638303
In [14]: b*1000/a*1000
Out[14]: 999999.9894638303
In [15]: d/c
Out[15]: 0.9999999894638303
In [16]: d*1000/c
Out[16]: 999.9999894638304
In [17]: d*1000/c*1000
Out[17]: 999999.9894638304
- 法二 不直接使用浮点数作为key键，而是使用欧几里得算法，求得最小公约数g，然后dy dx均除以g，以
{dy/g}/{dx/g}作为键。
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
from collections import Counter,defaultdict
#统计唯一点和重复点
points_dict = Counter([tuple(point) for point in points])
unique_points = list(points_dict.keys())
unique_num = len(unique_points)
if unique_num == 1: return points_dict[unique_points[0]]
res = 0
def gcd(a,b):
if b == 0:return a
else : return gcd(b,a%b)
for i in range(unique_num-1):
x1,y1 = unique_points[i][0],unique_points[i][1]
slopes = defaultdict(int)
for j in range(i+1,unique_num):
x2,y2 = unique_points[j][0],unique_points[j][1]
dx,dy = x2-x1,y2-y1
g = gcd(dy,dx)
if g!=0:
dy //= g
dx //= g
slopes["{}/{}".format(dy,dx)] += points_dict[unique_points[j]]
cur_point_max = max(slopes.values()) + points_dict[unique_points[i]]
res = max(res,cur_point_max)
return res
- 使用
defaultdict(int)时value会有默认值0，不用担心key不存在的问题。
leetcode 704: 二分查找
Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
class Solution:
def search(self, nums: List[int], target: int) -> int:
left , right = 0,len(nums)-1
while left <= right:
mid = (left + right)//2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid+1
else:
right = mid-1
return -1
