相关疑难解决方法(0)

这是一个面试问题.您需要设计一个包含整数值的堆栈,以便getMinimum()函数返回堆栈中的最小元素.

例如:考虑下面的例子

case #1

5  --> TOP
1
4
6
2

When getMinimum() is called it should return 1, which is the minimum element 
in the stack. 

case #2

stack.pop()
stack.pop()

Note: Both 5 and 1 are poped out of the stack. So after this, the stack
looks like,

4  --> TOP
6
2

When getMinimum() is called is should return 2 which is the minimum in the 
stack.

制约性:

1. getMinimum应返回O(1)中的最小值
2. 在设计时也必须考虑空间约束,如果使用额外的空间,它应该是恒定的空间.

我遇到了这个问题: 实现一个队列,其中push_rear(),pop_front()和get_min()都是常量时间操作.

我最初想过使用一个最小堆数据结构,它对于get_min()具有O(1)复杂度.但是push_rear()和pop_front()将是O(log(n)).

有谁知道实现这样一个有O(1)push(),pop()和min()的队列的最佳方法是什么？

我搜索了这个,并想指出这个算法极客线程.但似乎没有一个解决方案遵循所有3种方法的恒定时间规则:push(),pop()和min().

感谢所有的建议.

有人能告诉我哪个数据结构支持O(1)中的插入/删除/最大操作？

我在接受采访时被问到以下问题:如果你有一个整数堆栈,你如何在不使用Collections.max的情况下找到堆栈的最大值,而不是迭代堆栈并比较元素.我用下面的代码回答它,因为我不知道使用任何Collections API或迭代Stack并使用比较的另一种方式.有任何想法吗？

import java.util.Collections;
import java.util.Stack;

public class StackDemo {
    public static void main(String[] args){
        Stack lifo = new Stack();
        lifo.push(new Integer(4));
        lifo.push(new Integer(1));
        lifo.push(new Integer(150));
        lifo.push(new Integer(40));
        lifo.push(new Integer(0));
        lifo.push(new Integer(60));
        lifo.push(new Integer(47));
        lifo.push(new Integer(104));

        if(!lifo.isEmpty()){
            Object max = Collections.max(lifo);
            System.out.println("max=" + max.toString());
        }
    }
}

在之前的这个问题中,OP要求一个类似于堆栈的数据结构,在每个O(1)时间内支持以下操作:

• 推送,在堆栈顶部添加一个新元素,
• Pop,从堆栈中删除顶部元素,
• Find-Max,返回(但不删除)堆栈的最大元素,和
• Find-Min,返回(但不删除)堆栈的最小元素.

几分钟前,我发现这个相关的问题要求澄清一个类似的数据结构,而不是允许查​​询最大值和最小值,允许查询堆栈的中值元素.这两个数据结构似乎是支持以下操作的更通用数据结构的特例:

• 推送,将元素推到堆栈顶部,
• 弹出,弹出堆栈的顶部,和
• Find-Kth,对于在创建结构时确定的固定k,返回堆栈的第k个最大元素.

通过存储堆栈和保存前k个元素的平衡二叉搜索树,可以支持所有这些操作,这将使所有这些操作在O(log k)时间内运行.我的问题是:是否有可能比这更快地实现上述数据结构？也就是说,我们可以为所有三个操作获得O(1)吗？或者也许O(1)用于推送和弹出,O(log k)用于订单统计查找？

可能重复:
为什么要使用两个堆栈来建立队列？

我得到了这个赋值问题,要求我使用两个堆栈实现一个队列.我的问题不是如何做到,而是为什么这样做？我不是来自计算机背景,我试图找到答案,但无法真正找到原因吗？我认为你的专家可以帮助我理解实现这样一个东西有什么好处.我发现了一篇相关文章为什么要使用两个堆栈来建立队列？谈论这个,但想知道是否还有更多.

如何在0(1)时间复杂度的任何时间从队列中检索max和min元素？之前我使用Collections.max和min来查找元素,但这将是0(n).

我知道最长的路径问题对于一般图表来说是NP难的.但是,我正在考虑一种特殊的图形,包括一个周期,加上周期的每个顶点上的一个附加边缘事件.例如,对于长度为7的循环,我们有图表:

所有边都是加权的(权重是实数,可以是正数或负数).我想在此图上找到最大的简单路径,其中路径的大小是路径上边缘权重的总和.

该算法应该是循环大小的线性.但任何想法都值得赞赏.

面试问题:设计具有以下功能的数据结构

• 推送数据
• 弹出最后插入的数据[LIFO]
• 给予最低限度

所有上述操作都应该具有复杂性 O(1)