队列问题解析

一.用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 MyQueue 类:

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空,返回 true ;否则,返回 false

说明:

  • 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。

image-20231029204207345

这个题的思路是,将一个栈当作输入栈,用于压入 push 传入的数据;另一个栈当作输出栈,用于pop 和 peek 操作。
每次pop 或 peek 时,若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈,这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue(){
        inStack = new LinkedList<>();
        outStack= new LinkedList<>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if (outStack.isEmpty()){
            while (inStack.iterator().hasNext()){
                outStack.push(inStack.pop());
            }
        }
        if (empty()){
            return -1;
        }
        return outStack.pop();

    }

    public int peek() {
        if (empty()) {
            return -1;
        }
        if (outStack.isEmpty()){
            while (inStack.iterator().hasNext()){
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }

    public boolean empty() {
        return outStack.isEmpty()&&inStack.isEmpty();
    }

二.队列实现栈

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。

  • int pop() 移除并返回栈顶元素。

  • int top() 返回栈顶元素。

  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false

注意:

  • 你只能使用队列的基本操作 —— 也就是 push to backpeek/pop from frontsizeis empty 这些操作。

  • 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

image-20231029213953522

简单的方法是每次把新加的元素放在另一个空队列,然后把原来的队列已有的元素一次加入到后面

class MyStack {

     Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {

        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        if (queue1.isEmpty()) {
            queue1.add(x);
            add(queue1, queue2);

        } else {
            queue2.add(x);
            add(queue2, queue1);
        }

    }

    public int pop() {
        if (queue1.isEmpty()) {
            return queue2.remove();
        } else if (queue2.isEmpty()) {
            return queue1.remove();
        }
        return -1;
    }

    public int top() {
        if (queue1.isEmpty()) {
           return queue2.peek();
        } else if (queue2.isEmpty()) {
          return   queue1.peek();
        }
        return -1;
    }

    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }

    void add(Queue<Integer> queueE, Queue<Integer> queueF) {
        while (queueF.iterator().hasNext()) {
            queueE.add(queueF.remove());
        }
}
}

优化版本:

1.利用两队列的元素互换实现一个队列始终用来储存

class MyStack {

      Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {

        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
       queue2.offer(x);
       while (queue1.iterator().hasNext()){
           queue2.add(queue1.remove());
       }
       Queue<Integer>tem = queue2;
       queue2 = queue1;
       queue1 = tem;


    }

    public int pop() {
     return queue1.remove();
    }

    public int top() {
        if (queue1.isEmpty()){
            return -1;
        }
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.isEmpty();
    }

   
}
}

一个队列的实现:

核心思想是将队列计数,将新增元素前面的元素全部放到后面,就能实现,但是 记得在push和pop,计数都要变化

class MyStack {
 Queue<Integer> queue1;
    int n ;
    

    public MyStack() {

        queue1 = new LinkedList<>();
       
    }

    public void push(int x) {
        queue1.add(x);
        for (int i = 0; i <n; i++) {
            queue1.add(queue1.remove());
        }
        n++;
    }

    public int pop() {
        n--;
     return queue1.remove();
    }

    public int top() {
        if (queue1.isEmpty()){
            return -1;
        }
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.isEmpty();
    }

   
}

三.两数之和

LeetCode1.给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

示例1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例2:
输入:nums = [3,2,4], target = 6
输出:[1,2]

暴力破解

class Solution {
    public int[] twoSum(int[] nums, int target) {
  int j=0;
        for (int i = 0; i < nums.length ; i++) {
            for ( j = i+1; j < nums.length ; j++) {
                if (nums[i]+nums[j]==target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[0];
    }
}

哈希表

对于不全部遍历的解法:可以计算出每一个值的对应数字,检查数组中是否存在,因此可以利用hash表中map的不可重复性,key存为num[i],values存index,每一次put前可以检查key是否存在,不存在则直接put

class Solution {
    public int[] twoSum(int[] nums, int target) {
 Map<Integer,Integer>map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int key = nums[i];
            if (map.containsKey(target-key)){
                return new int[]{map.get(target-key),i};
            }
            map.put(nums[i],i );
        }
        return new int[0];
}
}

四.三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != kj != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

**注意:**答案中不可以包含重复的三元组。

image-20231030225056395

再利用两数之和的思想去map中存取或查找(-1)*target - num[j],但是这样的问题是无法消除重复结果,例如如果输入[-1,0,1,2,-1,-4],返回的结果是[[-1,1,0],[-1,-1,2],[0,1,-1],[0,-1,1],[1,-1,0],[2,-1,-1]],如果我们再增加一个去重方法,将直接导致执行超时。

整体思路:首先想到特殊情况,当排序后,两个相邻的数,当循环迭代时,应该跳过去重

之后的思路就是将三个数消除成为两个,通过等式a+b+c=0知道,a+b =-c,因此利用双指针

左指针指向第一个first的下一个元素,右指针指向最后一个元素,每次当left与right相加,小于0,代表和在left与right区间之间,并且大于left+right,因此将left右移,让和变大,反之right左移

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
 int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        for (int first = 0; first < nums.length; first++) {
            //总体指针
            if (nums[first] > 0) {
                return lists;
            }
            //起始值与前一个相同时,去重
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            //c 对应最右
            int left = first + 1, right = n - 1;
            //通过等式可知,将first值进行取反得到b+c的值,也就是target
            int target = -nums[first];
            while (left < right) {
                int tem = nums[right] + nums[left]+nums[first];
                if (tem==0){
                    List list = new ArrayList<>();
                list.add(nums[first]);
                list.add(nums[left]);
                list.add(nums[right]);
                lists.add(list);
                    //左右指针遇见重复时候跳过,否则停止
                    while (left<right&&nums[left]==nums[left+1]) {
                        left++;
                    }
                    while (left<right&&nums[right]==nums[right-1]){
                        right--;
                    }
                    //去重后需要移动left与right指针
                    left++;
                    right--;
                }else if (tem<0){
                    left++;
                }else {
                    right--;
                }

            }


            }
            return lists;
    }
}