1. The dictionary tree

Dictionary tree, Trie tree, also known as word lookup tree or key tree, is a tree structure. The typical application is to count and sort large numbers of strings (but not limited to strings), so it is often used for text word frequency statistics by search engine systems.

advantages

Minimizes unnecessary string comparisons and improves query efficiency over hash tables.

Basic properties

  1. The node itself does not contain the whole word;
  2. From the root node to a node, the characters passing through the path are joined together and are the string corresponding to that node:
  3. The paths of all children of each node represent different characters.

Additional information can also be stored, as the numbers in the figure represent occurrencesThe frequency of

Internal implementation

Each node has 26 English letters

core idea

  • The core idea of Trie trees is space for time.
  • The common prefix of string is used to reduce the cost of query time to improve efficiency.

Implement Trie (Prefix Tree)

答 案 : Dictionary tree

Word search

Word search (backtracking)

Word Search II

Word search II

2. Union-find

And the search set is used to solve group, matching problems, such as circle of friends

Basic operation

  • MakeSet (s): Creates a new lookup set with s single-element sets.
  • UnionSet (X, Y): Merges the set where element X and element Y are located, requiring that the sets where element X and y are located do not intersect. If they do, the merges will not occur.
  • Find (x): Finds the representation of the set in which element x is located. This operation can also be used to determine whether two elements are in the same set by comparing their representatives.

Initialization:

Query, merge

Path to the compression

116. Circle of friends

And look up the set

The surrounding area

3. Bloom filter

A long binary vector and a series of random mapping functions. Bloom filters can be used to retrieve whether an element is in a collection.

The advantage is that the space efficiency and query time are far more than the general algorithm, but the disadvantage is that there is a certain error recognition rate and deletion difficulty.

HashTable + zipper stores repeating elements

Schematic diagram of Bloom filter:

Error: B does not save, but the query result is true

If they’re both 1, they’re probably there, and if one of them isn’t 1, they’re definitely not there. The Bloom filter exists only as the outermost cache. To determine whether it exists, you need to go deeper into the database.

Common application

  1. Bitcoin network
  2. Map-reduce: Hadoop and Search Engine
  3. Redis cache
  4. Filtering of spam, comments, etc

Recommend the article

Principle and implementation of Bloom filter

Use bloom filter to solve cache breakdown, spam identification, set weight

Example of a Bloom filter Python implementation

4. LRU

Least recent use rule

  • Size and replacement policy
  • hashTable+Double LinkedList

Query O(1) Modify O(1) Update O(1)

LRU caching mechanism

5. Bit operations

Exclusive-or: The same value is 0, and the different value is 1. It can also be understood as “no carry addition”. Some characteristics of xOR operations: ^ 0 = x x x ^ 1 s = = ~ ~ x / / note 1 s 0 x ^ ~ (x) = 1 s x ^ x = 0 c = = > a ^ ^ b c = b, B ^ c = a / / exchange two Numbers a ^ ^ c b = a ^ ^ (b), c = c/(a ^ b) ^ / associative

The bit operation at the specified position

  1. Clear the rightmost n bit of x: x&(~0<
  2. Get the NTH bit of x (0 or 1) : (x>>n)&1
  3. Get the NTH power of x: x&(1<<(n-1))
  4. Only for the position of the n 1: x | (1 < < n)
  5. Only the NTH position is 0: x&(~(1<
  6. X &((1<
  7. X &(~((1<<(n+1))-1))

Operational points

  • Judge odd and even:
    • X % 2 = = 1 > (x & 1) = = 1
    • X % 2 = = 0 > (x & 1) = = 0
  • X > > a > 1 x / 2
    • That is: x=x/2 one > x=x>>1;
    • Mid = (left + right) / 2 a > mid = (left + right) > > 1;Copy the code
  • X = X&(X-1) clears the least significant 1
  • X& -x => gets the lowest 1
  • X&~X=>0

Convert from decimal to base 2

The number of ones

Number of bits 1 (bit operation)

A power of 2

A power of two

Reverse binary

Bit count

N queen

N queen II

Binary search

Binary search algorithms work in a similar way to guessing numbers, where someone says, “I’m thinking of a number between 1 and 100.” Every time we respond to a number, the person will say whether the number is too high, too low, or right.

This algorithm requires that the data structure being searched be sorted. Here are the steps the algorithm follows.

  1. Select the middle value of the array.
  2. If the selected value is to be searched, then the algorithm is done (the value was found).
  3. If the value to be searched is smaller than the selected value, return to Step 1 and look for (smaller) in the subarray to the left of the selected value.
  4. If the value to be searched is larger than the selected value, return to Step 1 and look for (larger) in the subarray to the right of the seed selection value.

Binary search premise

  1. Monotonicity of objective function (monotonically increasing or decreasing)
  2. There are upper and lower bounds.
  3. Index accessible

Code template

The JavaScript version:

let left = 0, right = len(array) - 1 
while (left <= right) {
    let mid = (left + right) >> 1  
    if (array[mid] === target) { 
        /*find the target*/; 
        return 
    } else if (array[mid] < target) {
        left = mid + 1  
    } else {
        right = mid - 1 
    }
}
Copy the code

Java version

int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1; / / note
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1; / / note
        else if (nums[mid] > target)
            right = mid - 1; / / note
    }
    return -1;
}
Copy the code

The square root of x

Valid perfect squares

Search rotation sort array

Search two dimensional matrix

Find the minimum value in the rotation sort array

Ke Ke who loves bananas

Difficulty: Medium

Coco who loves bananas (dichotomy)

Remove duplicate elements from an ordered array (fast or slow Pointers)

Removes duplicates from an ordered array

Delete duplicates from an ordered array

Removes duplicate elements from sorted linked lists

Difficulty: Easy

Delete duplicate elements from sorted lists

Longest string of subroutines

Difficulty: Medium

Longest callback substring (left and right Pointers)

7. The sorting

1. Comparison sorting determines the relative order of elements by comparison. Because its time complexity cannot break through 0(Nlogn), it is also called nonlinear time comparison sorting.

2. Non-comparative sorting does not determine the relative order of elements by comparison. It can break through the time lower bound based on comparison sorting and run in linear time, so it is also called linear time non-comparative sorting.

Primary sort 0(n^2)

  1. Selection Sort finds the minimum value and places it at the beginning of the array to be sorted.
  2. Insertion Sort progressively builds ordered sequence from front to back; For unsorted data, scan from back to front in the sorted sequence to find the appropriate location and insert.
  3. Bubble Sort is a nested loop that swaps adjacent elements each time it looks in reverse order.

Special sort -o (n)

  1. Counting Sort

Counting sort requires that the input data be integers with a defined range. Convert the input data values into keys and store them in the extra array space; Then fill the items whose count is greater than 1 back into the original array Sort works by assuming that the input data is evenly distributed, sorting the data into a finite number of buckets, and sorting each bucket separately (it is possible to use another sorting algorithm or recursive bucket sorting). Radix Sort is to Sort according to the low order first and then collect; And then sort it in order, and then collect it; And so on, all the way to the highest place. Sometimes some attributes are prioritized, first by low priority, then by high priority.

Ten classic sorting algorithms

Example quicksort code

Example merge sort code

Heapsort code example

Visual animation of 9 classical sorting algorithms

Watch 15 sorting algorithms in 6 minutes

Relative sorting of arrays

Valid letter heterotopic word

Merge range

Flip to

8. Advanced search

The primary search

  1. Simple search
  2. Optimization method: No repetition (Fibonacci), prune (generate parenthesis problem)
  3. Search direction:
    • DFS: depth first search Depth first search
    • BFS: Our lines first search

To optimize the direction

  • pruning

Climb the stairs

Parentheses generates

N queen

  • The bidirectional search

Minimum genetic change

randomly

  • Heuristic (A* Search)

Based on BFS code:

A* search:

Evaluation function

  • The heuristic function h(n), which evaluates which nodes are most promising is a node we’re looking for, h(n) returns a non-negative real number, or you can think of it as the estimated cost of the path to the destination node from node N.
  • A heuristic function is a way of telling the direction of a search. It provides an intelligent way to guess which neighbor nodes will lead to a target.

Shortest path in binary matrix

8 Comparison of puzzles

Sliding puzzle

AlphaZero: nikcheerla. Making. IO/deeplearnin…

DFS: shimo. Im/docs/ddgwCc…

BFS: shimo. Im/docs/P8TqKH…

9. String algorithms

Convert to lowercase

Convert to lowercase letters

The length of the last word

The length of the last word

Gems and Stones

Precious stones and stones

The first unique character in a string

The first unique character in a string

String conversion to integer (atoi)

String manipulation

Longest public prefix

The longest common prefix

Inverted string

Just invert letters

Flip the word in the string

Ectopic word

Valid letter heterotopic word

Grouping of letter ectopic words

Find all letter heterotopic words in the string

Palindrome list:

Validates palindrome strings

Verify palindrome string ⅱ

Longest string of subroutines

10. Faqs

1. The Sum problem

1. The sum of two Numbers

Difficulty: Easy

The sum of two numbers (dictionary)

Sum of two numbers II – Enter an ordered array

Difficulty: Easy

Solution: Sum of two numbers II – Input ordered array (two Pointers)

The sum of three number

Difficulty: Medium

Solution: Sum of three numbers (sort + double pointer)

The sum of four number

Difficulty: Medium

The sum of four numbers

2. The problem of sorting pancakes

Pancakes sorting

Difficulty: Medium

Pancakes sorting

3. Prefixes and tricks

And are subarrays of K

Difficulty: Medium

And subarrays of K (prefix and trick)

And the shortest subarray at least K

4. Other

Nim game

Solution: Nim games

Stone game

Solution: Stone game

Light switches

Solution: Light switch

Ability to deliver packages within D days

The surrounding area

Solution: the surrounding area

Their independence

Solution: Solve sudoku

Valid sudoku

Solution: Effective sudoku

Finger Offer 29. Print matrix clockwise