一：常用技巧：枚举右，维护左

1.双变量问题

        对于双变量问题，例如两数之和 ai + aj = t，可以枚举右边的aj，转换成单变量问题，也就是

        在aj左边查找是否有 ai = t - aj，这就可以用哈希表来维护

        也叫做：枚举右，维护左

        例子：两数之和

        给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值target

        的那两个整数，并返回他们的数组下标

        你可以假设每种输入只会对应一个答案，并且不能使用重复元素

        你可以按任意顺序返回答案

class Solution {public int[] twoSum(int[] nums, int target) {int[] arr = new int[2];Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int temp = target - nums[i];if (map.containsKey(temp)) {arr[0] = map.get(temp);arr[1] = i;break;} else {//将当前值存进mapmap.put(nums[i], i);}}return arr;}
}

2.好数对的数目

        给你一个整数数组nums，如果一组数字（i，j）满足 nums[i] == nums[j] 且 i < j，

        这就可以认为是一组好数对，请返回好数对的数目

class Solution {public int numIdenticalPairs(int[] nums) {/**还是用哈希表维护*/Map<Integer, Integer> map = new HashMap<>();int count = 0;for (int num : nums) {int ans = map.getOrDefault(num, 0);count += ans;//因为要求是i < j 所以自己不能重复map.put(num, ans + 1);} return count;}
}

二.栈-基础

1.用栈操作构建数组

        给你一个数组 target 和一个整数 n，每次迭代，需要从 list = {1, 2, 3, ......, n}中依次读取

        一个数字，请你用下述操作来构建目标数组 target：

        - "Push"：从 list 中读取一个新的元素，并将其推入数组中

        - "Pop"：删除数组中的最后一个元素

        - 如果目标数组构建完成，就停止读取梗多元素

        题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字

        请返回构建目标数组所用的操作序列，如果存在多个可行方案，返回任意即可。

class Solution {public List<String> buildArray(int[] target, int n) {//大概明白这题的意思了//每次操作都是递增的//所以target每两两相连的两个数之间相差几 比如 index0=1 index1=3//那么0和1之间肯定是先push1 push2 pop2 push3 做了这四个动作才会形成1，3这个结构//那么就是说两个相邻的数之间相差了几 就做了几组 push pop 然后最后会再push当前List<String> list = new ArrayList<>();for (int i = 1, j = 0; i <= n && j < target.length; i++) {list.add("Push");//如果push进来的数和当前数组中同位置的数不相等 则证明被pop了if (target[j] != i) {list.add("Pop");} else {j++;}}return list;}
}

2.比较含退格的字符串

        给定 s 和 t 两个字符串，当他们分别被输入到空白的文本编辑器后，如果两者相等，

        返回true。

        注意：如果对空文本输入退格字符，文本继续为空。

        

class Solution {public boolean backspaceCompare(String s, String t) {/**那么就是双循环 大循环就是 比较两个串的当前字符是否相等 不相等直接false相等就是 指针都--然后各自内部再循环 有两种情况当前字符是# 那么记录一下#的数量 继续往前循环当前字符不是# 然后#的数量>0 那么就意味着可以消除 #-- 指针--然后当前字符不是# 而且#的数量=0了 推出循环同理 另外一个串也是这样循环的逻辑*/int sIndex = s.length() - 1, tIndex = t.length() - 1;int sCount = 0, tCount = 0;while (sIndex >= 0 || tIndex >= 0) {while (sIndex >= 0) {if (s.charAt(sIndex) == '#') {sCount++;sIndex--;} else if (sCount > 0) {sCount--;sIndex--;} else {//退出循环break;}}while (tIndex >= 0) {if (t.charAt(tIndex) == '#') {tCount++;tIndex--;} else if (tCount > 0) {tCount--;tIndex--;} else {//退出循环break;}}//边界问题if (sIndex >= 0 && tIndex >= 0) {if (s.charAt(sIndex) != t.charAt(tIndex)) return false;} else {//其中有串已经循环结束了 但是另外一个可能还没结束//那么这个时候除非都结束了 不然只要有一个每结束就是不等于if (sIndex >= 0 || tIndex >= 0) return false;}sIndex--;tIndex--;} return true;}
}

三.栈-进阶

1.最小栈

        设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈

        实现 MinStack类：

        - MinStack（）初始化堆栈对象

        - void push(int val) 将元素val推入堆栈

        - void pop() 删除堆栈顶部元素

        - int top() 获取堆栈顶部的元素

        - int getMin() 获取堆栈中的最小元素

class MinStack {private LinkedList<Integer> queue;private LinkedList<Integer> min;public MinStack() {this.queue = new LinkedList<>();this.min = new LinkedList<>();}public void push(int val) {//两个栈 一个栈正常存数据 一个栈存最小值//但是有个问题 怎么维持这俩栈的同步大小 //每次push的时候min也存一份数据：当前的最小值//栈顶和当前push比较 这样queue里面比如存了 1， 2， -1//那么当push1的时候min里面没有元素 最小值就是1//push2 最小值还是1 又往min里面push1//push-1的时候 最小值是-1 那么min也push-1//这样 queue里面就是 -1 2 1 //     min就是       -1 1 1//这样两边数据就对的上 而且只要每次存最小值 就能保证push queue的时候不管是push什么 min里面的数据都是对的//就是相当于存一个queue里面每个元素对应的最小值 和min里面的元素位置相对应queue.push(val);if (min.isEmpty()) {min.push(val);return;}int minVal = min.peek();min.push(Math.min(minVal, val));}public void pop() {queue.pop();min.pop();}public int top() {return queue.peek();}public int getMin() {return min.peek();}
}

2.设计一个支持增量操作的栈

        请你设计一个支持对其元素进行增量操作的栈

        实现自定义栈类 CustomStack

        - CustomStack(int maxSize)：用maxSize初始化对象，maxSize是栈最多能容纳的元素数量

        - void push(int x)：如果栈还未增长到maxSize，就将x压入栈顶

        - int pop()：弹出栈顶元素，并返回栈顶的值，或栈顶为空时返回-1

        - void inc(int k, int val)：栈底的 k 个元素的值都增加val，如果栈中元素总数小于k，则栈中

        所有的元素都增加val

class CustomStack {private LinkedList<Integer> queue;private int maxSize;public CustomStack(int maxSize) {this.queue = new LinkedList<>();this.maxSize = maxSize;}public void push(int x) {if (queue.size() < maxSize) queue.push(x);}public int pop() {if (queue.isEmpty()) return -1;return queue.peek();}public void increment(int k, int val) {int num = 1;LinkedList<Integer> temp = new LinkedList<>();int size = queue.size();while (num <= size && num <= k) {Integer v = queue.pollLast();v += val;temp.push(v);num++;}while (!temp.isEmpty()) {queue.addLast(temp.pop());}}
}

3.有效的括号

        给定一个只包括 '('、')'、'{'、'}'、'['、']' 的字符串s，判断字符串是由有效

        有效满足：

        - 左括号必须用相同类型的右括号闭合

        - 左括号必须以正确的顺序闭合

        - 每个右括号都有一个对应的相同类型的左括号

class Solution {public boolean isValid(String s) {//这题可以不用栈//以为不是顺序的 噢 特尔的傻逼题目 还是要用顺序的LinkedList<Character> queue = new LinkedList<>();char[] arr = s.toCharArray();for (char c : arr) {if (c == '(' || c == '{' || c == '[') {queue.push(c);continue;}if (c == ')' && !queue.isEmpty() && queue.peek() == '(' ) {queue.pop();continue;}if (c == '}' && !queue.isEmpty() && queue.peek() == '{' ) {queue.pop();continue;}if (c == ']' && !queue.isEmpty() && queue.peek() == '[') {queue.pop();continue;}queue.push(c);}return queue.isEmpty();}
}

四.队列

1.最近的请求次数

        写一个 RecentCounter 类来计算特定时间范围内最近的请求

        请你实现 RecentCounter类：

        - RecentCounter() 初始化计数器，请求书为0

        - int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回

        过去 3000 毫秒内发生的所有请求数(包括新请求)，确切的说，返回 [t - 3000, t] 内发生

        的请求数

        保证每次队 ping的调用都使用比之前更大的 t 值。

class RecentCounter {private LinkedList<Integer> queue;public RecentCounter() {this.queue = new LinkedList<>();}public int ping(int t) {queue.add(t);//由于每次收到的请求的时间都比之前的大，因此从队首到队尾的时间值是单调递增的。//当在时间 t 收到请求时，为了求出 [t−3000,t] 内发生的请求数，//我们可以不断从队首弹出早于 t−3000 的时间。循环结束后队列的//长度就是 [t−3000,t] 内发生的请求数。while (queue.peek() < t - 3000) {queue.poll();}return queue.size();}
}

2.用队列实现栈

        请你仅使用两个队列实现一个后入先出(LIFO)的栈，并支持普通栈的全部四种操作(push、

        top、pop和empty)。

        实现 MyStack类

        - void push(int x) 入栈

        - int pop() 栈顶出栈

        - int top() 返回栈顶元素

        - boolean empty() 判断栈是否为空

class MyStack {private LinkedList<Integer> stack; private LinkedList<Integer> temp; public MyStack() {this.stack = new LinkedList<>();this.temp = new LinkedList<>();}public void push(int x) {/**思路：每次push的时候先进temp 然后从stack里面一个一个出队列并oush到temp最后temp和stack交换这样就能保证队列变为栈 先进后出比如：第一次push x = 1，这个时候stack是空的 temp也是空的进temp，temp变为： 1 然后temp和stack交换 temp为空 stack = 1然后第二次push x = 2temp = 2, temp.offer(stack.poll)---> temp= 1->2 然后交换第三次push x= 3最后temp就变为：1-2->3 这样队列就变为了一个后进先出的栈          */temp.offer(x);while (!stack.isEmpty()) {temp.offer(stack.poll());}LinkedList<Integer> t = stack;stack = temp;temp = t;}public int pop() {if (stack.isEmpty()) return - 1;return stack.poll();}public int top() {if (stack.isEmpty()) return - 1;return stack.peek();}public boolean empty() {return stack.isEmpty();}
}

3.用栈实现队列

        请你仅使用两个栈实现先入先出队列，队列应当支持一般队列的所有操作

class MyQueue {private LinkedList<Integer> queue;private LinkedList<Integer> temp;public MyQueue() {this.queue = new LinkedList<>();this.temp = new LinkedList<>();}public void push(int x) {/**思路和用2个队列实现栈是一样的先从queue正常出栈到temp然后temp正常出栈到queue这样就能用栈实现队列的先进先出*/while (!queue.isEmpty()) {temp.push(queue.poll());}temp.push(x);while (!temp.isEmpty()) {queue.push(temp.poll());}}public int pop() {return queue.pop();}public int peek() {return queue.peek();}public boolean empty() {return queue.isEmpty();}
}

4.设计循环队列

        设计你的循环队列实现，循环队列是一种线性数据结构，其操作表限基于 FIFO(先进先出)

        原则并且队尾连接在队首之后以形成一个循环，它也被称为 环形缓冲器

        循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦

        一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列

        我们能使用这些空间去存储新的值，

        你的实现应该支持如下操作

        - MyCircularQueue(k)：构造器，设置队长度为k

        - Front：从队首获取元素，为空返回-1

        - Rear：获取队尾元素，为空返回-1

        - enQueue(value)：向循环队列插入一个元素，如果成功返回true

        - deQueue()：从循环队列删除一个元素，成功返回true

        - isEmpty()：是否为空

        - isFull()：是否已满

class MyCircularQueue {private int[] queue;private int maxSize, head, tail;public MyCircularQueue(int k) {this.queue = new int[k];this.maxSize = k;this.head = 0;this.tail = 0;}public boolean enQueue(int value) {if (isFull()) return false;//意味着从队尾插入 因为队列都是从尾部插入数据//用模运算操作 这样就能实现循环 从而保证不会越界queue[tail % maxSize] = value;tail++; //尾部插入了数据之后向后移动一位 标示着这个位置是尾部return tail >= 0;}public boolean deQueue() {if (isEmpty()) return false;//从头删除 那就是直接将头往后移动一位head++;return head >= 0;}public int Front() {if (isEmpty()) return -1;return queue[head % maxSize];}public int Rear() {if (isEmpty()) return -1;//因为tail指针都是指向下一位的 所以真正队尾的数据是tail-1位return queue[(tail - 1) % maxSize];}public boolean isEmpty() {return head == tail;}public boolean isFull() {return tail - head == maxSize;}
}

五.堆（优先队列）

1.最后一块石头的重量

        有一堆石头，每块石头的重量都是正整数

        每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎，假设石头的重量分别为 x 和 y

        且 x <= y，那么粉碎的可能结果如下：

        - 如果 x == y，那么两块石头都会被完全粉碎

        - 如果 x != y，那么重量为 x 的石头完全粉碎，而为 y 的石头新重量为 y - x

        最后，最多只会剩下一快石头，返回此石头的重量，如果没有石头剩下，返回 0

class Solution {public int lastStoneWeight(int[] stones) {//用java自带的优先队列 默认降序排序PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);//将数据放入堆中for (int x : stones) {heap.offer(x);}//每次取出两个最上面的石头//保证里面最少有2个元素while (heap.size() > 1) {int y = heap.poll();int x = heap.poll();if (x != y) {heap.offer(y - x);}}return heap.isEmpty() ? 0 : heap.poll();}
}

2. K 次乘运算后的最终数组 I

        给你一个整数数组 nums，一个整数 k 和一个整数 multiplier

        你需要堆 mus 执行 k 次操作，每次操作中：

        - 找到 nums 中 最小的值 x，如果存在多个最小值，选择最前面的一个

        - 将 x 替换为 x * multiplier

        请你返回执行完 k 次乘运算只会，最终 nums 数组

class Solution {public int[] getFinalState(int[] nums, int k, int multiplier) {//优先队列存数组，0存元素 1存元素索引PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0] == 0 ? a[1] - b[1] : a[0] - b[0]);for (int i = 0; i < nums.length; i++) {int[] arr = new int[2];arr[0] = nums[i];arr[1] = i;heap.offer(arr);}for (int i = 0; i < k; i++) {int[] min = heap.poll();nums[min[1]] = min[0] * multiplier;heap.offer(new int[]{nums[min[1]], min[1]});}return nums;}
}

3.从数量最多的堆取走礼物

        给你一个整数数组 gifts，表示各堆礼物的数量，每一秒，你需要执行以下操作

        - 选择礼物数量最多的那一堆

        - 如果不止一堆都符合礼物数量最多，任选其一

        - 选中的那一堆留下平方根数量的礼物(向下取整)，取走其他的礼物

        返回在 k 秒后剩下的礼物数量

class Solution {public long pickGifts(int[] gifts, int k) {PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);for (int num : gifts) {heap.offer(num);}while (k-- > 0) {int max = heap.poll();int sqrt = (int)Math.sqrt(max);heap.offer(sqrt);}long sum = 0;while (!heap.isEmpty()) {sum += heap.poll();}return sum;}
}

4.无线集中的最小数字

        现有一个包含所有正整数的集合 [1, 2, 3, ,4 ,5, ......]

        实现 SmallesInfiniteSet类：

        - SmallesInfiniteSet() 初始化对象以包含所有 正整数

        - int popSmallest() 移除并返回该无线几种的最小整数

        - void addBack(int num) 如果正整数 num 不存在无限集中，则将一个num添加进来

        提示：1 <= num <= 1000

        

class SmallestInfiniteSet {private PriorityQueue<Integer> heap;    //没有去重功能private boolean[] bool; //用来判断去重private int min;        //用来标识无限集的最左边界public SmallestInfiniteSet() {this.heap = new PriorityQueue<>();this.min = 1;   //题目说了num>=1this.bool = new boolean[1001];}public int popSmallest() {//移除最小元素，如果不在最小堆中，那么就移除无限集的左边界 if (!heap.isEmpty()) {int poll = heap.poll();bool[poll] = false;return poll;}//因为每次都是移除最小整数，所以min每次++往右移动一位就行//前提是不在堆中//比如第一次调用 肯定是返回1//这个时候无限集的左边界已经是从2到正无穷//这个时候如果add了一个1，那么是不是说明不在无限集的范围内，//那么就会把这个1存进heap中//heap里面保存的数据都是小于无限集的左边界的数据 //也就是说都是已经移除了的数据return min++;}public void addBack(int num) {//>min 或者bool里面是true就表示存在if (num >= min || bool[num]) return;//否则不存在无限集中 证明曾经某次调用移除了 //这个时候就从heap中返回即可heap.offer(num);//并且标识已经添加过了bool[num] = true;}
}