第 5 关 | 算法的备胎 hash 和找靠山的队列:2.白银挑战——队栈和 Hash 的经典算法-灵析社区

1. 用栈实现队列

栈的特点是后进先出，队列的特点是先进先出。两个栈将底部拼接到一起就能实现队列的效果了,通过队列也能实现栈的功能，通过队列也能实现栈的功能，在很多的地方能让你通过两个栈实现队列，很多地方也有两个队列实现栈的题目，所以干脆一次看一下如何做。这个正好对应 leetcode232 和 225 两道题上。

232.用栈实现队列

2. 用队列实现栈

225.用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
  MyStack myStack = new MyStack();
  myStack.push(1);
  myStack.push(2);
  myStack.top(); // 返回 2
  myStack.pop(); // 返回 2
  myStack.empty(); // 返回 False

分析：这个问题首先想到的是使用两个队列来实现。为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈的时候，应该满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈dev操作，其中 pre 用于存储栈内的元素，after 作为入栈操作的辅助队列。

入栈的时候，首先将元素入队到 after，然后将 pre 的全部元素依次出队并且入队到 after，此时 after 的前端元素即为新入栈的元素，再将 pre 和 after互换，则 pre 的元素为栈内元素，pre 的前端和后端分别对应栈顶和栈底。

由于每次入栈操作都确保 pre 的前端元素为栈顶元素，因此出栈操作和获取栈顶元素都可以简单实现。出栈操作只需要移除 pre 的前端元素并返回就可以了，获取栈顶元素操作只需要获得 pre 的前端元素并且返回就可以了（不移除元素）。

由于 pre 用于存储栈内的元素，判断栈是否为空的时候，只需要判断 pre 是否为空就可以了。

class MyStack {
    Queue<Integer> pre;
    Queue<Integer> after;

    public MyStack() {
        pre = new LinkedList<Integer>();
        after = new LinkedList<Integer>(); 
    }

    public void push(int x) {
        after.offer(x);
        while(!pre.isEmpty()){
            after.offer(pre.poll());
        }
        Queue<Integer> temp = pre;
        pre = after;
        after = temp;
    }

    public int pop()  {
        return pre.poll();
    }

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

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

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

3. n 数之和专题

3.1. 两数之和

1.两数之和

给定一个整数数组 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] 
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]

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

}

3.2. 三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 
示例 2：
输入：nums = [] 输出：[] 
示例 3：
输入：nums = [0] 输出：[]

本题看似就是增加两个数，但是难度增加了很多，我们可以使用三层循环来找，时间复杂度是 O（n ^ 3）,太高了，放弃。也可以使用双层循环加上 Hash 的方法来实现，首先按照第一题两数之和的思路，我们可以固定一个数 target，再利用好两数之和的思想去 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]】,如果我们再增加一个去重方法，将会执行超时。

那这时候，我们就要想其他方法，这个公认最好的方式就是“排序 + 双指针”。我们可以像先将输入排序来处理重复结果，然后还是固定一个元素，由于数组是排好序的，所以我们用双指针来不断寻找求解就可以了，代码如下：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        // 枚举 a
        for(int first = 0;first < n; first++){
            // 需要和上次的枚举数不一样
            if(first > 0 && nums[first] == nums[first - 1]){
                continue;
            }
            // c 对应的指针指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for(int second = first + 1;second < n;second++){
                // 需要和上一次枚举的数字不一样
                if(second > first + 1 && nums[second] == nums[second - 1]){
                    continue;
                }
                //需要保证 b 的指针在 c 指针的左侧
                while(second < third && nums[second] + nums[third] > target){
                    third--;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会满足 a + b + c = 0 并且 b < c 的 c了，可以退出循环
                if(third == second){
                    break;
                }
                if(nums[second] + nums[third] == target){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    result.add(list);
                }
            }
        }
        return result;
    }
}

如果我们继续拓展，在前面的基础上再增加一个数呢？这就是 LeetCode 18 ，给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 满足

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

，这个题最直接的想法就是在上一题的基础上再套一层 for 循环来解决，思路虽然简单，但是实现过程非常复杂，感兴趣的同学可以研究一下。

如果我们再拓展一下，如果四个数字不是在一个数组里，而是分别在四个数组里面，如何从每个数组中分别获得一个元素，使得 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0，此时应该怎么做？这个是 leetcode 454 题，感兴趣的可以去看一下。

阅读量：151

点赞量：0

收藏量:0