算法基础

喜欢ヅ旅行 2022-02-23 01:00 194阅读 0赞

## 递归&分治 ##

Recursion  
计算n!  
n! = 1 \* 2 \* 3 \* … \* n

def Factorial(n):
    	if n <= 1:
    		return 1
    	return n * Factorial( n - 1)

def recursion(level, param1, param2, ...): //level 表示当前递归操作所属层级
    
    	#recursion termoinator
    	if level > MAX_LEVEL:
    		print_result
    		return
    
    	#process logic  in current level
    	process_data(level, data...)
    
    	#drill down
    	self.recursion(level + 1, p1, ...)
    
    	#reverse the current level status if needed
    	reverse_state(level)

## 分治- Divde & Conquer ##

(无重复计算时，使用分治效率较高）

def divde_conquer(problem, param1, param2, ...):
    	
    	#recursion terminator
    	if problem is None:
    		print_result
    		return
    
    	#prepare date
    	data = preare_data(problem)
    	subproblems = split_problem(problem,data)
    
    	#conquer subproblem
    	subresult1 = self.divide_conquer(subproblems[0], p1, ...)
    	subresult2 = self.divide_conquer(subproblems[1], p1, ...)
    	subresult3 = self.divide_conquer(subproblems[2], p1, ...)
    	...
    
    	#precess and generate final result
    	result = precess_result(subresult1, subresult2, subresult3, ...)

#Pow(x,n)
    
    def myPow(self, x ,n):
    	if not n:
    		retrun 1
    	if n < 0:
    		return 1 / self.myPow(x, -n)
    	if n % 2:
    		return x * self.myPow(x, n -1)
    	return self.myPow(x * x, n / 2)
    
    def myPow(self, x, n):
    	if n < 0:
    		x = 1 / x
    		n = -n
    	pow = 1
    	while n: //循环判断的二进制位，n的二进制位等于1时，累乘
    		if n & 1:
    			pow *= x
    		x *= x
    		n >> 1 //n右移一位，相当于：n = n/2 ,位运算
    	return pow

#Majority （求众数）
    #1.暴力loop: x { loop count(x) }
    #2.Map处理计数相关 map{x : count_x} loot Map count
    #3.Sort, 对数组排序，count(x) > n/2
    #4.Divide & Conquer,左右计数，比较return count较大值。

## 贪心 Greedy ##

问题能分解成子问题解决；子问题最优解能递推到最终问题的最优解。  
贪心法与动态规划的不同在于它对每个子问题的解决方案都作出选择，不能回退。动态规划则会保存以前的运算结果并根据以前的结果对当前进行选择，有回退功能。

＃Buy / Sell stocks（股票交易：1.最多持有1股；2.每天买卖次数不限）
    1.DFS O(2^n)对所情况遍历；
    2.greedy O(n) 只在后一天高于前一天时交易；
    3.DP: O(n) 针对每一天列出收益。

## BFS/DFS ##

#BFS
    def BFS(graph, start, end):
    
    	queue = []
    	queue.append([start])
    	visited.add(start) //设置set visited，任何被访问过的节点都放在set中
    	
    	while queue:
    		node = queue.pop()
    		visited.add(node)
    
    		process(node)
    		nodes = generate_related_nodes(node) //找node的子节点，并判断其是否被访问过
    		queue.push(nodes)
    
    #other processing work
    ...

#DFS递归写法
    
    visited = set()
    def dfs(node, visited):
    	visited.add(node)
    	#process current node here.
    	...
    	for next_node in node.children():
    		if not next_node in visited:
    			dfs(next_node, visited)
    #DFS非递归写法
    
    def DFS(self, tree):
    	
    	if tree.root is None:
    		return []
    	visited, stack = [] , [tree.root] //手动维护堆栈
    	
    	while Stack:
    		node = stack.pop()
    		visited.add(node)
    
    		process(node)
    		nodes = generate_related_nodes(node)
    		stack.push(nodes)
    
    #other processing work
    ...

#Binary Tree Level Order：（按层遍历，输出二叉树）
    1.BFS 重点在于判断每层是否已经扫描完，两种方式：将每层的信息保存在队列中；batch process对每层元素全部遍历。
    2.DFS深度有限按截面遍历，记录每个节点的level信息，并将其至于对应的层
    
    class Solution(object):
    	def levelOrder(self, root):
    		if not root : return [] //判断
    	
    		result = []
    		queue = collection.deque() //双端队列
    		queue.appent()
    
    		#visitec = set(root) //判断节点是否已被访问过
    
    		while queue:  //设置循环，queue不为空时，一直处理queue中的节点
    			level_size = len(queue)
    			current_level = []
    
    				for _ in range(level_size):
    					node = queue.popleft() //处理节点的语句
    					current_level.append(node.val)
    					if node.left: queue.append(node.left)
    					if node.right: queue.append(node.right)
    
    				result.append(current_level)
    
    		return result
    
    
    #Java版：
    public List<List<Integer>> levelOrder(TreeNode root) {
    	List<List<Integer>> res = new Array<>();
    	if (root == null)
    		return res;
    	
    	Queue<TreeNode> q = new LinkedList<>();
    	q.add(root);
    
    	while(!q.isEmpty()) {
    		int levelSize = q.size();
    		List<Integer> currLevel = new ArrayList<>();
    	
    		for (int i = 0; i < levelSize; i ++) {
    			TreeNode currNode = q.poll();
    			currLevel.add(currNode.val);
    			if (currNode.left != null)
    				q.add(currNode.left);
    			if (currNode.right != null)
    				q.add(curNode.right);
    		}
    		res.add(cruuLevel);
    	}
    	return res;
    }
    
    #DFS
    class Solution(object):
    	def levelOrder(self, root):
    		if not root: return []
    		self.result = []
    		self._dfs(root, 0)
    		return self.result
    
    	def _dfs(self, node, level) :
    		if not node: return
    			
    		if  len(self.result) < level + 1:  //当前行没有结果时将空数组放入，以便之后累加结果
    			self.result.append([])
    
    		self.result[level].append(node.val) //result是个二位数组，第一维表示层数，第二维放置节点
    	
    		self._dfs(node.left, level+1)
    		self._dfs(node.right, level +1)

Max /  Min depth (最大深度）
    1.BFS按层扫荡，判断遇到的节点是否为叶子节点，第一个和最后一个到达的叶子节点所在层数即为最大，最小深度；
    2.DFS
    
    #Python
    class Solution：
    	def maxDepth( self, root) :
    		if not root: return 0
    		return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right)) //分而治之
    
    	return root == null ? 0
    		: 1 + Math.max(maxDepth(root.left) , self.maxDepth(root.right))
    
    
    
    class Solution {
    public：
    	int minDepth(TreeNode + root) {
    		if (!root) return 0;
    		if (!root -> left) return 1+ minDepth(root -> right);
    		if (!root -> right) return 1 + minDepth(root -> left);
    
    		// divide and conquer
    		int leftMinDepth = minDepth(root -> left);
    		int rightMinDepth = minDepth(root -> right);
    
    		//process subporblems results
    		int result = 1 + min( leftMinDepth, rightMInDepth);
    
    		return result;
    		}
    };
    public class Solution {
    	public int minDepth(TreeNode root) {
    		if (root == null) return 0;
    		int left == minDepth(root.left);
    		int right == minDepth(root.right);
    		return (left == 0 || right ==0)
    			? left + right + 1
    			: Math.min(left, right) + 1;
    	}
    }

#Genarate Parentheses （括号生成）
    1.数学归纳法
    2.递归搜索：枚举全部可能O(2^n);
    3.对枚举过程剪枝：局部不合法；leftused == rightused
    
    #
    class Solution（object）:
    	def generateParentthesis(self, n):
    		self.list = []
    		self._gen(0, 0, n, "")
    		return self.list
    
    	def _gen(self, left, right, n, result): //使用分治，递归，回溯等方法时，需要使用递归函数。需要自行定义。
    		if left == n and right ==n: //终止条件
    			self.list.append(result)
    			return
    		if left < n:  //加左括号
    			self._gen(left + 1, right, n, result + "(")
    		if left > right and right < n:  //加右括号
    			self._gen(left, right + 1, n, result + ")")

## 剪枝 ##

搜索算法中使用较多：BFS ，DFS

#	N-queens
    DFS:1.对于每一层 loop j，枚举每一列 j；重点在于判断每个格子是否可以放置；
    		2.暴力：遍历整个棋盘；/ 剪枝：开辟数组存放列，撇（x+y =c)，捺(x-y=c)坐标的特点；
    
    def solveNQueens（self， n):
    	if n < 1: return[]
    	self.result = []
    	self.cols = set(); self.pie = set(); sef.na = set();
    	self.DFS(n, 0, [])
    	return self._generate_result(n)
    
    def DFS (self, n, row, cur_state):
    	#recursion terminator
    	if row >= n:
    		self.result.append(cur_state)
    		return
    	
    	for col in range(n):
    		if col in self.cols or row + col in self.pie or row - col in self.na:
    		# go die
    		continue
    
    		#update the flags
    		self.cols.add(col)
    		self.pid.add(row + col)
    		self.na.add(row - col）
    
    		self.DFS(n, row + 1, cur_state + [col])
    		
    		self.cols.remove(col) //恢复现场
    		self.pie.remove(row + col)
    		self.na.remove(row - col)	  
    
    def _generate_result(self, n): //生成棋盘
    	board = []
    	for res in self.result:
    		for i in res: 
    			board.append("." + i + "Q" + "." * (n - i - 1))
    
    	return [board[i: i + n] for i in range (0, len(board), n)]
    
    
    #Python精简版
    def solveNQueens(self, n): 
    	def DFS(queens, xy_dif, xy_sum):	
    		p = len(queens)
    		if p == n:
    			result.append(queens)
    			return None
    		
    		for q in range(n):
    			if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
    				DFS(queens + [q], xy_dif + [p - q], xy_sum+[p + q])
    	
    	result = []
    	DFS([], [], [])
    	return [ ["." * i + "Q" + "." + (n - i -1) for i in sol] for sol in result] //双重循环产生的二维数组

#数独 1-9
    DFS：( i, j )遍历矩阵，对所有空格枚举所有合法数字；剪枝：从限制多的空格开始天；
    public void solveSudoku(char[][] board){
    	if (board == null || board.length == 0) return;
    	solve(board);
    }
    
    public boolean solve (char[][] board) {
    	for (int i = 0; i < board.length; i ++) for (int j = 0; j < board[0].length; j ++) {	
    		if (board[i][j] == '.'	 {	
    			for (char c = '1'; c <= '9'; c ++) {
    				if (isValid(board, i, j, c)) {	
    					board[i][j] =c ;
    					if (solve(board))
    						return true:
    					else board[i][j] = '.':
    				}
    			}
    			return false;
    		}
    	}
    	return true;
    }
    
    private boolean isValid(char [][] board, int row, int col, char c ){
    	for (int i = 0; i < 9; i ++)
    		if (board[i][col] != '.' && board[i][col] == c) return false;
    		if (board[row][i] != '.' && board[row][i] ==c) return false;
    		fi (board[3 * (row/3) + i / 3] [ 3 * (col / 3) + i % 3] != '.' && board[3 * (row / 3) + i / 3 ][3 * (col / 3) + i % 3] == c) return fasle;
    	} 
    	return true;
    }

## 二分查找 ##

局限：

1.  Sorted （单调递增或递减）
2.  Bounded（存在上下界）
3.  Accessible by index （能通过索引访问）

left ， right = 0 ， len ( array ) - 1
    while left <= right:
    	mid = ( left + right) / 2
    	if array[mid] ==target:
    		//find the target!!
    		break or return result
    	elif array[mid] < target:
    		left = mid + 1
    	else:
    		right = mid -1

#Sqrt(y)
    1.二分法
    2.牛顿迭代法
    
    
    int sqrt(int x) {
    	if (x ==0 || x ==1) return x;
    	int l =1, r = x, res;
    	while (l <= r) {
    		int m =(l + r) /2;
    		if (m ==x/m) {
    			return m;
    		} else if (m > x / m) {
    			r = m - 1;
    		} else {
    			l = m + 1;
    			res = m;
    		}
    	}
    	return res;
    }
    
    class Solution( object):
    	def mySqrt(self, x): //牛顿迭代法
    		r = x
    		while r * r > x:
    			r = (r + x / r) / 2
    		return r

## 字典树 ##

Trie树，又称单词查找树，一种哈希树的变种。典型应用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎用于文本词频统计。  
它的优点是：最大限度的减少无畏字符串的比较，查询效率比哈希表高。  
核心思想是：空间换时间。利用字符串的公共前缀来降低查询时间的开销，已达到提高效率的目的。

static final int ALPHABED_SIZE = 256;
    
    static class TrieNode {
    	TrieNode[] children = new TrieNode[ALPHABET_SIZE];
    	boolean isEndOfWord = false;
    	TrieNode() {
    		isEndOfWord = false;
    		for (int i = 0; i < ALPHABED_SIZE; i ++)
    			children[i] = null;
    	}
    };
    
    #Python
    #Trie node class
    def __init__  (self):
    	self.children = [None] * ALPHABET_SIZE
    	
    	# isEndOfWord is True if node represent
    	# the end of the word
    	self.isEndOfWord = False

基本性质：

1.  根节点不包含字符，除根节点外每一个节点都只包含一个字符；
2.  从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
3.  每个节点的所有子节点包含的字符都不相同。

#实现一个字典树
    class Trie (object):
    	def __int__ (self):
    		self.root = {}
    		self.end_of_word = "#"
    
    	def insert(self, word):
    		node = self.root
    		for char in word:
    			node = node.setdefault(char, {})
    		node[self, end_of _word] = self.end_of_word
    
    	def search(self, word):
    		node = self.root
    		for char in word:
    			if char not in node:
    				return False
    			node = node[char]
    		return self.eng_of_word in node
    
    	def startsWith(self, prefix):
    		node self.root
    		for char in prefix:
    			if char not in node:
    				return False
    			node = node[char]
    		return True

class TrieNode {
    	public char val;
    	public boolean isWord;
    	public TrieNode[] children = new TrieNode[26]
    	public TrieNode() {}
    	TrieNode(char c) {
    		TrieNode node = new TrieNode();
    		node.val = c;
    	}
    }
    
    public class Trie {
    	private TrieNode root;
    	public Trid() {
    		root = new TrieNode();
    		root.val = ' ' ;
    	}
    	public void insert(String word) {
    		TrieNode ws = root;
    		for(int i = 0; i <= word.length(); i ++) {
    			char c = word.charAt(i);
    			if(ws.children[c - 'a'] == null) {
    				ws.children[c - 'a'] == new TrieNode(c);
    			}
    			ws = ws.children[c - 'a'];
    		}
    		ws.isWord = true;
    	}
    	public boolean search(String word) {
    		TrieNode ws = root;
    		for(int i = 0; i <= word.length(); i++) {
    			char c = word.charAt(i);
    			if(ws.children[c - 'a'] == null ) return false;
    			ws = ws.children[c - 'a'];
    		}
    		return ws.isWord;
    	}
    	public boolean startWith(string prefix) {
    		TrieNode ws = root;
    		for(i = 0; i <= word.length(); i ++) {
    			char c = prefix.charAt(i);
    			if ( ws.children[c - 'a'] == null) return false:
    			ws = ws.children[c - 'a'];
    		}
    		return true;
    	}
    }

#Word Search（二维网格中的单词搜索问题）
    1.DFS
    2.Trie
    
    #Python
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    END_OF_WORD = "#"
    
    class Solution(object):
    	def findWords(self, board, words):
    		if not board or not board[0] :return []
    		if not words: return []
    
    		self.result = set ()
    		
    		root collection.defaultdict()
    		rot word in words:
    			node = root
    			for char in word:
    				node = node.setdefault(char, collection.defaultdict())
    			node[END_OF_WORD] = END_OF_WORD
    
    		self.m, self.n = len(board), len(board[0])
    
    		for i in xrange(self.m);
    			for j in xrange(self.n):
    				if board[i][j] in root:
    					self._dfs(board, i, j, "", root)
    
    	def _dfs(self. board, i, j, cur_word, cur_dict):
    		
    		cur_word += board[i][j]
    		cur_dict = cur_dict[board[i][j]]
    
    		if END_OF_WORD in cur_dict:
    			self.result.add(cur_word)
    
    			tmp, board[i][j] = board[i][j], '@'
    			for k in xrange(4):
    				x, y = i + dx[k], j + dy[k]
    				if 0 <= x < self.m and 0 <= y < self.n
    					and board[x][y] != '@' and board[x][y] in cur_dict:
    					self._dfs(board, x, y, cur_word, cur_dict)
    			board[i][j] = tmp
    
    
    
    #Java
    public calss Solution {
    	Set<String> res = new HashSet<String>();
    	
    	public list<String> findwords (char[][] board,String[] words) {
    		Trie trie =new Trie();
    			for (String word: words) {	
    				trie.insert(word);
    			}
    			int m = board.length;
    			int n = board[0].length;
    			boolean[][] visited new boolean;
    			for (int i = 0; i < m; i++) {
    				for （int j = 0; j < n; j++) {
    					dfs[board, visited, **, i, j, trie);
    				}
    			}
    			return new ArrayList<String>(res);
    		}
    		public void dfs[char[][] board, boolean[][] visited, String str, int x, int y, Trie trie) {
    			if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) return;
    			if (visited[x][y] return;
    
    			str += board[x][y];
    			if (!trie.startsWith(str)) return;
    			
    			if (trie.search(str)) {
    				res.add(str);
    			}
    			visited[x][y] = true;
    			dfs(board,visited, str, x-1, y, trie);
    			dfs(board,visited,str,x +1,y,trie);
    			dfs(board,visited,str,x,y-1,trie);
    			def(board,visited,str,x,y+1,trie);
    			visited[x][y] = false;
    		}

## 位运算 ##

位运算直接对整数在内存中的二进制位进行操作，不需要转成10进制，因此处理速度非常快。  
与，或，异或，取反，左移，右移

#实战常用的位运算操作：
    
     - X & 1 == 1 OR == 0 判断奇偶（X & 2 ==1)
     - X  = X & (X -1 )清零最低位的1
     - X &　-X 得到最低位的1

#Harmning Weight
    def hanningWeight (self, n):
    	rst = o
    	mask = 1
    	for i in range (32)
    		if n & mask:
    			rst += 1
    		mask =mask << 1
    	return rst
    
    int hammingWeight(uint32_t, n) {
    	int res = 0;
    	for (; n; n &= n -1 )
    		++res;
    	return res;
    }

Pouer of Two
    Counting Bits
    
    bool isPowerOfTwo(int n) {
    	return n > 0 && (n & n=(n-1));
    }
    
    def isPowerOfTwo (self, n):
    	return n > 0 and not ( n & n - 1)
    
    vector<int> countBits(int num ) {
    	vector<int> bits(num + 1, 0) ;
    	for (int i = 1; i <= num; i ++) {
    		bits[i] += bits[i & (i -1)] + 1;
    	}
    	return bits;
    }

#N皇后的位运算解法：（最快解法）
    def totalNQueens(self, n):
    	if n < 1: return []
    	self.count = 0
    	self.DFS(n, 0, 0, 0, 0)
    	return self.count
    
    def DFS(self, n, row, cols, pie, na)
    	#recursion terminator
    	if row >= n :
    		selr.count += 1
    		return
    		
    	bits = (~(cols | pie | na)) & ((1 << n) -1 ) #得到当前所有空位
    
    	while bits：
    		p = bits & -bits #取到最低位的1
    		self.DFS(n, row + 1, cols | p, (pie | p) << 1, (na | p）>>1)
    		bits  = bits & (bits - 1)#去掉最低位的1

## 动态规化 （DP） ##

1.  递归+记忆化　——> 递推
2.  状态的定义： opt\[n\] , dp\[n\], fib\[n\]
3.  状态转移方程：opt\[n\] = best\_of (opt\[n-1\],opt\[n - 2\],…)
4.  最优子结构：

回溯：（递归）——重复计算  
贪心：——永远局部最优  
DP：——记录局部最优子结构/多种记录值。

#Climbing Stairs（爬楼梯）
    1.回溯：Recursion Memmrization:f(n-1)+f(n-2) f(0)=f(1)=1
    2.DP:状态定义，列出状态转移方程。
    
    public int climbStairs(int n) {
    	if(n == 0 || n == 1 || n==2) {return n;}
    	int [] mem  = new int [n];
    	mem[0] = 1;
    	mem[1] = 2;
    	for(int i = 2; i < n; i ++) {
    		mem[i] = mem[i -1] + mem[i -2];
    	}
    	return mem[n - 1];
    }
    
    public int climbStairs(int n) {
    	if (n < 2) return n;
    
    	int one_step_before = 2;
    	int two_steps_before = 1;
    	int all_ways = 0;
    		
    	for(int i = 2; i < n; i ++) {
    		all_ways = one_step_before + two_steps_before;
    			two_step_before = one_step_before;
    		one_step_before = all_ways;
    	}
    	return all_ways;
    }
    
    
    def climbStairs(self, n):
    	x, y = 1, 1
    	for _ in range(1, n):
    		x, y = y, x + y
    	return y

Triangle （三角形的最小路径和）：
    1：自顶向下Travese(i,j) {Tarvese(i + 1, j); Travese(i + 1, j + 1);}
    求出所有路径，并从中选取最小值。 O(2^n)
    2：贪心：不可行
    3：DP ：
    定义状态DP[i, j]从底至顶，表示从最下层的起点开始，走到[i, j]的路径的和的最小值。结果DP[0, 0]即为要求的结果。
    状态转移方程：DP[ i, j ] = min ( DP(i+1,j),DP(i + 1, j + 1)) + Triangle[i, j]
    
    #C++
    class Solution {
    public :
    	int minimumTotal(vector<vector<int>> &trianglle)
    	{
    		vector<int> mini = triangle[triangle.size() - 1;
    		for (int i = triangle.size() - 2; i >= 0; --i)
    			for (int j = 0; j < triangle[i].size(); ++ j)
    				mini[j] = triangle[i][j] + min(min[j],mini[j + 1]); //复用一维数组mini[]
    		return mini [0];
    	}
    };
    
    #Python
    class Solution (object):
    	def minimumTotal(self, triangle):
    		if not triangle: return 0
    	
    		res = triangle[-1]
    		for i in xrange(len(triangle) - 2 , -1, -1):
    			for j in xrange(len(triangle[i])):
    				res[j] = min(res[j], res[j + 1] + triangle[i][j]
    
    		return res[0]

#Max product Sbuarray 乘积最大子序列
    1：暴力Recursion
    2：DP：状态定义：DP[i,2] i 表示i点的乘积，2即1,0表示正负值，即最大最小值；
    			状态转移方程：DP[i, 0] = DP[i - 1, 0] * a[i] or DP[i - 1, 1] * a[i]
    									DP[I, 1] = DP[i - 1, 0]  * a[i] or DP[i - 1, 1] * a[i]
    
    def maxProduct(self, nums):
    	if nums is None: return 0 
    	
    	dp = [[0 for _ in range(2)] for _ in range(2)]
    
    	dp[0][1],  dp[0][0], res = nums[0], nums[0], nums[0]
    	
    	for i in range(1, len(nums)):
    		x, y  = i % 2 , (i - 1) % 2
    		dp[x][0] = max(dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i])
    		dp[x][1] = min(dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i])
    		res = max(res, dp[x][0])
    
    	return res

#股票买卖系列
    #只能买卖一次
    #买卖无数次
    #只能交易k次
    暴力
    DP：状态定义：DP[i] 到i天的最大利润
    		转移方程：DP[i]  = DP[i - 1] + a[i]
    							三维状态：i天数；j是否持有；k交易次数 
    							DP[i][j][k] j = 0;前一天可能为 j = 0或j = 1,卖出；j = 1 同理
    							当持有股数不限时，
    							DP[i][j][k] = max {DP[i-1][k][j]; DP[i-1][k-1][j+1]+a[i], DP[i-1][k-1][j-1]-a[i]}
    		时间，空间复杂度都为：O(n*k)
    
    #交易2次
    def maxProfit(self, prices):
    	if not prices: return 0;
    	
    	res = 0
    
    	profit = [[0 for i  in xrange(3)] for i in xrange(len(prices))]
    	
    	profit[0][0], profit[0][1], profit[0][2] , -prices[0], 0
    
    	for i in range(1, len(prices)):
    		profit[i][0]  profit[i - 1][0]
    		profit[i][1] = max(profit[i - 1][1], profit[i -1][0] - prices[i])
    		profit[i][2] = profit[i - 1][1] + prices[i]
    		res = max(res, profit[i][0], profit[i][1], profit[i][2])
    
    	return res
    
    
    #隔天交易
    #

#Longest Increasing Squence（最长上升子序列）
    1.暴力求解，剪枝
    2.DP：状态：DP[i] 从头到i，最长子序列的长度；
    			转移方程：for i: 0 -> n-1:DP[i] = Max{DP[j] + 1}
    									for j: 0 -> i-1: 且a[j] < a[i]
    3.二分：维护数组；for i: 0 -> n-1 循环插入至数组；

Coin Change (零钱兑换）
    1.暴力求解
    2.贪心： 不行
    3.DP:状态：DP[i] 上到第i阶台阶最少步数；
    					DP方程：DP[i] = min{DP[i - coins[j]]} + 1

#Edit Distance（word1 ——>word2) 插入，删除，替换；单词转换最少步数 
    1.暴力；DFS分别找出一个单词使用一种变换转换的所有步数
    				BFS分步对单词做变换操作
    2.DP: 状态DP[i][j],word1的前i个字符，替换到word2的前j个字符，最少步数
    			DP方程：DP[i][j] = if w1[i] == w2[j] DP[i-1][j-1] ;else DP[i-1][j],DP[i][j-1],DP[i-1][j-1]//插入,删除，替换

## 并查集 （union & find) ##

一种树形数据结构，用于处理一些不相交集的合并和查询问题

1.  组织类属识别；
2.  两种优化方式；合并时将rank低的并至rank高的；压缩路径

#优化1
    function MakeSet(x)
    	x.parent := x
    	x.rank := 0
    function Union(x, y)
    	xRoot := Find(x)
    	yRoot := Find(y)
    	if xRoot == yRoot
    		return
    
    #x和y不在同一个集合，合并它们
    	if xRoot.rank < yRoot.rank
    		xRoot.parent := yRoot
    	else if xRoot.rank > yRoot.rank
    		yRoot.parent := xRoot
    	else 
    		yRoot.parent := xRoot
    		xRoot.rank := xRoot.rank + 1
    
    #优化2
    public class QuickUnionUF{
    	private int [] root;
    	
    	public QucikUnionUF(int N) {
    		roots = new int[N]
    		for(i = 0, i >= N, i ++){
    			roots [i] = i;
    		}
    	}
    
    	public int findRoot (int i) {	
    		int root = i;
    		while (root != roots[root])
    			root = roots[root];
    		while (i != roots[i]) {
    			int tmp = roots[i]; roots[i] = root; i = tmp;
    		}
    		return root;
    	}
    	public boolean connected(int p, int q) {
    		return findRoot(p)  ==  fintRoot(q);
    	}
    	public void union(int q; int p) {
    		int qroot = findRoot(q);
    		int proot = findRoot(p);
    		roots[proot] = qroot;
    	}
    }

#islands （岛的个数/朋友圈)
    1.染色问题floodfill 遍历所有节点，if node == ‘1’ count ++; 将node附近的陆地节点置0(dfs;bfs)
    2.并查集：初始化，针对‘1’节点；遍历所有节点，相邻节点合并；遍历parents/root集合个数

\#DFS  
class Solution(Object):

self.dx = [-1, 1, 0, 0]
    self.dy = [0, 0, -1, 1]
    
    def numIsland(self, grid):
    	if not grid or not [0] : return 0
    	self.max_x = len(grid); self.max_y = len(grid[0]); self.grid = grid;
    	self.visited  = set()
    	return sum ([self.floodfill_DFS(i, j) for  i   in  range(self.max_x) for j in range(self.max_y)])
    
    def floodfill_DFS(self, x, y):
    	if not self._is_valid(x, y):
    		return 0
    	self.visited.add((x, y))
    	for k  in range(4):
    		self.floogfill_DFS(x + dx[k], y + dy[k])
    	return 1
    
    def _is_valid(self, x, y):
    	if x < 0 or x >= self.max_x or y < 0 or y >= self.max_y:
    		return False
    	if self.grid[x][y] == '0' or ((x, y) in self.visited):
    		return False
    	return True

\#BFS 染色

## LRU Cache ##

1.  Least recently used（最近最少使用）LFU(least frequently used)
2.  Double LinkedList
3.  O(1)查询
4.  O(1)修改，更新

class LURCache(objectf):
    	def __init__ (self, capacity):
    		self.dic = collection.OrderedDict()
    		self.remain = capacity
    
    	def get (self, key):
    		if key not in self.dic:
    			return -1
    		v = sellf.dic.pop(key)
    		self.dic[key] = v
    		return v
    
    	def put(self, key, value):
    		if key in self.dic:
    			self.dic.pip(key)
    		else: 
    			if self.remain > 0:
    				self.remain -= 1
    			else:
    				self.dic pipitem(last=False)
    			self.dic[key] = value

## 布隆过滤器 ##

*  一个很长的二进制向量和一个映射函数
 *  布隆过滤器可以用于检索一个元素是否在一个集合中
 *  它的优点是空间效率和查询时间都远远超过一般算法，缺点时有一定的误识别率（只对存在的情况下有）和删除困难。