快速学习队栈和Hash——第五关白银挑战

内容	1.如何用栈实现队列
	2.如何用队列实现栈
	3.三数之和如何做？

1.用栈实现队列

栈的特点是后进先出，队的特点是先进先出。

两个栈将底部拼到一起就实现队列的效果，荣国队列也能实现栈的功能。

在很多地方能看到让你通过两个栈实现队列的题目，也有很多地方是两个队列实现栈的题目。

例如LeetCode232题目链接

这个题目的思路就是，将一个栈当作输入栈，用于压入push传入的数据；另一个栈当作输出栈，用于pop和peek操作。

每次pop或peek时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

?

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

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

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

    public int pop() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.peek();
    }

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

    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

2.用队列实现栈LeetCode225题目链接

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

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

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

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

 class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}

3.n数之和专题

还记得LeetCode的第一题就是求两数之和的问题，事实上除此之外，还有几个类似的问题，例如LeetCode15三数之和，LeetCode18四数相加和LeetCode454四数相加II等等。

3.1两数之和

LeetCode1链接

?本道题可以使用两层循环解决，第一层确定一个数，2，7，一直到11.然后内层循环继续遍历后续元素。判断是否存在target-x的数即可，代码如下：

?方法一

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

这种方式不足在于寻找target-x的时间复杂度过高，我们可以使用哈希表，可以将寻找target-x的时间复杂度降低从O(N)降到O(1)。这样我们就创建了一个哈希表，读于每一个x，我们首先查询哈希表是否存在target-x，然后将x插入到哈希表中，即可保证不会让x和自己匹配。

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

3.2三数之和

如果将两个数换成三个数会怎么样？

LeetCode15链接

?我们可以使用三层循环直接找，时间复杂度为O(n^3)，太高了，放弃。

也可以使用双层循环+Hash来实现，再利用两数之和的思想去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) {
        Arrays.sort(nums); // 对数组进行排序，为了方便后面的去重
        List<List<Integer>> res = new ArrayList<>(); // 存储结果的列表
        for(int k = 0; k < nums.length - 2; k++){ // 循环，k表示当前固定的数的下标
            if(nums[k] > 0) break; // 如果当前固定的数已经大于0了，那么后面的数加上它也不可能等于0了，直接退出循环
            if(k > 0 && nums[k] == nums[k - 1]) continue; // 如果当前固定的数和前面一个数相同，那么这种情况已经处理过了，直接跳过
            int i = k + 1, j = nums.length - 1; // 双指针，i指向当前固定数的下一个数，j指向最后一个数
            while(i < j){ // 只要i<j就一直循环
                int sum = nums[k] + nums[i] + nums[j]; // 计算三个数的和
                if(sum < 0){ // 如果和小于0，那么说明i需要往右移动，才能让和变大
                    while(i < j && nums[i] == nums[++i]); // 跳过重复的数
                } else if (sum > 0) { // 如果和大于0，那么说明j需要往左移动，才能让和变小
                    while(i < j && nums[j] == nums[--j]); // 跳过重复的数
                } else { // 如果和等于0，那么就找到了一组解
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j]))); // 把这组解加入结果列表
                    while(i < j && nums[i] == nums[++i]); // 跳过重复的数
                    while(i < j && nums[j] == nums[--j]); // 跳过重复的数
                }
            }
        }
        return res; // 返回结果列表
    }
}

坚持每天学习算法，真的是一件很困难的事情，虽然我认为每天保持高效学习就是一个比较不容易的事情，但是加油吧，总会可以的！！！！