// more naive one, using getNum for calculating number of digit. // time:O(n * len(n)) space:O(1) // Runtime: 1ms publicintfindNumbers(int[] nums){ int n = nums.length; if (nums == null || n == 0) return0; int res = 0; for (int i = 0; i < n; i++) { int NumOfDigit = getNum(nums[i]); if (NumOfDigit % 2 == 0) res++; } return res; } publicintgetNum(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 publicintfindNumbers(int[] nums){ int n = nums.length; if (nums == null || n == 0) return0; 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.

// time:O(nlogn) space:O(n) publicbooleanisPossibleDivide(int[] nums, int k){ int n = nums.length; if (nums == null || n == 0) returnfalse; 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)) returnfalse; 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.

publicintmaxFreq(String s, int maxLetters, int minSize, int maxSize){ if (s == null || s.length() == 0) return0; 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.

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