张家港外贸网站制作,襄阳路桥建设集团有限公司网站,小鱼儿网站做啥用的,潜江做网站专题5-数据结构 2017-07-13 C Primer P329好好研读#xff0c;stack,queue,priority_queue都是顺序容器适配器adaptor。#xff08;接受一种已有的容器类型#xff0c;使其行为看起来像另一种事物一样#xff09; 适配器的底层容器#xff08;array和forward_list都不行 Primer P329好好研读stack,queue,priority_queue都是顺序容器适配器adaptor。接受一种已有的容器类型使其行为看起来像另一种事物一样 适配器的底层容器array和forward_list都不行stack默认基于deque实现除array和forward_list以外的容器都可以queue默认基于deque实现可以构造于list和deque之上但是不能基于vector进行构造priority_queue默认基于vector实现最大堆max-heap可以基于vetor和deque但是不能基于list需要随机访问能力1、基础知识 1.1、stack栈 栈操作s.pop()删除栈顶元素O(1)s.push()压入元素O(1)s.top()返回首元素但是不删除O(1)s.swap(stack)交换两个栈的内容 1.2、队列queue C primer P330 queue模板类的定义在queue头文件中。记住队列没有top()函数,使用front()总是记错。 与stack模板类很相似queue模板类也需要两个模板参数一个是元素类型一个容器类型元素类型是必要的容器类型是可选的默认为deque类型。 定义queue对象的示例代码如下 queueint q1; queuedouble q2; queue的基本操作有 q.push(x)入队将x接到队列的末端时间复杂度是O(1)q.pop()出队弹出队列的第一个元素注意并不会返回被弹出元素的值时间复杂度是O(1)q.front()访问队首元素即最早被压入队列的元素时间复杂度是O(1)q.back()访问队尾元素即最后被压入队列的元素时间复杂度是O(1)q.empty()判断队列空 q.size()访问队列中的元素个数 队列经常用于BFS之前总结过BFS要利用queue unordered_map实现还有就是二叉树的层次遍历。 1.3、priority_queue 主要操作是pop(),top(),push()。pop,push都是O(logk)top是O(1)的。 左边是队头右边是队尾默认是最大堆即返回的top是目前最大的元素默认是less,实现是x y因为有个建堆的过程所以不能以平常的大小来比较。 STL里面容器默认用的是 vector. 比较方式默认用 operator , 所以如果你把后面俩个参 缺省的话优先队列就是大顶堆队头元素最大。 priority_queue利用一个最大堆完成最大堆是一个以vector表现的完全二叉树所以缺省情况下它的底部容器是vector。queue以底部容器完成其所有的工作具有这种“修改某物接口形成另一种风貌”之性质者称为adapter适配器。 priority_queue 对于基本类型的使用方法相对简单。他的模板声明带有三个参数priority_queueType, Container, FunctionalType 为数据类型 Container 为保存数据的容器Functional 为元素比较方式。Container 必须是用数组实现的容器比如 vector, deque 但不能用 list。STL里面默认用的是 vector. 比较方式默认用 operator , 所以如果你把后面俩个参数缺省的话优先队列就是大顶堆队头元素最大。 如果要用到小顶堆则一般要把模板的三个参数都带进去。 使用方法 头文件 #include queue 声明方式 1、普通方法 priority_queueintq;//通过操作按照元素从大到小的顺序出队 2、自定义优先级 struct cmp
{ bool operator()(int x, int y) { return x y; }
}; //其中第二个参数为容器类型。第三个参数为比较函数。 结构体声明方式 struct node{ int x, y; friend bool operator (node a, node b) { return a.x b.x; //结构体中x小的优先级高 }};priority_queuenodeq;//定义方法//在该结构中y为值, x为优先级。//通过自定义operator操作符来比较元素中的优先级。//在重载””时最好不要重载””可能会发生编译错误 #include iostream
#include queue
using namespace std;
int main(){priority_queueint, vectorint, greaterint q; for( int i 0; i 10; i ) q.push( rand() );while( !q.empty() ){cout q.top() endl;q.pop();} getchar();return 0;
} **对于自定义类型则必须自己重载 operator 或者自己写仿函数** 1重载 operator自己联想一下每次弹出最小元素的queue形式{3,2,1}所以必须是返回a.x b.x;sort默认是小于排序从大到小排序所以重载的时候需要operator。只有自定义类类型才能重写操作符 bool operator( Node left, Node right ){if( left.x right.x ) return left.y right.y;return left.x right.x;
} 写仿函数注意有模板的时候才需要greaterint写这种形式是为了将模板里面的T变为int如果没用模板直接写greater。 struct greater{bool operator() (const int a, const int b) {return a b;}
};
//用的时候直接使用geater
templatetypename T
struct greater{bool operator() (const T a, const T b) {return a b;}
};//用的时候使用greaterint匹配模板 #include iostream
#include queueusing namespace std;struct Node{int x, y;Node( int a 0, int b 0 ):x(a), y(b) {}
};bool operator( Node a, Node b ){if( a.x b.x ) return a.y b.y;return a.x b.x;
}int main(){priority_queueNode q;for( int i 0; i 10; i )q.push( Node( rand(), rand() ) );while( !q.empty() ){cout q.top().x q.top().y endl;q.pop();}getchar();return 0;
} 重载operator形式代码示例 2自己写仿函数 自定义类型重载 operator 后声明对象时就可以只带一个模板参数。但此时不能像基本类型这样声明priority_queueNode, vectorNode, greaterNode ;原因是 greaterNode 没有定义如果想用这种方法定义则可以按如下方式 记住调用的时候格式为priority_queueNode, vectorNode, cmp q; struct cmp{bool operator() ( Node a, Node b ){if( a.x b.x ) {return a.y b.y;}return a.x b.x; }
}; #include iostream
#include queueusing namespace std;struct Node{int x, y;Node( int a 0, int b 0 ):x(a), y(b) {}
};struct cmp{bool operator() ( Node a, Node b ){if( a.x b.x ) return a.y b.y;return a.x b.x; }
};int main(){priority_queueNode, vectorNode, cmp q;for( int i 0; i 10; i )q.push( Node( rand(), rand() ) );while( !q.empty() ){cout q.top().x q.top().y endl;q.pop();}getchar();return 0;
} 自己写仿函数形式 不懂的话看下面的例子 #includeiostream
#includevector
#includestring
#include cstdio
#includequeue
#includealgorithm
using namespace std;
struct cmp {bool operator()(int a,int b) {return a b;}
};struct node {int x;int y;
};bool operator(node a, node b) {return a.x b.y;
}ostream operator(ostream os,const nodea) {os a.x a.y endl;return os;}
bool operator(node a, node b) {return a.x b.y;
}int main() {//priority_queueint q;priority_queuenode q;for (int i 0; i 5; i) {node a;cin a.x;cin a.y;q.push(a);}cout q.top() endl;system(pause);
} priority_queue仿函数例子重载 1.4、Hash哈希 参考链接1解决哈希表的冲突-开放地址法和链地址法 2哈希表的C实现一 链地址法实现一个很简单的hash表 3哈希函数。 基本概念 哈希表Hash Table也叫散列表是根据关键码值 (Key-Value) 而直接进行访问的数据结构。也就是说它通过把关键码值映射到表中一个位置来访问记录以加快查找的速度。哈希表的实现主要需要解决两个问题哈希函数和冲突解决。 哈希函数 哈希函数也叫散列函数它对不同的输出值得到一个固定长度的消息摘要。理想的哈希函数对于不同的输入应该产生不同的结构同时散列结果应当具有同一性输出值尽量均匀和雪崩效应微小的输入值变化使得输出值发生巨大的变化。 冲突解决 现实中的哈希函数不是完美的当两个不同的输入值对应一个输出值时就会产生“碰撞”这个时候便需要解决冲突。常见的冲突解决方法有开放定址法链地址法建立公共溢出区等。实际的哈希表实现中使用最多的是链地址法。 开放定址法 这个方法的基本思想是当发生地址冲突时按照某种方法继续探测哈希表中的其他存储单元直到找到空位置为止。这个过程可用下式描述 H i ( key ) ( H ( key ) d i ) mod m ( i 1,2,…… k ( k ≤ m – 1)) 其中 H ( key ) 为关键字 key 的直接哈希地址 m 为哈希表的长度 di 为每次再探测时的地址增量。 采用这种方法时首先计算出元素的直接哈希地址 H ( key ) 如果该存储单元已被其他元素占用则继续查看地址为 H ( key ) d 2 的存储单元如此重复直至找到某个存储单元为空时将关键字为 key 的数据元素存放到该单元。 增量 d 可以有不同的取法并根据其取法有不同的称呼 1 d i 1 2 3 …… 线性探测再散列 2 d i 1^2 1^2 2^2 2^2 k^2 -k^2…… 二次探测再散列 3 d i 伪随机序列 伪随机再散列 这种方法删除非常麻烦。 链地址法 链地址法解决冲突的做法是如果哈希表空间为 0 m - 1 设置一个由 m 个指针分量组成的一维数组 ST[ m ], 凡哈希地址为 i 的数据元素都插入到头指针为 ST[ i ] 的链表中。这种 方法有点近似于邻接表的基本思想且这种方法适合于冲突比较严重的情况。 实际中使用的比较多。 基本操作 hash基本操作插入时间复杂度O(1)删除时间复杂度O(1)查找时间复杂度O(1) 哈希函数 1.5 堆heap heap可以使用动态数组vector实现下标从1开始root就是vec[i]左儿子是2*i,右儿子是2*i1插入删除使用siftup,siftdown操作不断进行调整。删除将最下面的一个元素调整到root如果是最小堆就按照儿子大于父亲的调整策略进行调整插入就是插入到最后一个位置在按照上述策略进行调整。堆的最值放在vector中的第一个位置。 建立堆的时间复杂度是O(N)的 建堆算法是从最后一个非叶子结点开始下溯(即 Max-Heapify操作)也可以把建堆过程想成先对左子树建堆(T(n/2))再对右子树建堆(T(n/2))最后对根下溯(O(lg n))所以递推式是T(n) 2*T(n/2) O(lg n)它的解是 T(n) O(n) 链接https://www.zhihu.com/question/20729324/answer/132711265 函数说明 std::make_heap将[start, end)范围进行堆排序默认使用lessint, 即最大元素放在第一个。 std::pop_heap将front即第一个最大元素移动到end的前部同时将剩下的元素重新构造成(堆排序)一个新的heap并没有删除该元素。 std::push_heap对刚插入的尾部元素做堆排序。新加入的元素一定放在最下一层作为叶节点并填补在由左至右的第一个孔哥哥也就是插入到vector中的end前。 std::sort_heap将一个堆做排序,最终成为一个有序的系列可以看到sort_heap时必须先是一个堆两个特性1、最大元素在第一个 2、添加或者删除元素以对数时间因此必须先做一次make_heap. 其中使用仿函数来指定最大堆和最小堆less是最大堆greater是最小堆默认是最大堆。 2、leetcode题目实战 2.1 155. Min Stack https://leetcode.com/problems/min-stack/#/description 思路使用两个栈一个栈存正常数据另一个栈记录每个元素对应的最小值是多少这题细节压入MinStack的时候一定要使用if_elseminStack为空的时候要单独考虑top()操作是返回stack中的数据。 class MinStack {
public:/** initialize your data structure here. */stackint s;stackint minStack;MinStack() {}void push(int x) {s.push(x);if(minStack.empty()){minStack.push(x);}else{//总是忘记加上else只有非空的时候才能这样minStack.push(min(x,minStack.top()));}}void pop() {if(!s.empty()){s.pop();}if(!minStack.empty()){minStack.pop();} return;}int top() {//这里的top返回的是当前元素不是需要返回最小值 if(!s.empty()){return s.top();}return 0;}int getMin() {if(!minStack.empty()){return minStack.top();}return 0; }
};/*** Your MinStack object will be instantiated and called as such:* MinStack obj new MinStack();* obj.push(x);* obj.pop();* int param_3 obj.top();* int param_4 obj.getMin();*/ MinStack 2.2 232. Implement Queue using Stacks https://leetcode.com/problems/implement-queue-using-stacks/#/description 思路这题自己思路不清晰要理顺。使用两个栈oldStack和newStack其中newStack总是存储目前压入的元素在pop和front操作前如果oldStack中有元素就直接弹出oldStack的元素只有oldStack为空的时候才将newStack中的元素弹出压入到oldStack中。 class MyQueue {
public:/** Initialize your data structure here. */stackint newStack,oldStack;//newStack总是存储最新压入的元素MyQueue() {}/** Push element x to the back of queue. */void push(int x) {newStack.push(x);}/** Removes the element from in front of queue and returns that element. */int pop() {if(oldStack.empty()){while(!newStack.empty()){oldStack.push(newStack.top());newStack.pop();}} int tmp oldStack.top();oldStack.pop();return tmp;}/** Get the front element. */int peek() {if(oldStack.empty()){while(!newStack.empty()){oldStack.push(newStack.top());newStack.pop();}} return oldStack.top();}/** Returns whether the queue is empty. */bool empty() { return newStack.empty() oldStack.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj new MyQueue();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.peek();* bool param_4 obj.empty();*/ Implement Queue using Stacks 2.3 225. Implement Stack using Queues https://leetcode.com/problems/implement-stack-using-queues/#/description 思路这题有一个非常简单巧妙无敌的方法除了push操作其他操作都和queue正常操作一样使用一个队列就可以实现将新元素压入queue然后弹出一个front再压入到queue中这样就可以按照stack的顺序保存元素了。 4是需要压入的元素{1,2,3}是已经压入的元素然后将123弹出压入重新压入queue就形成了{1‘2‘3’4} class MyStack {
public:/** Initialize your data structure here. */queueint q;MyStack() {}/** Push element x onto stack. */void push(int x) {q.push(x);for(int i 0;i q.size() - 1;i){q.push(q.front());q.pop();} }/** Removes the element on top of the stack and returns that element. */int pop() {int tmp q.front();q.pop();return tmp;}/** Get the top element. */int top() { return q.front();}/** Returns whether the stack is empty. */bool empty() {return q.empty();}
};/*** Your MyStack object will be instantiated and called as such:* MyStack obj new MyStack();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.top();* bool param_4 obj.empty();*/ Implement Stack using Queues 2.4 84. Largest Rectangle in Histogram https://leetcode.com/problems/largest-rectangle-in-histogram/#/description 思路参照李二娃的文章这题思路很重要注意单调栈适合只要弹出元素就可以开始计算的情况。 1)heights.push_back(0);是为了后面将栈中所有元素弹出。记住变量一定要在定义的时候初始化不然后面比较的时候就会出错。stack里面存储的是索引值。 while循环里面的条件记住栈为空的时候直接将当前元素压栈当前元素大于栈顶元素的时候也是直接压栈所以就得到循环的退出条件 !s.empty() heights[i] heights[s.top()] 2另外一个细节需要注意的是弹栈过程中面积的计算。在求出高度后弹出一个元素保证栈顶元素是小于当前元素高度的这样求宽度的时候才能得到 int h heights[s.top()];
s.pop();//栈中存储的都是比目前索引小的元素
int w s.empty() ? i : (i - s.top() - 1); 第二步非常关键一定要理解再求宽度之前弹出一个元素。而且栈的首元素一定是最小的那个值最后栈为空的时候一定是目前长度乘上高度。而且访问栈之前一定啊哟判断它是否为空。 h[t] * (stack.isEmpty() ? i : i - stack.peek() - 1) h[t]是刚刚弹出的栈顶端元素。此时的面积计算是h[t]和前面的“上流社会”能围成的最大面积。这时候要注意哦栈内索引指向的元素都是比h[t]小的如果h[t]是目前最小的那么栈内就是空哦。而在目前栈顶元素和h[t]之间不包括h[t]和栈顶元素都是大于他们两者的。如下图所示 class Solution {
public:int largestRectangleArea(vectorint height) {if(height.size() 0){return 0;}int Max 0;stackint s;vectorint heights{height};heights.push_back(0);for(int i 0;i heights.size();i){ while(!s.empty() heights[i] heights[s.top()]){int h heights[s.top()];s.pop();//栈中存储的都是比目前索引小的元素int w s.empty() ? i : (i - s.top() - 1); Max max(Max,h * w);}s.push(i);}return Max;}
}; Largest Rectangle in Histogram 2.5 max tree(这题不是leetcode上的题目) 题目描述 Given an integer array with no duplicates. A max tree building on this array is defined as follow:
- The root is the maximum number in the array.
- The left subtree and right subtree are the max trees of the subarray divided by the root number.
- Construct the max tree by the given array.Example
Given [2, 5, 6, 0, 3, 1], the max tree constructed by this array is:6/ \5 3/ / \
2 0 1Challenge
O(n) time and memory. 思路使用一个栈下一个压栈元素比栈顶元素大的时候就将栈顶元素置为当前元素的左孩子如果当前节点小于栈顶元素那么就将当前节点置为栈顶元素的右孩子。 解题思路 如果是自顶向下按照 Max Tree 的定义构造那么时间复杂度至少是 O(nlogn) 。查找最大值的时间复杂度是 O(n) 如果最大值刚好可以将数组分为两部分那么复杂度递归关系如下 T(n) 2 * T(n / 2) O(n) 。最坏的情况是数组是降序/升序时间复杂度为 O(n^2) 。 考虑自底向上的方法。对一个数考察其父亲结点是谁它是左儿子还是右儿子。对于数 i寻找左边第一个比它大的数 x 和右边第一个比它大的数 y 如果 x y 那么 i 是 y 的左儿子否则是 i是 x 的右儿子。可以用反证法证明。 具体实现使用一个降序栈。 将数组按从左到右顺序迭代当处理一个新的结点 curt 时所有在栈中的结点全部都在其左边因此需要判断 curt 和栈中结点的关系 是 curt 的左儿子或者左父亲。当栈顶结点值大于当前结点值时将当前结点设为栈顶结点的右儿子进栈当栈顶结点值小于当前结点值时出栈将其设置为当前结点的左儿子。重复以上步骤并返回栈底元素即为最大数根结点。 struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x),left(NULL),right(NULL){}};
class solution{
public:TreeNode* maxTree(vectorint A){if(A.size() 0){return NULL;}stackTreeNode* s;for(int i 0;i A.size();i){TreeNode* curN new TreeNode(A[i]);while(!s.empty() curN - val s.top() - val){curN - left s.top();s.pop();}if(!s.empty()){stack.top() - right curN;}s.push(curN);}int len s.size();while(len 1){s.pop();--len;}return s.top();}}; MaxTree 2.6 rehashing重哈希 http://www.lintcode.com/zh-cn/problem/rehashing/ 思路思路其实很简单就是按照链表法每个原数组中的元素按照哈希函数进行计算压入到新的vector中如果有冲突就用一个链表组成单链表使用链表的插入操作即可。 注意每次取出来的元素可能是一个链表所以取出元素后需要循环遍历直到该元素为空为止。 主要是这题目的细节 1对比前面拷贝带有随机指针链表克隆图这两道题只要是这种有指针的必须要new一个原来的对象不然指针指向的还是原来的节点就不是复制得到一个新节点了 2刚开始的时候我没有新建一个变量使用的是result[idx]这样结果是错的记住数组中存的是每个单链表的表头result[idx]是一个指针如果不新建变量那么随着while操作就会指向最后一个元素为node前面一个元素。所以这里必须新建dummydummy是对原数组指针的拷贝原数组的指针仍然指向原区域。 3数组初始化为空可以直接全为NULL。 4新建new的时候直接赋整数值即可至于next的操作后面else会进行处理。 ListNode* dummy result[idx];
//这里必须要使用一个dummy因为数组中的元素必须是链表的索引while( dummy - next ! NULL){dummy dummy - next; }
dummy - next new ListNode(node - val); /*** Definition of ListNode* class ListNode {* public:* int val;* ListNode *next;* ListNode(int val) {* this-val val;* this-next NULL;* }* }*/
class Solution {
public:/*** param hashTable: A list of The first node of linked list* return: A list of The first node of linked list which have twice size*/ int hashcode(int key, int capacity) {if(key 0){return (key % capacity capacity ) % capacity;}return key % capacity;} vectorListNode* rehashing(vectorListNode* hashTable) {// write your code hereif(hashTable.size() 0){return {};}int size 2 * hashTable.size();vectorListNode* result(size,NULL);for(auto node : hashTable){if(node NULL){continue;}while(node ! NULL){int key node - val;int capacity size;int idx hashcode(key,capacity);// ListNode* dummy ;if(result[idx] NULL){result[idx] new ListNode(node - val);}else{ListNode* dummy result[idx];
//这里必须要使用一个dummy因为数组中的元素必须是链表的索引while( dummy - next ! NULL){dummy dummy - next; }dummy - next new ListNode(node - val);}node node - next;}}return result;}
}; rehashing 2.7 LRU Cache https://leetcode.com/problems/lru-cache/#/description 思路 1题目需要LRU的意思是最近使用的本题需要自己定义一个数据类型node,可以使用class也可以使用structclass里面记得加上public。定义构造函数。 class Node{
public:int key;int value;Node* prev;Node* next;Node(int k,int v):key(k),value(v),prev(nullptr),next(nullptr){}
}; class数据类型 struct Node{int key;int value;Node* prev;Node* next;Node(int k,int v):key(k),value(v),prev(nullptr),next(nullptr){}
}; struct数据类型 需要使用一个hash表以及一个自己实现的双链表node里面以及定义了prev指针和next指针。需要定义两个dummyNode分别为头尾节点因为头尾节点经常在改变就需要使用dummy Node。这两个节点不需要放在hash表里面。最近访问的节点都放在tail节点不常使用的节点就在head节点处因为两个函数都要用到所以定义一个moveToTail函数画图先prev然后next反转。 get函数的设计元素不在就返回-1元素在的话要将元素返回还需要将元素调整到前面最新访问的地方具体做法是首先将元素mremove然后再将该元素move到tail节点处。 put函数的设计 注意如果已经存在这个值比如已经有4,1那么再插入4,4key一样但是value不一样就需要对hash进行更新就行。 如果hash表以及达到了容量限制capacity的大小就需要先删除head - next的元素不仅仅是删除hash表中的元素还需要调整head删除head - next节点然后再执行hash表插入链表的调整。 class Node{
public:int key;int value;Node* prev;Node* next;Node(int k,int v):key(k),value(v),prev(nullptr),next(nullptr){}
};
class LRUCache {
public:LRUCache(int capacity) {//构造函数this - capacity capacity;dummyHead - next dummyTail;dummyTail - prev dummyHead; }void moveToTail(Node* cur){cur - prev dummyTail - prev;dummyTail - prev cur;cur - prev - next cur;cur - next dummyTail;}int get(int key) {if(hash.find(key) hash.end()){return -1;}Node* cur hash[key];//remove currentcur - prev - next cur - next;cur - next - prev cur - prev;//move to tailmoveToTail(cur);return cur - value;}void put(int key, int value) {//最近使用的放在tail//如果已经存在这个值比如已经有4,1那么再插入4,4key一样但是value不一样就需要对hash进行更新就行if (get(key) ! -1) {hash[key] - value value;return;}//if fullNode* insertNode new Node(key,value);if(hash.size() capacity){hash.erase(dummyHead - next - key);//remove dummyHead - next;Node* cur dummyHead - next;cur - next - prev cur - prev;cur - prev - next cur - next;// hash.insert(make_pair(key,insertNode));}//not fullhash.insert(make_pair(key,insertNode));moveToTail(insertNode);}
private:int capacity;Node* dummyHead new Node(-1,-1);Node* dummyTail new Node(-1,-1);unordered_mapint,Node* hash;};/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj new LRUCache(capacity);* int param_1 obj.get(key);* obj.put(key,value);*/ LRU Cache 2.8 128. Longest Consecutive Sequence最长连续序列 https://leetcode.com/problems/longest-consecutive-sequence/#/description 思路这道题是找到一个vector中最长连续序列的长度时间复杂度要求O(n)所以不能进行排序因为排序操作最快也需要O(nlogn)要使用哈希表使用unordered_set容器对于每个元素nums[i]每访问一次就马上删除接下来对于left nums[i] - 1,right nums[i] 1,执行两个循环看左边能达到哪个值每查找一个值就删除该元素并且left--同理右边执行相同操作 最后该元素的长度为right - left -1. 这个时候有个很巧妙的方法 res max(res,right - left - 1);
//这个思维很好免掉了还得找最大值的n次操作 不需要在用vector存储结果找最大值原来的思路太麻烦这种方法直接在运算过程中就确定了最大值。 关联容器总结 map可以执行下标操作如果key不存在就会自动插入该元素查找使用find(),count()这两个函数删除使用erase()插入使用insert();set不能使用下标操作查找使用find(),count()这两个函数删除使用erase()插入使用insert();使用下标操作如果不存在该元素则value默认为0。find操作不会在map里面增加值它找不到的情况下指向末尾enderase操作输入key就可以删除。 class Solution {
public:int longestConsecutive(vectorint nums) {if(nums.size() 0){return 0;}unordered_setint hashNums;for(int i : nums){hashNums.insert(i);}int res 0;for(int tmp : nums){hashNums.erase(tmp);int left tmp - 1;while(hashNums.count(left)){hashNums.erase(left);--left;}int right tmp 1;while(hashNums.count(right)){hashNums.erase(right);right;}res max(res,right - left - 1);//这个思维很好免掉了还得找最大值的n次操作}return res;}
}; Longest Consecutive Sequence 2.9 Subarray Sum(求出子数组和为0的数组对应的开始和结束下标) http://www.lintcode.com/en/problem/subarray-sum/ 思路最傻逼的方法是双循环我开始就想到了这一种方法然后看了看大神答案。。。。。。 简单的说就是使用一个unordered_mapsum,i出现两个一样的sum就表示中间区域就是和为0的区域i表示位置sum是求的和看下面例子; For example: SUM: 0 -3 -2 0 -3 1then we got the solution is : 0 - 2 开头使用一个虚拟点0-1因为开头第一个元素可能为0可能包含在结果中{1,2-3}。 之所以ans.push_back(hashMap.at(sum) 1)是因为第一个开始元素是虚拟的为-1. class Solution {
public:/*** param nums: A list of integers* return: A list of integers includes the index of the first number * and the index of the last number*/vectorint subarraySum(vectorint nums){// write your code hereint len nums.size();vectorint ans;unordered_mapint, int hashMap;hashMap.insert(make_pair(0, -1));int sum 0;for (int i 0; i len; i) {sum nums[i];if (hashMap.find(sum) ! hashMap.end()) {ans.push_back(hashMap.at(sum) 1);ans.push_back(i);return ans;}hashMap.insert(make_pair(sum, i));}return ans;}}; subarray sum 2.10 49. Group Anagrams https://leetcode.com/problems/group-anagrams/#/description 找到所有相同的“单词”单词字母相同但是顺序可以不同。 思路使用一个hash表的mapunordered_mapstring,vectorstring对于每个strs中的元素进行排序后存入map中只要排序后是一样的单词就压入vector中记住key是排序后的单词。 遍历关联容器使用迭代器方法it - first,it - second class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {vectorvectorstring result;if(strs.size() 0){return result;}unordered_mapstring,vectorstring hashMap;//排序后一样的单词就压入对应的vector中for(int i 0;i strs.size();i){string tmp strs[i];sort(tmp.begin(),tmp.end());if(hashMap.find(tmp) ! hashMap.end()){vectorstring vecStr;hashMap.insert({tmp,vecStr});}hashMap[tmp].push_back(strs[i]);}//遍历map将每个string对应的变换词压入result中for(auto index hashMap.begin();index ! hashMap.end();index){ result.push_back(index - second); }return result;}
}; Group Anagrams 2.11 295. Find Median from Data Stream https://leetcode.com/problems/find-median-from-data-stream/#/description 思路 思路可以看剑指offerP288 使用最大堆和最小堆实现左边是最大堆右边是最小堆要保证数据平均分配到两个堆中因此两个堆中的元素数目之差不能超过1.为了实现平均分配可以在数据的总数目是偶数时将新数据插入到最小堆中否则插入到最大堆中。 还要保证最大堆中的所有数据必须要小于最小堆中的数据有时会出现最小堆中的元素比最大堆中的元素要小这个时候应该采取以下措施可以先将这个元素插入到最大堆中接着把最大堆中的最大值拿出来插入到最小堆中。同理同样的方法处理最小堆中元素小于最大堆中的情况。 进行位运算是a1a有多少位1就前面就要补齐多少个0在进行位运算不要前面a-1位都和1位运算是和0位运算。结果只是和最后一位有关系。 1priority_queue 要保证最大堆中的元素数目大于等于最小堆中的元素数目。首先将元素压入到最大堆中然后取出最大元素压入到最小堆中因为最大堆中的元素数目会大于最小堆所以在奇数数目的时候result 最大堆的弹出值。 2heap 基于STL中的 函数push_heappop_heap以及vector来实现堆具体可以看STL源码剖析P174比较仿函数lessint, greaterint来实现最大堆和最小堆。偶数奇数的判断方法是number % 2,有double值得整数除法一定要记得除以2.0. class MedianFinder {
public:/** initialize your data structure here. */MedianFinder() {}void addNum(int num) {maxHeap.push(num);minHeap.push(maxHeap.top());maxHeap.pop();if(maxHeap.size() minHeap.size()){maxHeap.push(minHeap.top());minHeap.pop();}}double findMedian() {int size maxHeap.size() minHeap.size();double result 0;if(size 0){return result;}if(size % 2 0){result (maxHeap.top() minHeap.top()) / 2.0;}else{result maxHeap.top();}return result;}
private:priority_queueint maxHeap;priority_queueint,vectorint,greaterint minHeap;
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj new MedianFinder();* obj.addNum(num);* double param_2 obj.findMedian();*/ priority_queue data stream median class MedianFinder {
public:/** initialize your data structure here. */MedianFinder() {//minHeap,maxHeap;}void addNum(int num) {if( (maxHeap.size() minHeap.size() ) % 2 1){//insert to maxHeap//first insert to minHeap,then find the min number ,put it to maxHeapif(minHeap.size() 0 num minHeap[0]){minHeap.push_back(num);push_heap(minHeap.begin(),minHeap.end(),greaterint());num minHeap[0];pop_heap(minHeap.begin(),minHeap.end(),greaterint());minHeap.pop_back();}maxHeap.push_back(num);push_heap(maxHeap.begin(),maxHeap.end(),lessint());}else{//insert to minHeapif(maxHeap.size() 0 num maxHeap[0]){maxHeap.push_back(num);push_heap(maxHeap.begin(),maxHeap.end(),lessint());num maxHeap[0];pop_heap(maxHeap.begin(),maxHeap.end(),lessint());maxHeap.pop_back();}minHeap.push_back(num);push_heap(minHeap.begin(),minHeap.end(),greaterint());//cout minHeap[0]endl;}}double findMedian() {double result 0;int size minHeap.size() maxHeap.size();if(size 0){return result;}if( (minHeap.size() maxHeap.size() ) % 2 1){result minHeap[0];cout minHeap[0]endl;}else{result (minHeap[0] maxHeap[0]) / 2.0;}return result;}
private:vectorint minHeap;vectorint maxHeap;
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj new MedianFinder();* obj.addNum(num);* double param_2 obj.findMedian();*/ heap data stream median 2.12 79. Word Search https://leetcode.com/problems/word-search/#/description 思路:就是使用DFS的思想进行首先在board里面找到Word的第一个字母然后进行DFS进行上下左右四个方向的深搜只要有一个方向找到了结果就返回TRUE。深搜前做了什么深搜后一定要将状态改变回来。 时间复杂度分析搜索每个定点数量级为O(m*n)每个定点4条边那么就是O(m*n*4), 然后搜索长度为len(word),所以最后time complexity为O(m*n*4^len(word))。一次搜索的复杂度是O(EV)E是边的数量V是顶点数量在这个问题中他们都是O(m*n)量级的因为一个顶点有固定上下左右四条边。 参考http://blog.csdn.net/linhuanmars/article/details/24336987 class Solution {
public:bool findWord(vectorvectorchar board, string word,int row,int col,int index) {if(index word.size()){return true;}if(row 0 || row board.size() || col 0 || col board[0].size() || board[row][col] ! word[index]){return false;}board[row][col] 0;bool result findWord(board,word,row - 1,col,index 1) ||findWord(board,word,row 1,col,index 1) ||findWord(board,word,row,col - 1,index 1) ||findWord(board,word,row,col 1,index 1) ;board[row][col] word[index];return result;}bool exist(vectorvectorchar board, string word) {if(word.size() 0){return true;}if(board.empty() || board[0].empty()){return false;} for(int row 0;row board.size();row){for(int col 0;col board[row].size();col){ if(findWord(board,word,row,col,0)){ return true;} }}return false;}
}; Word search 转载于:https://www.cnblogs.com/dingxiaoqiang/p/7157445.html
