编程导航算法村 第五关 | 白银挑战

编程导航算法村 第五关 | 白银挑战

用栈实现队列

LeetCode 232题

class MyQueue {private Stack<Integer> stack; // 保存private Stack<Integer> tempstack; // 临沭队列public MyQueue() {stack = new Stack<>();tempstack = new Stack<>();}public void push(int x) {stack.push(x);}public int pop() {
//        如果栈是空，返回if (stack.isEmpty()) {return -1;}while (!stack.isEmpty()) {tempstack.push(stack.pop());}int pop = tempstack.pop();//while (!tempstack.isEmpty()){stack.push(tempstack.pop());}return pop;}public int peek() {//        如果栈是空，返回if (stack.isEmpty()) {return -1;}while (!stack.isEmpty()) {tempstack.push(stack.pop());}int peek = tempstack.peek();//while (!tempstack.isEmpty()) {stack.push(tempstack.pop());}return peek;}public boolean empty() {return stack.isEmpty();}}

用队列实现栈

• 实现的关键在于，inqueue是真实存储元素的队列，outqueue是辅助队列
• 当执行插入操作时，我们将新插入的元素要置于队列的队头，这样子我们才能直接进行删除与获取队头元素

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

三数之和

• 使用排序+双指针法
• 首先确定第一个数，然后使用双指针法，直到找到两数之和==nums[first]

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums); // 进行排序ArrayList<List<Integer>> resultList = new ArrayList<List<Integer>>();for (int i = 0; i < nums.length - 2; i++) {int one = nums[i];
//            避免重复值的发生if (i != 0) {if (nums[i] - nums[i - 1] == 0)continue;}
//            使用双指针法int left = i + 1;int right = nums.length - 1;int result = 0 - one;
//for (left=i+1;left<right;left++){if (left>i+1 && nums[left]==nums[left-1]){continue;}while (left < right && nums[left] + nums[right] > result) {right--;}if (left == right) {break;}if (nums[left] + nums[right] == result) {List<Integer> list = new ArrayList<Integer>();list.add(nums[left]);list.add(nums[right]);list.add(nums[i]);resultList.add(list);}}//}return resultList;}
}