剑指offer 计划1(栈与队列)java

作者: 程序员khaos

1.1、题目1

剑指 Offer 09. 用两个栈实现队列 {剑指-offer-09-用两个栈实现队列}

1.2、解法

解法如题目所说。定义两个栈。这里假设第一个栈为a,第二个栈为b。

实现两个函数增加尾和删除头。

增加即直接push入第一个栈。

删除函数:通过判断a是否为空进行循环,将已经存入的a的栈顶pop存到b中,以此达到倒置的效果。

再将b的栈顶pop出来即可达到删除。

此时a栈为空,下次判断若b栈为空,则输出-1。

否则则继续通过b栈输出栈顶。

1.3、代码

class CQueue {
    Deque<Integer> a;
    Deque<Integer> b;
    public CQueue() {
        a = new LinkedList<Integer>();
        b = new LinkedList<Integer>();
    }

    public void appendTail(int value) {
        a.push(value);
    }

    public int deleteHead() {
        if(b.isEmpty()){
           while(!a.isEmpty()){
               b.push(a.pop());
           } 
        }
        if(b.isEmpty()){
            return -1;
            return (int)b.pop();
        }
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

2.1、题目2

剑指 Offer 30. 包含min函数的栈 {剑指-offer-30-包含min函数的栈}

2.2、解法

仍是通过两个栈的方式,第一个栈为d1,第二个栈为d2

d1的push、pop、top不受影响。

至于d2,push时需将d2栈顶元素与目前元素判断,若大于或者等于,则存进d2

pop时,若d2栈顶元素与d1 pop的元素相同,则共同pop

此时d2的栈顶为最小值。

2.3、代码

class MinStack {
    Deque<Integer> d1,d2;
    /** initialize your data structure here. */
    public MinStack() {
        d1 = new LinkedList<Integer>();
        d2 = new LinkedList<Integer>();
    }

    public void push(int x) {
        d1.push(x);
        if(d2.isEmpty()||d2.peek()>=x){
            d2.push(x);
        }
    }

    public void pop() {
        if(d1.pop().equals(d2.peek())){
            d2.pop();
        }

    }



    public int top() {
        return (int)d1.peek();
    }

    public int min() {
        return (int)d2.peek();
    }
}

/**
 * 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.min();
 */

原文创作:程序员khaos

原文链接:https://www.cnblogs.com/urmkhaos/p/15214699.html

更多推荐

更多
  • Spark编程指南文档-在Mesos上运行Spark Spark 可以运行在 Apache Mesos 管理的硬件集群上。使用 Mesos 部署 Spark 的优点包括:Spark 与其他的 frameworks(框架) 之间的 dynamic partitioning(动态分区),...
  • Spark编程指南文档-Spark 调优 由于大多数Spark计算都在内存中,所以集群中的任何资源(CPU、网络带宽或内存)都可能成为Spark程序的瓶颈。在内存使用时进行调优,有三个考虑因素:GC优化,当你的程序存储了大量的 RDD ...
  • Spark编程指南文档-快速入门 本教程提供了如何使用 Spark 的快速入门介绍。首先通过运行 Spark 交互式的 shell(在 Python 或 Scala 中)来介绍 API,然后展示如何使用 Java,Scala 和 Python 来编写应用程序。Spark ...
  • Spark编程指南文档-Spark 安全 Spark 当前支持使用 shared secret(共享密钥)来 authentication(认证)。可以通过配置 spark.authenticate 参数来开启认证。这个参数用来控制 Spark ...
  • Spark编程指南文档-Spark 官方文档中文版翻译进度 Apache Spark 2.2.0 官方文档中文版翻译进度,| 是否完成 | 完成百分比 | 任务名称 | Markdown | 工期 | 开始时间 | 结束时间 | 贡献者 | 备注
  • Spark编程指南文档-20 k 属性](spark-properties) 控制着大多数应用参数,并且可以通过使用一个 [SparkConf](api/scala/index.html#org.apache.spark.SparkConf) 对象来设置,或者通过
  • Spark编程指南文档-Monitoring and Instrumentation xt 都会启动一个 Web UI,默认端口为 4040,显示有关应用程序的有用信息。这包括: * 调度器阶段和任务的列表 * RDD 大小和内存使用的概要信息 * 环境信息 * 正在运行的执行器的信息 您可以通过在
  • Spark编程指南文档-结构化流式编程指南 Spark SQL引擎将负责增量地、连续地运行它,并在流数据不断到达时更新最终结果。你可以使用 `Scala`、`Java`、`Python`或`R`中的[Dataset/DataFrame API](sql-programming-g
  • Spark编程指南文档-Spark RDD(Resilient Distributed Datasets)论文 的概念。当前的很多框架对迭代式算法场景与交互性数据挖掘场景的处理性能非常差,这个是 RDDs 的提出的动机。如果能将数据保存在内存中,将会使的上面两种场景的性能提高一个数量级。为了能达到高效的容错,RDDs 提供了一种受限制的共享内存
  • Spark编程指南文档-Spark Standalone模式 Spark 除了运行在 Mesos 或者 YARN 上以外,Spark 还提供了一个简单的 standalone 部署模式。安装 Spark Standalone 集群,您只需要将编译好的版本部署在集群中的每个节点上。您可以启动一个 ...
  • 近期文章

    更多
    文章目录

      推荐作者

      更多