Polaris-hzn8

算法分类 常见算法 1.贪心 2.动态规划 3.数学知识 4.搜索与图论 5.数据结构 6.字符串 7.二叉树 8.排序算法 9.二分算法 10.双指针/滑动窗口 11.位运算 12.模拟 13.枚举 14.递推与递归 15.算法技巧：高精度、前缀和与差分、离散化、区间合并、方向数组 16.杂题 17.总结 经验之谈 1.数组/单链表系列算法 双指针 二分搜索 滑动窗口 回文串 前缀和与差分数组 先学习像数组、链表这种基本数据结构的常用算法，比如单链表翻转，前缀和数组，二分搜索等 因为这些算法属于会者不难难者不会的类型，难度不大，学习它们不会花费太多时间。而且这些小而美的算法经常让你大呼精妙，能够有效培养你对算法的兴趣。 单链表常考的技巧就是双指针，后文 单链表六大技巧 全给你总结好了，这些技巧就是会者不难，难者不会。 比如判断单链表是否成环，拍脑袋的暴力解是什么？就是用一个 HashSet 之类的数据结构来缓存走过的节点，遇到重复的就说明有环对吧。但我们用快慢指针可以避免使用额外的空间，这就是聪明地穷举嘛。 当然，对于找链表中点这种问题，使用双指针技巧只是显示你学过这个技巧，和遍历两次链表的常规解法从时间空间复杂度的角度来说都是差不多的。 首先说二分搜索技巧，可以归为两端向中心的双指针。如果让你在数组中搜索元素，一个 for 循环穷举肯定能搞定对吧，但如果数组是有序的，二分搜索不就是一种更聪明的搜索方式么。 后文 二分搜索框架详解 给你总结了二分搜索代码模板，保证不会出现搜索边界的问题。后文 二分搜索算法运用 给你总结了二分搜索相关题目的共性以及如何将二分搜索思想运用到实际算法中。 类似的两端向中心的双指针技巧还有力扣上的 N 数之和系列问题，后文 一个函数秒杀所有 nSum 问题 讲了这些题目的共性，甭管几数之和，解法肯定要穷举所有的数字组合，然后看看那个数字组合的和等于目标和嘛。比较聪明的方式是先排序，利用双指针技巧快速计算结果。 **再说 滑动窗口算法技巧**，典型的快慢双指针，快慢指针中间就是滑动的「窗口」，主要用于解决子串问题。 文中最小覆盖子串这道题，让你寻找包含特定字符的最短子串，常规拍脑袋解法是什么？那肯定是类似字符串暴力匹配算法，用嵌套 ...

反转链表 原题链接：https://leetcode.cn/problems/reverse-linked-list/ 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000 1.利用外部空间主要思路：利用外部空间+STL算法 先申请一个动态扩容的数组或者容器，然后不断遍历链表，将链表中的元素添加到这个容器中。 再利用容器自身的 API，反转整个容器，这样就达到反转的效果了。 最后同时遍历容器和链表，将链表中的值改为容器中的值。 12345678910111213141516class Solution {public: int divide(int dividend, int divisor) { int flag = 0; int count = 0; if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) flag = 1; dividend = abs(dividend); divisor = abs(divisor); while (dividend - divisor >= 0) { dividend -= divisor; count++; } if (flag) count = -count; return count; }}; 2.双指针迭代3.优化的双指针4.递归

Q&AGroup1 高并发服务器开发需要以下几个方面的知识： 操作系统和网络基础知识：了解操作系统的基本原理和网络协议的工作原理，对高并发服务器的开发有很大帮助。 多线程和锁机制：了解多线程编程和锁机制，能够编写高效的线程安全代码，同时防止多线程竞争问题的发生。 数据库和缓存：了解数据库和缓存的基本原理和应用场景，能够设计和优化高性能的数据库和缓存方案。 消息队列：了解消息队列的基本原理和应用场景，能够应对高并发场景下的流量峰值和突发请求。 高并发服务器框架：了解高并发服务器框架的设计和实现，例如Netty、Node.js等，能够使用这些框架开发高性能的服务器应用。 分布式系统和负载均衡：了解分布式系统和负载均衡的基本原理和实现方式，能够设计和实现高可用性的分布式系统。 学习高并发服务器开发，需要对以上的知识有深入的理解和掌握，并进行不断的实践和优化。可以通过阅读相关的书籍和论文、参加相关的课程和培训、参与开源项目等方式进行学习和实践。同时，可以积极参加相关技术社区和论坛，与行业内的专家和开发者进行交流和学习。 C++知识体系 基础语法：包括变量、数据类型、运算符、控制流程语句等。 面向对象编程：包括类、继承、多态、虚函数等概念和应用。 模板编程：包括函数模板、类模板、元编程等概念和应用。 标准库：包括STL容器、算法、迭代器、流、文件等的使用。 异常处理：包括异常的概念、处理方式、异常安全性等。 并发编程：包括多线程、互斥量、条件变量、原子操作等。 内存管理：包括动态内存分配、智能指针、内存泄漏、内存安全等。 性能优化：包括算法优化、编译器优化、代码结构优化、内存优化等。 操作系统相关：包括进程、线程、同步机制、IO模型等。 高级应用：包括网络编程、图形界面、游戏开发、嵌入式开发、数据科学等 C++基础知识 变量和数据类型 运算符 控制语句（if-else、for、while、switch） 函数 数组 指针 内存管理（动态分配内存、指针运算、内存泄漏和悬空指针） 引用 类型转换 文件操作 C++面向对象编程 封装 继承 多态 抽象类和纯虚函数 虚函数和虚表 模板类和模板函数 智能指针 STL（容器、迭代器、算法） C++高级特性 异常处理 RAII 普通函数和Lambda表达式 函数对象和函数指针 常量表达式和con ...

Q&AGroup2 一、C/C++相关1.语言基础 static、const 作用？ 引用与指针作用以及区别？ 如何避免野指针？ malloc、free 和 new、delete 区别？ extern 有什么作用？ 简述 strcpy、sprintf 与 memcpy 的区别？ c/c++ 中强制类型转换使用场景？ 什么时候生成默认构造函数？ 什么时候生产默认拷贝构造函数？ 什么是深拷贝？什么是浅拷贝？ 2.STL vector 底层实现原理？ vector 内存增长机制？ vector 的 reserve 和 resize 的区别？ vector 的元素类型为什么不能是引用？ list 的底层实现原理？ deque 的底层实现原理？ 什么时候使用 vector、list、以及 deque？ priority_queue 的底层实现原理？ multiset 的底层实现原理？红黑树原理？ unordered_map的底层实现原理？哈希表原理？ 迭代器底层实现原理？以及有哪些种类？ 迭代器失效？连续和非连续存储容器的失效？ STL 容器的线程安全性？ 3.面向对象 面对对象的三大特征？ 简述多态实现原理？ 怎么解决菱形继承？ function,lambda,bind之间的关系 c++ 类型推导用法 关键字override,final的作用 继承下的构造函数和析构函数执行顺序？ 虚函数表和虚函数表指针(vptr)的创建时机？ 虚析构函数的作用？ 智能指针种类以及使用场景？ c++ 11 用过哪些特性？ 动态库和静态库的区别？ 左值引用与右值引用的区别？右值引用意义? 二、数据结构与算法 用两个栈实现队列？ 包含 min 函数的栈？ 队列的最大值？ 用一个栈实现另一个栈的排序？ 如何仅用递归函数和栈操作逆序一个栈？ 链表中倒数第 k 个节点？ 链表中环的入口节点？ 反转链表？ 从尾到头打印链表？ 两个链表的第一个公共节点？ 第一个只出现一次的字符？ 最长不含重复字符的子字符串？ 字符串的排列？ 反转字符串？ 把数字翻译成字符串？ 重建二叉树？ 二叉树的下一个节点？ 树的子结构？ 二叉树的镜像？ 对称的二叉树？ 从上到下打印二叉树？ 序列化二叉树？ 二叉树的深度？ 二叉树第 k 大节点？ 树中两个节点的最低公共祖先？ 剪绳子？ 二进制中 1 ...

删除链表中所有值为x的元素 1.不带头结点（1）不带头结点递归删除 递归算法 删除不带头结点的单链表 L 中所有值为 x 的结点 12345678910111213141516171819202122232425262728#include "presetNoHead.h"//利用递归 删除指定元素void recursiveDelete(Node *&L, int x) { Node *p = L; if (L == NULL) return;//递归出口 if (L->data == x) { L = L->next;//L->next = L->next->next; free(p); recursiveDelete(L, x); } else { recursiveDelete(L->next, x);//L = L->next; }}int main() { int n; Node list; Node *L = &list; cout << "enter the length of this linklist : "; cin >> n; createLinkList(L, n); cout << "current linklist: " << endl; print(L); int x; cout << "enter the target : "; cin >> x; recursiveDelete(L, x); cout << "after the deletion : "; print(L); return 0;} （2）不带头结点非递归删除1234567891011121314151617181920212223242526272829303132333435363738394 ...

反向输出每个结点的值 L为不带头结点的单链表， 编写算法实现从尾到头 反向输出每个结点的值， 123456789101112131415161718192021#include "presetNoHead.h"void rPrint(Node *L) { if (L != NULL) { rPrint(L->next); cout << L->data << " "; } else { return; }}int main() { Node list; Node *L = &list; int n; cout << "enter the length of this linklist : "; cin >> n; createLinkList(L, n); cout << "current linklist: " << endl; print(L); cout << "Reverse order : "; rPrint(L); return 0;}

删除链表中的最小元素 L为带头结点的单链表 编写算法实现 删除一个最小值结点的高效算法 12345678910111213141516171819202122232425#include "presetHead.h"void minDelete(LinkList &L) { Node *p = L; Node *preMin = L;//指向最小值所存储的结点 的前一个结点 while (p->next != NULL) { if (p->next->data < preMin->next->data) { preMin = p; } p = p->next; } Node *q = preMin->next; preMin->next = q->next; free(q);}int main() { int n; cout << "enter the length of this linklist : "; cin >> n; LinkList L; createLinkList(L, n); cout << "current linklist: "; print(L); minDelete(L); cout << "after the deletion : "; print(L); return 0;}

链表原地翻转 带有头结点的单链表L 单链表就地逆置，要求辅助空间复杂度为O(1) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <iostream>using namespace std;typedef struct Node { int data; struct Node *next;} Node, *LinkList;//头插法建立链表（有头结点）void createLinkList(LinkList &L, int n) { L = new Node; L->next = NULL; for (int i = 0; i < n; ++i) { Node *p = (Node *)malloc(sizeof(Node)); cin >> p->data; p->next = NULL; p->next = L->next; L->next = p; }}//链表数据打印void print(LinkList L) { Node *p = L->next; while (p != NULL) { //cout << p->data << ":" << p->next << " "; cout << p->data << " "; p = p->next; } cout << endl;}//利用头插法实现链表逆置void reverse(LinkList &L) { if (L == NULL) return; Node *p ...

链表插入排序

顺序表删除最小元素 从顺序表中删除具有最小值的元素（假设唯一），并由函数返回被删除元素的值。 删除后空出的位置由最后一个元素填补， 若顺序表为空则显示错误信息并退出运行。 preset.h12345678910111213141516171819202122232425#ifndef _PRESET_H#define _PRESET_H#include <iostream>using namespace std;#define MAXLENGTH 50typedef struct { int elem[MAXLENGTH]; int length;} SqList;void print(SqList sql) { if (sql.length == 0) { cout << "null" << endl; return; } for (int i = 0; i < sql.length; ++i) { cout << sql.elem[i] << " "; } cout << endl;}#endif 参考代码123456789101112131415161718192021222324252627282930313233343536#include "preset.h"//删除最小的元素bool listDelete(SqList &sql, int &e) { if (sql.length == 0) return false; int index = 0; int min = sql.elem[0]; for (int i = 1; i < sql.length; ++i) { if (sql.elem[i] < min) { min = sql.elem[i]; index = i; } ...