This is the 11th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

How data structures are stored

  • There are only two ways to store data structures:
    • Arrays: Sequential storage
    • List:Chain store
      • Hash tables, stacks, queues, heaps, trees, and graphs are all data structure superstructures based on arrays and linked lists

Common data structures

  • Hash table:The hash function maps the keys to a large array
    • Hash conflict resolution:
      • Zip:
        • The linked list feature is required
        • The operation is simple
        • However, additional storage space is required to store the Pointers
      • Linear probe method:
        • Required data features
        • Arrays are used to facilitate continuous addressing
        • No additional storage space is required to store Pointers, but the operation is relatively complex
  • Queue and stack data structures can be implemented using either an array or a linked list:
    • Arrays: To handle expansion
    • Linked list: No expansion problem, but more memory storage node Pointers are required
  • Pile:A heap is a tree implemented as an array
    • The heap is a complete binary tree
    • No node Pointers are required for array storage
    • The operation is simple
  • Tree:A common tree is implemented with a linked list
    • It doesn’t have to be a full binary tree, so it’s not good for array storage
    • Linked lists allow different cleverly designed trees to deal with different problems:
      • Binary search tree
      • AVL tree
      • Red and black tree
      • Interval tree
      • B tree
  • There are two ways to represent a graph:
    • Adjacency matrix:2 d array
      • Judge connectivity quickly
      • You can solve these problems by performing matrix operations
      • But it takes up space when the graph is sparse
    • Adjacency list:The list
      • Save a space
      • However, the efficiency of graph correlation operation is lower than that of adjacency matrix

Array and linked list comparison

An array of

  • Advantages:
    • Arrays are compact contiguous storage
    • Random access
    • Quickly locate elements by index
    • Relatively save storage space
  • Disadvantages:
    • Because arrays are stored contiguously, enough memory space must be allocated at once
    • If the array needs to be expanded, it needs to allocate a larger space and copy all the data to it. The time complexity is O(N).
    • If you want to insert and delete in the middle of an array, you have to move all of the following elements in order to maintain continuity, and the time is O(N).

The list

  • Advantages:
    • Linked list elements are discontinuous and use Pointers to point to the next element
    • There is no array expansion problem
    • If you know the predrive and the rear drive of an element, you can delete the element or insert the element with time of O(1).
  • Disadvantages:
    • Because the storage space of the linked list is discontinuous, the address of the corresponding element cannot be calculated according to an index, so it cannot be accessed randomly
    • Each element must store Pointers to before and after elements, so it consumes relatively more storage space

Basic operations on data structures

  • There are many types of data structures, all designed to be added, deleted, modified and checked as efficiently as possible in different application scenarios
  • Basic operation of data structure: traversal + access
  • There are two forms of traversal + access to data structures:
    • Linear: for-while iteration
    • Nonlinearity: recursion

Array traversal framework

  • Linear iterative structure:
void traverse(int[] arr) {
	for (int i = 0; i < arr.length; i++) {
		// Iteratively access arr[I]}}Copy the code

Linked list traversal framework

  • There are both iterative and recursive structures:
/* * Basic single linked list nodes */
 class ListNode {
 	int val;
 	ListNode next;
 }

void traverse(ListNode head) {
	for(ListNode p = head; p ! = null; p = p.next) {// Iteratively access p.val}}void traverse(ListNode head) {
	// Access head.val recursively
	traverse(head.next);
}
Copy the code

Binary tree traversal framework

  • A typical nonlinear recursive traversal structure:
/* * Basic binary tree nodes */
 class TreeNode {
 	int val;
 	TreeNode left, right;
 }

void traverse(TreeNode root) {
	// Recursively access the left and right child nodes
	traverse(root.left);
	traverse(root.right);
}
Copy the code
  • The recursive traversal of binary trees is similar to that of linked lists, and the structure of binary trees is similar to that of single linked lists
  • The binomial tree framework can be extended to an n-fork tree traversal framework:
/* * Basic n-tree nodes */
 class TreeNode {
 	int val;
 	TreeNode[] children;
 }

 void traverse(TreeNode root) {
 	// Access each subtree recursively
 	for(TreeNode child : children) { traverse(child); }}Copy the code
  • The traversal of the n-fork tree can be extended to the traversal of the graph. Because a graph is a combination of several N-fork trees

Algorithm subject

  • Data structures are tools, and algorithms are ways of solving specific problems with appropriate tools:
    • Before learning algorithms, you need to understand the features and weaknesses of common data structures
  • fromBinary treeThe topic began to study the algorithm problem:
    • Binary trees are the easiest way to cultivate frame thinking
    • Most algorithmic problems are essentially tree traversal problems
  • Look at the tree-related problem first, and try to see the problem from the framework:
    • Extract and extend based on the framework
    • You can quickly understand the core logic by looking at other people’s solutions
    • It also helps you find a way to think when you write your own solutions

Binary tree

  • The basic framework of binary tree:
void traverse(TreeNode root) {
	// Preorder traversal. traverse(root -> left);// In order traversal. traverse(root -> right);// Back-order traversal. }Copy the code
  • Problem: Find the maximum path sum in a binary tree
int ans = INT_MIN;
int oneSideMax(TreeNode* root) {
  if (root == nullptr) {
		return 0;
	}
	int left = max(0, oneSideMax(root -> left));
	int right = max(0, oneSideMax(root -> right));
	ins ans = max(ans, left + right + root -> val);
	return max(left, right) + root ->val;
}
Copy the code

This is a post-order traversal

  • Topic: Restore a binary tree based on the results of preorder traversal and in-order traversal
TreeNode buildTree(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
	if (preStart > preEnd || inStart > inEnd) {
		return null;
	}
	TreeNode root = new TreeNode(preOrder[preStart]);
	int inRoot = inMap.get(root -> val);
	int numsLeft = intRoot - inStart;
	root -> left = buildTree(preOrder, preStart + 1, preStart + numsLeft, inOrder, instart, inRoot - 1, inMap);
	root -> right = buildTree(preOrder, preStart + numsLeft + 1, preEnd, inOrder, inRoot + 1, inEnd, inMap);
	return root;
}
Copy the code

The multiple arguments in the function are used to control the index of the array, and the algorithm is essentially a preorder traversal

  • Title: Restoring a BST
void traverse(TreeNode* node) {
	if (! node) {
		return;
	}
	traverse(node -> left);
	if (node -> val < prev -> val) {
		s = (s == null) ? prev : s;
		t = node;
	}
	prev = node;
 traverse(node -> right)
}
Copy the code

This is an in-order traversal

  • It can be found that whenever recursion is involved, it is a tree problem

Dynamic programming

  • Most dynamic programming problems are simply traversing a tree:
    • Master the tree traversal operation
    • Skilled how to convert ideas into code
    • Skilled extraction of other people’s solution of the core ideas
  • The exact change problem in dynamic programming: the direct solution is to traverse an N – fork tree
def coinChange(coin: List[int], amount: int) :
	def dp(n) :
		if n == 0: return 0
		if n < 0: return -1
	
		res = float("INF")
		for coin in coins:
			subproblem = dp(n - coin)
			If the subproblem has no solution, skip the loop
			if subproblem == -1: continue
			res = min(res, 1 + subproblem)
		return res ifres ! =float("INF") else -1
	return dp(amount)
Copy the code
  • This code is essentially a walk through an n-fork tree:
def dp(n) :
	for coin in coins:
		dep(n - coin)
Copy the code

Backtracking algorithm

  • The backtracking algorithm is an n-cross tree traversal problem
  • N Queen question:
void backTrack(int[] nums, List<Integer> track) {
	if (track.size == nums.length) {
		res.add(new LinkList(track));
		return;
	}
	for (int id= 0; i < nums.length; i ++) {
		if(track.contains(nums[i])) {
			continue;
		}
		track.add(nums[i]);
		// Go to the next level of the decision treebackTrack(nums, track); track.removeLast(); }}Copy the code
  • This code’s N cross tree traversal framework:
void backTrack(int[] nums, List<Integer> track) {
	for (int i = 0; i < nums.length; i++) { backTrack(nums, track); }}Copy the code

Summary of algorithm framework thinking

  • Basic storage of data structures:
    • The chain
    • The order
  • Basic operations on data structures:
    • increase
    • delete
    • change
    • check
  • Data structure traversal mode:
    • The iteration
    • recursive
  • Algorithm topic:
    • Combining with frame thinking, the algorithm problem is studied from the tree
    • Now that you understand the structure of the tree, you can look at backtracking, dynamic programming, and divide and conquer