-
Leetcode BiWeekly Contest 11
Missing Number In Arithmetic Progression Just search if there is any neighbor value difference is not equal to the difference of others. The time complexity is O(N). def missingNumber(self, arr): """ :type arr: List[int] :rtype: int """ diff = (arr[-1] - arr[0])/(len(arr)) for i in range(1, len(arr)): if arr[i] - arr[i-1] != diff: return arr[i] - diff return arr[0] Meeting Scheduler …
-
Leetcode Weekly Contest 158
Split a String in Balanced Strings We can just use greedy search. Whenever there is left count equals right count, we clear both count and add 1 to final answer. The time complexity is O(N) def balancedStringSplit(self, s): """ :type s: str :rtype: int """ l, r, cnt = 0, 0, 0 for i in s: if i == "L": l += 1 else: r += 1 if l == r: cnt += 1 l = 0 r = 0 return cnt Queens That Can Attack the King …
-
What methods are in Java Object class?
In Java, Object class is the base class for any classes. According to the official document of [Java][https://docs.oracle.com/javase/7/docs/api/java/lang/Object.html], the Object class have 11 methods: …
-
Leetcode Weekly Contest 157
Play with Chips Since moving chips with 2 units cost 0, all chips on even index can be moved to position 0 with no cost and all chips on odd index can be move to position 1 with no cost. So we compare the number of chips on even index and number of chips on odd index and return the smaller one. The time complexity is O(N) def minCostToMoveChips(self, chips): """ :type chips: List[int] :rtype: int """ odd = 0 even = 0 for i in chips: if i%2==0: even+=1 else: odd+=1 return min(even, odd) Longest Arithmetic Subsequence of Given Difference …
-
Leetcode BiWeekly Contest 10
Intersection of Three Sorted Arrays We just convert three arrays into set and calculate the intersection of them and return the sorted result list. The time complexity is O(N^2) since we do intersection two times. def arraysIntersection(self, arr1, arr2, arr3): """ :type arr1: List[int] :type arr2: List[int] :type arr3: List[int] :rtype: List[int] """ ans = set(arr1).intersection(set(arr2)).intersection(set(arr3)) return sorted(list(ans)) Since the original three arrays are sorted. We can have another O(N) time solution, which use pointers. def arraysIntersection(self, arr1, arr2, arr3): """ :type arr1: List[int] :type arr2: List[int] :type arr3: List[int] :rtype: List[int] """ ans = [] p1, p2, p3 = 0, 0, 0 while p1 < len(arr1) and p2 < len(arr2) and p3 < len(arr3): minV = min(arr1[p1], arr2[p2], arr3[p3]) # If minV are in all three arrays, we add it to the answer if minV == arr1[p1] == arr2[p2] == arr3[p3]: ans.append(minV) # We moving the pointer if value in array equals minV if minV == arr1[p1]: p1 += 1 if minV == arr2[p2]: p2 += 1 if minV == arr3[p3]: p3 += 1 return ans Two Sum BSTs …
-
Leetcode Weekly Contest 156
Unique Number of Occurrences Use a map to remember the number of occurrences of each number in the array. Then we use set to remove duplicate to see if all number of occurrences are unique. The time complexity is O(N) def uniqueOccurrences(self, arr): """ :type arr: List[int] :rtype: bool """ dic = {} for i in arr: if i not in dic: dic[i] = 0 dic[i] += 1 return len(dic.values()) == len(set(dic.values())) Get Equal Substrings Within Budget …
-
Leetcode BiWeekly Contest 9
How Many Apples Can You Put into the Basket Sort the array and greedily choose the minimum apple until we can’t. The time complexity is O(N). def maxNumberOfApples(self, arr): """ :type arr: List[int] :rtype: int """ arr.sort() i = 0 cur = 0 if sum(arr) <= 5000: return len(arr) while i < len(arr) and cur <= 5000: cur += arr[i] i += 1 return i - 1 Minimum Knight Moves …
-
Leetcode Weekly Contest 154
Maximum Number of Balloons We use a map to count the number of occurrences of each letter in the text. The answer should be the minimum count of ‘b’, ‘a’, ‘n’ and half of ‘l’ and ‘o’. The time complexity is O(N). def maxNumberOfBalloons(self, text): """ :type text: str :rtype: int """ dic = {} for i in text: if i not in dic: dic[i] = 0 dic[i] += 1 for i in ['b', 'a', 'l', 'o', 'n']: if i not in dic: return 0 return min(dic['b'], dic['a'], dic['l']/2, dic['o']/2, dic['n']) Reverse Substrings Between Each Pair of Parentheses …
-
Leetcode Biweekly Contest 8
Count Substrings with Only One Distinct Letter From the start, we count the length of substrings that only contains one letter. For each such substring of length k, we can parse it into (k+1)*k/2 goal substrings. The time complexity is O(n). def countLetters(self, s): """ :type S: str :rtype: int """ if not s: return 0 cur = s[0] count = 0 ans = 0 for i in range(len(s)): if s[i] != cur: ans += (count+1)*count/2 count = 0 cur = s[i] count += 1 ans += (count+1)*count/2 return ans Before and After Puzzle …
-
Leetcode Biweekly Contest 7
Single-Row Keyboard Firstly, we use an hashmap to remember each character’s index, so we can get any character’s index in O(1) time. Next start from the index 0, we iteratively sum the index difference between current character and next character, then we update current character. The time complexity is O(n). def calculateTime(self, keyboard, word): """ :type keyboard: str :type word: str :rtype: int """ # Use an hashmap to remember each character's index of the keyboard dic = {} for i, v in enumerate(keyboard): dic[v] = i if len(word)<=1: return 0 # Iteratively get the index difference as the moving steps and sum the steps ans = 0 cur = keyboard[0] for i in range(len(word)): ans += abs(dic[cur] - dic[word[i]]) cur = word[i] return ans Design File System …