Preface

This blog is completed step by step in the following order, which is also a learning process, so you can comment on any questions at any time. I hope we can make progress together.

Stack, queue, heap

Stack, queue, heap data structure is not introduced, just need to know stack is first in first out, queue is first in first out. Here I will mainly introduce the heap, which is actually a binary tree. Let's go straight to the algorithm and implementation method.
1. Find the number K in an array
input:[2,3,4,5,6] k=2
output: 5

#include<iostream>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
//Algorithmic thinking
//1. Create a priority queue with the size of K
//2. Maintain the priority queue. If the number is larger than the top of the priority queue, push the new element at the top of the pop until the end.
//3. The first K-large element is saved in the priority queue, and the first one is the K-large element
int Kmax(vector<int>&input,int k){
    if(k>input.size())return 0;
    std::priority_queue<int,vector<int>,greater<int>> max_queue;
    int i;
    for(i=0;i<k;++i){
        max_queue.push(input[i]);
      }
    for(i=k;i<input.size();++i){
        if(input[i]>max_queue.top()){
            max_queue.pop();
            max_queue.push(input[i]);
          }
      }
    return max_queue.top();
  }

2. Find the median in an array
input:[1,2,3] output:2
input:[1,2,3,4] output:2.5

#include<iostream>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
namespace KMAX {
  int Kmax(vector<int>&input,int k){
    if(k>input.size())return 0;
    std::priority_queue<int,vector<int>,greater<int>> max_queue;
    int i;
    for(i=0;i<k;++i){
        max_queue.push(input[i]);
      }
    for(i=k;i<input.size();++i){
        if(input[i]>max_queue.top()){
            max_queue.pop();
            max_queue.push(input[i]);
          }
      }
    return max_queue.top();
  }
  //Get median
  double getMidNum(vector<int>&input){
    if(input.empty())return 0;
    if(input.size()%2!=0){
        return Kmax(input,input.size()/2+1);
      }
    else {
        return (double)(Kmax(input,input.size()/2)+Kmax(input,input.size()/2+1))/2;
      }
  }

Combined with the idea of the first question, in fact, the median is the element with the largest K/2. If K is an odd number, it is directly k/2+1. For example, if K=3, it is the second one, that is, 3 / 2 + 1. Similarly, we can get the even number.
Minimum number of K: design an algorithm to find the minimum number of K in the array. You can return these K numbers in any order.

Example:

Input: arr = [1,3,5,7,2,4,6,8], k = 4
Output: [1,2,3,4]

#include<iostream>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
 vector<int> smallestK(vector<int>& input, int k) {
      vector<int> output;
      if(k>input.size()){return output;}
      std::priority_queue<int,vector<int>,less<int>> min_queue;
      int i;
      for(i=0;i<k;++i){
          min_queue.push(input[i]);
      }
      if(min_queue.empty())return output;

      for(i=k;i<input.size();++i){
          if(input[i]<min_queue.top()){
              min_queue.pop();
              min_queue.push(input[i]);
          }
      }
    while(!min_queue.empty()){
        output.push_back(min_queue.top());
        min_queue.pop();
    }
  return output;
  }

Given two sorted arrays A and B, the end of A has enough buffer space for B. Write A method to merge B into A and sort.

The number of elements initializing A and B are m and n, respectively.

Example:

Input:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

//Reverse double pointer
 void merge(vector<int>& A, int m, vector<int>& B, int n) {
    int pa = m - 1, pb = n - 1;
    int tail = m + n - 1;
    int cur;
    while (pa >= 0 || pb >= 0) {
        if (pa == -1)
            cur = B[pb--];
        else if (pb == -1)
            cur = A[pa--];
        else if (A[pa] > B[pb])
            cur = A[pa--];
        else
            cur = B[pb--];
        A[tail--] = cur;
    }
    
  
      }

Linked list

greedy

Recursion, backtracking, divide and conquer

Binary tree and graph

Binary search and binary sort tree

Hash table and string

search

dynamic programming