算法哪些事儿---2

耐下心来1.vector和数组在大小指定上的区别2.O(1)时间复杂度可以获取容器内元素大小的容器(size)它们的本质都是在实现容器的时候维护了一个计算元素个数的计数器3.string在算法题中的常用函数①判断字符串是否为空s.empty();②字符串的尾插s.push_back();③字符串的尾删s.pop_back();④字符串的指定位置删除s.erase(str.begin()3);删除s的第四个元素,时间复杂度O(n)⑤字符串在指定位置插入元素s.insert(5,hello); 时间复杂度O(n)⑥字符串的拼接操作shello,等价于 s.append(hello);⑦字符串的截取substr(0,5);从0位置截取5个⑧字符串翻转reverse(s.begin(),s.end()),翻转整个数组4.string::npos是什么是string中的一个静态常量表示“未找到“或“直到字符串末尾”的特殊值一般用于是否找到的判断5.stack在算法中常用的函数①遇到表达式求和这类题我们通常使用的是栈来模拟这类题的解决方法是这个在leetcode字符串解码这道题中我们会使用两个栈来解决这个问题5. 队列算法题常用知识点队列和宽搜题往往是密不可分的因为队列在算法题中的多数情况是服务于宽搜题的宽搜就是BFS广度优先搜索。属于搜索类的算法而搜索类的算法说白了其实也就两种一种是宽搜一种是深搜常见的leetcode算法题中关于宽搜的题包括迷宫最短路径网格图上下左右 4 个方向走二叉树层序遍历一层一层打印树岛屿数量搜索连通块打开转盘锁、腐烂的橘子接下来我们先探讨一下宽搜这种算法在树中的应用首先我们要连接队列的基本函数① 队列在层序遍历中的应用class Solution { public: vectorvectorint levelOrder(Node* root) { vectorvectorint ret; //记录最终结果 queueNode* q; //层序遍历需要的队列 if(root nullptr) return ret; q.push(root); while(q.size()) { vectorint tmp; //存放本层的结点 int sz q.size(); //统计本层的结点个数 for(int i0;isz;i) { Node * t q.front(); q.pop(); tmp.push_back(t-val); for(Node * child :t-children) { if(child ! nullptr) { q.push(child); } } } ret.push_back(tmp); } return ret; } };有的队列的容器可以查找队头和队尾但是有的队列容器你只能查找对头查不到队尾这个题其实就是一个解决队列和树的关系的模板方法遇到这种题可以考虑用这个模板6.优先级队列堆算法堆的常用接口有如何在算法中创建大堆小堆面试常常会考手写堆所以我们需要自己会手撕堆的实现#include vector using namespace std; class MaxHeap { public: vectorint heap; //上浮 void up(int i) { while(i 0) { int fa (i - 1) / 2; if(heap[i] heap[fa]) { swap(heap[i], heap[fa]); i fa; } else { break; } } } //下沉 void down(int i) { int n heap.size(); while(true) { int left i * 2 1; int right i * 2 2; int maxIdx i; if(left n heap[left] heap[maxIdx]) maxIdx left; if(right n heap[right] heap[maxIdx]) maxIdx right; if(maxIdx i) break; swap(heap[i], heap[maxIdx]); i maxIdx; } } void push(int x) { heap.push_back(x); up(heap.size() - 1); } void pop() { swap(heap[0], heap.back()); heap.pop_back(); down(0); } int top() { return heap[0]; } bool empty() { return heap.empty(); } };在面试过程中我们遇到面试官问我们Topk问题面试官一般想要我们的解决方法有①堆②快排也就是快速选择算法这两个方法是时间复杂度都比价低关于用堆的方法解决第K大或者第K小的问题找第K大我们就建一个之后K个容量的小根堆从头到尾遍历这组数字遇到数字大于当前heap的top的值的时候我们删除heap的top然后把这个 数字插入heap这样做的目的是让heap中始终保存的是当前见到的K个最大的数字当走到数组结尾的时候在heap这个小根堆中保存的刚好是从最大数字到第K大的数值并且因为我们建的是小根堆所以堆顶元素的值就是我们要找的第K大同理当我们要找第K小这个问题我们建的是大根堆比如我们要找第3小我们每次要做的是让当前指针遍历到的值和堆顶元素的值比较如果比堆顶值小就删除堆顶的将这个元素push进堆中这样当遍历完之后我们就找到了整个数组中的3个最小值因为我们创建的是大根堆第3小肯定是最小的元素中的最大的呢个所以我们返回top即为第K小下面是我用heap实现的一道topK问题class Solution { public: int findKthLargest(vectorint nums, int k) { priority_queueint,vectorint,greaterint heap; for(auto x:nums) { heap.push(x); //堆在push之后会自动调整排序的 if(heap.size() k) { heap.pop(); //因为创建的是小根堆所以现在pop的一定是最小的元素 } } return heap.top(); } };值得注意的是我们创建的堆的比较方式是可以自己定义的下面这道算法题我们就是通过自己定义比较方式来进行比较的class Solution { typedef pairstring,int PSI; struct cmp { bool operator()(const PSIa,const PSIb) { if(a.second b.second) //频次相同字典序按照大根堆的方式排序 { return a.first b.first; } return a.second b.second; } }; public: vectorstring topKFrequent(vectorstring words, int k) { //1.统计单词出现的频次 unordered_mapstring,int hash; for(auto w:words) hash[w]; //2.创建堆 priority_queuePSI,vectorPSI,cmp heap; //3.topK的主逻辑 for(auto psi:hash) { heap.push(psi); if(heap.size()k) heap.pop(); } //4.提取结果,创建一个vector,默认大小是k,然后让堆顶元素依次倒着放进vector中 vectorstring ret(k); for(int ik-1;i0;i--) { ret[i] heap.top().first; heap.pop(); } return ret; } };7.关于算法题中的精度问题意思就是在我们做算法题的时候如果想要返回值是符合题目要求的精度的时候可以想办法利用这种精度提成的方式