713. Subarray Product Less Than K

二刷 06/2022

Version #1 Two Pointers

We can use two pointers is because all numbers are positive so that the product is increasing while we expand the length of subarray

Time O(N)

Space O(1)

Runtime: 11 ms, faster than 18.84% of Java online submissions for Subarray Product Less Than K.

Memory Usage: 68.9 MB, less than 60.76% of Java online submissions for Subarray Product Less Than K.

class Solution {

    public int numSubarrayProductLessThanK(int[] nums, int k) {

        long product = 1l;

        int count = 0;

        int slow = 0;

        // product is the product of all nums in subarray [slow, fast]

        for (int fast = 0; fast < nums.length; fast++) {

            product *= nums[fast];

            while (slow <= fast && product >= k) {

                product /= nums[slow];

                slow++;

            }

            count += fast - slow + 1;

        }

        return count;

    }

}

一刷

Two Pointers
key point: result set can be empty

beats 73.08 % 

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int left = 0;
        int right = 0;
        // [left, right]
        int product = 1;
        int result = 0;
        while (right < nums.length) {
            product *= nums[right];
            while (product >= k && left <= right) {
                product /= nums[left++];
            }
            // Result Set can be empty
            result += right - left + 1;
           
            // System.out.println(left + " " + right + " " + result);
            right++;
        }
        return result;
    }
}

853. Car Fleet

Version #2 HashMap

62.06 %
class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        if (position == null || position.length == 0 || speed == null || speed.length == 0 || position.length != speed.length) {
            return 0;
        }
        Map<Integer, Double> time = new HashMap<>();
        for (int i = 0; i < position.length; i++) {
            time.put(position[i], 1.0 * (target - position[i]) / speed[i]);
        }
        Arrays.sort(position);
        int fleet = 1;
        double currTime = time.get(position[position.length - 1]);
        double prevTime = currTime;
        for (int i = position.length - 2; i >= 0; i--) {
            currTime = time.get(position[i]);
            if (currTime > prevTime) {
                prevTime = currTime;
                fleet++;
            }
        }
        return fleet;
    }
}

Version #1 TreeMap
一刷
class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        TreeMap<Integer, Double> map = new TreeMap<>(Collections.reverseOrder());
        for (int i = 0; i < position.length; i++) {
            double time = (target - position[i]) / (double) speed[i];
            map.put(position[i], time);
        }
        int fleet = 0;
        double slowest = 0;
        // key -> position, value -> time
        for (double currTime : map.values()) {
            if (currTime > slowest) {
                fleet++;
                slowest = currTime;
            }
        }
        return fleet;
    }
}

852. Peak Index in a Mountain Array

二刷 05/2022

Version #1 Binary Search

Time O(logN)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Peak Index in a Mountain Array.

Memory Usage: 46.7 MB, less than 20.35% of Java online submissions for Peak Index in a Mountain Array.

class Solution {

    public int peakIndexInMountainArray(int[] arr) {

        if (arr == null || arr.length < 3) {

            return -1;

        }

        int start = 0, end = arr.length - 1;

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (arr[mid] < arr[mid + 1]) {

                start = mid + 1;

            } else {

                end = mid;

            }

        }

        if (arr[start] > arr[end]) {

            return start;

        }

        return end;

    }

}

一刷
Version #1 Binary Search
二分法的条件，不一定是left/right和mid比，找peak也可以是mid和自己左右比
[2ND TRY]
33.69 %
Should always take care of out of boundary exception
class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int start = 0;
        int end = A.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (mid != 0 && A[mid - 1] < A[mid] && A[mid] > A[mid + 1]) return mid;
            if (mid == 0 || A[mid - 1] < A[mid]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return start;
    }
}

[1ST TRY]
class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int left = 0;
        int right = A.length - 1;
        int mid = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (A[mid] < A[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

Version #2 One Pass
 8.24 %
class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int left = 0;
        int right = A.length - 1;
        while (left + 1 < right && A[left] < A[left + 1]) left++;
        while (right - 1 > left && A[right] < A[right - 1]) right--;
        return left;
     
    }
}

214. Shortest Palindrome

Version #1
Find the longest palindrome prefix
beats 17.77 %
Time O(n^2)
Space O(1)
class Solution {
    private int max;
    public String shortestPalindrome(String s) {
        // To find the longest palindrome prefix
        max = 0;
        for (int i = 0; i < s.length(); i++) {
            shortestPalindrome(s, i, i);
            shortestPalindrome(s, i, i + 1);
        }
        StringBuilder sb = new StringBuilder(s.substring(max, s.length()));
        sb = sb.reverse().append(s);
        return sb.toString();
    }
    private void shortestPalindrome(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // Is prefix
        if (left == -1) {
            max = Math.max(max, right - left - 1);
        }
    }
}

Version #2

125. Valid Palindrome

一刷
beats 80.01 %

class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() <= 1) return true;
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

二刷

Character.isLetter()

Character.isDigit()

Character.toLowerCase()

Character.toUpperCase()

Runtime: 4 ms, faster than 81.04% of Java online submissions for Valid Palindrome.

Memory Usage: 44 MB, less than 42.12% of Java online submissions for Valid Palindrome.

class Solution {

    public boolean isPalindrome(String s) {

        // We can create two pointers to scan toward each other

        // If a non-alphanumeric character is encountered, then skip that character

        if (s == null || s.equals("")) {

            return true;

        }

        //   l                         r

        // A man, a plan, a canal: Panama

        int left = 0, right = s.length() - 1;

        while (left < right) {

            while (left < right && !isAlphanumeric(s, left)) {

                left++;

            }

            while (left < right && !isAlphanumeric(s, right)) {

                right--;

            }

            if (left < right && Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {

                return false;

            }

            left++;

            right--;

        }

        return true;

    }

    

    private boolean isAlphanumeric(String s, int index) {

        char c = s.charAt(index);

        return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');

    }

}