数据结构基础

刺骨的言语ヽ痛彻心扉 2022-02-22 21:00 230阅读 0赞

前置：算法复杂度

O(1)  			int n =	1000;
    					System.out.println(n);
    
    O(N)			for (int i = 1; i <= n ; i++){
    						System.out.println( i );	
    					}
    					
    O(n^2)			for (int i = 1; i <= n; i++) {
    						for (int j = 1; j <=n ;j++) {
    							System.out.println(i + j);
    						}
    					}
    					
    O(log(n))		for (int i = 1; i < n; i = i *2) {
    						System.out.println( i );
    					}
    					
    O(k^n)			for (int i = 1; i <= Math.pow(2 , n); i++) {
    						System.out.println( i );
    					}
    
    O(n!) 			for (int i = i; i <= factoria(n); i++) {
    						System.out.println( i );
    					}

#recursion
    #Fibonacci array: 1,1,2,3,5,8,13,21,34;
    #F(n) = F(n-1) + F(n-2)
    
    def fib(n):
    	if n ==0 or n ==1:
    		return n
    	return fib(n-1) + fib(n-2)
    
    #O(n^2)

Master Theorem:数学中，涵盖各种情况的定理有时被称为主定理。提供了用渐进符号表示，由分治法得到的递推关系式的方法。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZJTllJRQ_size_16_color_FFFFFF_t_70]

1.  Array
2.  Stack/Queue
3.  PriorityQueue(heap)
4.  LinkedList(single/double)
5.  Tree/Binary Tree
6.  Binary Search Tree
7.  Hash Table
8.  Disjoint Set
9.  Trie
10. BloomFilter
11. LRU Cache

## Array 、 LinkedList ##

#Reverse Linked List （逆序）
    def reverseList(self, head):
    	cur, prev = head, None #设置当前节点为cur = head，前驱节点prev = None
    	while cur:  #循环至链表结束
    		cur.next,  prev, cur = prev, cur, cur.next #三句赋值
    	return prev

#Swap Nodes in Pairs （反转相邻的两个节点）
    def swapPairs(self, head):
    	pre, pre.next = sefl, head
    	while pre.next and pre.next.next:
    		a = pre.next
    		b = a.next
    		pre.next, b.next, a.next = b, a, b.next
    		pre = a 
    	return self.next

#Linked List Cycle （判断是否存在环）
    def hashCycle(self, head):
    	fast = slow = head
    	while slow and fast and fast.next:
    		slow = slow.next #设置快慢指针，循环，两指针相遇，则有环，否则为无环
    		fast = fast.next.next
    		if slow is fast:
    			return True
    	return False

#Linked List Cycle ii

#Reverse nodes in k group

## Stack 、Queue ##

常用数据结构操作：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZJTllJRQ_size_16_color_FFFFFF_t_70 1]  
BIG OCHEATSHEET  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZJTllJRQ_size_16_color_FFFFFF_t_70 2]

#Valid Parentheses （判断括号字符串是否有效）
    def isValid(self, s):
    	stack = []
    	paren_map = { ')' : '(' , ']' : '[' , '}' : '{' } #使用map存储左右括号的对应关系，右括号前置
    	for c in s:
    		if c not in paren_map: #判断c如果不是右括号，则为待定，压入栈中
    			stack.append(c) 
    		elif not stack or paren_map[c] != stack.pop(): #如果时右括号，判断栈中是否有元素，并判断c与栈中元素是否匹配
    			return False
    	return not stack #最后判断栈是否为空，为空即全部匹配，合法
    
    
    //另一种解法：(时间复杂度为2^n）
    public boolean isValid(String s) {
    	int lenth;
    	do {
    		length = s.length();
    		s = s.replace("()","").replace("{}","").replace("[]","");
    	} while (length != s.length());
    	return s.length() == 0;
    }

#栈实现队列；队列实现栈

## Priority Queue ##

实现机制：Heap(Binary, Binomial, Fibonacci) / Binary Search Tree

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZJTllJRQ_size_16_color_FFFFFF_t_70 3]

#Kth Largest Element in a Stream (流数据中前k大元素）
    class KthLargest {
    	final PriorityQueue<Integer> q;
    	final int k;
    	public KthLargest(int k , int [] a) {
    		this.k = k;
    		q = new PriorityQueue<>(k); //创建优先队列（Java默认PriorityQueue是最小堆）
    		for (int n : a)
    			add(n);
    	}
    	public int add(int n) {
    		if (q.size() < k)  //
    			q.offer(n);
    		else if (q.peek() < n) { //新元素与堆顶元素比较，如果大于堆顶元素，
    			q.poll(); //堆顶去掉
    			q.offer(n); //设置新堆顶
    		}
    		return q.peek();  //返回堆顶元素
    	}
    }

#Sliding Window Maximum （返回滑动窗口的最大值）
    
    def maxSlidingWindow1(self, nums, k ):
    	if not nums: return [] //对于传入的参数进行判断。
    	window, res = [] , [] //初始化window下标；res结果
    	for i, x in enumerate(nums) : 
    		if i >=k and window[0] <= i - k: //window移动，为保持window大小固定，移除左端元素
    			window.pop(0)
    		while window and nums[window[-1]] <= x: //新参数x若大于window中已存在的参数，则清空window
    			window.pop()
    		window.append(i)
    		if i >= k -1:
    			res.append(nums[window[0]]) //返回结果
    	return res

## Map 、Set ##

*  HashTable & Hash Function & Collisions
 *  Map vs Set
 *  HashMap , HashSet , TreeMap, TreeSet

#HashMap best practices HashSet类似
    Python 
    dict
    hashmap = {key: value}
    
    Java
    HashMap
    TreeMap
    
    C++
    std::unordered_map
    std::map
    
    C#
    Dictionary<TKey, TValue>
    Hashtable
    StringDictionary
    SortedDictionary

＃Valid Anagram （有效的字母异位词）
    def isAnagram3(self, s, t) : 
    	return sorted(s) == sorted(t) //排序，Ｏ(nlogn)
    
    def isAnagram2(self, s, t) : 
    	dic1, dic2 = {} {} //使用map存放异位词，统计各字母出现的次数是否相同
    	for item in s:
    		dict1[item] = dic1.get(item, 0 ) + 1
    	for item in t:
    		dict2[item] = dic2.get(item, 0 ) +1
    	return dic1 ==dic2
    
    def isAnagram1(self, s, t) :
    	dic1, dic2 = [0]*26, [0]*26 //使用数组自行实现朴素的哈希表（数组操作快于字典）
    	for item in s: 
    		dic1 [ord(item) - ord('a')] += 1
    	for item in t:
    		dic2 [ ord(item) - ord('a)] += 1
    	return dic1 ==dic2

Two Sum

#Three Sum
    def threeSum(self, nums):
    	if len(nums) < 3:
    		return [] 
    	nums.sort()
    	res = set() //使用set存储数据
    	for i, v in enumerate(nums[:-2]):
    		if i >= 1 and  v == nums[i - 1]:
    			continue
    		d = {}
    		for x in nums[i + 1: ] : 
    			if x not in d: 
    				d[-v-x] - 1 
    			else:
    				res.add((v, -v-x, x))
    		return map(list, res)
    
    def threeSum（self， nums):
    	res = []
    	nums.sort() //对数组排序，利用有序性，两边夹逼
    	for i in xrange(len(nums) - 2) :
    		if i > 0 and nums[i] == nums[i -1]:
    			continue
    		l, r = i + 1, len(nums)-1
    		while l < r:
    			s = nums[i] + nums[l] + nums[r]
    			if s < 0: l += 1 //边界移动
    			elif s > 0: r -= 1
    			else: 
    				res.append((nums[i],  nums[l], nums[r]))
    				while l < r and nums[l] == nums[l+1]: //判断重复解
    					l += 1
    				while l < r and nums[r] == nums[r+1]:
    					l -=1
    				l += 1; r -= 1

## Tree、Binary、Binary Search Tree 、 Graph ##

Linked List是特殊化的Tree；Tree是特殊化的Graph  
二叉树各语言实现：

Python
    class TreeNode:
    	def __init__ (self, val):
    		self.val = val
    		self.left, self.right = None,None
    
    Java
    public  class  TreeNode {
    	public int val;
    	public TreeNode left,right;
    	public TreeNode (int val) {
    		this.val = val;
    		this.left = null;
    		this.right = null;
    	}
    }
    
    C++
    struct TreeNode {
    	int val;
    	TreeNode = left;
    	TreeNode = right;
    	TreeNode (int x) : val(x), left(NULL), right(NULL) {}
    }

#Validate BST （验证二叉排序树）
    def isValidBST(self, root) :
    	inorder = self.inorder(root)
    	return inorder == list(sorted(set(inorder))) //set排重；sorted排序，判断是否为升序
    def inorder (self, root)
    	if root is None:
    		return []
    	return self.inorder(root.left) + [root.val] + self.inorder(root.right)
    
    def is ValieBST(self, root):
    	self.prev = None
    	return self.helper(root)	
    def helper(self, root): //新建部分需要比较的子树，helper减少空间占用
    	if root is None:
    		return True
    	if not self.helper(root.left):
    		return False
    	if self.prev and self.prev.val >= root.val:
    		return False
    	self.prev = root
    	return self.hepler(root.right)
    	
    
    public boolean isValid(TrddNode root, Integer min, Integer max) {
    	if (root == null) return true;
    	if (min != null && root.val <= min) return false; //递归查询左右子树节点大小，不符合BST定义则直接false
    	if (max != null && root.val >= max) return false;
    	return isValid (root.left, min, root.vallk) && isValid(root.right, root.val, max);
    }

#Lowest Common Ancestor（最近公共祖先）
    TreeNode lowstCommonAncestor(TreeNode root, TreeNode p, TrddNode q) { //递归遍历左右子树
    	if (root == null || root ==p || root == q) return root;
    	TreeNode left = lowestCommonAncestor(root.left, p, q);
    	TreeNode right = lowestCommonAncestor(root.right, p, q);
    	return left == null ? right : right == null ? left : root;
    
    ＃Lowest Common Ancestor of a Binary Search Tree (BST最近公共祖先）
    def lowestCommonAncestor(self, root, p, q): //递归比较子树与根节点的值
    	if p.val < root.val > q.val:
    		return self.lowestCommonAncestor(root.left, p, q)
    	if p.val > root.val < q.val:
    		return self.lowestCommonAncestor(root.right, p, q)
    	return root
    
    def lowestCommonAncestor（self, root, p, q): 
    	while root: //while循环代替递归
    		if p.val < root.val  > q.val:
    			root = root.left
    		elif p.val > root.val < q.val:
    		 	root = root.right
    		 else:
    		 	return root

#二叉树遍历
    
     1. 前序（Pre-order）：根-左-右
     2. 中序（In-order) ：左-根-右
     3. 后序（Post-order）：左-右-根
    
    def preorder(self, root):
    	if root:
    		self.traverse_path.append(root.val) 
    		self.preorder(root.left)
    		self.preorder(root.right)
    
    def inorder(self, root):
    	if root:
    		seft.inorder(root.left)
    		self.traverse_path.append(root.val)
    		self.inorder(root.right)
    
    def postorder(self, root);
    	if root:
    		self.postorder(root.left)
    		self.posrorder(root.right)
    		self.traverse_path.append(root.val)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZJTllJRQ_size_16_color_FFFFFF_t_70]: /images/20220223/f77432131ecb4655ab92d5d0c2b7b515.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZJTllJRQ_size_16_color_FFFFFF_t_70 1]: /images/20220223/d622285febae4222ace21ee4cbac584a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZJTllJRQ_size_16_color_FFFFFF_t_70 2]: /images/20220223/bf683ce6a6044f3ebb9a041e17e0cf0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZJTllJRQ_size_16_color_FFFFFF_t_70 3]: /images/20220223/70a0880a657344e682e0042faf96e1bf.png