昆明旅游网站建设,企业网络配置方案,代理浏览器在线,wordpress中查看发货信息题外话#xff1a;感觉脑子没长到栈这块…最近刷栈的题都好难啊…哭哭…坚持坚持#xff01;多刷几遍就好了#xff01;#xff01;
1. LC394.字符串解码
题目链接
先说数据结构。 维护两个栈#xff1a;一个栈存之前的字符串#xff0c;另一个栈存之后的字符串的重复…题外话感觉脑子没长到栈这块…最近刷栈的题都好难啊…哭哭…坚持坚持多刷几遍就好了
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();StackStringBuilder stack_Res new Stack();StackInteger 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 i0; icount; 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) {//建立哈希表维护 数值与频次 的键值对MapInteger, 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个高频元素PriorityQueueInteger queue new PriorityQueue(new ComparatorInteger(){Overridepublic 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 i0; ik; i){array[i] queue.poll();}return array;}
}解法二
遍历一遍建立哈希表存储数字与出现频次的映射。将Map.entrySet存放进listlist排序按照自定义规则排序按照频次即value值从大到小排序获取list中前k个元素的key值
时间复杂度 建立哈希表n放进listnsort方法排序nlogn遍历堆存进数组k 所以整体时间复杂度为O(nlogn)
空间复杂度 O(n)
class Solution {public int[] topKFrequent(int[] nums, int k) {//建立哈希表维护 数值与频次 的键值对MapInteger, 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进行排序ListMap.EntryInteger, Integer list new ArrayList();for (Map.EntryInteger, Integer entry: map.entrySet()){list.add(entry);}Collections.sort(list, (list1, list2) - list2.getValue() - list1.getValue());//获取前k个值int[] array new int[k];for (int i0; ik; i){array[i] list.get(i).getKey();}return array;}
}3. LC215.数组中的第k个最大元素
题目链接
用优先级队列方法做。 PriorityQueuepeek()方法返回的是堆顶元素poll()方法移除的也是堆顶元素offer()方法把元素插入队列末尾队列会根据自定义实现排序。 所以我们考虑使用大顶堆还是小顶堆呢 因为poll和peak针对的是堆顶元素所以我们每次新来一个元素若想加入堆都必须要移除堆顶的元素。如果是大顶堆的话堆顶是最大的元素但显然最大的元素不能被移除。所以我们要用小顶堆。若新来的元素比堆顶的大则移除堆顶元素把新元素加入进来。这样可以实现最后得到的大顶堆是前k个最大元素。堆顶就是第k个最大元素
代码 注意
优先级队列的定义还是要熟悉尤其是里面的comparator怎么写只有当新元素大于堆顶而非大于等于时才将新元素加入进来。比如考虑655,5是第二大元素无论哪个5都是第二大元素但如果两个5都加到堆里来的话那堆里就有三个元素了就成前3大元素了。所以加入堆的条件不能是等于。基本类型转包装类包装类转基本类型必须熟记。
class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueueInteger queue new PriorityQueue(new ComparatorInteger(){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();}
}
