网站制作网站,旅游最新资讯 新闻,wordpress采集伪原创,虹口北京网站建设1.两个栈实现队列 思路#xff1a;两个栈#xff0c;一个输入栈#xff0c;一个输出栈。
当需要输入的时候就往inStack中插入#xff0c;需要输出就往outStack中输出#xff0c;当输出栈是空就倒出输入栈的数据到输出栈中#xff0c;这样就保证了后插入的数据从栈顶倒入…1.两个栈实现队列 思路两个栈一个输入栈一个输出栈。
当需要输入的时候就往inStack中插入需要输出就往outStack中输出当输出栈是空就倒出输入栈的数据到输出栈中这样就保证了后插入的数据从栈顶倒入了栈底输出栈栈顶弹出的一定是原先输入栈栈底的数据也就是先进来的即先进先出。
class MyQueue {DequeInteger inStack ;DequeInteger 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和queue2queue2仍然为空
需要弹出的时候就弹出queue1的数据就行因为queue1始终保持后进数据在队列前端。 class MyStack {DequeInteger q1;DequeInteger q2;public MyStack() {q1 new LinkedList();q2 new LinkedList();}public void push(int x) {q2.offer(x);while(!q1.isEmpty()){q2.offer(q1.remove());}DequeInteger 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) {MapInteger,Integer map new HashMap();for(int i 0;inums.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 ListListInteger threeSum(int[] nums) {
ListListInteger 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];MapInteger, 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(i0nums[i] nums[i-1]){continue;}
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();if (nums null || nums.length 3) {return result;}Arrays.sort(nums);int i,l,r;for(i0;inums.length;i){if(nums[i]0) break;if(i0nums[i]nums[i-1]){continue;}int tar -nums[i];for(l i1,r nums.length -1;lr;){if(nums[l]nums[r]tar){r--;}else if(nums[l]nums[r]tar){l;}else{ListInteger 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;}
}
