最适合新人的写作网站,湖州市城市建设档案馆网站,极家装修口碑好不好,wordpress文章归档模板文章目录 907. 子数组的最小值之和#xff08;单调栈贡献法#xff09;1670. 设计前中后队列⭐#xff08;设计数据结构#xff09;解法1——双向链表解法2——两个双端队列 2336. 无限集中的最小数字解法1——维护最小变量mn 和 哈希表维护已经去掉的数字解法2——维护原本… 文章目录 907. 子数组的最小值之和单调栈贡献法1670. 设计前中后队列⭐设计数据结构解法1——双向链表解法2——两个双端队列 2336. 无限集中的最小数字解法1——维护最小变量mn 和 哈希表维护已经去掉的数字解法2——维护原本可用的最小值 和 有序集合维护后期添加的数值 1657. 确定两个字符串是否接近理解操作本质⭐2661. 找出叠涂元素哈希表、计数统计1094. 拼车差分1423. 可获得的最大点数滑动窗口 907. 子数组的最小值之和单调栈贡献法
https://leetcode.cn/problems/sum-of-subarray-minimums/description/?envTypedaily-questionenvId2023-11-27 提示
1 arr.length 3 * 10^4 1 arr[i] 3 * 10^4
class Solution {private static final int MOD (int)1e9 7;public int sumSubarrayMins(int[] arr) {long ans 0; // 使用long总归是有利于避免溢出int n arr.length;// 计算每个数字作为最小值的贡献即找到左右两侧第一个小于它的一边严格小于另一边小于等于DequeInteger stk new ArrayDeque();int[] right new int[n], left new int[n];Arrays.fill(left, -1);Arrays.fill(right, n);for (int i 0; i n; i) {while (!stk.isEmpty() arr[i] arr[stk.peek()]) {right[stk.pop()] i;}if (!stk.isEmpty()) left[i] stk.peek();stk.push(i);}for (int i 0; i n; i) {ans (ans (long)arr[i] * (right[i] - i) * (i - left[i])) % MOD;}return (int)ans;}
}1670. 设计前中后队列⭐设计数据结构
https://leetcode.cn/problems/design-front-middle-back-queue/description/?envTypedaily-questionenvId2023-11-28 提示
1 val 10^9 最多调用 1000 次 pushFront pushMiddle pushBack popFront popMiddle 和 popBack 。
解法1——双向链表
自己写的代码如下
class FrontMiddleBackQueue {Node head new Node(), tail new Node();int sz 0;public FrontMiddleBackQueue() {head.next tail;tail.prev head;}public void pushFront(int val) {Node node new Node(val, head, head.next);head.next.prev node;head.next node;sz;}public void pushMiddle(int val) {Node cur head;for (int i 0; i sz / 2; i) {cur cur.next;}Node node new Node(val, cur, cur.next);cur.next.prev node;cur.next node;sz;}public void pushBack(int val) {Node node new Node(val, tail.prev, tail);tail.prev.next node;tail.prev node;sz;}public int popFront() {if (sz 0) return -1;int res head.next.val;head.next.next.prev head;head.next head.next.next;--sz;return res;}public int popMiddle() {if (sz 0) return -1;Node cur head;for (int i 0; i (sz - 1) / 2; i) cur cur.next;int res cur.next.val;cur.next.next.prev cur;cur.next cur.next.next;--sz;return res;}public int popBack() {if (sz 0) return -1;int res tail.prev.val;tail.prev.prev.next tail;tail.prev tail.prev.prev;--sz;return res;}
}class Node {int val -1;Node prev null, next null;Node() {};Node(int _val, Node _prev, Node _next) {this.val _val;this.prev _prev;this.next _next;}
}/*** Your FrontMiddleBackQueue object will be instantiated and called as such:* FrontMiddleBackQueue obj new FrontMiddleBackQueue();* obj.pushFront(val);* obj.pushMiddle(val);* obj.pushBack(val);* int param_4 obj.popFront();* int param_5 obj.popMiddle();* int param_6 obj.popBack();*/一种优化方法是额外一个指针指向中间节点参见https://leetcode.cn/problems/design-front-middle-back-queue/solutions/502014/she-ji-qian-zhong-hou-dui-lie-by-zerotrac2/?envTypedaily-questionenvId2023-11-28 的方法二。
解法2——两个双端队列
参考官方题解的思想 和 0x3f的代码写的。
class FrontMiddleBackQueue {// 左边的双端队列和右边的双端队列等长 或恰好大1。可以保证中间节点是左队列的结尾节点DequeInteger left new ArrayDeque(), right new ArrayDeque();public FrontMiddleBackQueue() {}public void pushFront(int val) {left.addFirst(val);balance();}public void pushMiddle(int val) {if (left.size() right.size()) right.offerFirst(left.pollLast());left.offerLast(val);}public void pushBack(int val) {right.offerLast(val);balance();}public int popFront() {if (left.isEmpty()) return -1;int res left.pollFirst();balance();return res;}public int popMiddle() {if (left.isEmpty()) return -1;int res left.pollLast();balance();return res;}public int popBack() {if (left.isEmpty()) return -1;int res right.isEmpty()? left.pollLast(): right.pollLast();balance();return res;}// 保持两个队列的相对大小public void balance() {if (left.size() right.size() 1) {right.offerFirst(left.pollLast());} else if (left.size() right.size()) {left.offerLast(right.pollFirst());}}
}/*** Your FrontMiddleBackQueue object will be instantiated and called as such:* FrontMiddleBackQueue obj new FrontMiddleBackQueue();* obj.pushFront(val);* obj.pushMiddle(val);* obj.pushBack(val);* int param_4 obj.popFront();* int param_5 obj.popMiddle();* int param_6 obj.popBack();*/2336. 无限集中的最小数字
https://leetcode.cn/problems/smallest-number-in-infinite-set/description/?envTypedaily-questionenvId2023-11-29 解法1——维护最小变量mn 和 哈希表维护已经去掉的数字
维护最小变量mn哈希表记录已经去除的数字。 当新添加数字时如果更小则更新 mn 变量。
class SmallestInfiniteSet {int mn 1;SetInteger mv new HashSet();public SmallestInfiniteSet() {}public int popSmallest() {int res mn;mv.add(mn);while (mv.contains(mn)) mn;return res;}public void addBack(int num) {if (mv.contains(num)) {mv.remove(num);if (num mn) mn num;}}
}/*** Your SmallestInfiniteSet object will be instantiated and called as such:* SmallestInfiniteSet obj new SmallestInfiniteSet();* int param_1 obj.popSmallest();* obj.addBack(num);*/解法2——维护原本可用的最小值 和 有序集合维护后期添加的数值
去除时 是 去除最小的。 添加时 也只能添加 当前没有的也是小的。
用一个变量维护上界用一个有序集合维护新加的可用小数据。
class SmallestInfiniteSet {private int thres;private TreeSetInteger set;public SmallestInfiniteSet() {thres 1;set new TreeSetInteger();}public int popSmallest() {if (set.isEmpty()) {int ans thres;thres;return ans;}int ans set.pollFirst();return ans;}public void addBack(int num) {if (num thres) {set.add(num);}}
}1657. 确定两个字符串是否接近理解操作本质⭐
https://leetcode.cn/problems/determine-if-two-strings-are-close/description/?envTypedaily-questionenvId2023-11-30 提示 1 word1.length, word2.length 10^5 word1 和 word2 仅包含小写英文字母
https://leetcode.cn/problems/determine-if-two-strings-are-close/solutions/2547579/li-jie-cao-zuo-ben-zhi-jian-ji-xie-fa-py-b18i/?envTypedaily-questionenvId2023-11-30
class Solution {public boolean closeStrings(String word1, String word2) {if (word1.length() ! word2.length()) return false;int sMask 0, tMask 0;int[] sCnt new int[26], tCnt new int[26];for (char ch: word1.toCharArray()) {sMask | 1 (ch - a);sCnt[ch - a];}for (char ch: word2.toCharArray()) {tMask | 1 (ch - a);tCnt[ch - a];}Arrays.sort(sCnt);Arrays.sort(tCnt);return sMask tMask Arrays.equals(sCnt, tCnt);}
}2661. 找出叠涂元素哈希表、计数统计
https://leetcode.cn/problems/first-completely-painted-row-or-column/description/?envTypedaily-questionenvId2023-12-01 提示
m mat.length n mat[i].length arr.length m * n 1 m, n 10^5 1 m * n 10^5 1 arr[i], mat[r][c] m * n arr 中的所有整数 互不相同 mat 中的所有整数 互不相同
class Solution {public int firstCompleteIndex(int[] arr, int[][] mat) {int m mat.length, n mat[0].length;// 记录位置信息int[] c new int[m * n 1], r new int[m * n 1];for (int i 0; i m; i) {for (int j 0; j n; j) {r[mat[i][j]] i;c[mat[i][j]] j;}}// 计数统计int[] cc new int[n], rc new int[m];for (int i 0; i m * n; i) {int v arr[i], row r[v], col c[v];cc[col];rc[row];if (cc[col] m || rc[row] n) return i;}return -1;}
}1094. 拼车差分
https://leetcode.cn/problems/car-pooling/description/?envTypedaily-questionenvId2023-12-02 提示
1 trips.length 1000 trips[i].length 3 1 numPassengersi 100 0 fromi toi 1000 1 capacity 10^5
用差分 表示 from 到 to 的范围内增加了多少人然后再还原。
class Solution {public boolean carPooling(int[][] trips, int capacity) {int[] diff new int[1001];for (int[] t: trips) {diff[t[1]] t[0];diff[t[2]] - t[0];}int s 0;for (int i 0; i 1001; i) {s diff[i];if (s capacity) return false;}return true;}
}1423. 可获得的最大点数滑动窗口
https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/description/?envTypedaily-questionenvId2023-12-03 提示 1 cardPoints.length 10^5 1 cardPoints[i] 10^4 1 k cardPoints.length
就是找到长度为 n - k 和最小的窗口答案是 sum - mn。
class Solution {public int maxScore(int[] cardPoints, int k) {int n cardPoints.length, sum 0, s 0, mn Integer.MAX_VALUE / 2;if (k n) return Arrays.stream(cardPoints).sum();k n - k;for (int l 0, r 0; r n; r) {s cardPoints[r];sum cardPoints[r];if (r - l 1 k) {mn Math.min(mn, s);s - cardPoints[l];}}return sum - mn;}
}
