Skip to content

Commit dc6fea4

Browse files
author
Chris Wu
committed
no message
1 parent 528b143 commit dc6fea4

10 files changed

Lines changed: 408 additions & 2 deletions

‎problems/h-index-ii.py‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
"""
2+
Time: O(LogN)
3+
Space: O(1)
4+
5+
Since citations is sorted,
6+
i = N-1, if 1<=citations[i], it means that at least 1 of the citations is larger than 1. h-index is 1.
7+
i = N-2, if 2<=citations[i], it means that at least 2 of the citations is larger than 2. h-index is 2.
8+
...
9+
i = 0, if N<=citations[i], it means that at least N of the citations is larger than N. h-index is N.
10+
11+
We can iterate from N-1 to 0. See what h-index ends up. Using O(N) of time.
12+
13+
We can also binary search the i, see which i match the condition.
14+
"""
15+
class Solution(object):
16+
def hIndex(self, citations):
17+
N = len(citations)
18+
19+
l = 0
20+
r = N-1
21+
22+
while l<r:
23+
i = (l+r)/2
24+
h = N-i
25+
26+
if citations[i]>=h:
27+
#h may be the h-index, check larger h.
28+
r = i
29+
else:
30+
#h is not h-index, check smaller h.
31+
l = i+1
32+
33+
#now, l is equal to r
34+
35+
return N-l if citations[l]!=0 else 0 #take care of edge case [0], [0, 0] or [0, 0, 0]

‎problems/h-index.py‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
"""
2+
First, reverse sort the list and iterate though it.
3+
i = 0, if 1>=citations[i], it means that at least 1 of the citations is larger than 1.
4+
i = 1, if 2>=citations[i], it means that at least 2 of the citations is larger than 2.
5+
i = 3, if 3>=citations[i], it means that at least 3 of the citations is larger than 3.
6+
...
7+
...
8+
Keep iterating until we fail the condition.
9+
10+
Time: O(NLogN)
11+
Space: O(1)
12+
"""
13+
class Solution(object):
14+
def hIndex(self, citations):
15+
citations.sort(reverse=True)
16+
17+
ans = 0
18+
for i in xrange(len(citations)):
19+
if i+1>citations[i]: break
20+
ans = i+1
21+
22+
return ans
23+
24+
25+
"""
26+
First, count each citation and store it in counter.
27+
The citation that is larger than N will be stored to N. [0]
28+
Since for citations, the max possible h-index will be N (the length of the citations).
29+
This can greatly reduce the index we go through when we iterate through counter.
30+
31+
Second, since the max possible h-index is N, we start from N and iterate to 0.
32+
Check if any of them is answer
33+
34+
Time: O(N)
35+
Space: O(N)
36+
"""
37+
import collections
38+
39+
class Solution(object):
40+
def hIndex(self, citations):
41+
counter = collections.Counter() #count for each citation
42+
N = len(citations)
43+
count = 0
44+
45+
for citation in citations:
46+
counter[min(N, citation)] += 1 #[0]
47+
48+
for n in xrange(N, -1, -1):
49+
count += counter[n] #count of citation that is larger or equal to n
50+
if count>=n: return n
51+
52+
return 0

‎problems/isomorphic-strings.py‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
"""
2+
The description of the problem is unclear, let me rephrase it.
3+
4+
Given two strings s and t, determine if they are isomorphic.
5+
Two strings s and t are isomorphic if the characters in s can be replaced to get t and t can be replaced to get s.
6+
7+
For each replacement, the characters in the same string must be replaced with another character while preserving the order of characters.
8+
No two characters in the same string may map to the same character, but a character may map to itself.
9+
10+
Two replacement are independent from each other. In other words, s -> t and t -> s does not affect each other.
11+
"""
12+
13+
"""
14+
Time: O(N)
15+
Space: O(N)
16+
"""
17+
class Solution(object):
18+
def isIsomorphic(self, s, t):
19+
if len(s)!=len(t): return False
20+
21+
# check if s1 chars could be replaced and become s2
22+
def helper(s1, s2):
23+
memo = {}
24+
25+
for i in xrange(len(s)):
26+
c1 = s1[i]
27+
c2 = s2[i]
28+
29+
if c1 in memo and memo[c1]!=c2: return False
30+
memo[c1] = c2
31+
return True
32+
33+
return helper(s, t) and helper(t, s)

‎problems/longest-substring-without-repeating-characters.py‎

Lines changed: 24 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,4 +46,27 @@ def lengthOfLongestSubstring(self, s):
4646
lastSeen[c] = i
4747
maxLength = max(maxLength, i-start+1)
4848

49-
return maxLength
49+
return maxLength
50+
51+
52+
"""
53+
Time: O(N).
54+
Space: O(N).
55+
56+
Iterate throught s, while constantly update the "start" using "lastSeen".
57+
start~i does not have repeated character.
58+
Also, start should only be incremental [0]
59+
consider case `s = abba`, some at some point `lastSeen[c]` might be smaller than current start.
60+
"""
61+
class Solution(object):
62+
def lengthOfLongestSubstring(self, s):
63+
ans = 0
64+
start = 0
65+
lastSeen = {}
66+
67+
for i, c in enumerate(s):
68+
if c in lastSeen: start = max(start, lastSeen[c]+1) #[0]
69+
lastSeen[c] = i
70+
ans = max(ans, i-start+1)
71+
72+
return ans

‎problems/palindrome-pairs.py‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
"""
2+
Time: O(N x L^2), assume the average length of word is L. Note that, eversing the string takes O(L).
3+
Space: O(L), beside from ans, need `left` and `right` constantly to store the word.
4+
"""
5+
class Solution(object):
6+
def palindromePairs(self, words):
7+
ans = set()
8+
index = {word:i for i, word in enumerate(words)}
9+
10+
for i, word in enumerate(words):
11+
for j in xrange(len(word)+1):
12+
left = word[:j]
13+
right = word[j:]
14+
15+
# check if any other word that concat to the left will make palindrome: "OTHER_WORD+`left`+`right`"
16+
# The above will be palindrome only if
17+
# 1. `left` is palindrome (left==left[::-1])
18+
# 2. Exsit an "OTHER_WORD" in word in words that equals to the reverse of `right` (right[::-1] in index and index[right[::-1]]!=i).
19+
if left==left[::-1]:
20+
if right[::-1] in index and index[right[::-1]]!=i:
21+
ans.add((index[right[::-1]], i))
22+
23+
# check if any other word that concat to the right will make palindrome: "`left`+`right`+OTHER_WORD"
24+
# The above will be palindrome only if
25+
# 1. `rihgt` is palindrome (right==right[::-1])
26+
# 2. Exsit an "OTHER_WORD" in words that equals to the reverse of `left` (left[::-1] in index and index[left[::-1]]!=i).
27+
if right==right[::-1]:
28+
if left[::-1] in index and index[left[::-1]]!=i:
29+
ans.add((i, index[left[::-1]]))
30+
31+
return ans
32+
33+
34+
"""
35+
Time: O(N^2 x L), will cause TLE.
36+
Space: O(L), can reduce to O(1) by improving isPalindrome()
37+
"""
38+
class Solution(object):
39+
def palindromePairs(self, words):
40+
N = len(words)
41+
ans = []
42+
43+
for i in xrange(N):
44+
for j in xrange(N):
45+
if i==j: continue
46+
if self.isPalindrome(words[i]+words[j]):
47+
ans.append([i, j])
48+
return ans
49+
50+
def isPalindrome(self, word):
51+
l = 0
52+
r = len(word)-1
53+
54+
while l<=r:
55+
if word[l]==word[r]:
56+
l += 1
57+
r -= 1
58+
else:
59+
return False
60+
return True
61+
62+

‎problems/russian-doll-envelopes.py‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
"""
2+
dp[i] := number of envelopes that envelopes[i] can contains the most.
3+
Very similar to LIS problem (Leetcode 300)
4+
This method will get TLE
5+
6+
Time: O(N^2)
7+
Space: O(N)
8+
"""
9+
class Solution(object):
10+
def maxEnvelopes(self, envelopes):
11+
if not envelopes: return 0
12+
13+
N = len(envelopes)
14+
dp = [1]*N
15+
envelopes = sorted(envelopes)
16+
ans = 1
17+
18+
for i in xrange(N):
19+
for j in xrange(i):
20+
if envelopes[i][0]>envelopes[j][0] and envelopes[i][1]>envelopes[j][1]:
21+
dp[i] = max(dp[i], dp[j]+1)
22+
ans = max(ans, dp[i])
23+
24+
return ans
25+
26+
"""
27+
dp[i] := the smallest ending number of a sequence that has length i+1
28+
First, sort the envelopes by width. (envelope[0])
29+
Second, return the LIS of heights ([envelope[1] for envelope in envelopes]).
30+
This automatically gets the number of "russian dolls".
31+
32+
However, we might choose [3,4], [3,7] as a valid solution. This is not correct because w1==w2.
33+
So we do a quick fix by sorting the envelopes with w and h reversed.
34+
So that getLIS() will not choose [3,4], [3,7]
35+
36+
Time: O(NLogN)
37+
Space: O(N)
38+
"""
39+
import bisect
40+
class Solution(object):
41+
def maxEnvelopes(self, envelopes):
42+
if not envelopes: return 0
43+
44+
N = len(envelopes)
45+
dp = [1]*N
46+
envelopes = envelopes.sort(key=lambda x:(x[0], -x[1]))
47+
48+
return self.getLIS([envelope[1] for envelope in envelopes])
49+
50+
def getLIS(self, A):
51+
dp = []
52+
53+
for n in A:
54+
i = bisect.bisect_left(dp, n)
55+
56+
if i==len(dp):
57+
dp.append(n)
58+
else:
59+
dp[i] = n
60+
61+
return len(dp)

‎problems/subarray-sum-equals-k.py‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
"""
2+
Time: O(N^2), this will get TLE
3+
Space: O(N)
4+
5+
prefixSum[i] == sum(nums[:i]) (nums[0] + nums[1] + ... + nums[i-1])
6+
prefixSum[j]-prefixSum[i] == sum(nums[i:j]) (nums[i] + nums[i+1] + ... + nums[j-1])
7+
By iterating through all i and j possibilities, we get all the subarray sum that equals to k.
8+
"""
9+
class Solution(object):
10+
def subarraySum(self, nums, k):
11+
N = len(nums)
12+
prefixSum = [0]
13+
ans = 0
14+
15+
temp = 0
16+
for n in nums:
17+
temp += n
18+
prefixSum.append(temp)
19+
20+
for i in xrange(N+1):
21+
for j in xrange(i+1, N+1):
22+
if prefixSum[j]-prefixSum[i]==k: ans += 1
23+
24+
return ans
25+
26+
27+
"""
28+
Time: O(N)
29+
Space: O(N)
30+
31+
Let's optimize from above solution.
32+
Let prefixSum[j] as J.
33+
Let prefixSum[i] as I.
34+
35+
We are basically looking for J-I that equals to k. (J-I == k)
36+
In other words, given a J we are actually looking for an I that eauals to J-k.
37+
If there are, 3 I that equals to J-k exists beforehand, there are 3 J-I combinations that equal to k.
38+
ans += 3
39+
"""
40+
class Solution(object):
41+
def subarraySum(self, nums, k):
42+
N = len(nums)
43+
ans = 0
44+
45+
prefixSumCount = collections.Counter()
46+
prefixSumCount[0] = 1
47+
48+
J = 0
49+
for n in nums:
50+
J += n
51+
I = J-k #the I that we are looking for.
52+
ans += prefixSumCount[I] #there are "prefixSumCount[I]" combinations of J-I that equals to k.
53+
prefixSumCount[J] += 1
54+
55+
return ans

‎problems/substring-with-concatenation-of-all-words.py‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
"""
2+
Time: O(N*wl), N is the length of the input string s; wl is the length of each word.
3+
Space: O(N)
4+
5+
For word count wc and word length wl, the string we are looking for will be between i and j (s[i:j]).
6+
`test()` all s[i:j]. If pass, append into ans.
7+
8+
Each `test()` will test the sub-string s[i:j]`.
9+
If any "word" in the sub-string is not in the countExpected, the test failed.
10+
If the word is used too many times (more than "countExpected"), the test failed.
11+
Otherwise, the test pass.
12+
13+
This is the solution I learn from @gabbu.
14+
"""
15+
import collections
16+
17+
class Solution(object):
18+
def findSubstring(self, s, words):
19+
if not words: return []
20+
21+
wc = len(words) #word count
22+
wl = len(words[0]) #word length
23+
ans = []
24+
25+
i = 0
26+
j = wc*wl
27+
28+
countExpected = collections.Counter(words)
29+
30+
while j<=len(s):
31+
if self.test(s[i:j], wl, countExpected): ans.append(i)
32+
i += 1
33+
j += 1
34+
35+
return ans
36+
37+
38+
def test(self, s, wl, countExpected):
39+
counter = collections.Counter() #{word:how many time the word is used}
40+
i = 0
41+
42+
while i<len(s):
43+
word = s[i:i+wl]
44+
if word not in countExpected or counter[word]>=countExpected[word]: return False
45+
i += wl
46+
counter[word] += 1
47+
48+
return True
49+
50+

0 commit comments

Comments
 (0)