l*****a
发帖数: 14598 | 1 if so, how do u push_front and pop_front
Double ended queue
deque (usually pronounced like "deck") is an irregular acronym of double-
ended queue. Double-ended queues are a kind of sequence container. As such,
their elements are ordered following a strict linear sequence.
Deques may be implemented by specific libraries in different ways, but in
all cases they allow for the individual elements to be accessed through
random access iterators, with storage always handled automatically (
expanding an... 阅读全帖 |
|
b***y
发帖数: 2799 | 2 Interestingly, deque's iterators may be invalidated when insertions are made
only at the ends of the container, deque is the only standard STL container
whose iterators may be invalidated without also invalidating its pointers a
nd references.)
deque里不是直接用iterator吗？这pointer和reference是咋个概念？ |
|
d****n
发帖数: 1637 | 3 写deque的人比 写queue的人牛气。
但是写deque的人发现 好名字都被写queue的人用了。
于是写deque的人发愤图强 用实力鄙视了写queue的人。
~~你认为呢？ |
|
f*******n
发帖数: 12623 | 4 deque, vector, list, etc. are real containers
queue, stack, priority_queue are container *adaptors*. They are built on top
of some other container and only allow the operations needed by their name.
"queue" only allows insertion at one end and peek removal at the other. "
stack" only allows insertion, peeking, and removal at one end. If you need
any more operations, you should just use the underlying container. For queue
the underlying container is by default deque. |
|
|
a********m
发帖数: 15480 | 6 deque 很少用到index吧。 （刚看到题目里面要求了，刚才没注意）
如果要支持这个的话用vector好一点。 |
|
f*****y
发帖数: 444 | 7 deque 兼具数组和队列的优点，还可以从头和尾插入，是怎么实现的？看了一下源代码
，没看懂。请大侠指教，谢谢！ |
|
m*****r
发帖数: 130 | 8 pointer是那个指向单个element的，你两头插入后，这个poiner还是正确的，但是
iterator有可能不对了，因为end和begin变了。reference同理。
你可以想象这个deque是一个array实现的，头尾在插入后会变。
made
container
a |
|
m*****r
发帖数: 130 | 9 这个iterator也可以是pointer实现的。简单的deque实现就是一个array。如果用
pointer直接取地址就好了。
pointer来 |
|
j******n
发帖数: 271 | 10 来自主题: Programming版 - deque Can anyone tell if it is safe to manipulate std::deque simultaneously,
without any locking, from two threads if care is taken so that one thread
always add to one end and the other always remove from the other? |
|
z***9
发帖数: 696 | 11 来自主题: Programming版 - deque I guess deque is not thread-safe, unless specifically mentioned. |
|
j******n
发帖数: 271 | 12 来自主题: Programming版 - deque A naive implementation of deque seems to allow safely adding at one end by
one thread and removing from the other end simultaneously. I would know if
there is anything in the implementation in std that breaks that. |
|
c**********e
发帖数: 2007 | 13 为什么C++里面定义的 deque 有random accessor iterator, [], 而queue却什么也没
有？ |
|
|
j**7
发帖数: 143 | 15 // time O(N). space O(X)
public int solution(int[] A, int X, int D) {
LinkedList deque = new LinkedList();
int[] pos = new int[X + 1];
pos[0] = 0;
pos[X] = 0;
for (int i = 1; i < X; i++) {
pos[i] = -1;
}
for (int i = 0; i < A.length; i++) {
if (pos[A[i]] == -1) {
pos[A[i]] = i;
}
}
int[] DP = new int[X + 1];
DP[0] = 0;
deque.add(0);
... 阅读全帖 |
|
C****p
发帖数: 6 | 16 我的java代码，暴力两层dfs，672ms竟然过了。。。
第一层遍历所有数字组合，第二层遍历所有运算符组合，calculate的时候用了deque来
处理乘法优先的情况
不得不说这题有点变态，好像是G家的面试题？
public class Solution {
public List addOperators(String num, int target) {
List ans = new ArrayList();
if (num == null || num.length() == 0) {
return ans;
}
char[] digits = num.toCharArray();
List numbers = new ArrayList();
dfs(ans, target, numbers, digits, 0);
return ans;
}
... 阅读全帖 |
|
j**7
发帖数: 143 | 17 // time O(N). space O(X)
public int solution(int[] A, int X, int D) {
LinkedList deque = new LinkedList();
int[] pos = new int[X + 1];
pos[0] = 0;
pos[X] = 0;
for (int i = 1; i < X; i++) {
pos[i] = -1;
}
for (int i = 0; i < A.length; i++) {
if (pos[A[i]] == -1) {
pos[A[i]] = i;
}
}
int[] DP = new int[X + 1];
DP[0] = 0;
deque.add(0);
... 阅读全帖 |
|
l****1
发帖数: 19 | 18 上一个自己写的第三题的Java实现。请求大神门指教。。
顺便为明天G电面intern攒点人品。。
import java.util.*;
public class MaxWindow{
public LinkedList findMax(int[] in, int k){
ArrayDeque deque=new ArrayDeque();
LinkedList result=new LinkedList();
for(int i=0;i
if(!deque.isEmpty() && deque.getFirst().index<=i-k)
deque.pollFirst();
while(!deque.isE... 阅读全帖 |
|
l****1
发帖数: 19 | 19 上一个自己写的第三题的Java实现。请求大神门指教。。
顺便为明天G电面intern攒点人品。。
import java.util.*;
public class MaxWindow{
public LinkedList findMax(int[] in, int k){
ArrayDeque deque=new ArrayDeque();
LinkedList result=new LinkedList();
for(int i=0;i
if(!deque.isEmpty() && deque.getFirst().index<=i-k)
deque.pollFirst();
while(!deque.isE... 阅读全帖 |
|
z********i
发帖数: 568 | 20 The following algorithm for queue with max is correct to me:
http://www.sureinterview.com/wiki/Shwqst/903001
idea:
1 用数据队列保存所有数据X[0]，X[1]，...
2 用辅助队列保存数据中的X[i1],X[i2],etc. such that
2.1 X[i1]>=X[i2]>=...。
2.2 X[i1]是从X[i1]开始最大的数。
3 enque的时候,删除辅助队列中比要插入的数据小（<）的数据。
4 deque的时候，删除数据队列的第一个数据。同时，如果辅助队列的第一个数据等于数据队列的第一个数据，删除辅助队列的第一个数据。
5 max就是辅助队列的第一个数据
例子一。
数据队列：6 5 4。
辅助队列：6 5 4。
1) max: 辅助队列的第一个数据6.
2) deque：
数据队列：5 4。
辅助队列：5 4
max: 5
3) deque:
数据队列：4。
辅助队列：4
max: 4
例子二。
数据队列：4 5 6。
辅助队列：6。
1) max: 辅助... 阅读全帖 |
|
S******t
发帖数: 151 | 21 It is easy to come up with an $O(SL)$ algorithm for this problem but what is
good about this problem is that it actually has a linear time solution:
Let’s first make some notations clear:
1) |S| -> The length of S.
2) |L| -> The number of words in the list $L$.
3) $len_L$ -> The length of each string in $L$.
First we use an Aho-Corasick automaton to find out the occurrences of all
patterns. The time complexity of this step is $O(|S| + |L| * len_L + z)$
where $z$ is the number of output matches. ... 阅读全帖 |
|
r*c
发帖数: 167 | 22 贴个pattern字符串有重复字符的解法， 是dek,cpp1等大牛的解法的扩展。
#include
#include
#include
#include
using namespace std;
#define INT_MAX 2147483647
#define INT_MIN -2147483648
class MinWindowSolution
{
public:
struct TreeNode
{
TreeNode *parent;
int val;
vector children;
TreeNode(int i, TreeNode *p) : val(i), parent(p){}
};
void FindMinWindow_Tree(const vector& input , const vector&
query , int& nStart,... 阅读全帖 |
|
f*******t
发帖数: 7549 | 23 看了下，发现删一行就够了。pre是单调递增的，不会超过k
private long getNextMin(long[] map, long start, long k) {
while (map[(int)(start)] > 0)
start++;
return start;
}
public long findNth(long n, long k, long a, long b, long c, long r) {
long[] cache = new long[100010];
long[] map = new long[100010];
long pre = a;
for (int i = 0; i < k; i++) {
long num;
if (i == 0)
num = a;
else
... 阅读全帖 |
|
c*****e
发帖数: 74 | 24 /*
How can we generate all possibilities on braces ?
N value has given to us and we have to generate all possibilities.
**Examples:**
1) if N == 1, then only one possibility () .
2) if N==2, then possibilities are (()), ()()
3) if N==3, then possibilities are ((())), (())(),()()(), ()(()) ...
Note: left and right braces should match. I mean )( is INVALID for the N==1
How can we solve this problem by using recurrence approach ?
*/
#include
using namespace std;
void PrintStack(deque&... 阅读全帖 |
|
t****e
发帖数: 279 | 25 What is iterator invalidation?
Answer:
Insertion
Sequence containers
vector: all iterators and references before the point of insertion are
unaffected, unless the new container size is greater than the previous
capacity (in which case all iterators and references are invalidated) [23.2.
4.3/1]
deque: all iterators and references are invalidated, unless the inserted
member is at an end (front or back) of the deque (in which case all
iterators are invalidated, but references to elements are unaffe... 阅读全帖 |
|
s******g
发帖数: 139 | 26 用个 deque 就可以了, deque 的front() 是 sliding window中的最小的元素. 扫描数
组, 如果当前元素 大于front(), update res as res = max(res, x[i]-dq.front());
if front() is moving out of the L-sliding window, pop_front(), pop all the
elments in the deque starting from the back() that is no less than x[i],
then push x[i] in the deque.
(e.g. while(!dq.empty()) if(dq.back()>=x[i]) dq.pop_back(); dq.push_back(x[
i]);
Should be O(N) since each element gets in/out the deque only once |
|
c*****e
发帖数: 74 | 27 题目：一个board上，每个cell是一个字母，从一个cell出发，可以到它相邻的8个cell
。这样可以在board上walk。但是一个walk上一个cell不能出现2次。
要求：找出所有的可以由walk得到到的不同的单词。编程中可以自己假定一些已经实现
的方法。
以前面试被问到过，时间浪费在一些细节（怎么解决8个相邻cell的问题，怎么检查是
否一个cell重复出现）上了，当时也没有充分利用try，没答好，主要还是对递归、Try
的接口不熟。今天好好想了想该怎么写，下面是我的代码，花了不少时间，觉得收获不
少。好好写写这道题应该对面试很有帮助的。
有问题帮忙指出一下。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
class CTryNode;
class CTry
{
public:
CTryNode* Advance(CTryNode* pNode, char ch);
CTryNode* Back(CTryNode* pNode);
string GetValue(pTryNode* pNode);
bool IsCurr... 阅读全帖 |
|
s****j
发帖数: 67 | 28 来自主题: JobHunting版 - 问个算法题 你说的n是什么？10分钟？还是200条？
deque和这两个都没关系啊
deque记录的是时间
每次push_back的时候check deque的front的时间，和当前时间差大于等于10分钟全部
pop_front，如果此时deque的size大于等于200那就不能push啊,否则就push_back |
|
b*********s
发帖数: 115 | 29
You are right. deque is much better. Below is the implementation using deque
def solve2(s, k):
from collections import deque
d = deque(maxlen=k + 1)
n = len(s)
if n <= k:
return ''
for i in xrange(k + 1):
while d and ord(d[-1][1]) > ord(s[i]):
if s[i] == '0':
break
d.pop()
d.append((i, s[i]))
res = []
for i in xrange(k + 1, n):
res.append(d.popleft()[1])
while d and d[0][0] < i - k:
... 阅读全帖 |
|
m***y
发帖数: 14763 | 30 这主要是硬件原因。Qsort的内循环很容易在硬件上实现，软硬的速度之差就是天壤之
别了。
就事论事，这道题，老汉能找到的标准答案都是deque，不是说它明显比用别的数据结
构好很多，而是deque在很多平台上要不有专门硬件实现，你可以调asm或者native
function,要不有专门的优化过的库。
就stackoverflow的那个链结，下面有人讨论如何用banker's queue,就是用两个stack
来模拟deque。看起来绕圈子，但是在只提供stack的硬件上，这样还是比咱自己写的软
件deque快的多。 |
|
B*******t
发帖数: 135 | 31 你这两条都是deque的属性，如果用STL的话就是用deque。如果不用STL，那就是要你自
己实现一个deque。
具体的实现，取决于你想做多fancy，最简单的deque就是一个数组加两个指针（head & tail） |
|
I*****y
发帖数: 602 | 32 这道题确实有些trick在里面。昨晚想了很长时间，下面的代码应该没有问题：
#include
#include
using namespace std;
deque n2s(int n)
{
std::deque s;
int j = n % 26 ;
n /=26;
s.push_front('A' + j);
while(n)
{
j = n % 26 ;
s.push_front('A' + (j + 25) % 26); // 这里j=1->a,...,0->z
n = n / 26;
if(j==0) // 这里j=0时需要调整，不然输出序列为YZ,AZA,AZB,...,AZZ,
AAA...
n -= 1;
}
return s;
}
int main()
{
int a = numeric_limits::max();
for(i |
|
j*****y
发帖数: 1071 | 33 armortized 是 O(n) 吧？
两个 stack: s1, s2
s2 is empty.
enque: s1.push
deque: pop s1 to s2 until s1 is empty, s2.pop(). then push s2 back to s1
until s2 is empty
for the amortized time: T(n). firstly T(n) <= O(n)
But we can show T(n) >= \Omega(n)
enque n times, then enque(time cost is 1 ), deque(time cost is 3(n + 1)),
enque(time cose is 1), deque(time cost is 3(n + 1)),...., in this case, the
average time cose >= \Omega(n)
So the amortized cost is O(n) |
|
b*****n
发帖数: 618 | 34 来自主题: JobHunting版 - RF 面经 姑且称为RF吧
申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
online code test，onsite和一次电面。
好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
一样，
第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
细看，还有详细的提示也要注意。
我遇到的题：
1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
或者改变激光方向（4个方向）
问激光射出矩阵之前一共经过了多少格子，如果死循环了就输出－1
2. 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
和到达时间没有重复的）要求时间复杂度
code test过了之后我直接就安排onsite了，onsite本来安排6个人但实际上只面了5个
，题目如下：
1. 两个不一样长度的sorted array，求median。
leetcod... 阅读全帖 |
|
b*****n
发帖数: 618 | 35 来自主题: JobHunting版 - RF 面经 姑且称为RF吧
申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
online code test，onsite和一次电面。
好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
一样，
第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
细看，还有详细的提示也要注意。
我遇到的题：
1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
或者改变激光方向（4个方向）
问激光射出矩阵之前一共经过了多少格子，如果死循环了就输出－1
2. 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
和到达时间没有重复的）要求时间复杂度
code test过了之后我直接就安排onsite了，onsite本来安排6个人但实际上只面了5个
，题目如下：
1. 两个不一样长度的sorted array，求median。
leetcod... 阅读全帖 |
|
w****x
发帖数: 2483 | 36 来自主题: JobHunting版 - 周末上道题
其实我也不是很清楚，
是不是可以一开始当读入数据个数小于k时候是保持k个sorted number, 然后每读入一
个，
把array当作deque, k个以后每读入一个x， 如果x小于当前deque最大的（last），
removeLast, 然后一个个removeFirst直到first >= x，然后addFirst, 保持deque递增
？ |
|
s*w
发帖数: 729 | 37 要有人觉得有所帮助，给发个包子
【 以下文字转载自 Programming 讨论区 】
发信人: saw (句子熊), 信区: Programming
标 题: Re: 一道count frequency of all words的面试题 (转载)
发信站: BBS 未名空间站 (Mon Sep 23 00:28:12 2013, 美东)
又琢磨了两天，看了不少相关东西，终于搞定了，觉得自己对这个多线程的理解加强了
很多。思考比单纯的看人说原理更刻骨铭心。
这个问题我设计的用一个 producer 多个 consumer 的架构，上个版本的是两头用
condition_variable, 一个通知 producer 有空间了开始干活生产，另一个通知
consumer 有库存了开始消费。参见上篇里面的 wait 和 notify_all,notify_one 语
句。 这个思路对于单 producer 单 consumer 没问题，可是不适用于 多 consumer.
因为所有的 consumer 可能同时睡觉（没空存），同时醒来（有库存）,结果只有一个
能抢占mutex(拿到库存)，... 阅读全帖 |
|
i********s
发帖数: 22 | 38 需要两个数据结构。deque & 类似BST
deque，保存长度N的窗口信息，不断push_back & popfront
另外需要一个类BST的结构，可以获取最大，最小，中间值的数据结构，然后在deque中
保存指向BST节点的指针，随时删除对应节点数据。 |
|
f**********t
发帖数: 1001 | 39 // 一个deque，但是只支持pushBack，pushFront，popBack， 没有popFront
// 给一个1-N的排列，问能否把1-N按照从小到大的顺序push到deque，pop的时机可以
任选
// ，使得pop出的顺序刚好是给定的排列
// 比如： 给定 23145， 那么对12345对应的操作序列是pushBack，pushBack，
popBack，
// pushBack，popBack，popBack，pushBack，popBack，pushBack，popBack
// 要求如果可能，输出任意一个可能的操作序列，如果没有可能的操作序列，输出
// impossible
bool OpSequense(vector vi) {
deque dq;
size_t cur = 0;
vector indexes(vi.size() + 1);
for (size_t i = 0; i < vi.size(); ++i) {
indexes[vi[i]] = i;
}
for (int i =... 阅读全帖 |
|
c********t
发帖数: 5706 | 40 原谅我再执着问一次。synchronized 等待状态是block，不需要唤醒, 和wait是有区别
的。notify是唤醒wait状态的。到底会不
会有enque, deque同时wait的时候呢？如果没有，那notify只会wake对方的莫个thread
, 我写了一个最简单的，没用
notifyAll, 用的notify. 这个也是每次只唤醒一个线程。但如果有enque,
deque同时wait，这代码会有应该有deadlock，但是测试了很多次，上百线程，也没有
发生deadlock. 请大牛们帮看看下面代码有问题吗？
public class BlockingQueue3 {
private Deque queue;
private int limit = 10;
public BlockingQueue3(int pLimit) {
limit = pLimit;
queue = new ArrayDeque<>();
}
public synchronized void put(T ite... 阅读全帖 |
|
|
w******7
发帖数: 24 | 42 #include
#include
int main()
{
using namespace std;
deque que;
for(int i=0; i<10; ++i)
que.push_back(i);
deque::iterator iter = que.begin();
while(iter != que.end()) {
cout << *iter << endl;
++iter;
}
iter = que.begin();
while(iter != que.end())
{
cout << *iter << endl;
que.erase(iter);
}
return 0;
}
results:
0
1
2
3
4
5
6
7
8
9
0
0
1
2
3
4
5
6
7
8
9
Question: Why is there two "0" printed out when erasing? And if change
the c... 阅读全帖 |
|
M*******r
发帖数: 165 | 43 Sorry 这里是include的头文件，有一些全局定义在这里面，应该是比main早一步吧
#ifndef BarGame_H
#define BarGame_H
#pragma once
//#include
//#include
//#include
#include
#include
#include
#define MM 8 // size of memory
#define SS 6 // number of strategies per company
#define NN 101 // number of companies
#define PMM 4096 // pow(... 阅读全帖 |
|
s*w
发帖数: 729 | 44 又琢磨了两天，看了不少相关东西，终于搞定了，觉得自己对这个多线程的理解加强了
很多。思考比单纯的看人说原理更刻骨铭心。
这个问题我设计的用一个 producer 多个 consumer 的架构，上个版本的是两头用
condition_variable, 一个通知 producer 有空间了开始干活生产，另一个通知
consumer 有库存了开始消费。参见上篇里面的 wait 和 notify_all,notify_one 语
句。 这个思路对于单 producer 单 consumer 没问题，可是不适用于 多 consumer.
因为所有的 consumer 可能同时睡觉（没空存），同时醒来（有库存）,结果只有一个
能抢占mutex(拿到库存)，其他的只好继续睡觉（while 循环 wait）. 如果无限制的
生产下去，每个睡觉的都有机会醒来干活。可是在有限生产的情况下，producer 干完
活了后，总有睡觉的 consumer 无人唤醒导致死锁。解决的办法就是用 non-block
的 try_lock, lock 不上就返回 false，这样有机会检查是否需要(还在生产或是有
... 阅读全帖 |
|
d******3
发帖数: 70 | 45 找到正解了。emplace_back()既不copy也不move。但是vector要求里面的个体或者copy
constructible，或者move constructible。所以下面的代码是可以编译的，因为
deque没有这个要求：
class Person {
public:
Person(string name) { }
Person(const Person&) = delete;
};
int main() {
deque persons; // changed to deque
persons.emplace_back("George");
}
如果一定要用vector，也可以这样：
class Person {
public:
Person(string name) { }
Person(const Person&) = delete;
Person(Person&&) = default; // move constructor
};
int main() {
vector阅读全帖 |
|
b*********n
发帖数: 464 | 46 上周三面的，怎么现在都没有消息。是不是没有消息就是拒掉了？
感觉电面不难，就是当时问deque和list的区别的时候，我以为deque支持random
access,结果被追了两个问题。 |
|
K******g
发帖数: 1870 | 47 基本上是对的，但是有一点要做修改：
不需要区分i是在前一半还是后一半，每次都要把k放入队列，也不要把队列销毁。当i
是偶数的时候，每次deque出来一个后，和当前的i值比较，如果小于i，就扔掉，再
deque。
我用abcdefghi 012345678 测试了一下，好象是对的。
不过这种办法很不容易想到，不知道你是怎么想到的？ |
|
x******3
发帖数: 245 | 48 I used a DP method and get the same result with your sample outputs.
My approach is to assume the last Ctrl-C is at position j,
then everything after the last Ctrl-C should be Ctrl-V.
I also think the operation right before Ctrl-C should be Ctrl-A.
So j can be varied to pick the maximum.
python code here, it prints out the solution key sequence
#!/usr/bin/env python
... 阅读全帖 |
|
k***s
发帖数: 277 | 49 受到wiki上的启发， http://en.wikipedia.org/wiki/Integer_partition
wiki上是用smallest addedn is k, 我改成with m's largest addend k
// k is the maximum number of integer partition;
// m is the num of k of integer partition.
void ip_helper(int n, int k, int m, std::deque sequence) {
if (n < k*m)
return;
if (k < 1)
return;
int i, j, r = n-k*m;
for (i=0; i
sequence.push_back(k);
if (r == 0) {
for (i=0; i<(int)sequence.size(); ++i)
std::c... 阅读全帖 |
|
d**e
发帖数: 6098 | 50 不知写个non-recursive的DFS会不会好点,减少system stack call.
要用一个stack，但因为我想打印出路径，所以觉得用一个deque来保存各个点比较好点。
void FindAllPath(G, source, dest)
deque d;
d.push_back(source);
//这里还要一个数据结构visit表示点是否访问过，跟DFS那里一样。
while(!d.empty())
u = d.back();
for(each v in u's neighbor)
if( v == dest)
print path (that is from d's front to end)
else if v has been visited
continue;
else
d.push_back(v);
end if
u = d.back();
end for
... 阅读全帖 |
|
