LC吐血整理-Array篇

Posted on | In
人生苦短 我学python

所有题解方法请移步 github-Leecode_summary

1. 两数之和

　　hash() 用于获取取一个对象（字符串或者数值等）的哈希值

散列表(Hash table，也叫哈希表)，是根据关键码值(Key value)而直接进行访问的数据结构。
　　它通过把关键码值(Key)映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数f(Key)，存放记录的表叫做散列表(M)。给定表M。

第一题的题解方法用dict模拟hash： 

1
2
3
4
5
6
7
8
class Solution(object):
        hashmap = {}
        for ind,num in enumerate(nums):
            hashmap[num] = ind            # num不唯一会覆盖  因为题目声明存在唯一解 so who care
        for i,num in enumerate(nums):
            j = hashmap.get(target - num)      # 根据key获取value: dict.get(key)/dict[key]
            if j is not None and i!=j:
                return [i,j]
1
2
3
# 附： 根据dict的value获取对应的key
def get_keys(d, value):  
    return [k for k,v in d.items() if v == value]      #value 可以不唯一

27. 移除元素

List.pop(）/ dict.pop()
　　删除元素，会把后面的元素往前移。在数组剔除操作中，如果采用正循环，会打乱原有的数组顺序，建议考虑逆循环
list.remove()
　　删除列表中首次出现的指定元素，不存在该元素则抛出异常
filter()
　　filter(lambda x: x != val, nums)

26. 删除排序数组中的重复项

出现了一个重要的问题　不认真审题，题目强调是 排序数组 和 不使用额外的数组空间 所以做题之前还是要有效率的看题 ==
数组操作型可以考虑 双指针 !! set(list): 　　返回的是一个无序和不重复序列

80. 删除排序数组中的重复项 II

突然觉得想法还是很重要的，像我就只会用最原始最笨重的方法，看了题解之后竟然觉得有点神奇？？？（请叫我菜鸡）
　　比如这个题，其实可以拓展到保留k个重复元素，尽量写出来的代码变换需求之后不需要重新写~~ 

1
2
3
4
5
6
7
8
9
# range盘点
>>> range(1, 10, 2)
[ 1, 3, 5, 7, 9]
>>> range(0, 10, -1)
[0, -1, -2, -3, -4, -5, -6, -7, -8, -9]
>>> range(5, -1, -1)
[5, 4, 3, 2, 1, 0]
>>> range(5, 1, -1)
[5, 4, 3, 2]
1
2
3
4
5
6
7
8
# list索引问题
>>> nums = [0, 1, 2, 3, 4, 5, 6]
>>> nums[-1] 
5
>>> nums[-2:]
[ 5, 6]
>>> range(: -3)
[0, 1, 2, 3]

41. 缺失的第一个正数

骄傲脸（我觉得我做的方法时间真的很短！虽然题目确实有点简单，既然在题解里面看到有用桶排序做的，那就来了解并学习桶排序吧！

桶排序(Bucket sort)，也称箱排序 工作原理： 将数组分到有限数量的桶，每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）@wiki
通俗理解：一个萝卜一个坑，先把坑占好

今日份Tips-1:: 桶排序 

1
2
3
4
5
6
7
8
# 伪代码 nums->list
def bucket_sort():
    n: 桶数，可以是len(a)/len(max(nums))
    for i ← 1 to n
        do insert A[i] into list B[floor(nA[i])] # 将n个数分布到各个桶中,根据要求桶里面可能一个数可能多个
    for i ← 0 to n-1
        do sort list B[i] with insertion sort # 对各个桶中的数进行排序
    concatenate the lists B[0],B[1],...,B[n-1] together in order   #依次串联各桶中的元素

今日份Tips-2: 异或运算实现交换

  1. 多元赋值
  2. 看答案看到一个小trick
基于异或交换(a!=b) 基于加减交换(python中不需考虑溢出)
a = a^b
b = a^b
a = a^b		 a = a+b
b = a-b
a = a-b

299. 猜数字游戏

写在前面： 　　今天看比赛的baseline的时候，看到一条代码set(A) & set(B)求取AB特征的交集，今天在做这个题目的时候需要用到list(A) & list(B)，但人家list没这个运算啊，所以再用其他方法做题的同时，我暗戳戳的想一定会有什么语法糖！！果然看答案还真有… 今日份Tips-1: collections.Counter
　　collections遇到很多次了，官方文档中解释是 High-performace container datatype(高性能容量数据类型)，用的较多的是defaultdict OrderedDict deque, 还包括 namedtuple Counter

1
2
3
4
5
6
7
8
9
10
11
12
13
from collections import Counter
# 计数  
>>> listA = [1,2,3,4,2,4,5,6,8,3]
>>> c = Counter(listA)
>>> dict(c)     # 传统方法可能是遍历计数的方式
{1: 1, 2: 2, 3: 2, 4: 2, 5: 1, 6: 1, 8: 1}
>>> c['10']    # 不存在即为0
0
>>> listB = [2,3,4,5,6,7,8,9,0,1]
>>> Counter(listA) & Counter(listB)  # 对应可以求A|B
Counter({1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 8: 1})
>>> sum((Counter(listA) & Counter(listB)).values())   # 统计listA和listB中共有的元素个数
7

给我的感觉Counter就是n个桶，每个桶记录数据，类似桶排序？？更多操作指路 → collections.Counter

剩下的 namedtuple就不多说了，随用随学习

@ amilyxy 2019.8.27 感觉一个题目做好久啊~~ 坚持！！！！ 2019.11.5 经历了差不多两个月 终于轮回来了 坚持呀！！！