System Design[TODO]

5分钟超过一千次算恶意访问 怎么写程序探测这个恶意访问

228. Summary Ranges

Your input

[0,1,2,4,5,7]

Your answer

["0->1->2","4->5"]

Expected answer

["0->2","4->5","7"]

Input:[0,2,3,4,6,8,9]

Output:["0->0","2->4","6->6","8"]

Expected:["0","2->4","6","8->9"]

50.15 %

// LC228 Beats 50.15 %
// There are 2 edge cases:
// 1.start == end like "6->6" should be treated as a single number "6"， so we should check prev != start
// 2. Since discontinuous gap triggers adding String to result, the last String won't be added. We should deal with it before return
class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        if (nums == null || nums.length <= 0) return result;
        int prev = nums[0];
        int start = prev;
        StringBuilder sb = new StringBuilder();
        sb.append(start);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != prev + 1) {
                if (start != prev) sb.append("->" + prev);
                result.add(sb.toString()); // add previous String to result
                sb.setLength(0); // clear StringBuilder
                start = nums[i];
                sb.append(start); // new Starting point
            }
            prev = nums[i];
        }
        if (sb.length() != 0) {
            if (start != prev) sb.append("->" + prev);
            result.add(sb.toString());
        }
        return result;
    }
}

720. Longest Word in Dictionary

Version #1 Trie + DFS
因为只有length 比当前的max大才会Update，所以保证了当有不只一个max的时候，返回的是 smallest lexicographical order

91.21 %
// Time O(n*l) Space O(n*l) -> n:possible words count, l:average word length
class Solution {
    class TrieNode {
    TrieNode[] children;
    boolean isWord;
    public TrieNode() {
        children = new TrieNode[26];
    }
}
class Trie {
    TrieNode root;
    public Trie(String[] words) {
        root = new TrieNode();
        for (String word : words) {
            this.insert(word);
        }
    }
    public void insert(String word) {
        TrieNode curr = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (curr.children[index] == null) {
                curr.children[index] = new TrieNode();
            }
            curr = curr.children[index];
        }
        curr.isWord = true;
    }
}
    public String longestWord(String[] words) {
        if (words == null || words.length == 0) return "";
        Trie trie = new Trie(words);
        String[] result = new String[]{""};
        dfs(trie.root, result, new StringBuilder());
        return result[0];
    }
    private void dfs(TrieNode currNode, String[] result, StringBuilder sb) {
        TrieNode[] children = currNode.children;
        boolean flag = false;
        for (int i = 0; i < children.length; i++) {
            if (children[i] != null && children[i].isWord) {
                flag = true;
                sb.append((char)('a' + i));
                dfs(children[i], result, sb);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        if (!flag && sb.length() > result[0].length()) {
            result[0] = sb.toString();
        }
    }
 
}

Version #2 HashSet

二刷
class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> set = new HashSet<>();
        String result = "";
        for (String word : words) {
            if (word.length() == 1 || set.contains(word.substring(0, word.length() - 1))) {
                set.add(word);
                if (word.length() > result.length()) {
                    result = word;
                }
            }
        }
        return result;
    }
}

一刷
 60.70 % 
// Time O(nlogn) Space O(n*l)
class Solution {
    public String longestWord(String[] words) {
        if (words == null || words.length == 0) return "";
        Arrays.sort(words);
        Set<String> dict = new HashSet<>();
        String result = "";
        for (String word : words) {
            if (word.length() == 1 || dict.contains(word.substring(0, word.length() - 1))) {
                dict.add(word);
                if (word.length() > result.length()) result = word;
            }
        }
        return result;
    }
}

698. Partition to K Equal Sum Subsets

Version #1 DFS

89.41 % 

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (nums == null || k <= 0 || nums.length < k) return false;
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % k != 0) return false;
        int target = sum / k;
        Arrays.sort(nums); // Must sort and add from larger elements
        boolean[] visited = new boolean[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            if (!visited[i] && !partition(nums, i, visited, target)) return false;
        }
        return true;
    }
    public boolean partition(int[] nums, int start, boolean[] visited, int target) {
        if (nums[start] > target) return false;
        // nums[start] <= target
        visited[start] = true;
        if (nums[start] == target) {
            return true; // no need to reset, marked as visited
        }
        for (int i = start - 1; i >= 0; i--) {
            if (visited[i]) continue; // make sure nums[i] is not visited
            if (partition(nums, i, visited, target - nums[start])) return true;
        }
        visited[start] = false;
        return false;
    }
}

692. Top K Frequent Words

Version #1 Sort All with Lambda
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> wordCount = new HashMap<>();
        Integer tempCount = null;
        List<String> distinctWords = new ArrayList<>();
        // O(n) Space + O(n) Time to get Count
        for (String word : words) {
            tempCount = wordCount.get(word);
            if (tempCount == null) {
                wordCount.put(word, 1);
                distinctWords.add(word);
            } else {
                wordCount.put(word, tempCount + 1);
            }
            tempCount = null;
        }
        Collections.sort(distinctWords, (s1, s2) -> {
            if (wordCount.get(s1) == wordCount.get(s2)){
                return s1.compareTo(s2);
            } else {
                return wordCount.get(s2).compareTo(wordCount.get(s1));
            }
        });
        return distinctWords.subList(0, k);
    }
}

252. Meeting Rooms

二刷
100.00 %
sort start and end points separately
class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return true;
        }
        int size = intervals.length;
        // s s  e   e
        int[] starts = new int[size];
        int[] ends = new int[size];
        for (int i = 0; i < size; i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        for (int i = 0; i < size; i++) {
            if (i != 0 && starts[i] < ends[i - 1]) {
                return false;
            }
        }
        return true;
    }
}

一刷
41.11 %
class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        if (intervals == null || intervals.length <= 1) return true;
        Arrays.sort(intervals, (i1, i2) -> i1.start - i2.start);
        Interval prev = null;
        for (Interval interval : intervals) {
            if (prev == null) {
                prev = interval;
                continue;
            }
            if (interval.start < prev.end) return false;
            prev = interval;
        }
        return true;
    }
}

384. Shuffle an Array

三刷 07/2022

Version #1 Randomly swap

Time O(N)

Space O(N)

Runtime: 75 ms, faster than 74.21% of Java online submissions for Shuffle an Array.

Memory Usage: 65.6 MB, less than 64.08% of Java online submissions for Shuffle an Array.

class Solution {

    int[] arr;

    Random rd;

    public Solution(int[] nums) {

        this.arr = nums;

        this.rd = new Random();

    }

    

    public int[] reset() {

        return arr;

    }

    

    public int[] shuffle() {

        int[] nums = arr.clone();

        for (int i = nums.length - 1; i >= 0; i--) {

            int j = rd.nextInt(i + 1);

            // System.out.printf("i=%d,j=%d\n", i, j);

            swap(nums, i, j);

        }

        return nums;

    }

    

    private void swap(int[] nums, int i, int j) {

        if (i == j) {

            return;

        }

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

}

/**

 * Your Solution object will be instantiated and called as such:

 * Solution obj = new Solution(nums);

 * int[] param_1 = obj.reset();

 * int[] param_2 = obj.shuffle();

 */

二刷 06/2022

Version #1 Randomly swap

重点是nextInt的时候一定是nextInt(i + 1)因为也有概率和自己swap

同时nums.clone对于primitive type是deep copy对于object是shallow copy

Time O(N)

Space O(N)

Runtime: 54 ms, faster than 85.79% of Java online submissions for Shuffle an Array.

Memory Usage: 48 MB, less than 94.38% of Java online submissions for Shuffle an Array.

class Solution {

    private int[] originalNums;

    public Solution(int[] nums) {

        originalNums = nums;

    }

    

    public int[] reset() {

        int[] copy = originalNums.clone();

        return copy;

    }

    

    public int[] shuffle() {

        int[] copy = originalNums.clone();

        Random rd = new Random();

        for (int i = copy.length - 1; i > 0; i--) {

            int j = rd.nextInt(i + 1);

            int temp = copy[i];

            copy[i] = copy[j];

            copy[j] = temp;

        }

        return copy;

    }

}

/**

 * Your Solution object will be instantiated and called as such:

 * Solution obj = new Solution(nums);

 * int[] param_1 = obj.reset();

 * int[] param_2 = obj.shuffle();

 */

一刷
92.78 %
class Solution {
    int[] nums;
    public Solution(int[] nums) {
        this.nums = nums;
    }
   
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return nums;
    }
   
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        if (nums == null) return null;
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[i] = nums[i];
        }
        Random rd = new Random();
        for (int i = result.length - 1; i > 0; i--) {
            int index = rd.nextInt(i + 1); // randomly pick a number from [0, i]
            int temp = result[index];
            result[index] = result[i];
            result[i] = temp;
           
        }
        return result;
    }
}

119. Pascal's Triangle II

49.87 %
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<>();
        if (rowIndex < 0) return result;
        for (int x = 0; x <= rowIndex; x++) {
            result.add(1);
            for (int y = x - 1; y > 0; y--) {
                result.set(y, result.get(y) + result.get(y - 1));
            }
        }
        return result;
       
    }
}

383. Ransom Note

二刷 08/2022

Version #1 Array as counter map

Time O(M + N)

Space O(1)

Runtime: 5 ms, faster than 74.47% of Java online submissions for Ransom Note.

Memory Usage: 44.8 MB, less than 85.10% of Java online submissions for Ransom Note.

class Solution {

    public boolean canConstruct(String ransomNote, String magazine) {

        int[] count = new int[26];

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

            count[magazine.charAt(i) - 'a']++;

        }

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

            if (--count[ransomNote.charAt(i) - 'a'] < 0) {

                return false;

            }

        }

        return true;

    }

}

一刷

对于 “” “” 的情况要在最后判断一下

 61.66 %

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote == null || magazine == null) return false;
        int[] counter = new int[256];
        int match = 0;
        for (int i = 0; i < ransomNote.length(); i++) {
            counter[ransomNote.charAt(i)]++;
            match++;
        }
        for (int j = 0; j < magazine.length(); j++) {
            if (counter[magazine.charAt(j)] > 0) {
                counter[magazine.charAt(j)]--;
                match--;
            }
            if (match == 0) return true;
        }
        return match == 0;
    }
}

165. Compare Version Numbers

11.57 %
class Solution {
    public int compareVersion(String version1, String version2) {
        if (version1 == null || version2 == null) return 0;
        String[] array1 = version1.split("\\.");
        String[] array2 = version2.split("\\.");
        int i = 0;
        for (i = 0; i < array1.length || i < array2.length; i++) {
            Integer v1 = i < array1.length ? Integer.valueOf(array1[i]) : 0;
            Integer v2 = i < array2.length ? Integer.valueOf(array2[i]) : 0;
            int compare = v1.compareTo(v2);
            if (compare != 0) return compare;
        }
        return 0;
    }
}

7. Reverse Integer

 67.49 %
class Solution {
    public int reverse(int x) {
        // x = -123, return -321
        int result = 0;
        int currResult = 0;
        int tail = 0;
        while (x != 0) {
            tail = x % 10;
            currResult = result * 10 + tail;
            if ((currResult - tail) / 10 != result) return 0;
            result = currResult;
            x /= 10;
        }
        return result;
    }
}

190. Reverse Bits

二刷 06/2022

Version #2

Time O(32)

Space O(1)

Runtime: 2 ms, faster than 27.48% of Java online submissions for Reverse Bits.

Memory Usage: 41.5 MB, less than 91.42% of Java online submissions for Reverse Bits.

public class Solution {

    // you need treat n as an unsigned value

    public int reverseBits(int n) {

        int result = 0;

        for (int i = 0; i < 32; i++) {

            result = (result << 1) + (n & 1);

            n >>>= 1;

        }

        return result;

    }

}

一刷

Version #2
12.19 %
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n >>>= 1;
        }
        return result;
    }
}


Version # 1 swap
28.24 %
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        for (int i = 0; i < 16; i++) {
            n = swapBits(n, i, 32 - i - 1);
        }
        return n;
    }
    private int swapBits(int n, int i, int j) {
        int a = (n >>> i) & 1;
        int b = (n >>> j) & 1;
        if ((a ^ b) != 0) {
            return n ^= (1 << i) | (1 << j);
        }
        return n;
    }
}

171. Excel Sheet Column Number

33.93 %

class Solution {
    public int titleToNumber(String s) {
        if (s == null || s.length() == 0) return 0;
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            // 'A' -> 1
            result = result * 26 + curr - 'A' + 1;
        }
        return result;
    }
}

168. Excel Sheet Column Title

5.18 %
class Solution {
    public String convertToTitle(int n) {
        if (n <= 0) return null;
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            n--;
            sb.insert(0, (char)('A' + n % 26));
            n /= 26;
        }
        return sb.toString();
    }
}

36. Valid Sudoku

三刷
53.79 %
class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<Integer> row = new HashSet<>();
        Set<Integer> col = new HashSet<>();
        Set<Integer> cube = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (Character.isDigit(board[i][j]) && !row.add((int) (board[i][j] - 'a'))) {
                    return false;
                }
                if (Character.isDigit(board[j][i]) && !col.add((int) (board[j][i] - 'a'))) {
                    return false;
                }
                int y = (i / 3) * 3 + (j / 3);
                int x = (i % 3) * 3 + (j % 3);
                if (Character.isDigit(board[y][x]) && !cube.add((int) (board[y][x] - 'a'))) {
                    return false;
                }
            }
            row.clear();
            col.clear();
            cube.clear();
        }
        return true;
    }
}

二刷
Next solution is better

42.04 %
class Solution {
    public boolean isValidSudoku(char[][] board) {
        List<Set<Integer>> rows = new ArrayList<>();
        List<Set<Integer>> cols = new ArrayList<>();
        List<Set<Integer>> subBoxes = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            rows.add(new HashSet<>());
            cols.add(new HashSet<>());
            subBoxes.add(new HashSet<>());
        }
        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[0].length; x++) {
                if (Character.isDigit(board[y][x])) {
                    int num = (int) (board[y][x] - '0');
                    if (!rows.get(y).add(num)) {
                        return false;
                    }
                    if (!cols.get(x).add(num)) {
                        return false;
                    }
                    int boxId = y / 3 * 3 + (x / 3);
                    if (!subBoxes.get(boxId).add(num)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

一刷

49.94 %
class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length != 9 || board[0] == null || board[0].length != 9) return false;
        Set<Character> row = new HashSet<>();
        Set<Character> col = new HashSet<>();
        Set<Character> cube = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // for ith row
                if (board[i][j] != '.' && !row.add(board[i][j])) return false;
                if (board[j][i] != '.' && !col.add(board[j][i])) return false;
                int x = (i / 3) * 3 + j / 3;
                int y = (i % 3) * 3 + j % 3;
                if (board[x][y] != '.' && !cube.add(board[x][y])) return false;
             
            }
            row.clear();
            col.clear();
            cube.clear();
        }
        return true;
    }
}



41.01 %

class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length != 9 || board[0] == null || board[0].length != 9) return false;
        Set<Integer> row = new HashSet<>();
        Set<Integer> col = new HashSet<>();
        Set<Integer> cube = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // for ith row
                if (board[i][j] != '.' && !row.add(Character.getNumericValue(board[i][j]))) return false;
                if (board[j][i] != '.' && !col.add(Character.getNumericValue(board[j][i]))) return false;
                int x = (i / 3) * 3 + j / 3;
                int y = (i % 3) * 3 + j % 3;
                if (board[x][y] != '.' && !cube.add(Character.getNumericValue(board[x][y]))) return false;
             
            }
            row.clear();
            col.clear();
            cube.clear();
        }
        return true;
    }
}

284. Peeking Iterator

 80.54 %

class PeekingIterator implements Iterator<Integer> {

    Integer top = null;

    Iterator<Integer> iterator;

public PeekingIterator(Iterator<Integer> iterator) {

    // initialize any member here.

        this.iterator = iterator;

        if (this.iterator.hasNext()) top = this.iterator.next();

}

    // Returns the next element in the iteration without advancing the iterator.

public Integer peek() {

        return top;

}

// hasNext() and next() should behave the same as in the Iterator interface.

// Override them if needed.

@Override

public Integer next() {

    Integer result = top;

        if (iterator.hasNext()) {

            top = iterator.next();

        } else {

            top = null;

        }

        return result;

}

@Override

public boolean hasNext() {

    return top != null;

}

}

69. Sqrt(x)

Version 1
61.32 %
class Solution {
    public int mySqrt(int x) {
        if (x <= 1) return x;
        int start = 1;
        int end = x;
        int mid;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (mid == x / mid) return mid;
            if (mid < x / mid) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return end;
    }
 
}


Version 2
98.32 %

Find the critical point that mid^2 <= x and (mid + 1)^ > x

class Solution {
    public int mySqrt(int x) {
        long start = 0;
        long end = x;
        long mid = 0;
        while (start < end) {
            mid = start + (end - start) / 2;
            if (mid * mid <= x && (mid + 1) * (mid + 1) > x) {
                return (int)mid;
            } else if (mid * mid > x) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        if (start == end) {
            return (int)start;
        } else {
            return (int)end;
        }
    }
}

二刷
12.20 %
class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        long start = 0;
        long end = x;
        while (start < end) {
            long mid = start + (end - start) / 2;
            if (mid * mid <= x) {
                if ((mid + 1) * (mid + 1) > x) {
                    return (int)mid;
                } else {
                    start = mid + 1;
                }
            } else { // mid * mid > x
                end = mid - 1;
            }
        }
        return (int)start;
    }
}

Version 3
mid * mid <= x
-> (x / mid) < actual x / mid
所以 mid * mid <= x can't guarantee that mid <= x / mid
however mid * mid > x can guarantee that mix > x / mid
 96.02 % 

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        int start = 1;
        int end = x;
        int mid = 0;
        while (start < end) {
            mid = start + (end - start) / 2;
            // mid^2 > x
            if (mid > x / mid) {
                end = mid - 1;
            } else {
                // (mid + 1)^2 > x
                if ((mid + 1) > x / (mid + 1)) {
                    return mid;
                } else {
                    start = mid + 1;
                }
            }
        }
        // mid       
        // start end
        return start;
    }
}

217. Contains Duplicate

Version #2 Sort
Version #1 HashSet

68.38 %
class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length <= 1) return false;
        Set<Integer> visited = new HashSet<>();
        for (int num : nums) {
            if (!visited.add(num)) return true;
        }
        return false;
    }
}

19. Remove Nth Node From End of List

三刷 06/2022

Version #1 Two Passes - get length

Time O(N)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Nth Node From End of List.

Memory Usage: 43.2 MB, less than 5.08% of Java online submissions for Remove Nth Node From End of List.

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode curr = head;

        int cnt = 0;

        // c

        // 1

        while (curr != null) {

            cnt++;

            curr = curr.next;

        }

        // m is zero based index of the node to be deleted

        int m = cnt - n;

        if (m == 0) {

            return head.next;

        }

        curr = head;

        // c

        // 1 2 3 - m = 1

        while (m-- > 1) {

            curr = curr.next;

        }

        curr.next = curr.next.next;

        return head;

    }

}

Version #2 One Pass

Time O(N)

Space O(1)

Runtime: 1 ms, faster than 65.32% of Java online submissions for Remove Nth Node From End of List.

Memory Usage: 42.8 MB, less than 17.25% of Java online submissions for Remove Nth Node From End of List.

class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {

        // s

        //     f

        // 1 2 3 4 5

        // s

        // f

        // 1

        ListNode slow = head, fast = head;

        while (n-- > 0 && fast != null) {

            fast = fast.next;

        }

        if (fast == null) {

            return head.next;

        }

        while (fast.next != null) {

            slow = slow.next;

            fast = fast.next;

        }

        slow.next = slow.next.next;

        return head;

    }

}

Version #2 One pass
Two pointers
Find a node which is n nodes away from head -> curr
Define prev as the previous node of head
let curr go forward until it reaches tail, and prev also walk in the same pace
When curr reaches null, prev.next is n nodes away from curr -> we should remove prev.next
-> prev.next = prev.next.next

二刷
50.57 %
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //prev           p        c   
        //dummy -> 1->2->3->4->5->null
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        while (n > 0) {
            curr = curr.next;
            n--;
        }
        while (curr != null) {
            prev = prev.next;
            curr = curr.next;
        }
        prev.next = prev.next.next;
        return dummy.next;
    }
}


一刷
67.80 %
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n == 0) return head;
        // n = 1
        //sf
        // 1-> 2 -> null
        ListNode fast = head;
        ListNode slow = head;
        while (n-- > 0 && fast != null) {
            fast = fast.next;
        }
        if (fast == null) return head.next;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}



Version #1 Two pass
二刷
 99.83 %
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int len = 0;
        ListNode curr = head;
        while (curr != null) {
            len++;
            curr = curr.next;
        }
        // len = 5, target = 0
        int target = len - n;
        //       p
        // 1->2->3->4->5
        ListNode prev = dummy;
        while (target > 0) {
            prev = prev.next;
            target--;
        }
        prev.next = prev.next == null ? null : prev.next.next;
        return dummy.next;
    }
}


一刷
getLength
14.97 %
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n == 0) return head;
        int len = getLength(head);
        // e.g. len = 5, n = 2 delete index (5 - 2) = 3
        // i 0  1  2  3
        //   1->2->null
        ListNode curr = head;
        if (n == len) return head.next;
     
        for (int i = 0; i < len - n - 1; i++) {
            curr = curr.next;
        }
     
        curr.next = curr.next.next;
        return head;
    }
    private int getLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }
}

218. The Skyline Problem

[DONE] Write a int[2] version
四刷
38.16 %
class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        // check if the highest hight has changed or not
        // int[] 0-represents the x, 0-represents height, minus if it is the end
        List<int[]> heights = new ArrayList<>();
        for (int[] building : buildings) {
            // building[0] -> start
            // building[1] -> end
            // building[2] -> height
            heights.add(new int[]{building[0], building[2]});
            heights.add(new int[]{building[1], -building[2]});
        }
        // compare by x
        // if 1 end and 1 start, start should come before end
        // if both start, heigher one should come first
        // if both end, lower one should come first
        Collections.sort(heights, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return b[1] - a[1];
        });
        // all the points that are under consideration
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(0);
        List<int[]> result = new ArrayList<>();
        int currHeight = 0;
        for (int[] height : heights) {
            if (height[1] > 0) {
                maxHeap.offer(height[1]);
            } else {
                maxHeap.remove(-height[1]);
            }
            if (maxHeap.peek() != currHeight) {
                currHeight = maxHeap.peek();
                result.add(new int[]{height[0], currHeight});
            }
        }
        return result;
    }
}


[3rd TRY]
1 bug -> should have checked if pq is empty before do pq.peek()

51.67 %
class Solution {
    class Point {
int x;
int height;
int isEnd; // 0 for start, 1 for end
public Point(int x, int height, int isEnd) {
this.x = x;
this.height = height;
this.isEnd = isEnd;
}
}
    public List<int[]> getSkyline(int[][] buildings) {
// we keep a list of heights -> if the highest point changes, then it should be added to skyline
// sort by their x positions, we need to know either it is a start point or a end point
// 4 kinds of ties
// if a ends and b starts, a < b, then we want to add b first and then remove a -> start 0, end 1
// if a ends and b starts, a > b, same
// if a,b ends at the same time, then we want to remove the lower one first
// if a,b stars at the same time, then we want to add the higher one first
List<Point> list = new ArrayList<>();
for (int[] building : buildings) {
list.add(new Point(building[0], building[2], 0));
list.add(new Point(building[1], building[2], 1));
}
Collections.sort(list, (a, b) -> {
if (a.x != b.x) {
return a.x - b.x;
}
if (a.isEnd != b.isEnd) {
return a.isEnd - b.isEnd; // Always return the start one first
} else if (a.isEnd == 0) {
return b.height - a.height;
} else {
return a.height - b.height;
}
});
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(16, Collections.reverseOrder());
int prevHeight = 0;
List<int[]> result = new ArrayList<>();
for (Point curr : list) {
if (curr.isEnd == 0) { // isStart
maxHeap.add(curr.height);
} else {
maxHeap.remove(curr.height);
}
int currHeight = maxHeap.isEmpty() ? 0 : maxHeap.peek();
if (currHeight != prevHeight) {
prevHeight = currHeight;
result.add(new int[]{curr.x, currHeight});
}
}
return result;
}
}

二刷
Time O(n^2) -> linear time to remove
Space O(n)
class Solution {
    // int[0] -> x, int[1] -> height, int[2] -> 0 start, 1 end
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<>();
        if (buildings == null || buildings.length == 0) {
            return result;
        }
        // buildings[i][0] -> start, buildings[i][1] -> end, buildings[i][2] -> height
        List<int[]> list = new ArrayList<>();
        for (int[] building : buildings) {
            list.add(new int[]{building[0], building[2], 0});
            list.add(new int[]{building[1], building[2], 1});
        }
        Collections.sort(list, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else if (a[2] != b[2]) {
                // start before end
                return a[2] - b[2];
            } else if (a[2] == 0) {
                // Two start, add the higher one first
                return b[1] - a[1];
            } else {
                // Two end, remove the lower one first
                return a[1] - b[1];
            }
        });
        PriorityQueue<Integer> pq = new PriorityQueue<>(10, Collections.reverseOrder());
        int currHeight = 0;
        int[] curr = null;
        for (int i = 0; i < list.size(); i++) {
            curr = list.get(i);
            if (curr[2] == 0) {
                pq.add(curr[1]);
            } else {
                pq.remove(curr[1]);
            }
            if (pq.isEmpty()) {
                result.add(new int[]{curr[0], 0});
                currHeight = 0;
            } else if (currHeight != pq.peek()){
                result.add(new int[]{curr[0], pq.peek()});
                currHeight = pq.peek();
            }
        }
        return result;
    }
}





一刷

Input:[[0,2,3],[2,5,3]]

Output:[[0,3],[2,3],[5,0]]

Expected:[[0,3],[5,0]]

有四种breaking tie的情况，决定了sort的顺序
上面的一个bug要注意如果second largest和之前pop出去的一样高，就不往结果里面加

还有一个是PriorityQueue remove(Object)
是remove single one

 59.53 %

class Solution {
    class Tuple {
        int pos;
        int height;
        int isEnd; // 0 -> isStart, 1 -> isEnd
        public Tuple(int pos, int height, int isEnd) {
            this.pos = pos;
            this.height = height;
            this.isEnd = isEnd;
        }
    }
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<>();
        if (buildings == null || buildings.length == 0) return result;
        List<Tuple> tuples = new ArrayList<>();
        for (int[] building : buildings) {
            //  0   1   2
            // [Li, Ri, Hi]
            tuples.add(new Tuple(building[0], building[2], 0));
            tuples.add(new Tuple(building[1], building[2], 1));
        }
        // maxHeap
        PriorityQueue<Integer> pq = new PriorityQueue<>(10, Collections.reverseOrder());
   
        Collections.sort(tuples, new Comparator<Tuple>() {
            @Override
            public int compare(Tuple t1, Tuple t2) {
                if (t1.pos != t2.pos) {
                    return t1.pos - t2.pos;
                } else if (t1.isEnd != t2.isEnd) {
                    // start(0) befor end(1)
                    return t1.isEnd - t2.isEnd;
                } else if (t1.isEnd == 0) {
                    // if both start, higher before lower
                    return t2.height - t1.height;
                } else {
                    // if both end, lower before higher
                    return t1.height - t2.height;
                }
            }
        });
        // output [x1,y1] -> [pos, height]
        for (int i = 0; i < tuples.size(); i++) {
            Tuple curr = tuples.get(i);
            // start -> add
            if (curr.isEnd == 0) {
           
                if (pq.isEmpty() || curr.height > pq.peek()) {
                    result.add(new int[]{curr.pos, curr.height});
                }
                pq.add(curr.height);
            } else { // end -> delete
                if (pq.peek() == curr.height) {
                    pq.poll();
                    if (pq.isEmpty()) {
                        result.add(new int[]{curr.pos, 0});
                    } else if (pq.peek() != curr.height){
                        result.add(new int[]{curr.pos, pq.peek()});
                    }
                } else {
                    pq.remove(new Integer(curr.height));
                }
            }
        }
        return result;
    }
}

393. UTF-8 Validation

报错的算是一个edge case
如果只有1byte，应该是0 开头
也就是说不存在只有一个1开头的meta data

Input:[145]

Output:true

Expected:false

10010001

68.61 %

class Solution {
    public boolean validUtf8(int[] data) {
        if (data == null || data.length == 0) return false;
        return helper(data, 0, 0);
    }
    private boolean helper(int[] data, int index, int toMatch) {
        if (index == data.length) return toMatch == 0;
        int curr = data[index];
     
        if (toMatch != 0) {
            if (curr >> 6 != 0b10) return false;
            else return helper(data, index + 1, toMatch - 1);
        }
        // get the count of 1s
        int count = 0;
        int bit = 7;
        while ((curr & (1 << bit--)) != 0) {
            count++;
        }
        // can't be 1 since 1 byte is a special case
        // can't be more than 4 bytes
        if (count == 1 || count > 4) return false;
        count = count == 0 ? 0 : count - 1;
        return helper(data, index + 1, count);
    }
}

219. Contains Duplicate II

二刷
Versuib #2 Sliding Window
14.63 %
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null) {
            return false;
        }
        // sliding window of size k
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.size() > k) {
                set.remove(nums[i - k - 1]);
            }
            if (set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
        }
        return false;
    }
}

Version #1 第一反应还是写了hashmap
Seems like this problem is actually a sliding window problem
81.40 %
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // key-> num, value -> index
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer index = map.get(nums[i]);
            if (index != null && i - index <= k) {
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }
}


一刷
Version #2 HashSet(Better)
82.57 %
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length <= 1) return false;
        // set of numbers in the sliding window
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            // i - j <= k ->  j >= i - k
            if (i - k > 0) {
                set.remove(nums[i - k - 1]);
            }
            if (!set.add(nums[i])) return true;
        }
        return false;
    }
}

Version #1 HashMap
看了答案发现自己这么写很烂
这个题有点像sliding window
只要用set看window里面有没有重复值就可以了

9.84 %
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length <= 1) return false;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int prev = map.getOrDefault(nums[i], -1);
            if (prev != -1 && i - prev <= k) {
                return true;
            } else {
                map.put(nums[i], i);
            }
        }
        return false;
    }
}