题外话：感觉脑子没长到栈这块…最近刷栈的题都好难啊…哭哭…坚持坚持！多刷几遍就好了！！
1. LC394.字符串解码
题目链接
先说数据结构。
维护两个栈：一个栈存之前的字符串，另一个栈存之后的字符串的重复次数（数字）
维护两个变量：res表示目前遍历到的字符组成的字符串，k表示遍历到的数字组成的数字
工作原理：
最开始的字符串为""。
遇到字符时：存到res里。
遇到数字时：存到k里。
遇到左括号：把左括号前面的字符串，以及左括号内要循环的次数（数字），分别入栈，即res和k入栈。然后res和k重置。
遇到右括号：说明此时的res为最小单位，将数字栈里的栈顶元素出栈，这个数字将是res循环的次数。然后将字符串栈里的栈顶元素出栈，这个元素是括号前的字符串，后面需要拼接res。拼接后，形成新的res。不入栈。等遇到左括号再入栈。
例：
3[a2[c]] 看成 ""3[a2[c]]
图片版：
文字版：
代码
注意当字符是数字字符的处理逻辑。
- 用
c >= '0' && c <= '9'来确定当前字符是不是数字字符 c-'0'得到当前字符代表的数字，将字符转为数字k = k * 10 + (c-'0');这个也很妙。如果k已经有数字了，例如k已经等于12了，这时又遍历到3，那么就是k*10再加上当前的数字，123。
class Solution {
public String decodeString(String s) {
int k = 0;
StringBuilder res = new StringBuilder();
Stack<StringBuilder> stack_Res = new Stack<>();
Stack<Integer> stack_K = new Stack<>();
for (char c : s.toCharArray()){
if (c >= '0' && c <= '9'){
k = k * 10 + (c-'0');
}
else if (c == '['){
stack_Res.push(res);
stack_K.push(k);
res = new StringBuilder();
k = 0;
}
else if (c == ']'){
int count = stack_K.pop();
StringBuilder temp = new StringBuilder();
for (int i=0; i<count; i++){
temp.append(res);
}
res = stack_Res.pop().append(temp);
}
else{
res.append(c);
}
}
return res.toString();
}
}
2. LC347、前K个高频元素
题目链接
解法一：
- 遍历一遍，建立哈希表存储数字与出现频次的映射。
- 维护一个元素数目为k的小顶堆。（堆中存放的是元素，但是priority queue可以按照自定义顺序排序，自定义顺序为：元素的频次）。
- 当有新元素来的时候，与堆顶元素作比较，若频次比堆顶元素大，则该元素应放到前k个高频元素中，所以堆顶元素出队列，该元素加队列。堆会自动按定义顺序排序。
- 最终堆中的元素就是前K个高频元素。
时间复杂度：
建立哈希表：n；小顶堆本身维护：logk；遍历哈希，维护小顶堆：nlogk；遍历堆存进数组：k
所以整体时间复杂度为O(nlogk)
空间复杂度：
哈希表：n，小顶堆：k。
所以整体空间复杂度为O(n)
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//建立哈希表维护 数值与频次 的键值对
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums){
if (map.containsKey(i)){
map.put(i, map.get(i)+1);
}else{
map.put(i, 1);
}
}
//定义PriorityQueue存放前k个高频元素
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
@Override
public int compare(Integer a, Integer b){
return (map.get(a) - map.get(b));
}
});
//遍历map,更新堆
for (Integer key: map.keySet()){
if (queue.size() < k){
queue.offer(key);
}else{
if (map.get(key) > map.get(queue.peek())){
queue.poll();
queue.offer(key);
}
}
}
//输出堆元素
int[] array = new int[k];
for (int i=0; i<k; i++){
array[i] = queue.poll();
}
return array;
}
}
解法二：
- 遍历一遍，建立哈希表存储数字与出现频次的映射。
- 将Map.entrySet<>存放进list，list排序，按照自定义规则排序（按照频次，即value值从大到小排序）
- 获取list中前k个元素的key值
时间复杂度：
建立哈希表：n；放进list：n；sort方法排序：nlogn；遍历堆存进数组：k
所以整体时间复杂度为O(nlogn)
空间复杂度：
O(n)
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//建立哈希表维护 数值与频次 的键值对
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums){
if (map.containsKey(i)){
map.put(i, map.get(i)+1);
}else{
map.put(i, 1);
}
}
//将entryset放进list，对list进行排序
List<Map.Entry<Integer, Integer>> list = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry: map.entrySet()){
list.add(entry);
}
Collections.sort(list, (list1, list2) -> list2.getValue() - list1.getValue());
//获取前k个值
int[] array = new int[k];
for (int i=0; i<k; i++){
array[i] = list.get(i).getKey();
}
return array;
}
}
3. LC215.数组中的第k个最大元素
题目链接
用优先级队列方法做。
PriorityQueue，peek()方法返回的是堆顶元素，poll()方法移除的也是堆顶元素，offer()方法把元素插入队列末尾，队列会根据自定义实现排序。
所以我们考虑使用大顶堆还是小顶堆呢？
因为poll和peak针对的是堆顶元素，所以我们每次新来一个元素若想加入堆，都必须要移除堆顶的元素。如果是大顶堆的话，堆顶是最大的元素，但显然最大的元素不能被移除。所以我们要用小顶堆。若新来的元素比堆顶的大，则移除堆顶元素，把新元素加入进来。这样可以实现最后得到的大顶堆是前k个最大元素。堆顶就是第k个最大元素
代码
注意：
- 优先级队列的定义，还是要熟悉，尤其是里面的comparator怎么写
- 只有当新元素大于堆顶，而非大于等于时，才将新元素加入进来。比如考虑655,5是第二大元素，无论哪个5都是第二大元素，但如果两个5都加到堆里来的话，那堆里就有三个元素了，就成前3大元素了。所以加入堆的条件不能是等于。
- 基本类型转包装类，包装类转基本类型，必须熟记。
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer a, Integer b){
return a.intValue() - b.intValue();
}
});
int index = 0;
for (int i: nums){
if (index < k){
queue.offer(Integer.valueOf(i));
}
else{
if (i > queue.peek()){
queue.poll();
queue.offer(Integer.valueOf(i));
}
}
index++;
}
return queue.peek();
}
}
![Spring boot 请求参数包含[]等特殊字符，导致无法接收问题](https://img-blog.csdnimg.cn/direct/96fedd17fa6e4af2bdb791f93c0bdef5.png)
