Solution of Weekly Contest 168

, , , , ,

[Easy] 1295. Find Numbers with Even Number of Digits

Solution:

Calculate the length of each digit (convert to String) and see if it is even.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// more naive one, using getNum for calculating number of digit.
// time:O(n * len(n)) space:O(1)
// Runtime: 1ms
public int findNumbers(int[] nums) {
        int n = nums.length;
        if (nums == null || n == 0) return 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            int NumOfDigit = getNum(nums[i]);
            if (NumOfDigit % 2 == 0) res++;
        }
        return res;
    }
    
    public int getNum(int num) {
        int count = 0;
        while (num != 0) {
            count++;
            num /= 10;
        }
        return count;
    }

// convert to the String first and use the length.
// time:O(n * len(n)) space:O(1)
// Runtime: 2ms
public int findNumbers(int[] nums) {
        int n = nums.length;
        if (nums == null || n == 0) return 0;
        int res = 0;
        for(int num : nums) {
            res += (String.valueOf(num).length() % 2 == 0) ? 1 : 0;
        } 
        return res;
    }

[Medium] 1296. Divide Array in Sets of K Consecutive Numbers

Solution

Use the PriorityQueue to maintain the order of number and use the k to iterate the following k numbers and check at the end.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// time:O(nlogn) space:O(n)
public boolean isPossibleDivide(int[] nums, int k) {
        int n = nums.length;
        if (nums == null || n == 0) return false;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : nums) pq.offer(num);
        int count = k;
        while (!pq.isEmpty()) {
            count--;
            int cur = pq.poll();
            while (count > 0) { // remove the consecutive one
                if (!pq.remove(cur + 1)) return false;
                else {
                    cur += 1;
                    count--;
                }
            }
            if (count == 0) count = k;
        }
        return pq.isEmpty() && count == k;
    }

[Medium] 1297. Maximum Number of Occurrences of a Substring

Solution

Use the sliding window strategy, use one HashMap (Counter) to keep tracking the number of each distinct character, another one (Map) to maintain the number of same satisfying string. Also, we only need to focus on minSize, because the smaller size it maintains the larger number we might get, and forget the maxSize.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        if (s == null || s.length() == 0) return 0;
        int start = 0;
        int end = 0;
        int res = 0;
        HashMap<Character, Integer> counter = new HashMap<>(); // maintain the number of each character
        HashMap<String, Integer> map = new HashMap<>(); // maintain the number of the satisfying string
        while (end < s.length()) {
            counter.put(s.charAt(end), counter.getOrDefault(s.charAt(end), 0) + 1);
            while (end + 1 - start > minSize) { // when the length is greater than minSize, move start pointer.
                counter.put(s.charAt(start), counter.get(s.charAt(start)) - 1);
                if (counter.get(s.charAt(start)) == 0) {
                    counter.remove(s.charAt(start));
                }
                start++;
            }
            if (end + 1 - start == minSize && counter.size() <= maxLetters) { // compare the max and add to the result.
                String str = s.substring(start, end + 1);
                map.put(str, map.getOrDefault(str, 0) + 1);
                res = Math.max(res, map.get(str));
            }
            end++;
        }
        return res;
    }

[Hard] 1298. Maximum Candies You Can Get from Boxes

Solution

Use BFS and keep tracking of boxes and keys we can get and add to the queue.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        // 利用BFS加入既有钥匙又有盒子的人。
        HashSet<Integer> hasKeys = new HashSet<>();   
        HashSet<Integer> hasBoxes = new HashSet<>();  
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < status.length; i++) {
            if (status[i] == 1) hasKeys.add(i);
        }
        for (int box : initialBoxes) {
            hasBoxes.add(box);
            if (hasKeys.contains(box)) queue.offer(box);
        }
        int res = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            res += candies[cur];
            // check the boxes in it.
            for (int box : containedBoxes[cur]) {
                hasBoxes.add(box);
                if (hasKeys.contains(box)) queue.offer(box);
            }
            // check the keys in it.
            for (int key: keys[cur]) {
                // 防止多个key导致的死循环
                if (!hasKeys.contains(key) && hasBoxes.contains(key)) queue.offer(key);
                hasKeys.add(key);
            }
        }
        return res;
    }

Reference:

Rank: 1744/5525. Solved 2/4 in 27min 02s.