What is a data structure?

• Data structures are the way computers store and organize data

One, linear structure, linear table

• A linear list is a finite sequence of n elements of the same type (n >= 0)
• Common linear tables are: array, linked list, stack, queue, hash table (hash table)

The basic concept

Time complexity

• In the big O notation, the time complexity formula is: T(n) = O(f(n)), where F (n) represents the sum of The Times of each code execution, and O represents the direct proportional relationship. The full name of this formula is: the progressive time complexity of the algorithm.
• The usual order of time complexity increases from top to bottom:
• • Constant order O (1)
• • The logarithmic order O (logN)
• • Linear log order O(nlogN)
• • Squared square order O (n)
• • Cubic order O (n) after
• • Order N to the K.
• • The index order O (2 ^ n)

Spatial complexity

• Space complexity is a measure of the amount of storage space temporarily occupied by an algorithm during its operation. It also reflects a trend and is defined by S(n).
• Space complexity is commonly used: O(1), O(n), O(n²).
• If the temporary space required for algorithm execution does not change with the size of a variable N, that is, the space complexity of this algorithm is a constant, which can be expressed as O(1).

S(n) = O(1) int j = 1; int j = 2; ++i; j++; int m = i + j;Copy the code

• Space complexity O(n)

int[] m = new int[n];
for (i = 1; i <= n; ++i) 
{
    j = i;
    j++
}
Copy the code

• In this code, the first line of the new array, the size of this data is N, the code 2 to 6, although there is a loop, but no new space allocation, therefore, the space complexity of this code mainly depends on the first line, that is, S(n) = O(n);

1. Array

• An array is a linear list of sequentially stored elements with contiguous memory addresses

• In many programming languages, arrays have the disadvantage of not being able to change their size dynamically
• In practice, we would prefer that the size of an array be dynamically variable

Dynamic array interface design

Dynamic array design

• Add (E element)

• Print the array

• Remove elements

• newApply for continuous memory space, can not be cut out in the middle

• Insert add elementadd(int index, E element)

• Extract the compliance judgment

2. List (LinkedList)

• Dynamic arrays have an obvious drawback
• • May cause a large waste of memory space
• Request as much memory as the linked list gets
• The listIt is a kind ofChain storetheThe linear tableThe memory addresses of all elements are not necessarily contiguous

Reverse a linked list

• Input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL
• Output: NULL – > 5 – > 4 – > 2 – > 3 – > 1

Recursively flip the linked list

• ListNode newHead = reverseList(head.next)do

/ / recursive inversion lists public ListNode reverseList (ListNode head) {if (head = = null | | head. The next = = null) return the head; ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; }Copy the code

Bidirectional circular linked lists

-add (int index, E element)

– remove(int index, E element)

public E remove(int index) {
    rangeCheck(index);
    
    Node<E> node = first;
    if (size == 1) {
        first = null;
        last = null;
    } else {
        node = node(index);
        Node<E> prev = node.prev;
        Node<E> next = nodex.next;
        prev.next = next;
        next.prev = prev;
        
        if (node == first) {// index == 0
            first = next;
        }
    }
    
    size--;
    return node.element;
}
Copy the code

Jesephus Problem

• Shoot on the count of three

• Consider adding 1 member variable and 3 methods
• • Current: indicates a node
• • Void reset(): makes current point to the headerfirst
• • E next () : let mecurrentTake a step back, which iscurrent = current.next
• • E the remove () : delete itcurrentAfter the node pointing to is successfully deleted, letCurrent points to the next node

A static linked list

• An array contains two elements, mimicking a linked list

Can ArrayList be further optimized?

• Int first: Where the first element is stored
• Delete bit 0, change pointer to first, first = 1

The difference between a bidirectional list and a dynamic array

• Dynamic arrays: Memory space is opened and destroyed relatively few times, but memory space can be wasted (can be reduced by scaling)
• Bidirectional linked list: the number of open and destroy space is relatively large, but does not cause the waste of memory space

Use of ArrayList and LinkList selection recommendations

• If frequent inThe tailAdd, delete operations, dynamic array, bidirectional linked listAll canchoose
• If frequent inThe headYou are advised to add or deleteTwo-way linked list
• If there are frequentAt any positionYou are advised to add or deleteTwo-way linked list
• If there are frequentThe queryOperation. You are advised to use this parameterThe dynamic array

2. Tree structure

Basic concepts of trees

Binary tree

• Properties of binary trees

Proper Binary Tree

• All nodes have degrees of either 0 or 2

Full Binary Tree

Complete Binary Tree

• Properties of complete binary trees

• It’s not a perfect binary tree

Often the examination site

Traversal of binary trees

• Traversal is a common operation in data structures, where all elements are accessed once
• Linear structure traversal is relatively simple, order traversal/reverse order traversal
• According to the order of node access, there are four common traversal methods of binary tree
• • The former sequence traversal
• • In the sequence traversal
• • After the sequence traversal
• • Sequence traversal

Preorder Traversal

• Access to the order

Inorder Traversal

• Access to the order
• • Middle order traverses the left subtree, the root node, and the right subtree

Postorder Traversal

• Access to the order
• • Post-traversal left subtree, post-traversal right subtree, root node

Level Order Traversal

• Access to the order
• • Each node is accessed from top to bottom and left to right

Flip the binary tree

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) return null; TreeNode tmpNode = root.left; TreeNode tmpNode = root.left; root.left = root.right; root.right = tmpNode; invertTree(root.left); invertTree(root.right); return root; } } class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) return null; InvertTree (root.left) invertTree(root.left); invertTree(root.right); TreeNode tmpNode = root.left; root.left = root.right; root.right = tmpNode; return root; } } class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) return null; InvertTree (root.left); TreeNode tmpNode = root.left; root.left = root.right; root.right = tmpNode; invertTree(root.left); return root; }}Copy the code

Power button brush

The sorting

Bubble sort

• Execute the process

• • Compare each pair of adjacent elements from the beginning, and if the first is larger than the second, swap their positions
• • • After a round, the last element is the largest element
• • Ignore the largest element ever found and repeat the first step until all elements are in order

• Worst, average time complexity: O(n²)

• Best time complexity: O(n)

• Space complexity: O(1)

for (int end = array.length - 1; end > 0; end--) { for (int begin = 1; begin <= end; begin++) { if (cmp(begin, begin - 1) < 0) { swap(begin, begin - 1); For (NSInteger end = result.count - 1; end > 0; end--) { for (NSInteger begin = 1; begin <= end; begin++) { NSInteger left = [result[begin-1] integerValue]; NSInteger right = [result[begin] integerValue]; if (left > right) { [result exchangeObjectAtIndex:begin-1 withObjectAtIndex:begin]; }}}Copy the code

• If the sequence is completely ordered, bubble sort can be terminated early to optimize 1

for (int end = array.length - 1; end > 0; end--) { boolean sorted = true; for (int begin = 1; begin <= end; begin++) { if (cmp(begin, begin - 1) < 0) { swap(begin, begin - 1); sorted = false; } } if (sorted) break; } NSMutableArray *result = [[NSMutableArray alloc] initWithArray:@[@1, @2, @5, @4, @3]]; for (NSInteger end = result.count - 1; end > 0; end--) { BOOL sorted = YES; for (NSInteger begin = 1; begin <= end; begin++) { NSInteger left = [result[begin-1] integerValue]; NSInteger right = [result[begin] integerValue]; if (left > right) { [result exchangeObjectAtIndex:begin-1 withObjectAtIndex:begin]; sorted = NO; } } if (sorted) { break; }}Copy the code

• If the tail of the sequence has been locally ordered, the position of the last exchange can be recorded to reduce the number of comparisons and optimize 2

for (int end = array.length - 1; end > 0; end--) { int sortedIndex = 1; for (int begin = 1; begin <= end; begin++) { if (cmp(begin, begin - 1) < 0) { swap(begin, begin - 1); sortedIndex = begin; } } end = sortedIndex; } NSMutableArray *result = [[NSMutableArray alloc] initWithArray:@[@1, @2, @5, @4, @3]]; for (NSInteger end = result.count - 1; end > 0; end--) { NSInteger sortedIndex = 1; for (NSInteger begin = 1; begin <= end; begin++) { NSInteger left = [result[begin-1] integerValue]; NSInteger right = [result[begin] integerValue]; if (left > right) { [result exchangeObjectAtIndex:begin-1 withObjectAtIndex:begin]; } sortedIndex = begin; } end = sortedIndex; }Copy the code

Stability of sorting algorithm

• If the relative positions of two elements, which are equal, remain the same before and after sorting, then this is a stable sorting algorithm
• • 5, 1, 3𝑎, 4, 7, 3𝑏
• • Stable order: 1, 3𝑎, 3𝑏, 4, 5, 7
• • Order of instability :1, 3𝑏, 3𝑎, 4, 5, 7
• When sorting custom objects, stability affects the final sorting effect
• Bubble sort is a stable sorting algorithm
• • A stable sorting algorithm can also be written as an unstable sorting algorithm if you’re not careful

for (NSInteger end = result.count - 1; end > 0; end--) { for (NSInteger begin = 1; begin <= end; begin++) { NSInteger left = [result[begin-1] integerValue]; NSInteger right = [result[begin] integerValue]; If (left > = right) {/ / > written carelessly > = [result exchangeObjectAtIndex: withObjectAtIndex begin - 1: begin]; }}}Copy the code

In-place Algorithm

• What is in place algorithm?
• • Not dependent on additional resources or on a few additional resources, relying only on the output to override the input
• • The space complexity of O(1) can be considered as in situ algorithm
• The non-in-situ algorithm is called not-in-place or out-of-place
• Bubble sort is in-place

Selection sort

• Execute the process

1. Find the largest element in the sequence and swap places with the last element

• • After a round, the last element is the largest element

2. Ignore the largest element found in Step 1 and repeat Step 1

for (int end = array.length - 1; end > 0; end--) { int max = 0; for (int begin = 1; begin <= end; begin++) { if (cmp(max, begin) < 0) { max = begin; } } swap(max, end); } NSMutableArray *result = [[NSMutableArray alloc] initWithArray:@[@1, @2, @5, @4, @3]]; for (NSInteger end = result.count - 1; end > 0; end--) { NSInteger max = 0; for (NSInteger begin = 1; begin <= end; begin++) { NSInteger begin = [result[begin] integerValue]; NSInteger max = [result[max] integerValue]; if (begin > max) { max = begin; } } [result exchangeObjectAtIndex:end withObjectAtIndex:max]; }Copy the code

• The number of swaps of selection sort is much less than bubble sort and the average performance is better than bubble sort
• Best, worst, average time complexity: O(n²), space complexity: O(1), belonging to unstable order

Heap sort

• Heap sort can be thought of as an optimization of selection sort.
• Big pile top

Data structures & algorithms

Master the most common data structures

• An array of @ [@ “12” @ “34”]

• • Advantages: Query quick index traversal convenient
• • Disadvantages: Slow addition and deletion (find the 5, delete, 678 move forward) can only store one type of data (new tuple) fixed size inconvenient expansion (int[10] fixed)

• The list

• • Advantages: Fast addition and deletion (change the pointer to the linked list)
• • Disadvantages: query is particularly troublesome (go down from the beginning node first)

• Two-way linked list

• • Pointers point to before and after data
• • @autoreleasepool

• The linear table

• The queue

• • Queue, where you put tasks

• The stack

• Stack, stack, in and out, page pop

• figure

The tree

• • Binary trees, traversal, order, flipping of binary trees
• • Binary trees have the benefits of linked lists as well as arrays

Hash

• • 1-10 find 7, go through
• • Dichotomy reduces time complexity
• • Once in place, the key is used to find the value directly, and the bottom of the dictionary is hash
• Hash function :f
• • 1 – key – f(key) -> index=1
• • The hash puts the value 1 at index=1,
• 11, 12, 13, 15, 18
• • Waste of resources, hash function is not well designed
• • F (key) = key-10 = index Key > 10
• • Simple calculation + uniform distribution, direct address method, data analysis,
• • Square the middle method (increase the range of drop, resulting in reduced conflict), hashing conflict
• • Take more method
• • • 9 13 14 15 16 18 percent 10
• • • 9, 3, 4, 5, 6, 8
• Data analysis – Bit operation – index – Value
• It is difficult to design a reasonable, uniformly distributed hash function

Hash conflict

• Square the middle
• • 9, 13, 14, 15, 16, 18
• • 81 169 196 225 256 324 — Hash conflict
• Go ahead and hash. – Rehash the hash function
• Judgment. – Every move
• Reflatten method – reduce your operations
• • 11 of 12 22 32
• • 1 plus 2 squared is 5
• • 1 plus 2 squared plus 3 squared is 14
• Zipper method –
• • 11, 12, 22, 32, 42, 52

Common algorithm problems

1. String reversal

• Hello,word =>
• Dorw,olleh
• • Two variable records, one from the front, one from the end, change to the very middle
• • Move the swap pointer

Char *begin = cha; char * reverse(char *cha) {char * reverse(char *cha); char * reverse(char *cha); char * reverse(char *cha); char * reverse(char *cha); Char *end = cha + strlen(cha) -1; While (begin < end) {char jh_tmp = *begin; *(begin++) = *end; *(end--) = jh_tmp; }}Copy the code

2. Flip the list

• One of the things about linked lists is that they start from scratch, they have no subscripts, and they’re very easy to break
• Create an empty header

Struct JHNode* reverseList(struct JHNode* head) { Struct JHNode *newH = NULL; // iterate over the list while (p! Struct JHNode *temp = p->next; P ->next = newH; // Change the head of the new list to the current node newH = p; // move p pointer p = temp; } // return newH; }Copy the code

Power button brush

Flip the word in the string

1. Eliminate redundant whitespace from strings

2. Reverse the sequence from 0 to 10 and then one by one

Public String reverseWords(String s) {if (s == null) return ""; char[] chars = s.toCharArray(); // The final valid length of the string int len = 0; Int cur = 0; // The first character is a space character Boolean preIsSpace = true; For (int I = 0; i < chars.length; i++) { if (chars[i] ! Chars [cur] = chars[I]; chars[cur] = chars[I]; cur++; preIsSpace = false; Else if (preIsSpace == false) {// chars[I] is a space character and chars[i-1] is not a space character chars[cur] = ' '; cur++; preIsSpace = true; }} // After traversal, the final first character is the space character len = preIsSpace? (cur - 1) : cur; if (len <= 0) return ""; // 2. Reverse the entire string (chars, 0, len); Int preSpaceIdx = -1; // Int preSpaceIdx = -1; // preSpaceIdx = -1; for (int i = 0; i < len; i++) { if (chars[i] ! = ' ') continue; // Traverse the space character reverse(chars, preSpaceIdx + 1, I); preSpaceIdx = i; } // 4. Reverse the last word (chars, preSpaceIdx + 1, len); return new String(chars, 0, len); Private void reverse(char[] chars, int li, int ri) {ri--; private void reverse(char[] chars, int li, int ri);  while (li < ri) { char tmp = chars[li]; chars[li] = chars[ri]; chars[ri] = tmp; li++; ri--; } } }Copy the code

3. The largest string without repeating characters

• Given a string, find the length of the smallest string that does not contain repeating characters.

• It’s kind of like dynamic programming
• Longest non-repeating string

• Hash table technology

public int lengthOfLongestSubstring(String s) { if (s == null) return 0; char[] chars = s.toCharArray(); if (chars.length== 0) return 0; Map<Character, Integer> prevIdxes = new HashMap<>(); PrevIdxes. Put (chars[0], 0); Int [] prevIdxed = new int[128]; // prevIdxed = new int[128]; for (int i = 0; i < prevIdxed.length; i++) { prevIdxes[i] = -1; } prevIdxes[chars[0]] = 0; */ // Start index (left-most index) of the longest non-repeating string ending with character in position i-1 int li = 0; int max = 1; for (int i = 1; i < chars.length; I ++) {// The last position of the I character Integer PI = prevIdxes. Get (chars[I]); if (pi ! = null && li <= pi) { li = pi +1; } // store prevIdxes. Put (chars[I], I); Int PI = prevIdxes[chars[I]]; int PI = prevIdxes[chars[I]]; if (li <= pi) { li = pi + 1; PrevIdxes [chars[I]] = I; Max = math.max (Max, i-li + 1); } return max; }Copy the code

Dynamic Programming

• Dynamic planning, build DP
• • It is a common strategy for solving optimization problems
• Common usage routines (step by step optimization)

1. Recursion of violence (top down, overlapping subproblems occur)
2. Memorized search (top-down)
3. Recursion (bottom up)

Offer47. The maximum value of the gift

Public int maxValue(int[][] grid) {// rows = grid.length; Int cols = grid[0]. Length; Int [][] dp = new int[rows][cols]; Dp [0][0] = grid[0][0]; Int col = 1; for (int col = 1; col < cols; col++) { dp[0][col] = dp[0][col - 1] + grid[0][col]; } for (int row = 1; int row = 1; row < rows; row++) { dp[row][0] = dp[row - 1][0] + grid[row][0]; } for (int row = 1; row < rows; row++) { for (int col = 1; col < cols; col++) { dp[row][col] = Math.max(dp[row - 1][col], dp[row][col - 1]) + grid[row][col]; } } return dp[rows - 1][cols - 1]; }Copy the code

The best time to buy and sell stocks

• Given an array prices, its ith element prices[I] represents the price of a given stock on day I.
• You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.
• Return the maximum profit you can make from the transaction. If you can’t make any profit, return 0.

public int maxProfit(int[] prices) { if ( prices == null || prices.length == 0) return 0; Int minPrice = prices[0]; Int maxProfit = 0; For (int I = 1; i < prices.length; If (prices[I] < minPrice) {// if (prices[I] < minPrice) {// if (prices[I] < minPrice) {// if (prices[I] < minPrice) { } else {maxProfit = Math. Max (maxProfit, prices[I] -minprice); } } return maxProfit; }Copy the code

Difficulty in editing distance

• Edit-distance algorithm is widely used by data scientists as a basic algorithm for evaluating machine translation and speech recognition.
• Given two words word1 and word2, calculate the minimum operand needed to convert word1 to word2.
• • You can do one of three things with a word:

1. Insert a character
2. Delete a character
3. Replace a character

Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (delete 'r') rose -> ros (delete 'e')Copy the code

• The first two cases

• The third case

• The fourth case

• Three ways: from the top, from the left, from the top left

• Pick the smallest one

public int minDistance(String word1, String word2) { if (word1 == null || word2 == null) return 0; char[] cs1 = word1.toCharArray(); // Line char[] cs2 = word2.tochararray (); Int [][] dp = new int[cs1.length + 1][cs2.length + 1]; dp[0][0] = 0; For (int I = 1; i <= cs1.length; i++) { dp[i][0] = i; } // The shortest path is the length of the current column string. j <= cs2.length; j++) { dp[0][j] = j; } // For (int I = 1; i <= cs1.length; i++) { for (int j = 1; j <= cs2.length; Int top = dp[i-1][j] + 1; int top = dp[i-1] + 1; Int left = dp[I][j-1] + 1; Int leftTop = dp[i-1][j-1]; // If the last string is not equal, an additional substitution operation is required if (cs1[i-1]! = cs2[j - 1]) { leftTop++; } dp[i][j] = Math.min(Math.min(top, left), leftTop); } } return dp[cs1.length][cs2.length]; }Copy the code

• The difficulty is state definition, state transition equation, how to derive the next one

• A two-dimensional array can be optimized to a one-dimensional array

Force clasp 5. Maximum loop substring

Violence law

Dynamic programming method

• Compared to the brute force method, it’s actually the brute force method that takes the time optimization from n^3 to n^2
• Space O(n^2), space in time

• From the bottom to the top, from the right

public String longestPalindrome(String s) { if (s == null) return null; char[] cs = s.toCharArray(); if (cs.length == 0) return s; Int maxLength = 1; Int begin = 0; Boolean [][] dp = new Boolean [cs.length][cs.length]; For (int I = cs.length - 1; i >= 0; For (int j = I; int j = I; j < cs.length ; J ++) {// cs[I, j] string length int length = j - I + 1; / / / * * 1. Two cases the length of the string < = 2, the length of 1 or 2, cs is equal to the cs [j] [I] characters characters, then cs [I, j] is palindrome string, the dp [I] [j] = cs cs [j] [I] = = 2. If cs[I + 1, j-1] is a palindrome aaadefed and cs[I] is equal to cs[j] when the string length is greater than 2, then cs[I, J] is a palindrome string The dp [I] [j] = dp + 1] [I] [j - 1 && (cs) = = cs [j] [I]) * / dp [I] [j] = (cs = = cs [j] [I]) && (length < = 2 | | dp [I + 1] [j - 1)); If (dp[I][j] && (length > maxLength)) {maxLength = length; if (dp[I][j] && (length > maxLength)) {maxLength = length; begin = i; } } } return new String(cs, begin, maxLength); }Copy the code

Post is not easy, like the likes of the people have more good luck 👍 :), regular updates + attention not lost ~

Ps: Welcome to join the author’s 18 years of research iOS audit and cutting-edge technology of the 3000 link group: 662339934, limited pit, note “gold diggers” can be through the group