LeetCode 621

Link: leetcode.com/problems/ta…

Method: Find a pattern

Time complexity: O(tasks.length) Idea: see leetcode-cn.com/problems/ta… The first case: when MX is large, we can imagine that the total interval is basically determined by the highest frequency letter. Because they’re asking for the fewest intervals so that everything gets done, so the most frequent task you’re going to get done anyway, let’s say the most times that ‘K’ occurs, so there’s a certain amount of space between each of the two ‘K’ s, so there’s enough space between them, so that all the other tasks get done pretty much, Except for the same frequency as ‘K’. So in this case, it’s mx-1 times n plus 1 plus how many letters have the same frequency as ‘K’. Case number two: we can quickly think of counterexamples to that after we’ve done that, let’s say that ‘K’ doesn’t happen a lot, let’s say three times, and n is a little bit small, let’s say one, and then there’s a lot of different letters. In this case, the ‘K’ doesn’t leave enough space for the rest of the letters to be almost empty, which is not the case. In this case, instead of using the same strategy as in the first case, let’s say we have A4B4C3D3E3F3G2, n=2, and the array length is 22. In this case, we play as many types of letters as possible in each round, in the order ABCDEFGABCDEFGABCDEFAB. At this time, because there are enough types of letters, each same letter is stretched far enough before the cooling time, so there is no idle, and it is directly finished with the time of tasks.length. Code:

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] cnt = new int[26];
        for (char c : tasks) {
            cnt[c - 'A']++;
        }
        
        Arrays.sort(cnt);
        int mx = cnt[25], i = 25;
        for (; i >= 0; i--) {
            if (cnt[i] != mx) {
                break;
            }
        }
        
        return Math.max(tasks.length, (mx - 1) * (n + 1) + 25 - i);
    }
}
Copy the code

LeetCode 581

Link: leetcode.com/problems/sh…

Method: greedy, or monotonous stack

Time complexity: O(n) Idea: Monotonous stack approaches are really want to, is the left endpoint of the interval, for example, make a stack, and then is monotone increasing stack, if back scan have been growing, has been put things inside the stack, if there is a value to a time than drab little stack stack, that while loop pop up the stack, but actually also can’t again to put the new element, that’s all. And when we’re done, we’re left with the left side of the stack. You can do the same thing on the right-hand side, and then you have the middle segment that needs to be sorted. Of course the easiest way to do this is to be greedy. And notice that the right end of this interval, if you keep sweeping from left to right, is the last place that’s not the maximum value of all the elements before. The left endpoint, you’re going from right to left, and the last one is not the minimum of all the previous elements. Notice that and just scan it. Code:

class Solution { public int findUnsortedSubarray(int[] nums) { int i = 0, j = -1, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE; for (int l = 0, r = nums.length-1; r >= 0; l++, r--){ max = Math.max(max, nums[l]); if (nums[l] ! = max) j = l; min = Math.min(min, nums[r]); if (nums[r] ! = min) i = r; } return (j - i + 1); }}Copy the code

LeetCode 503

Link: leetcode.com/problems/ne…

Method: monotone stack

Time complexity: O(n) Idea: Monotonous stack again. So the way I started thinking about it is imagine making a copy of this array, and then joining these two together. I’m just going to put the one on the stack, and then the one on the left, I’m going to scan backwards, mindlessly looking for the next one on the stack that’s bigger than that. The beat rate is low, but I think it’s mainly intuitive. Code:

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int n = nums.length;
        
        for (int i = n - 1; i >= 0; i--) {
            stack.push(i);
        }
        
        int[] res = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? -1 : nums[stack.peek()];
            stack.push(i);
        }
        
        return res;
    }
}
Copy the code

If you do a monotone decrement stack and scan from left to right, every time you encounter an element larger than the top of the stack, the element larger than itself to the right of the top of the stack is the value that you are walking through now. That way you don’t have to do a bunch of pushing stuff at the beginning.

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        
        for (int i = 0; i < 2 * n; i++) {
            int num = nums[i % n];
            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                res[stack.peek()] = num;
                stack.pop();
            }
            if (i < n) {
                stack.push(i);
            }
        }
        
        return res;
    }
}
Copy the code

LeetCode 442

Link: leetcode.com/problems/fi…

Method: Brainstorm

Time complexity: O(n) Idea: I think the brainstorming for this question is not entirely out of the question. There are several questions in LeetCode that limit the number length to N and the number to [1,n] range. In the future, I will write an idea to convert this type of question into Linked List Cycle II. But anyway, this type of problem is saying, if you get a value somewhere, it’s at [1,n] directly, you can’t cross the line by using the value -1 as an index. So in this case, we’re essentially doing things on the old array, and since we’re not going to open a new hash table, we’re going to use the old array to record things. He says there are only two possible values in this array that occur once or twice. So using the idea above, since you can appear twice, if I visit another place with the value as the subscript, that place will be visited twice. And they say the initial values are all positive integers, so we’re just going to once we get to that place, we’re going to set the values there as negative values, and then the next time you run over here you’ll know that you’ve been here before, and then the value that led you to that place, it’s going to happen twice. Code:

class Solution { public List<Integer> findDuplicates(int[] nums) { List<Integer> res = new ArrayList<>(); for (int num : nums) { num = Math.abs(num); int target = nums[num - 1]; if (target < 0) { res.add(num); } else { nums[num - 1] = -target; } } return res; }}Copy the code