剑指offer(五,六),用两个栈实现队列,旋转数组的最小数字

题目描述

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

 一个栈就是把队列反过来,那再来一个栈push进第一个栈就“正”过来了。
第一个栈就是存下反过来的序列。
 每次push进一个数,要先判断stack2“正”序列是否为空,不为空要还原“反序列”,还要stack1 push进所有的stack2。
 每次pop一个数,把stack1全部push进来,就变成了“正序列”,return stack2的pop即可。
 但是想想,有个小优化,push的时候不用在stack1还原反序列,直接push进stack1,这样在pop的时候判断stack2是否为空,不为空,直接pop,这样把早先“入队列”的pop完,再push stack1的。加了一个判断,简化了第一个栈的操作。
 任何时候pop要判断是否还有元素。

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}
import java.util.Stack;

class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        while(!stack2.empty()){
            stack1.push(stack2.pop());
        }
        stack1.push(node);
    }

    public int pop() {
        if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        while(!stack1.empty()) {
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}

class Main {

}

然后又用我大JS做了一遍,我大JS,每个数组就是一个栈,233,直接push和pop方法。
注意js对pop() 时两个栈为空的处理。 js 是默认返回 undefined ,其他静态语言一般是报异常。

var stack1 = [],
    stack2 = [];
function push(node) {
    stack1.push(node);
}
function pop() {
    if (!stack2.length&&!stack2.length) {
        //处理
    }
    if (!stack2.length) {
        while (stack1.length) {
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop();
}

/*
// 测试
var arr = [];
arr.push(1)
arr.push(2)
arr.push(3)
console.log(arr);
console.log(arr.pop());*/

题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

 普通查找时间复杂度为n,出在这里肯定是要找优化的。明显是二分,二分的条件,边界和判断就是关键。
 序列保证是旋转过的,如果长度是2,直接返回右边的。我们现在就找这个边界值,未旋转的非递减序列左边肯定小于右边。现在我们就不断缩小这个边界存在的区间。
 中间元素大于第一个元素,则这个中间元素处于从left开始到中间元素只有一个的序列当中,此时最小元素位于中间元素的后面。
 中间元素小于第一个元素,则这个中间元素“非正常”,左面元素到这个元素之间包含了两个序列,最小的数肯定在中间元素前面。
 我这个二分,是留存mid的,所以最后肯定是分到只剩下两个数,且这两个数一定是旋转的,那么右边就是最小的数。
 eg:
 3 1 2,返回3 1,因为缩小的是“旋转的区间的长度”
 3 4 1,返回4 1,最终的都是右边最小,返回即可。
 另外的最坏情况就是有相同的元素,array[l] == array[r] && array[l] == array[mid],不能用条件来缩小查找区间,这时候的序列肯定只有两种数,只能顺序查找,找到第一个小的,直接break即可。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int len = array.length;
        if(len==0)
            return 0;
        int l = 0;
        int r = len-1;
        int mid = 0;
        while(r-l!=1) {
            mid = (l+r)/2;
            if(array[l] == array[r] && array[l] == array[mid]){
                return OtherSolve(array,l,r);
            }
            //当中间比第一个元素大时,最小数在右边,因为右边的最小序列整体都是小于左边的大序列
            if(array[mid]>=array[l])
                l = mid;
            //当中间比第一个元素小时,最小数在左边,最小序列的任何一个数整体都是小于左边的大序列
            else if(array[mid]<=array[l]) {
                r = mid;
            }
        }
        return array[r];
    }
     int OtherSolve(int array[],int l,int r){
        int t = array[l];
        for(int i = l+1; i<=r; i++) {
            if(array[i]<t)
                t = array[i];
        }
        return t;
    }
}
相关文章
相关标签/搜索