- 博客(15)
- 资源 (1)
- 收藏
- 关注
RSS订阅转载 Python有序数组bisect模块
bisect模块采用经典的二分算法查找元素。模块提供下面几个方法：bisect.bisect_left(a, x, lo=0, hi=len(a))定位x在序列a中的插入点，并保持原来的有序状态不变。参数lo和hi用于指定查找区间。如果x已经存在于a中，那么插入点在已存在元素的左边。函数的返回值是列表的整数下标。bisect.bisect_right(a, x, lo=0, hi=len(a))和上面的区别是插入点在右边。函数的返回值依然是一个列表下标整数。bisect.bisect(a
2020-09-03 11:38:14
219
原创 Union Find原理及模板
实质：多叉树功能：快速合并和查找时间复杂度：Union - O(1) Find - O(1)核心思想：连接根底层数据结构：父亲表示法——用一个Array/HashTable来记录每个节点的父亲是谁father[A] = B查询所在集合：用所在集合最顶层的老大哥节点来代表这个集合合并两个集合：找到两个集合中最顶层的两个老大哥节点A和Bfather[A] = B or father[B] = APython模板：f = {} #初始化父亲表for e...
2020-05-26 13:26:35
227
原创 Trie 字典树/前缀树 Python实现
class Trie: def __init__(self): """ Initialize your data structure here. """ self.root = {} self.end = -1 def insert(self, word: str) -> None: ...
2020-02-11 03:07:26
133
转载 求有向图强连通分量—Tarjan's Algorithm
在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。...
2020-01-21 01:42:41
519
转载 Find Maximum Sum Subarray - Kadane's Algorithm
问题： 给定一个数列，例如【−2, 1, −3, 4, −1, 2, 1, −5, 4】， 求一个连续的数列使得数列内的元素和最大， 示例中最大子数列应该是【4, −1, 2, 1】, 求和值为6。这个问题是的衍生变种问题，常出现与各笔试面试中， 如清晰解题： 网易笔试合唱团该问题最早于1977年提出，但是直到1984年才被Jay Kadane 发现了线性时间的最优解法，所以算法虽然长度很...
2020-01-20 03:28:25
120
转载 Bitwise Operators
Bitwise Operators : NOT, AND and XORIntuitionNow let's discussO(1)O(1)space solution by using threebitwise operators∼xthatmeansbitwiseNOT∼xthatmeansbitwiseNOTx&ythatmeansbitwiseAN...
2019-10-09 11:36:40
144
原创 Py3 知识点杂记
Dict的key可以是二叉树的节点，这一点很强势。Python多空格字符串的分割, str.split()Visited 用Set 比 List更快， visited = Set()Dict可以用sorted方法，返回一个排好序的key list位Bit运算技巧：判断一个数num是不是2的幂，num & (num-1) == 0...
2019-09-25 01:34:58
144
原创 Py3 字符串相关
#列表转字符串(字符串加数字)：li = [11, 22, 33, "asd", "xyz", "879", "hello"]s = ""for item in li: s = s + str(item)print(s)#列表转字符串(只有字符串)：li = ["ety", "xyz", "hello", "world"]s = "".join(li)print(s)...
2019-09-22 12:36:41
89
原创 Py3 排序相关
Sorted方法List = sorted(List) //单个元素的list如果有多个元素,按第一个排序sorted(List,key=lambda x:x[0])如需降序，增加参数“reverse = True”
2019-09-16 02:52:03
78
转载 Heap 在py3中的基本操作
from heapq import *导入heapq这个模块提供了堆队列算法的实现，也称为优先队列算法。堆是一个二叉树，它的每个父节点的值都只会小于或大于所有孩子节点（的值）。它使用了数组来实现：从零开始计数，对于所有的k，都有heap[k]<=heap[2*k+1]和heap[k]<=heap[2*k+2]。 为了便于比较，不存在的元素被认为是无限大。 ...
2019-09-14 05:41:47
223
转载 字典序 Lexicographical Order
求下一个字典序的方法1.求 i = max{j | p[j – 1] < p[j]} （找最后一个正序）；2.求 j = max{k| p[i – 1] < p[k]} （找最后大于 p[i – 1] 的）；3.交换 p[i – 1] 与 p[j]得到 p[1] … p[i-2] p[j] p[i] p[i+1] … p[j-1] p[i-1]p[j+1] … p[n]；4....
2019-09-11 14:30:23
1949
原创 Two Sum问题及一系列follow up的解析与代码
1.Two SumGiven an array of integers, returnindicesof the two numbers such that they add up to a specific target.You may assume that each input would haveexactlyone solution, and you may not us...
2019-09-09 09:31:50
239
转载 Python双端队列(Deque)用法in BFS
宽度优先搜索(BFS)需要用到队列(Queue)，在面试时推荐使用Py3的Deque。问题:二叉树的层次遍历代码：from collections import deque #导入模块class Solution: """ @param root: A Tree @return: Level order a list of lists of in...
2019-07-08 23:04:18
490
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人