查找 1

Posted on | | Visitors: ℃
Words count in article: 1.5k

查找

349. 两个数组的交集

利用set的不重复性，

1
2
3
4
def intersection(self, nums1: List[int], nums2: List[int])
    set1 = set(nums1)
    set2 = set(nums2)
    return [i for i in set1 if i in set2]

62 ms

也可以直接使用set的求交符号，但是底层实现类似

1
2
def intersection(self, nums1: List[int], nums2: List[int]) 
    return set(nums1)&set(nums2)

84 ms

350. 两个数组的交集 II

增加了次数的要求，此时就需要一个计数表，使用Counter简单实现

1
2
3
4
5
6
7
8
9
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
    res = []
    from collections import Counter
    cnt1 = Counter(nums1)
    for i in nums2:
        if cnt1[i] > 0:
            res.append(i)
            cnt1[i] -= 1
    return res

时间 88 ms 有点慢， 复杂度是O（M+N）的

为什么很慢在提示给出了，nums1很小，nums2很大，所以可以稍微加一句if len(nums1) < len(nums2): nums2, nums1 = nums1, nums2 让conter执行较长的，循环较小的，速度比较稳定在60 ms

202. 快乐数

1
2
3
4
5
6
7
输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

定义： 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

题目的建模过程是简单的，分开然后求平方和，不为1就继续，需要判断的是，在发生始终变不到1的情况下，如何及时跳出。而且每一各数字对应的下一个数字都是绝对的，是一个链表一样的情况。

仔细思考可以发现，一个数字的平凡和结果最后是不可能溢出的，那么这个while循环的结果只有两种，变成了1，或者变成了之前的数字，导致有环

用一个set来记录之前出现过的数字，一直迭代下去，如果是出现了重复的数字就是环，返回False就行，这样代码就很简单了

1
2
3
4
5
6
7
8
9
10
11
12
13
def isHappy(self, n: int) -> bool:
    num_table = set()
    while n >= 1 and n not in num_table:
        sum = 0
        num_table.add(n)
        while n > 0:
            n, mod = divmod(n, 10)
            sum += mod ** 2
        if sum == 1:
            return True
        else:
            n = sum
    return False

290. 单词规律

1
2
输入: pattern = "abba", str = "dog cat cat dog"
输出: true

遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律

很明显的映射关系，只要一个个匹配就行，对pattern中的每个a,b,c 都存放在一个dict，a对应的是dog

pattern str_list
a dog
b cat
c apple 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def wordPattern(self, pattern: str, str: str) -> bool:
   str_list = str.split(' ')
   if len(pattern) != len(str_list):
       return False
   hash_table = {}
   for i in range(len(pattern)):
       if pattern[i] not in hash_table.keys():
           if str_list[i] in hash_table.values():
               return False
           else:
               hash_table[pattern[i]] = str_list[i]
       elif hash_table[pattern[i]] != str_list[i]:
           return False
   return True

算法时间 40 ms 复杂度是O（N）级别

451. 根据字符出现频率排序

这个就是典型的排序加哈希表题，哈希表存储每个字符的出现次数

1
2
3
4
5
6
7
8
9
输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

采用Counter 来计数，喜欢自己写的也可以用dict实现，效率没有太大区别

1
2
3
4
5
6
7
8
9
10
def frequencySort(self, s: str) -> str:
    from collections import Counter
    s1 = Counter(s)

    s2 = sorted(s1.items(),key=lambda item:item[1],reverse=True)

    res = ''
    for key,value in s2:
        res += key*value
    return res

执行时间 40 ms

242. 有效的字母异位词

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

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

满足字符串的长度，字母出现的次数一致即可，那还是用两个Counter来实现应该最为简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def isAnagram(self, s: str, t: str) -> bool:
    if s is None or t is None:
        return False
    if len(s) != len(t):
        return False

    from collections import Counter
    cnt1 = Counter(s)
    cnt2 = Counter(t)
    char_tab = cnt2.keys()
    for char in cnt1.keys():
        if char not in char_tab:
            return False
        elif cnt2[char] != cnt1[char]:
            return False
    return True

时间：44 ms, 在所有 Python3 提交中击败了96.13%的用户

205. 同构字符串

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身

这个题和上面的单词规律是一样，都检查映射关系是否正确：

一个非常python 的写法是

map(s.index, s) == map(t.index, t)

由于返回的是map的对象，没有实现 == 运算符重载

1
2
def isIsomorphic(self, s: str, t: str) -> bool:
    return list(map(s.index,s)) == list(map(t.index,t))

540. 有序数组中的单一元素

一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数

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

如果全都是两个的，那么肯定num[奇数] == nums[偶数]，由于只有一个，导致后面发生变化，每一次取一个mid，来缩短查询距离，如果mid是偶数，那么和1异或的话，那么得到的是mid+1，如果mid是奇数，得到的是mid-1。如果相等的话，那么唯一的元素还在这之后，往后找就可以了

1
2
3
4
5
6
7
8
9
def singleNonDuplicate(self, nums):
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] == nums[mid ^ 1]:
                lo = mid + 1
            else:
                hi = mid
        return nums[lo]
-------------本文结束感谢您的阅读 :D -------------
Show comments from Gitment