当前位置：首页 > news >正文

算法通关村第五关|白银|队栈和Hash的经典算法题【持续更新】

news 2025/7/9 4:08:46

1.用栈实现队列

用两个栈实现队列。

class MyQueue {Deque<Integer> inStack;Deque<Integer> outStack;public MyQueue() {inStack = new LinkedList<Integer>();outStack = new LinkedList<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.用队列实现栈

2.1 用两个队列实现栈。
queue2 作缓冲区， 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();}
}

2.2 用一个队列实现栈。
利用先进先出的特点，将队列中已有的内容放到新的元素后边。

class MyStack {Queue<Integer> queue;int count;public MyStack() {queue = new LinkedList<Integer>();count = 0;}public void push(int x) {queue.offer(x);for (int i = 0; i < count; i++) {queue.push(queue.poll());}count++;}public int pop() {count--;return queue.poll();}public int top() {return queue.peek();}public boolean empty() {return queue.isEmpty();}
}

3.n数之和专题

3.1 两数之和。

public int[] twoSum(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 三数之和。

class Solution {public List<List<Integer>> threeSum(int[] nums) {int n = nums.length;Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<List<Integer>>();for (int first = 0; first < n; first++) {if (first > 0 && nums[first] == nums[first - 1] {continue;}int third = n - 1;int target = -nums[first];for (int second = first + 1; second < n; second++) {if (second > first + 1 && nums[second] == nums[second - 1] {continue;}while (second < third && nums[second] + nums[third] > target) {third--;}if (second == third) {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]);ans.add(list);}}}return ans;}
}