本文主要是介绍力扣爆刷第113天之CodeTop100五连刷51-55,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣爆刷第113天之CodeTop100五连刷51-55
文章目录
- 力扣爆刷第113天之CodeTop100五连刷51-55
- 一、239. 滑动窗口最大值
- 二、41. 缺失的第一个正数
- 三、LCR 140. 训练计划 II
- 四、322. 零钱兑换
- 五、76. 最小覆盖子串
一、239. 滑动窗口最大值
题目链接:https://leetcode.cn/problems/sliding-window-maximum/description/
思路:自己创建一个队列,提供API,关键在于,往队列里添加元素时,但凡是小于当前值的都可以出队,然后遍历数组,维护好滑动窗口,最大值就是队列左端(得益于上面的出队操作),滑动窗口缩小就从队列左端比较,nums[i-k+1] == 左端,就删除元素,其他的记录即可。
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {MyQueue queue = new MyQueue();int[] res = new int[nums.length-k+1];int j = 0;for(int i = 0; i < nums.length; i++) {queue.add(nums[i]);if(i >= k-1) {res[j++] = queue.getMax();queue.remove(nums[i-k+1]);}}return res;}class MyQueue{LinkedList<Integer> queue = new LinkedList<>();public MyQueue(){}void add(int v) {while(!queue.isEmpty() && queue.getLast() < v) {queue.removeLast();}queue.addLast(v);}void remove(int v) {if(v == queue.getFirst()) {queue.removeFirst();}}int getMax() {return queue.getFirst();}}
}
二、41. 缺失的第一个正数
题目链接:https://leetcode.cn/problems/first-missing-positive/description/
思路:要求时间复杂度为O(N),空间复杂度为常量级,则可以使用原地hash的方法,把原数组作为一个hash表,既然是求第一个缺失的正整数,nums从1开始铺满,假设为,len=4, nums就可以存放正整数1,2,3,4,如果有<=0的数我们就标记为len+1。然后再把小于len+1的值做为key,把对应的value给标记为负数,这样没被标记的位置就是大于4的,即为缺失的。
class Solution {public int firstMissingPositive(int[] nums) {int k = nums.length+1;for(int i = 0; i < nums.length; i++) {if(nums[i] <= 0) nums[i] = k;}for(int i = 0; i < nums.length; i++) {int t = Math.abs(nums[i]);if(t < k) {nums[t-1] = -Math.abs(nums[t-1]);}}for(int i = 0; i < nums.length; i++) {if(nums[i] > 0) return i+1;}return k;}
}
三、LCR 140. 训练计划 II
题目链接:https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/description/
思路:求链表倒数第n个节点,典型的快慢指针。
class Solution {public ListNode trainingPlan(ListNode head, int cnt) {ListNode root = new ListNode(-1, head);ListNode slow = root, fast = root;for(int i = 0; i < cnt; i++) {fast = fast.next;}while(fast != null) {fast = fast.next;slow = slow.next;}return slow;}
}
四、322. 零钱兑换
题目链接:https://leetcode.cn/problems/coin-change/description/
思路:零钱数量无限,正序遍历,求达到总数所需的最少硬币数,定义dp[i]表示,装满 i 所需的最少硬币数,那么,动态规划的状态转移,一定是从上一个硬币位置开始的,也就是 i - coins[j],这个位置,即 dp[i - coins[j]],上一个硬币位置只要是有值的,那么就可以推导出状态转移,是dp[i]=dp[i - coins[j]] + 1,当然还得再和自身历史值进行比较,留下最小值。
class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for(int i = 0; i < coins.length; i++) {for(int j = coins[i]; j <= amount; j++) {if(dp[j-coins[i]] != Integer.MAX_VALUE) {dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);}}}return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}
}
五、76. 最小覆盖子串
题目链接:https://leetcode.cn/problems/minimum-window-substring/description/
思路:典型滑动窗口,维护好一个变量值,作为进入滑动窗口的契机,没进入时扩大右边界,进入时,缩小左边界。在扩大的过程修改契机,直到满足,在缩小的过程修改契机,同时记录最小值,直到不再满足契机。之后新的一轮又重新开始。
class Solution {public String minWindow(String s, String t) {Map<Character, Integer> window = new HashMap<>();Map<Character, Integer> need = new HashMap<>();for (char c : t.toCharArray()) {need.put(c, need.getOrDefault(c, 0) + 1);}int left = 0, right = 0, valid = 0, init = 0;int min = Integer.MAX_VALUE;while (right < s.length()) {char rc = s.charAt(right);right++;if (need.containsKey(rc)) {window.put(rc, window.getOrDefault(rc, 0) + 1);if (window.get(rc).equals(need.get(rc))) {valid++;}}while (valid == need.size()) {if (right - left < min) {min = right - left;init = left;}char lc = s.charAt(left);left++;if (need.containsKey(lc)) {if (need.get(lc).equals(window.get(lc))) {valid--;}window.put(lc, window.get(lc)-1);}}}return min == Integer.MAX_VALUE ? "" : s.substring(init, init+min);}
}
这篇关于力扣爆刷第113天之CodeTop100五连刷51-55的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!