Leetcode

134. Gas Station There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique ...

287. Find the Duplicate Number Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and uses only constant extra space. Example 1: Input: nums = [1,3,4,2,2] Output: 2 Example 2: Input: nums = [3,1,3,4,2] Output: 3 Example 3: Input: nums = [1,1] Output: 1 Example 4: Input: nums = [1,1,2] Output: 1 Constraints: ...

621. Task Scheduler Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle. However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks. ...

252. Meeting Rooms Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings. Example 1: Input: intervals = [[0,30],[5,10],[15,20]] Output: false Example 2: Input: intervals = [[7,10],[2,4]] Output: true Constraints: 0 <= intervals.length <= 10^4 intervals[i].length == 2 0 <= starti < endi <= 10^6 Solution class Solution { public boolean canAttendMeetings(int[][] intervals) { if (intervals.length < 2) { return true; } Arrays.sort(intervals, (a, b) -> a[0] - b[0]); for (int i = 1; i < intervals.length; i++) { int[] curr = intervals[i]; int[] prev = intervals[i - 1]; if (overlap(prev, curr)) { return false; } } return true; } /* ---------------| |-------------------------- -----------| |-------------- */ boolean overlap(int[] a, int[] b) { return Math.max(a[0], b[0]) < Math.min(a[1], b[1]); } }

253. Meeting Rooms II Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required. Example 1: Input: intervals = [[0,30],[5,10],[15,20]] Output: 2 Example 2: Input: intervals = [[7,10],[2,4]] Output: 1 Constraints: 1 <= intervals.length <= 10^4 0 <= starti < endi <= 10^6 Solution class Solution { /* [[0,30],[5,10],[15,20]] [ 0,30] [ 5,10] ---- [15,20] (1, 10), (2, 7), (3, 19), (8, 12), (10, 20), (11, 30) */ public int minMeetingRooms(int[][] intervals) { Arrays.sort(intervals, (a,b) -> a[0] - b[0]); PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a,b) -> { return a[1] - b[1]; }); for (int[] interval: intervals) { if (!pq.isEmpty() && pq.peek()[1] <= interval[0]) { pq.poll(); } pq.add(interval); } return pq.size(); } } Solution 2 class Solution { public int minMeetingRooms(int[][] intervals) { Integer min = Integer.MAX_VALUE; Integer max = Integer.MIN_VALUE; for (int[] i: intervals) { min = Math.min(min, i[0]); max = Math.max(max, i[1]); } int[] times = new int[max - min + 1]; for (int[] i: intervals) { times[i[0] - min]++; times[i[1] - min]--; } int count = 0; int result = 0; for (int time: times) { count += time; result = Math.max(result, count); } return result; } }

314. Binary Tree Vertical Order Traversal Given the root of a binary tree, return the vertical order traversal of its nodes’ values. (i.e., from top to bottom, column by column). If two nodes are in the same row and column, the order should be from left to right. Example 1: Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]] Example 2: Input: root = [3,9,8,4,0,1,7] Output: [[4],[9],[3,0,1],[8],[7]] Example 3: Input: root = [3,9,8,4,0,1,7,null,null,null,2,5] Output: [[4],[9,5],[3,0,1],[8,2],[7]] ...

987. Vertical Order Traversal of a Binary Tree Given the root of a binary tree, calculate the vertical order traversal of the binary tree. For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0). The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values. ...

157. Read N Characters Given Read4 Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters. Method read4: The API read4 reads four consecutive characters from file, then writes those characters into the buffer array buf4. The return value is the number of actual characters read. Note that read4() has its own file pointer, much like FILE *fp in C. ...

303. Range Sum Query - Immutable Given an integer array nums, handle multiple queries of the following type: Calculate the sum of the elements of nums between indices left and right inclusive where left <= right. Implement the NumArray class: NumArray(int[] nums) Initializes the object with the integer array nums. int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + … + nums[right]). Example 1: Input ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] Output [null, 1, -1, -3] Explanation NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1 numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1 numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3 Constraints: ...

1482. Minimum Number of Days to Make m Bouquets Given a string s, reverse only all the vowels in the string and return it. The vowels are ‘a’, ’e’, ‘i’, ‘o’, and ‘u’, and they can appear in both cases. Example 1: Input: s = "hello" Output: "holle" Example 2: Input: s = "leetcode" Output: "leotcede" Constraints: 1 <= s.length <= 3 * 105 s consist of printable ASCII characters. Solution class Solution { public String reverseVowels(String s) { Set<Character> vowels = new HashSet<>(); vowels.addAll(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U')); int lo = 0; int hi = s.length() - 1; char[] word = s.toCharArray(); while (lo < hi) { while (lo < hi && !vowels.contains(word[lo])) { lo++; } while (lo < hi && !vowels.contains(word[hi])) { hi--; } char c = word[lo]; word[lo] = word[hi]; word[hi] = c; lo++; hi--; } return new String(word); } }