中级农民
- 积分
- 113
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2020-2-6
- 最后登录
- 1970-1-1
|
刷题第25天
480. Sliding Window Median 练习用两个heap实现中位数的维持。几个关键要点:1)python heapq不支持高效删除,可以用lazy delete. 2) 可以写函数来处理奇偶数算中位数以及从大小堆中互相移动的过程,3)初始化时将k个数全加入左堆再把其中一半从左堆移到右堆,3)记得想清楚个数为奇数时,中位数应该在左右两堆哪个之中。4)如果想挪k/2+1到右堆,可以使用k-k//2,5)python只支持最小堆所以可以用-实现最大堆,但是过程中处理符号千万要小心,不要搞反或者漏掉。6)为了记录数组的index,可以将值和index组成tuple进入heap。7)为了处理中位数duplicate的问题,lazy delete操作需要拿整个tuple进行比较,而不是简单的数值本身。
208. Implement Trie (Prefix Tree) 练习实现Trie的好题,用python实现的几个要点,1)想清楚TrieNode的成员变量,不需要char,但是IsWord至关重要。2)想清楚Trie的成员变量和方法,执行insert时不需要检查word是否已经存在,按照正常顺序走就行,但是记得最后一定要设IsWord变量,3)Search的时候最后一定要检查isWord变量.
305. Number of Islands II: 此题为UnionFind。关键是想明白UnionFind的类有哪些方法,成员变量有哪些,加速计算的方法,比如降低层数的方法等。另外要正确检查遍历节点是否越界,执行union操作时是对双方的root进行操作等等。另外,union find在python里可以用dict作为id的数据结构,熟练掌握weighted sizing的写法。在python里面巧妙使用tuple,和map可以解决1D,2D转换问题,tuple本身可以作为dict的key。
|
|