Leetcode record - July 2023

关于区间集合：

这个问题的难点在于如何有效地处理会议的冲突。具体来说，需要在每个时间点追踪哪些会议正在进行，然后决定是否需要额外的会议室。下面是一些思考的建议和线索：

排序：这是一个重要的线索。当你看到这种需要比较或者组织时间区间的问题时，排序通常是一个有用的第一步。在本问题中，按照开始时间对会议进行排序可以帮助我们逐个地处理会议，确保我们先处理开始时间早的会议。
优先队列（最小堆）：在处理一系列事件，其中每个事件都有开始和结束时间，并且可能会发生冲突的情况下，优先队列（特别是最小堆）经常会被用到。在本问题中，我们需要知道当前正在进行的所有会议中最早结束的那一个，以决定是否需要一个新的会议室。最小堆正好可以提供这个功能，因为它总是把最小的元素放在前面。
贪心思想：这是一个隐藏的线索。这个问题可以通过一种贪心的方式来解决，即总是尽可能地复用会议室。具体来说，每次当一个新的会议开始时，如果有一个会议已经结束，那么我们就可以在同一个会议室举行这个新的会议，而不需要新开一个会议室。这个策略保证了我们总是使用最少数量的会议室。
重叠区间问题：类似的问题经常出现在算法问题中，所以可以作为一个模式来识别。当你看到需要处理重叠区间的问题时，可以想到使用排序和优先队列来解决。

在碰到这类问题时，练习和经验也很重要。一开始可能不容易看出解决方案，但通过解决更多的类似问题，你将能够更容易地识别出相应的模式，并找到正确的方法来解决这类问题。

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]] Output: 2

Example 2:

Input: intervals = [[7,10],[2,4]] Output: 1

Constraints:

1 <= intervals.length <= 104
0 <= starti < endi <= 106

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b)->Integer.compare(a[0], b[0]));
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.add(intervals[0][1]);
        int res = 1;
        for(int i = 1;i<intervals.length;i++){
            if(intervals[i][0]>=heap.peek()){
                heap.poll();
            }else{
                res++;
            }
            heap.add(intervals[i][1]);
        }
        return res;
    }
}

这段代码的主要结构和组成：

首先，代码按照每个会议的开始时间进行排序。这样，我们可以依次处理每个会议，并确保我们在处理任何一个会议之前已经处理完了所有开始时间更早的会议。
然后，代码创建了一个最小堆（PriorityQueue），用来跟踪所有当前正在进行的会议的结束时间。这样，我们可以快速找到最早结束的会议。

接下来，我会详细解释这段代码的每一步：

heap.add(intervals[0][1]); 这行代码把第一个会议的结束时间添加到了堆中。因为这是第一个会议，所以我们一定需要一个会议室来举行这个会议。
然后，代码进入了一个循环，依次处理每一个会议。对于每一个会议，它首先检查这个会议的开始时间是否晚于当前最早结束的会议的结束时间（if(intervals[i][0] >= heap.peek()){...}）。如果是的话，那么我们可以在同一个会议室举行这个新的会议，因此我们从堆中移除最早结束的会议的结束时间（heap.poll();），并把新的会议的结束时间添加到堆中（heap.add(intervals[i][1]);）。如果不是的话，那么我们需要一个新的会议室来举行这个会议，因此我们直接把新的会议的结束时间添加到堆中（heap.add(intervals[i][1]);）。
最后，当所有的会议都被处理完之后，堆中剩下的元素数量就是我们需要的会议室的数量。因为对于堆中的每一个元素，都存在一个正在进行的会议或者将要进行的会议，而且这些会议的时间都是有冲突的，所以我们需要为堆中的每一个元素提供一个会议室。因此，我们返回了堆的大小（return heap.size();），作为最小需要的会议室的数量。

616. Add Bold Tag in String

You are given a string s and an array of strings words.

You should add a closed pair of bold tag and to wrap the substrings in s that exist in words.

If two such substrings overlap, you should wrap them together with only one pair of closed bold-tag. If two substrings wrapped by bold tags are consecutive, you should combine them. Return s after adding the bold tags.

Example 1:

Input: s = "abcxyz123", words = ["abc","123"] Output: "abcxyz123"

Input: s = "aaabbb", words = ["aa","b"] Output: "aaabbb"

class Solution {
    public String addBoldTag(String s, String[] words) {
        int n = s.length();
        boolean[] bold = new boolean[n + 2];
        for (String word : words) {
            int i = -1;
            i = s.indexOf(word, i + 1);
            while (i!= -1) {
                for(int j = i;j<i+word.length();j++){
                    bold[j] = true;
                }
                i = s.indexOf(word, i + 1);
            }
        }
        
        StringBuilder ans = new StringBuilder();
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            if (bold[i] && (i == 0 || !bold[i - 1])) {
                ans.append("<b>");
            }
            ans.append(s.charAt(i));
            if (bold[i] && !bold[i + 1]) {
                ans.append("</b>");
            }
        }
        return ans.toString();
    }
}

不同与上一题的处理思路，这里设置了一个bold数组来记录每一位的状态（因为数据为String，遍历次数少，如果上一题的话时间复杂度达到了N^2，可能会超时）。区间集合问题有时需要关注两端（头和尾），有时可以采取像这样区间合并的方法。

1272. Remove Interval

A set of real numbers can be represented as the union of several disjoint intervals, where each interval is in the form [a, b). A real number x is in the set if one of its intervals [a, b) contains x (i.e. a <= x < b).

You are given a sorted list of disjoint intervals intervals representing a set of real numbers as described above, where intervals[i] = [ai, bi] represents the interval [ai, bi). You are also given another interval toBeRemoved.

Return the set of real numbers with the interval toBeRemoved removed from intervals. In other words, return the set of real numbers such that every x in the set is in intervals but not in toBeRemoved. Your answer should be a sorted list of disjoint intervals as described above.

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6] Output: [[0,1],[6,7]]

//分类讨论
class Solution {
    //intervals[i][j] >= toBeRemoved[0] && intervals[i][j] <= toBeRemoved[1]
    public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
    
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0;i<intervals.length;i++){
            if(intervals[i][1] < toBeRemoved[0] || intervals[i][0] > toBeRemoved[1]){
                res.add(new ArrayList<Integer>(Arrays.asList(intervals[i][0], intervals[i][1]))); 
            }else{
// From toBeRemoved's point of view!
                if (intervals[i][0] < toBeRemoved[0]) {
                    res.add(Arrays.asList(intervals[i][0], toBeRemoved[0]));
                }
                if (intervals[i][1] > toBeRemoved[1]) {
                    res.add(Arrays.asList(toBeRemoved[1], intervals[i][1]));
                }
            }
        }
        return res;
    }
}

关于栈

遇到问题时的关键词：反转

439. Ternary Expression Parser

Input: expression = “F?1:T?4:5” Output: “4” Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as: “(F ? 1 : (T ? 4 : 5))” –> “(F ? 1 : 4)” –> “4” or “(F ? 1 : (T ? 4 : 5))” –> “(T ? 4 : 5)” –> “4”

class Solution {
    public String parseTernary(String expression) {
        if (expression == null || expression.length() == 0) return "";
        Stack<Character> stack = new Stack<>();
        for (int i = expression.length() - 1; i >= 0; i--) {
            char c = expression.charAt(i);
            if (!stack.isEmpty() && stack.peek() == '?') {
                // Pop '?' symbol
                stack.pop();
                char first = stack.pop();
                // Pop ':' symbol
                stack.pop();
                char second = stack.pop();
                //for every ternary expression, only left one value. So in 
                // the enad, there is only one value.
                if (c == 'T') {
                    stack.push(first);
                } else if (c == 'F') {
                    stack.push(second);
                }

            } else {
                stack.push(c);
            }
        }

        return String.valueOf(stack.peek());
    }
}

三元表达式从右向左扫描更简单和方便

**484. Find Permutation

Input: s = “DI” Output: [2,1,3] Explanation: Both [2,1,3] and [3,1,2] can be represented as “DI”, but since we want to find the smallest lexicographical permutation, you should return [2,1,3]

class Solution {
    public int[] findPermutation(String s) {
        int lens = s.length();
        Stack<Integer> st = new Stack<>();
        int []ret = new int[s.length()+1];
        int index = 0;
        for(int i = 0; i < lens; i++) {
            st.push(i+1);
            if(s.charAt(i) == 'I'){
                while(!st.isEmpty()){
                    ret[index] = st.pop();
                    index++;
                }
            }
        }
        st.push(lens+1);
        while(!st.isEmpty()){
            ret[index] = st.pop();
            index++;
        }
        return ret;
    }
}

理解这个问题的关键在于理解题目中的 “lexicographically smallest” 和 “I”、“D” 这两个条件的含义，并根据这些条件来进行思考。

“Lexicographically smallest”：这意味着你希望在可能的所有满足条件的数组中，你希望数字尽可能的靠前，尤其是在比较高位的数字。
“I” 和 “D”：这两个条件给你提供了数组中相邻元素之间的关系。“I” 表示下一个数字比当前数字大，“D” 表示下一个数字比当前数字小。

将这两个条件结合，你可以得到这样的想法：在满足 “I” 和 “D” 条件的同时，尽可能地让数组的每一位都尽可能小，那么最直观的想法就是在满足条件的情况下，尽可能使用较小的数字。于是，一个自然的想法是，每次遇到 “I” 时，就尽可能地使用小的数字，而每次遇到 “D” 时，由于要比前一个数字小，所以可能需要使用较大的数字，但我们希望它尽可能小，所以会尽量延后选择，直到遇到 “I” 或者字符串结束时，再进行选择。

再深一步，我们会注意到，字符串中的 “D” 总是连续出现的，而且 “I” 和 “D” 是交替出现的。这时，我们可以联想到 “反转” 这个操作，也就是说，每次遇到一段连续的 “D”，我们可以先顺序选择数字，然后在最后进行反转，这样就可以满足 “D” 的条件，同时又保证了字典序最小。

2050. Parallel Courses III

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        int[] in = new int[n];
        for (int[] e : relations) {
            int pre = e[0] - 1, then = e[1] - 1;
            g[pre].add(then);
            ++in[then];
        }
        // 0: 1     1: 1       2: 2     3: 1     4:0
//入度 = 0：此课无任何先修课程要求
        Queue <Integer> q = new ArrayDeque<>();
        int[] f = new int[n];
        int ans = 0;
        for(int i = 0;i<n;i++){
            if(in[i] ==0){
                q.add(i);
                f[i] = time[i];
                ans = Math.max(ans, time[i]); //处理edge case
            }
        }
        while(!q.isEmpty()){
            int tmp = q.poll();
            for(int j: g[tmp]){
                in[j] --;
                f[j] = Math.max(f[j],f[tmp]+time[j]);
                ans = Math.max(ans, f[j]);
                if(in[j] == 0){
                    q.add(j);
                }
            }
        }
        return ans;
    }
};
//51243

难点主要在于将拓扑排序和动态规划结合。

关于栈#

关于栈