leetcode-013

Alpha

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

return res

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

class Solution:
def compress(self, chars: List[str]) -> int:
cnt = 1
for i in reversed(range(len(chars))):
if i > 0 and chars[i]==chars[i-1]:
cnt += 1
chars.pop(i)
else:
if cnt > 1:
# for the case there are 12 b
for val 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.

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
36
37
38
39
40
41
42
# 210. Course Schedule II

class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adj = [[] for _ in range(numCourses)]
inorders = [0 for _ 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)
if len(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)
return res if 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 410. Split Array Largest Sum

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 = [], []
for interval in intervals:
if interval[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.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# 387. First Unique Character in a String

class Solution:
def firstUniqChar(self, s: str) -> int:
minChar = len(s)
for letter in string.ascii_lowercase:
left = s.find(letter)
if left != -1 and left == s.rfind(letter):
if left < minChar:
minChar = left
return minChar if minChar != len(s) else -1


class Solution1:
def firstUniqChar(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


class Solution2:
def firstUniqChar(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


class Solution3:
def firstUniqChar(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#字典赋值可以是任何值
if not Hashmap:#特殊情况先判断可减少时间
return -1
for i in range(len(s)):
if s[i] in Hashmap:#使用Hashmap.keys()会增加时间
return i


class Solution4:
def firstUniqChar(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.

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
# 528. Random Pick with Weight

import bisect, random
class Solution:

def __init__(self, w: List[int]):
self.bs = [0]
for weight in w:
self.bs.append(weight + self.bs[-1])

def pickIndex(self) -> int:
return bisect.bisect_right(self.bs, random.random()*self.bs[-1]) - 1


class Solution1:

def __init__(self, w: List[int]):
self.w = list(itertools.accumulate(w))

def pickIndex(self) -> int:
return bisect.bisect_left(self.w, random.randint(1, self.w[-1]))


# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()

EQ-8

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

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
# 143. Reorder List

# 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

cur1, cur2 = head1, pre
while cur2:
next1, next2 = cur1.next, cur2.next
cur1.next = cur2
cur2.next = next1
cur1, cur2 = next1, next2

EQ-9

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 472. Concatenated Words

class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:

words.sort(key = len)
minL = max(1, len(words[0]))
ans, seen = [], set()

def dfs(word):
if word in seen:
return True
for i in range(minL, len(word) - minL + 1):
if word[:i] in seen and dfs(word[i:]):
return True
return False

for word in words:
if dfs(word):
ans.append(word)
seen.add(word)

return ans

EQ-10

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

1
2
3
4
5
6
# 9. Palindrome Number

class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0: return False
return str(x) == str(x)[::-1]

Sigma

Feb 12, 2020
La Jolla, CA

Omega

https://leetcode.com/