[后台开发工程师总结系列] 10. 常用算法及参考实现

常考算法题

设计类问题

// 1. 带过期时间LRU

// 2. 设计一个Hashmap

基础数据结构及算法

// 1. 二叉树的三种非递归遍历 + 层次遍历

// 2. 单例模式

// 3. 并查集及最小生成树

// 4. 最短路（Dijikstra算法）

// 5. 拓扑排序

// 6. 先序和中序 构造二叉树

// 7. 字典树

// 8. 合并k个排序的链表、数组

// 9. 二叉树的最长路径（最大路径和）

// 10. LCA问题

// 11. 三个经典的进程同步模型
// 生产者消费者、读者写者问题、哲学家进餐问题

// 12. 二叉树中序的下一个节点

// 13. 两个排序数组中位数，TOP K

// 14. 快排

// 15. 链表排序

// 16. 堆排序

// 17. 几个C语言函数实现（strlen(), strcmp(), strcpy(), memset()）

// 18. 字符串全排列

// 设计类问题
// 1. 带过期时间LRU
class LRU{
public:
  int LRU(int num):cap(num){};
  int get(int key){
    if(kv[key]){
      touch(key);
      return kv[key];
    }else{
      return -1;
    }
  }
  void put(int key, int val){
    if(node.size()==cap&&!kt[key]){
      kv.erase(node.back());
      kt.erase(node.back());
      node.pop_back();
    }
    touch(key);
    kv[key] = val;
  }
private:
  int cap;
  list<int> node;
  unordered_map<int, int> kv;
  unordered_map<int, list<int>::iterator> kt;
  void touch(int key){
    if(kt[key]){
      node.erase(kt[key]);
    }
    node.push_front(key);
    kt[key] = node.begin();
  }
};

// 2. 设计一个Hashmap
struct ListNode{
  int key;
  int val;
  ListNode* next;
  ListNode(int k, int v):key(k),val(v){};
};
class HashMap{
public:
  HashMap(int num):cap(num){
    ListNode* head = new ListNode(0, 0);
    pt = vector<ListNode*>(num,head);
  }
  void put(int key, int val){
    int k = getIndex(hash(key));
    ListNode* root = vector[k];
    ListNode* node = searchList(root, key);
    if(node!=NULL){
      node->val = val;
    }else{
      ListNode* node = new ListNode(key, val);
      node->next = root->next;
      root->next = node;
    }
  }
  int get(int key){
    int k = getIndex(hash(key));
    ListNode* root = vector[k];
    ListNode* node = searchList(root, key);
    if(node!=NULL){
      return node->val;
    }else{
      return -1;
    }
  }
  ListNode* searchList(ListNode* root, int key){
    root = root->next;
    while(root){
      if(root->key==key) break;
      root=root->next;
    }
    return root;
  }
private:
  int cap;
  vector<ListNode*> pt;
  int hash(int key){
    return (key>>16)^key;
  }
  int getIndex(int key){
    return key%cap;
  }
};


// 基础数据结构
// 1. 二叉树的三种非递归遍历 + 层次遍历
void preorder(TreeNode* root){
  stack<TreeNode*> buf;
  while(root!=NULL&&!buf.empty()){
    buf.push(root);
    cout<<root->val<<endl;
    root=root->left;
    while(root==NULL&&!buf.empty()){
      TreeNode temp = buf.top();
      buf.pop();
      temp = temp->right;
    }
  }
}

void inorder(TreeNode* root){
  stack<TreeNode*> buf;
  while(root!=NULL&&!buf.empty()){
    if(root){
      buf.push(root);
      root=root->left;
    }else{
      TreeNode* temp = buf.top();
      buf.pop();
      cout<<temp->val<<endl;
      root = temp->right;
    }
  }
}

void postorder(TreeNode* root){
  stack<TreeNode*> buf;
  TreeNode* ref = NULL;
  if(root) buf.push(root);
  while(!buf.empty()){
    TreeNode* temp = buf.top();
    if((temp->left==NULL&&temp->right==NULL)||ref!=NULL&&(temp->left==ref||temp->right==ref)){
      cout<<temp->val<<endl;
      ref = temp;
      buf.pop();
    }else{
      if(temp->right) buf.push(temp->right);
      if(temp->left) buf.push(temp->left);
    }
  }
}

vector<vector<int>> levelorder(TreeNode* root){
  queue<TreeNode*> buf;
  vector<vector<int>> rs;
  vector<int> level;
  if(root) buf.push(buf);
  int curr = 1, next = 0;
  while(!buf.empty()){
    TreeNode* temp = buf.top();
    buf.pop();
    curr--;
    level.push_back(temp->val);
    if(temp->left) {buf.push(temp->left); next++;}
    if(temp->right) {buf.push(temp->right); next++;}
    if(curr==0){
      rs.push_back(level);
      level.clear();
      curr = next;
      next = 0;
    }
  }
}

// 2. 单例模式
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
class Singleton{
private:
  Singleton(){};
  static Singleton* sin;
public:
  static Singleton* getInstance(){
    if(sin==NULL){
      pthread_mutex_lock(&mutex);
      if(sin==NULL){
        sin = new Singleton();
      }
      pthread_mutex_unlock(&mutex);
    }
  }
}
Singleton::sin=NULL;
// 3. 并查集及最小生成树
class UF{
private:
  int cap;
  int count;
  vector<int> _size;
  vector<int> _id;
public:
  UF(int N):cap(N){
    count = N;
    _size = vector<int>(size(), 1);
    for(int i=0; i<N; i++){
      _id.push_back(i);
    }
  }
  int id(int k){
    while(_id[k]!=k) k = id[k];
  }
  void union(int left, int right){
    int l = _id[left];
    int r = _id[right];
    if(l==r) return ;
    count--;
    if(_size(l)<_size(r)){
      _id[l] = r;
      _size[r] += _size[l];
    }else{
      _id[r] = l;
      _size[l] += _size[r];
    }
  }
  int find(int left, int right){
    return id(left)==id(right);
  }
}

// 4. 最短路（Dijikstra算法）
#define max_len 2147483647
int Dijikstra(vector<vector<int>> _map, int start, int end){
  int N = _map.size();
  vector<int> distance(N, max_len);
  vector<int> visit(N);
  distance[start] = 0;
  visit[start] = 1;
  for(int count=1; count<N; i++){
    int len = max_len, k = -1;
    for(int i=0; i<N;  i++){
      if(visit[i]==0&&_map[start][i]<len){
        len = _map[start][i];
        k = i;
      }
    }
    visit[k] = 1;
    distance[k] = len;
    for(int i=0; i<N; i++){
      if(distance[start][k]+distance[k][i] < distance[start][i]){
        distance[start][i] = distance[start][k]+distance[k][i];
      }
    }
  }
  return distance[start][end];
}

// 5. 拓扑排序
bool dfs(vector<unordered_map<int>>& _map, vector<int>& markded, vector<int>& round, stack<int>& con, int i){
  if(marked[i]) return fasle;
  marked[i] = round[i] = 1;
  for(int num:_map[i]){
    if(round[i]||dfs(_map, marked, round, con, num)) return true;
  }
  con.push(i);
  round[i] = 0;
  return false;
}
vector<int> Topological(int numCourses, vector<pair<int, int>>& prerequirty){
  vector<unordered_map<int>> _map;
  vector<int> marked(numCourses);
  vector<int> round(numCourses);
  vector<int> res;
  stack<int> con;
  for(int i=0; i<prerequirty.size(); i++){
      _map[prerequirty[i].second].insert(prerequirty[i].first);
  }
  for(int i=0; i<numCourses; i++){
    if(!marked[i]&&dfs()) return res;
  }
  while(!con.empty()){
    res.push_back(con.top());
    con.pop();
  }
  return res;
}

// 6. 先序和中序 构造二叉树
TreeNoode* Tree(vector<int> preorder, vectr<int> inorder, int pivot, int left, int right){
  if(left<right){
    int key = preorder[pivot];
    int pos = find(inorder.begin(), inorder.end(), key);
    TreeNode* root = new TreeNode(key);
    root->left = Tree(preorder, inorder, pivot+1, left, pos-1);
    root->right = Tree(preorder, inorder, pivot+1+right-pos, pos+1, right);
  }
}
TreeNode* piTree(vector<int> preorder, vector<int> inorder){
  return Tree(preorder, inorder, 0, 0, inorder.size()-1);
}

// 7. 字典树
class Trie{
private:
  Trie* node[26];
  bool _end;
public:
  Trie():end(false){
    memset(node, 0, sizeof(node));
  }
  void insert(string s){
    Trie* cur = this;
    for(int i=0; i<s.size(); i++){
      int pos = s[i] - 'a';
      if(cur->node[pos]==NULL){
        Trie* temp = new Trie();
        cur->node[pos] = temp;
      }
      cur = cur->node[pos];
    }
    cur->_end = true;
  }
  bool find(string s){
    Trie* cur = this;
    for(int i=0; i<s.size(); i++){
      int pos =s[i]-'a';
      if(cur->node[pos]==NULL){
        return false;
      }else{
        cur = cur->node[pos];
      }
    }
    return _end;
  }
  bool startWith(string s){
    Trie* cur = this;
    for(int i=0; i<s.size(); i++){
      int pos =s[i]-'a';
      if(cur->node[pos]==NULL){
        return false;
      }else{
        cur = cur->node[pos];
      }
    }
    return true;
  }
}

struct cmp{
  bool operater <(Node* a, Node* b){
    a->val > b->val;
  }
}
// 8. 合并k个排序的链表、数组
Node* mergeKarr(vector<Node*> vec){
  priority_queue<Node*, vector<Node*>, cmp> pq;
  Node* root = new Node(0);
  Node* pt = root;
  for(int i=0; i<vec.size(); i++){
    if(vec[i]!=NULL) pq.push(vec[i]);
  }
  while(!pq.empty()){
    Node* temp = pq.top();
    pq.pop();
    pt->next = temp;
    pt=pt->next;
    if(temp->next!=NULL){
      pq.push(temp->next);
    }
  }
  return root->next;
}

// 9. 二叉树的最长路径（最大路径和）
int LongPath(TreeNode* root, int& sum){
  if(root==NULL) return -1;
  int left = LongPath(root->left, sum)+1;
  int right = LongPath(root->right, sum)+1;
  int sum = max(sum, left+right);
  return max(left, right)+1;
}

int maxlen(TreeNode* root){
  int len = 0;
  LongPaht(root, len);
  return len;
}

int LongSum(TreeNode* root, int& sum){
  if(root==NULL) return 0;
  int left = max(LongSum(root->left, sum),0);
  int right = max(LongSum(root->right, sum),0);
  int sum = max(sum, left + right+ root->val);
  return left>right?left+root->val:right+root->val;
}

// 10. LCA问题
TreeNode* LCA(TreeNode* root, TreeNode* left, TreeNode* right){
  if(root==NULL||root==left||root==right) return root;
  TreeNode* left = LCA(root->left, left, right);
  TreeNode* right = LCA(root->right, left, right);
  if(left!=NULL&&right!=NULL) return root;
  return left!=NULL?left:right;
}

// 11. 三个经典的进程同步模型
// 生产者消费者、读者写者问题、哲学家进餐问题
// P() V()
#define int sem_t;
sem_t mutex = 1;
sem_t full = 100;
sem_t empty = 0;
queue<Item> cache;

void producer(){
  while(1){
    P(&full);
    P(&mutex);
    Item it = new Item();
    cache.push(it);
    V(&mutex);
    V(&empty);
  }
}

void consumer(){
  while(1){
    P(&empty);
    P(&mutex);
    Item it = cache.top();
    it.pop();
    V(&mutex);
    V(&full);
  }
}

sem_t mutex = 1;
sem_t read = 1, write = 1;
int count = 0;

void reader(){
  P(&read);
  count++;
  if(count==1) P(&write);
  V(&read);
  _read();
  P(&read);
  count--;
  if(count==0) V(&write);
  V(&read);
}
void writer(){
  P(&write);
  _write();
  V(&write);
}

sem_t mutex = 1;
sem_t chop[] = {1,1,1,1,1};

void eat(){
  while(1){
      P(&mutex);
      P(chop[i%5]);
      P(chp[(i+1)%5]);
      V(&mutex);
      _eat();
      P(&mutex);
      P(chop[i%5]);
      P(chp[(i+1)%5]);
      V(&mutex);
  }
}

// 12. 二叉树中序的下一个节点
TreeNode* nextNode(TreeNode* root){
  if(root->right){
    while(root->left) root=root->left;
    return root;
  }
  while(root->parent){
    if(root==root->parent->left) return root->parent;
    else root=root->parent;
  }
  return NULL;
}

// 13. 两个排序数组中位数，TOP K
// 两个数组长度相同， 中位数问题
int midnum(vector<int> vec1, vector<int> vec2){
  int N = vec1.size();
  int s1 = 0, e1 = N-1, m1 = 0;
  int s2 = 0, e2 = N-1, m2 = 0;
  int offset = N%2==0?1:0;
  while(s1<s2){
    int m1 = (s1 + e1)/2;
    int m2 = (s2 + e2)/2;
    if(vec1[m1]==vec2[m2]){
      return vec1[m1];
    }else if(vec1[m1]<vec2[m2]){
      s1 = m1 + 1;
      e2 = m2;
    }else{
      e1 = m1;
      s2 = m2 + 1;
    }
  }
  return min(vec1[s1], vec2[s2]);
}

// 和为sum的序列
void dfs(vector<int>& vec, vector<vector<int>>& rs, vector<int>& temp, int k, int tar){
  if(tar==0){
    rs.push_back(temp);
    return ;
  }
  if(tar<0) return ;
  for(int i=k; i<vec.size(); i++){
    temp.push_back(vec[i]);
    dfs(vec, rs, temp, k+1, tar-vec[i]);
    temp.pop_back();
  }
}
vector<vector<int>> getSeq(vector<int> vec, int tar){
  vector<vector<int>> rs;
  vector<int> temp;
  sort(vec.begin(), vec.end());
  dfs(vec, rs, temp, 0, tar);
  reutrn rs;
}
// 基础算法
// 1. 快排
int findPivot(vector<int>& vec, int left, int right){
  int pivot = vec[left];
  while(left<right){
    while(left<right&&vec[right]>pivot) right--;
    vec[left] = vec[right];
    while(left<right&&vec[left]<pivot) left++;
    vec[right] = vec[left];
  }
  vec[left] = pivot;
}
void quicksort(vector<int>& vec, int left, int right){
  if(left<right){
    int pivot = findPivot(vec, left, right);
    quicksort(vec, left, pivot-1);
    quicksort(vec, pivot+1, right);
  }
}

// 2. 链表排序
ListNode* Listsort(ListNode* root){
  if(root==NULL) return NULL;
  if(root->next==NULL) return root;
  ListNode* p = root, *q = root, *pre = root;
  while(q!=NULL&&q->next!=NULL){
    pre = p;
    p = p->next;
    q = q->next->next;
  }
  pre->next = NULL;
  ListNode* left = Listsort(root);
  ListNode* right = Listsort(p);
  return merge(left, right);
}

ListNode* merge(ListNode* left, ListNode* rigth){
  // 略
}

// 3. 堆排序
void sink(vector<int> vec, int i, int N){
  int pivot = vec[i];
  while(2*i+1<N){
    int k = 2*i + 1;
    if(vec[k]<vec[k+1]){
      k++;
    }
    if(vec[i]>vec[k]){
      vec[i] = vec[k];
      i = k;
    }else{
      break;
    }
  }
  vec[i] = pivot;
}
void heapsort(vector<int> vec){
  int N = vec.size();
  for(int i= N/2; i>=0; i--){
    sink(vec, i, N);
  }
  swap(vec[0], vec[N-1]);
  for(int i=vec.size()-1; i>=0; i--){
    sink(vec, 0, i);
  }
}

// 4. 几个C语言函数实现（strlen(), strcmp(), strcpy(), memset()）
int strlen(char* s){
  assert(s!=NULL);
  int len = 0;
  while(*s++!='\0') len++;
  return len;
}
int cmp(char* s1, char* s2){
  assert(s1!=NULL&&s2!=NULL);
  int pt;
  while((pt=*(unsigned char *)s1++ - *(unsigned char*)s2+=)!=0);
  if(pt>0) return 1;
  else if(pt<0) return -1;
  else return pt;
}
void strcpy(char* s1, char* s2){
  assert(s1!=NULL&&s2!=NULL);
  char* ori = s1;
  while(*s1++ != '\0');
  while(*s2!='\0') s1++ = s2++;
  s1 = '\0';
  return ori;
}
void memset(void* a, int c, n){
  assert(a!=NULL);
  byte* pt = (byte*) a;
  while(n--) *pt++ = c;
}

// 5. 字符串全排列
void dfs(vector<string>& rs, string s, string& temp, vector<int>& visit){
  if(s.size()==temp.size()){
    rs.push_back(temp);
  }
  for(int i=0; i<s.size(); i++){
    if(visit[i]==0){
      visit[i]++ ;
      temp.push_back(s[i]);
      dfs(rs, s, temp, visit);
      temp.pop_back();
      visit[i]-- ;
    }
  }
}
vector<stirng> Permutation(string s){
  vector<string> rs;
  string temp;
  vector<int> visit(s.size());
  dfs(rs, s, temp, visit);
  return rs;
}

string nextpermutation(string s){
  int left = s.size()-1, right = s.size()-1;
  while(left>=1&&s[left]<=s[left-1]) left--;
  int pivot = s[left-1];
  while(right>=0&&s[right]<=pivot) right--;
  swap(s[left-1], s[right]);
  reverse(s.begin()+left,s.end());
  return s;
}

// 6. 出栈序列是否合法
bool valid(vector<int> vec1, vector<int> vec2){
  stack<int> cache;
  for(int i=0, j=0; i<vec1.size(); i++){
    cache.push(vec1[i]);
    while(!cache.empty()&&cache.top()==vec2[j]){
      cache.pop();
      j++;
    }
  }
  return vec1.empty();
}