26. Remove Duplicates from Sorted Array

92.45 %
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        //  l   r
        // [0,0,1,1,1,2,2,3,3,4]
        int left = 0;
        int right = 0;
        for (right = 0; right < nums.length; right++) {
            if (nums[left] != nums[right]) {
                left++;
                nums[left] = nums[right];
            }
        }
        return left + 1;
    }
}

424. Longest Repeating Character Replacement

Two Pointers Sliding Window
一开始理解错题意了，以为window里面最多只有两种不同的char
后来发现是window里可以有最多k个和最大char不一样的char
每次需要维持count最大的char，一开始是以为是PriorityQueue
问题在于pq的remove time是O(m)
还不如直接扫一遍 m = 26约等于constant
67.66 %

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = -1;
        int right = 0;
        int max = 0;
        // (left, right]
        int curr;
        for (right = 0; right < s.length(); right++) {
            curr = s.charAt(right) - 'A';
            count[curr]++;
            while (check(count) > k) {
                left++;
                curr = s.charAt(left) - 'A';
                count[curr]--;
            }
            max = Math.max(max, right - left);
        }
        return max;
    }
    private int check(int[] count) {
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < count.length; i++) {
            sum += count[i];
            max = Math.max(max, count[i]);
        }
        return sum - max;
    }
}

84. Largest Rectangle in Histogram

Version #3 Array
Space O(n)
Time O(n)
用两个array分别记录当前index的最左边界和最右边界
tricky的地方在于如果i - 1比i 低，left[i]就是 i- 1
如果i-1比i 高，那么可以直接跳到left[i - 1]的那个点
It is O(n) because each left[i] can be skipped only once
If it has been skipped before, means there's some bar on its right which is lower than it, so it would never be touched again. We can only have a look at the left[x] of that x lower than it

99.69 %
class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int len = heights.length;
        //closest left index lower than current
        //closest right index higher than current
        int[] left = new int[len];
        int[] right = new int[len];
        left[0] = -1;
        right[len - 1] = len;
        int p = 0;
        for (int i = 1; i < len; i++) {
            p = i - 1;
            while (p >= 0 && heights[p] >= heights[i]) {
                p = left[p];
            }
            left[i] = p;
        }
        for (int j = len - 2; j >= 0; j--) {
            p = j + 1;
            while (p < len && heights[p] >= heights[j]) {
                p = right[p];
            }
            right[j] = p;
        }
        int max = 0;
        for (int k = 0; k < len; k++) {
            max = Math.max(max, heights[k] * (right[k] - left[k] - 1));
        }
        return max;
    }
}

Version #1 Stack
Time O(n)
Space O(n)
90.01 % 
class Solution {
    public int largestRectangleArea(int[] heights) {
        // Keep track of start height
        // if a lower rectangle is found, then that height ends, it should be poped up
        // up date the lower rectangle's start point as current point
        // curr[0] -> x, curr[1] -> height
        Deque<int[]> stack = new ArrayDeque<>();
        int max = 0;
        int[] prev;
        int i = 0;
        // [2,1,5,6,2,3]
        // (0, 1) (2, 5)(3, 6)
        for (i = 0; i < heights.length; i++) {
            int currHeight = heights[i];
            int x = i;
            while (!stack.isEmpty() && stack.peekFirst()[1] >= currHeight) {
                prev = stack.removeFirst();
                max = Math.max(max, prev[1] * (i - prev[0]));
                x = prev[0];
            }
            stack.addFirst(new int[]{x, currHeight});
        }
        while (!stack.isEmpty()) {
            prev = stack.removeFirst();
            max = Math.max(max, prev[1] * (i - prev[0]));
        }
        return max;
    }
}

Version #2 Stack
89.55 %
和上面方法一样但是更巧妙，用stack里面的上一个index作为左边界
class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int x = 0;
        int max = 0;
        int left = 0;
        int i = 0;
        for (i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peekFirst()] >= heights[i]) {
                x = stack.removeFirst();
                // left bound is its previous in stack
                left = stack.isEmpty() ? -1 : stack.peekFirst();
                // right bound is current index
                max = Math.max(max, heights[x] * (i - left - 1));
            }
            stack.addFirst(i);
        }
        while (!stack.isEmpty()) {
            x = stack.removeFirst();
            left = stack.isEmpty() ? -1 : stack.peekFirst();
            max = Math.max(max, heights[x] * (i - left - 1));
        }
        return max;
    }
}

134. Gas Station

二刷 06/2022

Version #2 Two Passes

基本上是照着答案才写出来

Runtime: 1 ms, faster than 100.00% of Java online submissions for Gas Station.

Memory Usage: 62.1 MB, less than 92.15% of Java online submissions for Gas Station.

class Solution {

    public int canCompleteCircuit(int[] gas, int[] cost) {

        //step1 start from index 0, try the furthest index that we can reach

        //step2 if we stopped at index i, try start from index i+1 and retry step1

        // It is guaranteed that if we start at index i and stoped at j(j > i), all indexes between index [i, j] won't be the answer, since the real_gas[k]=remaining gas before k + gas[k], which is larger than or equals to gas[k], if we cannot finish the trip with the real_gas[k], then we definitly cannot finish the trip with gas[k]

        int total = 0;

        for (int i = 0; i < gas.length; i++) {

            total += gas[i] - cost[i];

        }

        if (total < 0) {

            return -1;

        }

        // We just need to find the start point

        int diff = 0;

        int startIndex = 0;

        for (int i = 0; i < gas.length; i++) {

            diff += gas[i] - cost[i];

            if (diff < 0) {

                startIndex = i + 1;

                diff = 0;

            }

        }

        return startIndex;

    }

}

Version #1 Two Pointer
如果当前start得到的sum为负，就必须向前搜其他的start point
如果当前的为正，就可以尝试向后走
问题是最终返回的时候，如果最终start和end相遇时sum都为负，则不存在解
二刷

100.00 %
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // the difference between gasSum - costSum must always larger or equals to zero
        // (startIndex, endIndex]
        int len = gas.length;
        int diff = 0;
        int startIndex = len, endIndex = 0;
        while (startIndex > endIndex) {
            diff += gas[endIndex] - cost[endIndex];
            endIndex++;
            while (startIndex > endIndex && diff < 0) {
                startIndex--;
                diff += gas[startIndex] - cost[startIndex];
            }
        }
        return diff >= 0 ? startIndex % len : -1;
    }
}

一刷

100.00 %
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int start = gas.length;
        int end = 0;
        int sum = 0;
        // [start, end)
        while (start > end) {
            sum += gas[end] - cost[end];
            while (start > end && sum < 0) {
                start--;
                sum += gas[start] - cost[start];
            }
            end++;
        }
        return sum < 0 ? -1 : start % gas.length;
    }
}

268. Missing Number

class Solution {
    public int missingNumber(int[] nums) {
        long expected = nums.length * (nums.length + 1) / 2;
        for (int n : nums) {
            expected -= n;
        }
        return (int) expected;
    }
}

345. Reverse Vowels of a String

Two Pointers
Time O(N)
60.04 %
class Solution {
    public String reverseVowels(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
        char[] chars = s.toCharArray();
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            while (left < right && !vowels.contains(chars[left])) {
                left++;
            }
            while (left < right && !vowels.contains(chars[right])) {
                right--;
            }
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
        return new String(chars);
    }
}

245. Shortest Word Distance III

word1 ... word1 ... word1 ... word2
always update lastIndex no matter it is a pair or not


50.68 %
class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        int lastIndex = -1;
        int min = words.length;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                if (lastIndex != -1 && words[lastIndex].equals(word2)) {
                    min = Math.min(min, i - lastIndex);
                }
                lastIndex = i;
            } else if (words[i].equals(word2)) {
                if (lastIndex != -1 && words[lastIndex].equals(word1)) {
                    min = Math.min(min, i - lastIndex);
                }
                lastIndex = i;
            }
        }
        return min;
    }
}