Day 33 of LeetCode

Documenting LeetCode solving.

Q95

58. Length of Last Word

Easy. String

class Solution {
    public int lengthOfLastWord(String s) {
        // eliminate front and end spaces
        s = s.trim();

        int n = s.length();
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == ' ') {
                return (n - i - 1);
            }
        }

        return n;

    }
}

Q96

20. Valid Parentheses

Easy. String

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> pair = new HashMap<>();
        pair.put(')', '(');
        pair.put('}', '{');
        pair.put(']', '[');

        Stack<Character> stack = new Stack();

        for (char c : s.toCharArray()) {
            if (pair.containsValue(c)) {
                stack.push(c);
            }
            else {
                if (!stack.isEmpty() && stack.peek() == pair.get(c)) {
                    stack.pop();
                }
                else {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

Q97

344. Reverse String

Easy.

class Solution {
    public void reverseString(char[] s) {
        int l = 0, r = s.length - 1;
        while (l < r) {
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++;
            r--;
        }
    }
}

Q98

Given a String that represents a number, print the number; unless greater than 1 million, then print number as millions with one significant digit; unless billion or trillion. (i.e: 12,300,000 -> 12.3M)

import java.math.BigDecimal;
import java.math.RoundingMode;

class HelloWorld {

    public static void printFormatted(String s) {
        s = s.replace(",", "");
        BigDecimal number = new BigDecimal(s);
        BigDecimal million = new BigDecimal("1000000");
        BigDecimal billion = new BigDecimal("1000000000");
        BigDecimal trillion = new BigDecimal("1000000000000");

        if (number.compareTo(million) < 0) {
            System.out.println(number.toPlainString());
        }
        else if (number.compareTo(million) >= 0 && number.compareTo(billion) < 0) {
            System.out.println(number.divide(million).setScale(1,  RoundingMode.HALF_UP) + "M");
        }
        else if (number.compareTo(billion) >= 0 && number.compareTo(trillion) < 0) {
            System.out.println(number.divide(billion).setScale(1,  RoundingMode.HALF_UP) + "B");
        }
        else {
            System.out.println(number.divide(trillion).setScale(1,  RoundingMode.HALF_UP) + "T");
        }
    }

    public static void main(String[] args) {
        printFormatted("9999");
        printFormatted("19,999");
        printFormatted("23,129,999");
        printFormatted("999,234,999,999");
        printFormatted("76,999,234,999,999");

    }

}

R18

76. Minimum Window Substring

Hard.

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();

        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int l = 0, r = 0;
        int match = 0;
        int start = 0;
        int minLen = Integer.MAX_VALUE;

        while (r < s.length()) {
            char rc = s.charAt(r);
            r++;
            if (need.containsKey(rc)) {
                window.put(rc, window.getOrDefault(rc, 0) + 1);
                if (need.get(rc).equals(window.get(rc))) {
                    match++;
                }
            }

            while (match >= need.size()) {
                if (r - l < minLen) {
                    start = l;
                    minLen = r - l;
                }
                char lc = s.charAt(l);
                l++;
                if (need.containsKey(lc)) {
                    if (need.get(lc).equals(window.get(lc))) {
                        match--;
                    }
                    window.put(lc, window.get(lc) - 1);         
                }
            }
        }
        // remember to check invalid output
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

R19

239. Sliding Window Maximum

Hard.

class Solution {

    class MyQueue {
        LinkedList<Integer> q = new LinkedList<>();

        public void push(int x) {
            while (!q.isEmpty() && q.getLast() < x) {
                q.pollLast();
            }
            q.addLast(x);
        }

        public void pop(int x) {
            if (x == q.getFirst()) {
                q.pollFirst();
            }
        }

        public int max() {
            return q.getFirst();
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        MyQueue window = new MyQueue();
        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (i < k - 1) {
                window.push(nums[i]);
            }
            else {
                window.push(nums[i]);
                res.add(window.max());
                window.pop(nums[i - k + 1]);
            }
        }

        int[] arr = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            arr[i] = res.get(i);
        }

        return arr;
    }
}