1.两个栈实现队列
思路：两个栈，一个输入栈，一个输出栈。
当需要输入的时候就往inStack中插入，需要输出就往outStack中输出，当输出栈是空就倒出输入栈的数据到输出栈中，这样就保证了后插入的数据从栈顶倒入了栈底，输出栈栈顶弹出的一定是原先输入栈栈底的数据，也就是先进来的，即先进先出。
class MyQueue {
Deque
Deque
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
Deque
public MyStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
}
public void push(int x) {
q2.offer(x);
while(!q1.isEmpty()){
q2.offer(q1.remove());
}
Deque
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
for(int i = 0;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 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 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 if (nums == null || nums.length < 3) { return result; } Arrays.sort(nums); int i,l,r; for(i=0;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 if(nums[l]+nums[r]>tar){ r--; }else if(nums[l]+nums[r] l++; }else{ List 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; } } 相关文章
发表评论