Daily Temperatures String Compression Course Schedule II Split Array Largest Sum Insert Interval
First Unique Character in a String Random Pick with Weight Reorder List Concatenated Words Palindrome Number
Beta
EQ-1
Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead. For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0]. Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
# 739. Daily Temperatures
class Solution: def dailyTemperatures(self, T: List[int]) -> List[int]:
right_max = float("-inf") res = [0] * len(T)
for i in reversed(range(len(T))): curr = T[i] if curr >= right_max: right_max = curr else: count = 1 while T[i+count] <= curr: count += res[i+count] res[i] = count
returnres
EQ-2
Given an array of characters, compress it in-place. The length after compression must always be smaller than or equal to the original array. Every element of the array should be a character (not int) of length 1. After you are done modifying the input array in-place, return the new length of the array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
# 443. String Compression
classSolution: defcompress(self, chars: List[str]) -> int: cnt = 1 fori in reversed(range(len(chars))): ifi > 0 and chars[i]==chars[i-1]: cnt+= 1 chars.pop(i) else: ifcnt > 1: # for the case there are 12 b forval in str(cnt)[::-1]: chars.insert(i+1,val) cnt = 1
EQ-3 *
There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
class Solution: def findOrder(self, numCourses:int, prerequisites: List[List[int]]) -> List[int]: adj = [[] for _ in range(numCourses)] inorders = [0for _ in range(numCourses)] for course, pre in prerequisites: adj[pre].append(course) inorders[course] += 1 queue = [i for i in range(numCourses) if inorders[i] == 0] ans = [] while queue: course = queue.pop() for next_course in adj[course]: inorders[next_course] -= 1 if inorders[next_course] == 0: queue.append(next_course) ans.append(course) iflen(ans) != numCourses: return [] return ans
class Solution1: def findOrder(self, numCourses:int, prerequisites: List[List[int]]) -> List[int]:
dic = collections.defaultdict(set) neigh = collections.defaultdict(set) for i, j in prerequisites: dic[i].add(j) neigh[j].add(i) stack = [i for i in range(numCourses) if not dic[i]] res = [] while stack: node = stack.pop() res.append(node) for i in neigh[node]: dic[i].remove(node) if not dic[i]: stack.append(i) dic.pop(node) returnresif not dic else []
EQ-4
Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.
class Solution(object): def is_valid(self, nums, m, mid): # assume mid is < max(nums) cuts, curr_sum = 0, 0 for x in nums: curr_sum += x if curr_sum > mid: cuts, curr_sum = cuts+1, x subs = cuts + 1 return (subs <= m)
def splitArray(self, nums: List[int], m: int) -> int: low, high, ans = max(nums), sum(nums), -1 while low <= high: mid = (low+high)//2 if self.is_valid(nums, m, mid): # can you make at-most m sub-arrays with maximum sum atmost mid ans, high = mid, mid-1 else: low = mid + 1 return ans
EQ-5
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times.
1 2 3 4 5 6 7 8 9 10 11 12 13
# 57. Insert Interval
class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: start, end = newInterval[0], newInterval[1] l, r = [], [] forintervalin intervals: ifinterval[1] < start: l += interval, elif interval[0] > end: r += interval, else: start = min(start, interval[0]) end = max(end, interval[1]) return l + [[start, end]] + r
EQ-6
Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.
classSolution: deffirstUniqChar(self, s: str) -> int: minChar = len(s) for letter in string.ascii_lowercase: left = s.find(letter) if left != -1and left == s.rfind(letter): if left < minChar: minChar = left return minChar if minChar != len(s) else-1
classSolution1: deffirstUniqChar(self, s: str) -> int: # build hash map : character and how often it appears count = collections.Counter(s) # find the index for idx, ch in enumerate(s): if count[ch] == 1: return idx return-1
classSolution2: deffirstUniqChar(self, s: str) -> int: letters='abcdefghijklmnopqrstuvwxyz' #找到出现次数为1的字母，该字母在s中的最小索引位置 index=[s.index(l) for l in letters if s.count(l) == 1] return min(index) if index else-1
classSolution3: deffirstUniqChar(self, s: str) -> int: Hashmap={} #使用ord和chr判断比 for i in string.ascii_lowercase速度快 for i in range(ord('a'), ord('z')+1): if s.count(chr(i)) == 1: Hashmap[chr(i)] = True#字典赋值可以是任何值 ifnot Hashmap:#特殊情况先判断可减少时间 return-1 for i in range(len(s)): if s[i] in Hashmap:#使用Hashmap.keys()会增加时间 return i
classSolution4: deffirstUniqChar(self, s: str) -> int: d={} for ch in s: d[ch]=d.get(ch, 0) + 1 for i in range(len(s)): if d[s[i]] == 1: return i return-1
EQ-7
Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None
class Solution: def reorderList(self, head: ListNode) -> None: """ Do not return anything, modify head in-place instead. """ if not head: return slow, fast = head, head while fast and fast.next: slow = slow.next fast = fast.next.next
head1, head2 = head, slow.next slow.next, cur, pre = None, head2, None while cur: curnext = cur.next cur.next = pre pre = cur cur = curnext
Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.