1.两个栈实现队列
思路:两个栈,一个输入栈,一个输出栈。
当需要输入的时候就往inStack中插入,需要输出就往outStack中输出,当输出栈是空就倒出输入栈的数据到输出栈中,这样就保证了后插入的数据从栈顶倒入了栈底,输出栈栈顶弹出的一定是原先输入栈栈底的数据,也就是先进来的,即先进先出。
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.isEmpty()){outStack.push(inStack.pop());}return outStack.pop();}else{return outStack.pop();}}public int peek() {if(outStack.isEmpty()){while(!inStack.isEmpty()){outStack.push(inStack.pop());}return outStack.peek();}else{return outStack.peek();}}public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}
}
2.两个队列实现栈
思路:确保队列前端是后进数据,用两个队列实现后插入数据在前面效果
(从下方叠罗汉,每次插入,先放好一层,然后将原先所有数据抬起然后放到新的一层上面,这样达到后加入数据始终在前面)。
queue2必定为空,数据压入queue2,这样就确保队列前端是后进的数据
然后将queue1的数据灌入queue2,交换queue1和queue2,queue2仍然为空
需要弹出的时候就弹出queue1的数据就行,因为queue1始终保持后进数据在队列前端。
class MyStack {Deque<Integer> q1;Deque<Integer> q2;public MyStack() {q1 = new LinkedList<>();q2 = new LinkedList<>();}public void push(int x) {q2.offer(x);while(!q1.isEmpty()){q2.offer(q1.remove());}Deque<Integer> t = q1;q1 = q2;q2 = t;}public int pop() {return q1.remove();}public int top() {return q1.peek();}public boolean empty() {return q1.isEmpty();}
}
3.n数之和
两数之和
思路:
一、暴力两层循环 ,不可取
二、使用哈希表。每遍历过一个元素就记录下来,判断有没有包含target-nums[i]的值
class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for(int i = 0;i<nums.length;i++){int tar = target - nums[i];if(map.containsKey(tar)){return new int[]{i,map.get(tar)};}else{map.put(nums[i],i);}}return null;}
}
三数之和
思路:
一、双层循环+两数之和。
排序之后,先确定nums[i]为三数之一,然后从剩下的数中找到两数之和为-nums[i]的数,三数之和就是0.
class Solution {public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();if (nums == null || nums.length < 3) {return result;}Arrays.sort(nums);for (int i = 0; i < nums.length - 2; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue; // Skip duplicates}int target = -nums[i];Map<Integer, Integer> map = new HashMap<>();for (int j = i + 1; j < nums.length; j++) {int complement = target - nums[j];if (map.containsKey(complement)) {result.add(Arrays.asList(nums[i], complement, nums[j]));while (j + 1 < nums.length && nums[j] == nums[j + 1]) {j++; // Skip duplicates}}map.put(nums[j], j);}}return result;}
}
二、排序+双指针
先从小到大排序,两层循环
外层循环用来确定一个三数之一,然后内层循环双指针确定另外两数
之和大于目标right--
之和小于目标left++
之和等于目标加入答案,同时为了避免重复答案,需要跳过相同的数字
外层循环需要跳过相同的数字避免重复答案,同时必须是nums[i]==nums[i-1]
例如:[-1,-1,0,1,2]
[-1,0,1],[-1,-1,2]都是答案,不能跳过第一个-1
if(i>0&&nums[i] == nums[i-1]){continue;}
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();if (nums == null || nums.length < 3) {return result;}Arrays.sort(nums);int i,l,r;for(i=0;i<nums.length;i++){if(nums[i]>0) break;if(i>0&&nums[i]==nums[i-1]){continue;}int tar = -nums[i];for(l = i+1,r = nums.length -1;l<r;){if(nums[l]+nums[r]>tar){r--;}else if(nums[l]+nums[r]<tar){l++;}else{List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[l]);list.add(nums[r]);result.add(list);while (r > l && nums[r] == nums[r - 1]) r--;while (r > l && nums[l] == nums[l + 1]) l++;l++;r--;}}}return result;}
}