【数据结构】B/B-树（目录树）
引言 关于B树的性质 一、B树的结构 二、B树的实现 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931 ...
【数据结构】字典树T树
引言：为什么需要字典树？ 实现类似搜索引擎的效果，当输入“西安”关键字时，下面出现的联想词（如下图） 一、字典树逻辑图 T字典树功能，只能插入结点、暂不能删除结点（删除过程比较复杂）、根据关键码进行查询二、数据结点的设计（1）逻辑图（2）详细类型1234567891011121314151617181920212223242526272829303132333435const int MaxChSize = 26; //最长关键码const int LinkSize = 27; //分支结点的指针个数//T树结点的类型typedef enum {ELEM = 1, BRCH = 2} NodeType; //1元素结点，2分支结点//关键码类型typedef struct { char ch[MaxChSize]; //关键字符 int CurSize; //当前的字符长度}KeyType;//元素类型(关键码 + 相关信息)typedef struct{ KeyType key; //关键码 void* InfoPtr; // ...
【设计模式】类关系
引言 耦合性：参考文章 下面就通过耦合性的由弱到强，依赖、关联、聚合、组合、继承（泛化）、实现。（总结：衣冠剧组呈现） 一、依赖Dependency例：A类是B类的成员函数的参数、返回值（局部变量） 123456789class A{};class B{public: void FunB(A& a){} A GetA() { return A(); }}; 二、关联Association例：A类是B类的一个成员属性 （1）弱关联 12345678910111213141516class A{};class B{private: A* pa;public: B(A* ptr):pa(ptr) {} //B析构函数不能delete pa，弱关联关系 ~B(){}};int main(){ A a; B b(&a); return 0;} （2）强关联 123456789101112131415 ...
【C++多线程】银行多人转账模拟
一、题目要求 使用C++的线程并发库，实现并模拟多人在线同时转账的过程，确保转账不能出现差错。 例如：Account A(“xiaoming”, 1000);Account B(“zhangqiang”, 2000);Account C(“zq”, 1500); B->A 200 A 1200 B 1800 B->C 500 B 1300 C 2000 C->A 300 A 1500 C 1700 二、代码实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108#if 1#include<iostream>#include<mutex>#includ ...
【C++多线程】生产者消费者模型
一、题目要求 生产者消费者模型：在多线程下生产0~100个数，生产者线程1生产20个数据后，消费者线程1进行消费输出。 二、解答使用到的技术：互斥锁、条件变量、多线程、双端队列 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#if 1#include<iostream>#include<deque>#include<mutex>#include<condition_variable>using namespace std;mutex mtx;std::condition_variable cv;class Queue{public: //生产数据: index是生产者编号，val是生产的结果 void PushData(int index, int val) { unique_lock<mutex> ...
【LC动态规划】542. 01 矩阵
一、题目描述 二、算法分析 三、代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455class Solution {public: vector<vector<int>> updateMatrix(vector<vector<int>>& mat) { int m = mat.size(); int n = mat[0].size(); vector<vector<int>> dp(m, vector<int>(n, INT_MAX - 100000)); for(int i = 0; i < m; ++i) { for(int j = 0; j < n; ++j) { ...
【LC动态规划】91. 解码方法
一、题目描述 二、算法分析 三、代码12345678910111213141516171819202122class Solution {public: int numDecodings(string s) { int n = s.size(); vector<int> dp(n + 1, 0); dp[0] = 1; for(int i = 1; i <= n; ++i) { //单字符解析：当前s[i - 1]字符 非零 if(s[i - 1] != '0') { dp[i] = dp[i - 1]; } //双字符解析：当前字符s[i - 1]+前一个字符s[i - 2] if(i > 1 && s[i - 2] != '0 ...
【LC动态规划】最小路径和
一、题目描述 二、分析过程 三、代码123456789101112131415161718192021class Solution {public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<vector<int>> dp(m, vector<int>(n, 0)); dp[0][0] = grid[0][0]; //初始化dp for(int i = 1; i < m; i++) dp[i][0] = grid[i][0] + dp[i - 1][0]; for(int j = 1; j < n; j++) dp[0][j] = grid[0][j] + dp[0][j - 1]; for(int i = 1; i & ...
【LC动态规划】不同路径II
一、题目描述 二、分析本题是62.不同路径的障碍版，整体思路大体一致。 但就算是做过62.不同路径，在做本题也会有感觉遇到障碍无从下手。 其实只要考虑到，遇到障碍dp[i][j]保持0就可以了。 也有一些小细节，例如：初始化的部分，很容易忽略了障碍之后应该都是0的情况。 三、代码123456789101112131415161718192021222324252627class Solution {public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size();//row if(m == 0) return 0; int n = obstacleGrid[0].size();//col vector<vector<int>> dp(m); for(auto& vc: dp) ...
【动态规划】判断子序列
题目描述 双指针解法12345678910111213141516171819class Solution {public: bool isSubsequence(string s, string t) { int m = s.size(); int n = t.size(); int i = 0, j = 0; while(i < m && j < n) { if(s[i] == t[j]) { ++i; } ++j; } if(m == i) return true; return false; }}; 时间复杂度：Max(O(m), O(n))空间复杂度：O(1) 动态规划 12345678910111213 ...
