力扣爆刷第97天之hot100五连刷71-75

本文主要是介绍力扣爆刷第97天之hot100五连刷71-75，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣爆刷第97天之hot100五连刷71-75

一、394. 字符串解码

题目链接：https://leetcode.cn/problems/decode-string/description/?envType=study-plan-v2&envId=top-100-liked
思路：使用栈进行操作，如果是数字或者字母左括号直接进栈，否则开始出栈，出栈按数子拼接子串即可。

class Solution {int ptr;public String decodeString(String s) {LinkedList<String> stk = new LinkedList<String>();ptr = 0;while (ptr < s.length()) {char cur = s.charAt(ptr);if (Character.isDigit(cur)) {String digits = getDigits(s);stk.addLast(digits);} else if (Character.isLetter(cur) || cur == '[') {stk.addLast(String.valueOf(s.charAt(ptr++))); } else {++ptr;LinkedList<String> sub = new LinkedList<String>();while (!"[".equals(stk.peekLast())) {sub.addLast(stk.removeLast());}Collections.reverse(sub);stk.removeLast();int repTime = Integer.parseInt(stk.removeLast());StringBuffer t = new StringBuffer();String o = getString(sub);while (repTime-- > 0) {t.append(o);}stk.addLast(t.toString());}}return getString(stk);}public String getDigits(String s) {StringBuffer ret = new StringBuffer();while (Character.isDigit(s.charAt(ptr))) {ret.append(s.charAt(ptr++));}return ret.toString();}public String getString(LinkedList<String> v) {StringBuffer ret = new StringBuffer();for (String s : v) {ret.append(s);}return ret.toString();}
}

二、739. 每日温度

题目链接：https://leetcode.cn/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-liked
思路：求某一个数左边或者右边离他最近的一个大于或小于它的数，就使用单调栈，典型单调栈解法。

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res = new int[temperatures.length];Deque<Integer> stack = new LinkedList<>();for(int i = 0; i < temperatures.length; i++) {while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {int j = stack.pop();res[j] = i - j;}stack.push(i);}return res;}
}

三、84. 柱状图中最大的矩形

题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/description/?envType=study-plan-v2&envId=top-100-liked
思路：典型单调栈，构造凸起，当前元素小于栈顶时，栈顶元素为凸起处，然后出栈，进行计算即可。

class Solution {public int largestRectangleArea(int[] heights) {int[] nums = new int[heights.length + 2];for(int i = 0; i < heights.length; i++) {nums[i+1] = heights[i];}heights = nums;int max = 0;Deque<Integer> stack = new LinkedList<>();for(int i = 0; i < heights.length; i++) {while(!stack.isEmpty() && heights[stack.peek()] > heights[i]) {int mid = stack.pop();int w = i - stack.peek() - 1;int h = heights[mid];max = Math.max(max, w * h);}stack.push(i);}return max;}
}

四、215. 数组中的第K个最大元素

题目链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-100-liked
思路：桶排序，把所有元素分配到桶里，然后倒序遍历数够数直接返回。

class Solution {public int findKthLargest(int[] nums, int k) {// 桶排序int[] buckets = new int[20001];for(int i = 0; i < nums.length; i++) {buckets[nums[i] + 10000]++;}for(int i = buckets.length-1; i > 0; i--) {k = k - buckets[i];if(k <= 0) {return i - 10000;}}return 0;}}

五、347. 前 K 个高频元素

题目链接：https://leetcode.cn/problems/top-k-frequent-elements/description/?envType=study-plan-v2&envId=top-100-liked
思路：求前k个高频元素，先使用map去记录元素与元素出现的次数，然后使用优先级队列进行排序，最后收集即可。

class Solution {public int[] topKFrequent(int[] nums, int k) {int[] res = new int[k];PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[1]-a[1]);Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i < nums.length; i++) {map.put(nums[i], map.getOrDefault(nums[i], 0)+1);}Set<Integer> set = map.keySet();Iterator<Integer> iter = set.iterator();for(int i = 0; i < set.size(); i++) {int key = iter.next();queue.add(new int[]{key, map.get(key)});}for(int i = 0; i < k; i++) {res[i] = queue.poll()[0];}return res;}
}

这篇关于力扣爆刷第97天之hot100五连刷71-75的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---