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;
    }
}