【LeetCode每日一题合集】2023.11.27-2023.12.3 （⭐）

文章目录

907. 子数组的最小值之和（单调栈+贡献法）
1670. 设计前中后队列⭐（设计数据结构）
- 解法1——双向链表
- 解法2——两个双端队列
2336. 无限集中的最小数字
- 解法1——维护最小变量mn 和哈希表维护已经去掉的数字
- 解法2——维护原本可用的最小值和有序集合维护后期添加的数值👌
1657. 确定两个字符串是否接近（理解操作本质）⭐
2661. 找出叠涂元素（哈希表、计数统计）
1094. 拼车（差分）
1423. 可获得的最大点数（滑动窗口）

907. 子数组的最小值之和（单调栈+贡献法）

https://leetcode.cn/problems/sum-of-subarray-minimums/description/?envType=daily-question&envId=2023-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;
        // 计算每个数字作为最小值的贡献，即找到左右两侧第一个小于它的（一边严格小于，另一边小于等于）
        Deque<Integer> 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/?envType=daily-question&envId=2023-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/?envType=daily-question&envId=2023-11-28 的方法二。

解法2——两个双端队列

参考官方题解的思想和 0x3f的代码写的。

class FrontMiddleBackQueue {
    // 左边的双端队列和右边的双端队列等长 或恰好大1。可以保证中间节点是左队列的结尾节点
    Deque<Integer> 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/?envType=daily-question&envId=2023-11-29

在这里插入图片描述

解法1——维护最小变量mn 和哈希表维护已经去掉的数字

维护最小变量mn，哈希表记录已经去除的数字。
当新添加数字时，如果更小，则更新 mn 变量。

class SmallestInfiniteSet {
    int mn = 1;
    Set<Integer> 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 TreeSet<Integer> set;

    public SmallestInfiniteSet() {
        thres = 1;
        set = new TreeSet<Integer>();
    }

    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/?envType=daily-question&envId=2023-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/?envType=daily-question&envId=2023-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/?envType=daily-question&envId=2023-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/?envType=daily-question&envId=2023-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/?envType=daily-question&envId=2023-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;
    }
}