Tag: 每日一题

Posted 2022-08-27Updated 2022-08-27LeetCode / Medium2 minutes read (About 234 words)

Question

A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix’s end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].

Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

Solution

分别遍历数组的两条边。
按对角线顺序进行遍历，用列表记录访问过的数字。
排序列表后按对角线填入原数组。

Code

class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        List<Integer> arr = new ArrayList<>();
        
        for(int t = 0; t < m; t++){
            int i = t, j = 0;
            
            while(i < m && j < n){
                arr.add(mat[i][j]);
                i++;
                j++;
            }
            
            Collections.sort(arr);
            
            i = t;
            j = 0;
            
            while(i < m && j < n){
                mat[i][j] = arr.get(j);
                i++;
                j++;
            }
            arr.clear();
        }

        for(int t = 1; t < n; t++){
            int i = 0, j = t;
            
            while(i < m && j < n){
                arr.add(mat[i][j]);
                i++;
                j++;
            }
            
            Collections.sort(arr);
            
            i = 0;
            j = t;
            
            while(i < m && j < n){
                mat[i][j] = arr.get(i);
                i++;
                j++;
            }
            arr.clear();
        }
        return mat;
    }
}

Posted 2022-08-27Updated 2022-08-27LeetCode / Hard / 复习2 minutes read (About 231 words)

363. Max Sum of Rectangle No Larger Than K

Question

Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.

It is guaranteed that there will be a rectangle with a sum no larger than k.

Solution

前缀和，计算矩阵中每个位置对应的方形的和。
遍历方形的两个对角线上的点。
其面积等于大块加小块的面积减去两个长方形的面积。
如果面积有小于k的，则记录其最大值并返回。

Code

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int x = matrix.length, y = matrix[0].length, max = Integer.MIN_VALUE;
        int[][] sum = new int[x+1][y+1];
        
        for(int i = 1; i <= x; i++){
            int total = 0;
            for(int j = 1; j <= y; j++){
                total += matrix[i-1][j-1];
                sum[i][j] = sum[i-1][j] + total;
            }
        }
 
        for(int i = 0; i <= x; i++){
            for(int j = 0; j <= y; j++){
                for(int m = i + 1; m <= x; m++){
                    for(int n = j + 1; n <= y; n++){
                        int area = sum[m][n] + sum[i][j] - sum[m][j] - sum[i][n];
                        if(area <= k) max = Math.max(max, area);
                    }
                }
            }
        }
        return max;
    }
}

Posted 2022-08-26Updated 2022-08-26LeetCode / Medium / 复习3 minutes read (About 411 words)

869. Reordered Power of 2

Question

You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this so that the resulting number is a power of two.

Solution

打表，将所有二的指数全部计算出来，并用数组统计各个数字出现的频率。
然后同样统计n中各个数字出现的频率。

如果两者中有频率完全相同的情况，则返回true，反之返回false。

Code

class Solution {
    public boolean reorderedPowerOf2(int n) {
        int[] reorders = new int[10];
        int m = 1, digits = 0;
        for(int i = n; i > 0; i/=10){
            reorders[i % 10]++;
            digits++;
        }
        
        int size = 0;
        List<Integer[]> powerOfTwo = new ArrayList<>();
        
        while(m > 0 && size <= digits){
            size = 0;
            Integer[] bin = new Integer[10];
            Arrays.fill(bin, 0);
            for(int i = m; i > 0; i/=10){
                size++;
                bin[i % 10]++;
            }
            if(size == digits) powerOfTwo.add(bin);
            m *= 2;
        }
        
        for(Integer[] bin : powerOfTwo) if(check(bin, reorders)) return true;
        return false;
    }
    
    private boolean check(Integer[] bin, int[] reorders){
        for(int i = 0; i < bin.length; i++) if(bin[i] != reorders[i]) return false;
        return true;        
    }
}

Solution 2

回溯，遍历计算可以组成的所有数字。
打表记录所有二的指数并记录在哈希表内，如果所有组成数字中有哈希表内的数字则返回true，反之返回false。

Code

class Solution {
    HashSet<Integer> visited, set, numbers;
    List<Integer> arr, res;
    public boolean reorderedPowerOf2(int n) {
        int m = 1;
        set = new HashSet<>();
        visited = new HashSet<>();
        numbers = new HashSet<>();
        res = new ArrayList<Integer>();
        while(m > 0){
            set.add(m);
            m *= 2;
        }
        
        arr = new ArrayList<>();
        
        while(n > 0){
            arr.add(n % 10);
            n /= 10;
        }
        
        for(int i = 0; i< arr.size(); i++){
            if(arr.get(i) == 0) continue;
            visited.add(i);
            reorder(arr.get(i));
            visited.remove(i);
        }
        
        
        for(int num : res) if(set.contains(num)) return true;
        return false;
    }
    
    private void reorder(int num){
        if(visited.size() == arr.size()){
            res.add(num);
            return;
        };
        
        if(numbers.contains(num)) return;
        numbers.add(num);

        for(int i = 0; i < arr.size(); i++){
            if(visited.contains(i)) continue;
            int next = num * 10 + arr.get(i);
            visited.add(i);
            reorder(next);
            visited.remove(i);
        }
    }
}

Posted 2022-08-25Updated 2022-08-25LeetCode / Easya minute read (About 125 words)

383. Ransom Note

Question

Given two strings ransomNote and magazine, return true* if ransomNote can be constructed by using the letters from magazine and false otherwise*.

Each letter in magazine can only be used once in ransomNote.

Solution

数组统计，统计magazine内的字符。
遍历ransomNote，如果对字符数组位置为0则返回false。
每次遍历减少数组统计结果。

最后返回true。

Code

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] bin = new char[26];
        
        for(char c : magazine.toCharArray()) bin[c-'a']++;
        for(char c : ransomNote.toCharArray()){
            if(bin[c-'a'] == 0) return false;
            bin[c-'a']--;
        }
        
        return true;
    }
}

Posted 2022-08-23Updated 2022-08-23LeetCode / Easya few seconds read (About 109 words)

326. Power of Three

Question

Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer n is a power of three, if there exists an integer x such that n == 3x.

Solution

与isPowerOfFour相同，如果n小于0则返回false。
如果n等于1则返回true。
递归，如果n可以整除3，则返回isPowerOfThree(n / 3)。
否则返回false。

Code

class Solution {
    public boolean isPowerOfThree(int n) {
        if(n <= 0) return false;
        if(n == 1) return true;
        if(n % 3 == 0) return isPowerOfThree(n / 3);
        else return false;
    }
}

Posted 2022-08-22Updated 2022-08-22LeetCode / Easy4 minutes read (About 603 words)

234. Palindrome Linked List

Question

Given the head of a singly linked list, return true if it is a palindrome.

Solution 1

快慢指针，快指针遍历到底时慢指针正好到一半。
根据快指针的位置判断奇数个还是偶数个。
如果是奇数个则翻转链表时需要向前移动一位。

接下来翻转后半段链表。
翻转完成后从第一段的头部和翻转过的链表头部开始遍历。
如果两个节点的值不同则返回false。

遍历完毕返回true。

Code

/**
 * 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 boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode slow = head, fast = head;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode curr = fast == null ? slow : slow.next, prev = null;   //make sure curr is the head of the 2nd part
        
        while(curr != null){    //reverse the 2nd part of the nodes
            ListNode temp = curr.next; //preserve nodes that after current node
            curr.next = prev; //add previous node to the current node's next
            prev = curr; //save previous node
            curr = temp; //update current node
        }
        
        while(head != null && prev != null){
            if(head.val != prev.val) return false;
            prev = prev.next;
            head = head.next;
        }
        return true;
    }
}

Solution 2

快慢指针的原理，不是记录长度而是当快指针遍历到链表尾时停止。
然后对照栈内的值是否和剩余的值相等。

Code

/**
 * 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 boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        Stack<ListNode> stack = new Stack<>();

        while(fast != null && fast.next != null){
            stack.add(slow);

            slow = slow.next;
            fast = fast.next.next;
        }
        
        if(fast != null) slow = slow.next;
        
        while(!stack.isEmpty()){
            if(stack.pop().val != slow.val) return false;
            slow = slow.next;
        }
        
        return true;
    }
}

Solution 3

回文，先计算链表长度。
记录链表长度是否为奇数。

如果链表长度为偶数，则将一半的节点放入栈中。
如果为奇数则抛弃一个节点。
剩下一半的节点和栈顶节点比较，如果值不相同则返回false。

遍历完成返回true。

Code

/**
 * 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 boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode root = head;
        Stack<ListNode> stack = new Stack<>();
        
        while(root != null){
            root = root.next;
            len++;
        }
        
        root = head;
        for(int i = 0; i < len/2; i++){
            stack.add(root);
            root = root.next;
        }
        
        if(len % 2 != 0) root = root.next;
        
        for(int i = 0; i < len/2; i++){
            if(stack.peek().val == root.val) stack.pop();
            else return false;
            root = root.next;
        }
        return true;
    }
}

Posted 2022-08-22Updated 2022-08-22LeetCode / Easya few seconds read (About 102 words)

342. Power of Four

Question

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4x.

Solution

递归，如果n小于等于零则返回false。
如果n等于1则返回true。

如果n可以除以4，则递归返回n/4。

Code

class Solution {
    public boolean isPowerOfFour(int n) {
        if(n <= 0) return false;
        if(n == 1) return true;
        
        if(n % 4 == 0) return isPowerOfFour(n / 4);
        else return false;
    }
}

Posted 2022-08-21Updated 2022-08-21LeetCode / Medium / 复习3 minutes read (About 466 words)

659. Split Array into Consecutive Subsequences

Question

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).

All subsequences have a length of 3** or more**.

Return true* if you can split nums according to the above conditions, or false otherwise*.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

Solution

用优先级队列储存每个可组成的列表。
优先级队列根据列表的长度排列。

用哈希表记录每个列表的尾数，和其对应的优先级队列。
遍历所有数字，如果存在当前数字num-1为尾数的队列，则获取长度最小的列表，并添加当前数字num在列表中。
然后将新的优先级队列放入哈希表中。

遍历整个哈希表中的数组，如果有数组的长度小于3，则返回false，否则返回true。

Code

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer, PriorityQueue<List<Integer>>> map = new HashMap<>();
        
        for(int num : nums){
            PriorityQueue<List<Integer>> last = map.getOrDefault(num - 1, null);
            PriorityQueue<List<Integer>> curr = map.getOrDefault(num, new PriorityQueue<List<Integer>>((a,b) -> a.size() - b.size()));

            if(last == null || last.size() == 0){
                List<Integer> arr = new ArrayList<>();
                arr.add(num);
                curr.add(arr);
                map.put(num, curr);
            }
            else{
                List<Integer> arr = last.poll();
                arr.add(num);
                curr.add(arr);
                map.put(num, curr);
            }
        }                   
                                      
        for(int last : map.keySet()){
            for(List<Integer> arr : map.get(last)){
                if(arr.size() < 3) return false;
            }
        }
        return true;
        
    }
}

Solution 2

不需要保存整个列表，只需要保存对应末尾数字的列表长度即可。

Code

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        
        for(int num : nums){
            PriorityQueue<Integer> last = map.getOrDefault(num - 1, null);
            PriorityQueue<Integer> curr = map.getOrDefault(num, new PriorityQueue<Integer>());

            if(last == null || last.size() == 0){
                curr.add(1);
                map.put(num, curr);
            }
            else{
                int min = last.poll();
                curr.add(min+1);
                map.put(num, curr);
            }
        }                   
                                      
        for(int last : map.keySet()){
            for(int len : map.get(last)){
                if(len < 3) return false;
            }
        }
        return true;

    }
}

Posted 2022-08-17Updated 2022-08-17LeetCode / Easya minute read (About 149 words)

804. Unique Morse Code Words

Question

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows:

'a' maps to ".-",

'b' maps to "-...",

'c' maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Given an array of strings words where each word can be written as a concatenation of the Morse code of each letter.

For example, "cab" can be written as "-.-..--...", which is the concatenation of "-.-.", ".-", and "-...". We will call such a concatenation the transformation of a word.

Return the number of different transformations among all words we have.

Solution

Code

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] alphabet = new String[]{".-","-...","-.-.","-..",".","..-.","--.",
                                         "....","..",".---","-.-",".-..","--","-.",
                                         "---",".--.","--.-",".-.","...","-","..-",
                                         "...-",".--","-..-","-.--","--.."};
        HashSet<String> set = new HashSet<>();
        
        for(String word : words){
            StringBuffer sb = new StringBuffer();
            for(char c : word.toCharArray()){
                sb.append(alphabet[c - 'a']);
            }
            set.add(sb.toString());
        }
        
        return set.size();
    }
}

Posted 2022-08-15Updated 2022-08-15LeetCode / Easy2 minutes read (About 342 words)

13. Roman to Integer

Question

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.

X can be placed before L (50) and C (100) to make 40 and 90.

C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Solution

倒叙遍历，记录几个mark以标注是否出现对应的字母。

初始res为0，根据字符加减数值。
如果出现则将mark设置为真。
如果mark为真，且上一个字符出现对应需要减去的罗马字符，则改加为减。

最后返回res值。

Code

class Solution {
    public int romanToInt(String s) {
        int res = 0;
        boolean markX = false, markC = false, markM = false;
        
        for(int i = s.length()-1; i >= 0; i--){
            char c = s.charAt(i);
            if(c == 'I'){
                if(markX) res -= 1;
                else res += 1;
            }
            else if(c == 'V'){
                markX = true;
                res += 5;
            }
            else if(c == 'X'){
                markX = true;
                if(markC) res -= 10;
                else res += 10;
            }
            else if(c == 'L'){
                markC = true;
                res += 50;
            }
            else if(c == 'C'){
                markC = true;
                if(markM) res -= 100;
                else res += 100;
            }
            else if(c == 'D'){
                markM = true;
                res += 500;
            }
            else if(c == 'M'){
                markM = true;
                res += 1000;
            }
        }
        return res;
    }
}

Posted 2022-08-08Updated 2022-08-08LeetCode / Medium / 复习3 minutes read (About 474 words)

823. Binary Trees With Factors

Question

Given an array of unique integers, arr, where each integer arr[i] is strictly greater than 1.

We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node’s value should be equal to the product of the values of its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo 109 + 7.

Solution

根据题意，二叉树的根是两个子节点的乘积，因此一个根节点可组成的二叉树总数，相当于其左子节点可组成的二叉树总数，乘以其右子节点可组成的二叉树总数。

因此我们可以先将数组arr排序，用dp[]数组记录以从小到大的数字作为根节点可组成的最大二叉树总数。

由于每个根节点至少可以和自身组成一个节点，因此将dp[]数组初始化为1。

动态规划

从小到大遍历dp[]数组。
在遍历时，从遍历数值i的左侧选取当前位置的子节点。（根据题意子节点一定小于根节点）
当当前位置arr[i]可以整除arr[left]时，则有可能存在另一个子节点。此时根据哈希表中获得对应的另一个子节点right。如果right存在，则dp[i]更新为dp[i]+dp[left]*dp[right]的值。

最后将dp[]数组中记录的所有数字加和并返回。

Code

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        final int MOD = (int) Math.pow(10, 9) + 7;
        Arrays.sort(arr);   //from minium to maxium
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < arr.length; i++){
            map.put(arr[i], i);
        }
        
        long[] dp = new long[arr.length];
        Arrays.fill(dp, 1);
        
        for(int i = 0; i < arr.length; i++){
            for(int left = 0; left < i; left++){
                if(arr[i] % arr[left] == 0){   //make sure divisible
                    int k = arr[i] / arr[left];
                    if(map.containsKey(k)){
                        int right = map.get(k);
                        dp[i] = (dp[i] + dp[left] * dp[right]) % MOD; 
                    }
                }
            }
        }
        
        int res = 0;
        
        for(long num : dp){
            res += num;
            res %= MOD;
        }
        
        return (int) res;
    }
}

Posted 2022-08-06Updated 2022-08-06LeetCode / Hard2 minutes read (About 291 words)

1220. Count Vowels Permutation

Question

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')

Each vowel 'a' may only be followed by an 'e'.

Each vowel 'e' may only be followed by an 'a' or an 'i'.

Each vowel 'i' may not be followed by another 'i'.

Each vowel 'o' may only be followed by an 'i' or a 'u'.

Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.

Solution

DFS搜索，记忆化剪枝。
每次根据上一个字母last来从哈希表里选择下一个可选字母进行遍历，并计算总的可组成数sum。

Code

class Solution {
    final int MOD = (int) Math.pow(10, 9) + 7;
    int[][] memo;
    HashMap<Character, Character[]> map;
    public int countVowelPermutation(int n) {
        if(n == 1) return 5;
        map = new HashMap<>();
        memo = new int[26][n+1];
        Character[] vowels = {'a', 'e', 'i', 'o', 'u'}, 
        a = {'e'}, e = {'a','i'}, i = {'a','e','o','u'}, o = {'i', 'u'}, u = {'a'};
        map.put('a', a);
        map.put('e', e);
        map.put('i', i);
        map.put('o', o);
        map.put('u', u);
        
        int ans = 0;
        
        for(char vowel : vowels){
            ans += count(vowel, n-1);
            ans %= MOD;
        }
        return ans;
    }
    
    private int count(char last, int n){
        if(memo[last-'a'][n] != 0) return memo[last-'a'][n];
        if(n == 1){
            memo[last-'a'][n] = map.get(last).length;
            return memo[last-'a'][n];
        }
        
        int sum = 0;
        for(char next : map.get(last)){
            sum += count(next, n-1);
            sum %= MOD;
        }
        memo[last-'a'][n] = sum;
        return sum;
    }
}

Posted 2022-08-05Updated 2022-08-05LeetCode / Medium2 minutes read (About 296 words)

377. Combination Sum IV

Question

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Solution

记忆化搜索，memo[]数组用来记录达到某个总和时的可行方案数量。
辅助方法count记录累计的总和memo[total]。

递归DFS，记忆化剪枝，如果memo[]数组不为空，则直接返回记忆内容。
当total等于target时，该组合成立，返回1。

遍历nums[]数组中的每个元素，并将总组合数相加记录到memo[total]中。
最后返回总组合数memo[total]。

*非常奇怪的是，当我使用int[]数组进行记忆化搜索时部分case会超时，推测是因为我判断int[]数组是否被记录是通过是否等于0而非是否为空导致的。

Code

class Solution {
    int[] numbers;
    Integer[] memo;
    public int combinationSum4(int[] nums, int target) {
        numbers = nums;
        memo = new Integer[target+1];
        return count(0, target);
    }
    
    private int count(int total, int target){
        if(memo[total] != null) return memo[total];
        if(total == target) return 1;
    
        int sum = 0;
        for(int i = 0; i < numbers.length; i++){
            if(total + numbers[i] <= target) sum += count(total + numbers[i], target);
        }
        memo[total] = sum;
        
        return memo[total];
    }
}

Posted 2022-08-04Updated 2022-08-04LeetCode / Medium2 minutes read (About 326 words)

858. Mirror Reflection

Question

There is a special square room with mirrors on each of the four walls. Except for the southwest corner, there are receptors on each of the remaining corners, numbered 0, 1, and 2.

The square room has walls of length p and a laser ray from the southwest corner first meets the east wall at a distance q from the 0th receptor.

Given the two integers p and q, return the number of the receptor that the ray meets first.

The test cases are guaranteed so that the ray will meet a receptor eventually.

Solution

激光在箱子里折射，可以想象成在无限延展的空间内直线发射光线。
因此三个接收器可以被视作组成了一个无限延展的矩阵。

只需要将q和p化简，然后确定坐标(q, p)所对应的接收器即可。
由于接收器是间隔的，因此只需要先化简q，p后计算两者的奇偶性即可。

如果q与p皆为奇数，则返回1号接收器。
如果q是奇数，p不是，则返回0号接收器。
如果p是奇数，q不是，则返回2号接收器。

Code

class Solution {
    public int mirrorReflection(int p, int q) {
        int gcd = gcd(p, q);
        p/=gcd;
        q/=gcd;
        boolean xIsOdd = (p & 1) == 1, yIsOdd = (q & 1) == 1;
        if(xIsOdd && yIsOdd) return 1;
        else if(xIsOdd) return 0;
        else return 2;
    }
    
    private int gcd(int a, int b){
        if(a == b) return a;
        if(a > b) return gcd(b, a-b);
        else return gcd(a, b-a);
    }
}

Posted 2022-08-03Updated 2022-08-03LeetCode / Medium / 复习2 minutes read (About 361 words)

729. My Calendar I

Question

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

MyCalendar() Initializes the calendar object.

boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Solution

有更快速的解法，需要用到TreeMap，有时间再研究。

使用一个队列记录已经预定的范围。
添加无穷大到队列中，方便后期计算。

当预定新的时间段时，遍历队列，如果上一个数组的最大值小于start和end且当前遍历数组大于start和end，则可以预定，将当前的数组插入当前位置，并返回true。
如果没有满足条件的，则返回false。

Code

class MyCalendar {
    List<int[]> arr;
    public MyCalendar() {
        arr = new ArrayList<>();
        int[] inf = new int[2];
        inf[0] = Integer.MAX_VALUE;
        inf[1] = Integer.MAX_VALUE;
        arr.add(inf);
    }
    
    public boolean book(int start, int end) {
        int[] last = new int[2];
        for(int i = 0; i < arr.size(); i++){
            int[] curr = arr.get(i);
            if(last[1] < end && last[1] <= start && curr[0] >= end && curr[0] > start){
                int[] n = new int[2];
                n[0] = start;
                n[1] = end;
                arr.add(i, n);
                return true;
            }
            last = curr;
        }
        return false;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(start,end);
 */

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Solution 3

Code

Question

Solution

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

动态规划

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Recents

Archives

Links