Skip to content

Commit b84495c

Browse files
author
chris
committed
initial commit
0 parents  commit b84495c

39 files changed

+849
-0
lines changed

‎add-binary.py‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
#https://leetcode.com/problems/add-binary/
2+
class Solution(object):
3+
def addBinary(self, a, b):
4+
return bin(int(a, 2)+int(b, 2))[2:]

‎add-digits.py‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
#https://leetcode.com/problems/add-digits/
2+
class Solution(object):
3+
def addDigits(self, num):
4+
if num==0: return 0
5+
6+
while len(str(num))>1:
7+
counter = 0
8+
for i in str(num):
9+
counter+=int(i)
10+
num = counter
11+
return num

‎backspace-string-compare.py‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
#https://leetcode.com/problems/backspace-string-compare/
2+
class Solution:
3+
#Compare from backward. Because we need to count the hashtags first.
4+
#Compare the char that are not canceled by the hashtags, letter by letter.
5+
#So we don't have to convert the whole string if they are not the same.
6+
#Return Fasle, as soon as we find out that they are not the same.
7+
8+
def backspaceCompare(self, S1, S2):
9+
#index compared so far
10+
i = len(S1)-1
11+
j = len(S2)-1
12+
13+
while i>=0 or j>=0:
14+
#the first char that are not canceled by the hashtags
15+
c1 = ''
16+
c2 = ''
17+
18+
if i>=0:
19+
c1, i = self.getChar(S1, i)
20+
if j>=0:
21+
c2, j = self.getChar(S2, j)
22+
if c1!=c2:
23+
return False
24+
return True
25+
26+
def getChar(self, s, i):
27+
#return the first character that are not canceled by the hashtag
28+
#return inedx compared so far so we don't have to do that again
29+
c = ''
30+
hashtag = 0
31+
32+
while i>=0 and c=='':
33+
char = s[i]
34+
if char=='#':
35+
hashtag+=1
36+
elif hashtag==0:
37+
c = char
38+
else:
39+
hashtag-=1
40+
i-=1
41+
return c, i

‎best-time-to-buy-an-stock.py‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
#https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
2+
class Solution(object):
3+
def maxProfit(self, prices):
4+
if (len(prices)==0):
5+
return 0
6+
7+
minPrice = prices[0]
8+
maxProfit = 0
9+
for price in prices:
10+
if (price<minPrice):
11+
minPrice = price
12+
if (price-minPrice>maxProfit):
13+
maxProfit = price-minPrice
14+
return maxProfit

‎big-countries.sql‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
-- https://leetcode.com/problems/big-countries/
2+
select name, population, area from World where area>3000000 or population>25000000

‎climbing-stairs.py‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
#https://leetcode.com/problems/climbing-stairs/
2+
class Solution(object):
3+
#if there are 13 stairs
4+
#the max two steps are 6, so there can be
5+
#6 two step, 1 one step -> case1
6+
#5 two step, 3 one step -> case2
7+
# ...
8+
#0 two step, 13 one step -> case7
9+
10+
#each case may have more than one way to arrange
11+
#take case2 as example, 22222111. how many combination can it be?
12+
#you can think this as, there are 8 seats you have to choose 3 seats for number 1 to sit on it.
13+
14+
#we call this combination m choose n, thus
15+
#case1 is combination 7 choose 1
16+
#case2 is combination 8 choose 3
17+
# ...
18+
#case7 is combination 13 choose 13
19+
#the calculation of combination is m!/(n!*(m-n)!)
20+
#https://en.wikipedia.org/wiki/Combination
21+
22+
#Efficaiency is O(N), N is the stairs count.
23+
#Space is O(1)
24+
25+
def climbStairs(self, n):
26+
counter = 0
27+
max_two_step = n/2
28+
for two_step in range(max_two_step+1):
29+
one_step = n-two_step*2
30+
combination = self.combination(two_step+one_step, one_step)
31+
counter+=combination
32+
return counter
33+
34+
35+
#combination m choose n
36+
def combination(self, m, n):
37+
def factorial(int_num):
38+
if int_num<0: return None
39+
if int_num==0: return 1
40+
counter = 1
41+
while int_num>=1:
42+
counter*=int_num
43+
int_num-=1
44+
return counter
45+
46+
return factorial(m)/(factorial(n)*factorial(m-n))

‎combine-two-tables.sql‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
-- https://leetcode.com/problems/combine-two-tables/
2+
select FirstName, LastName, City, State
3+
from Person left join Address
4+
on Person.PersonId = Address.PersonId

‎convert-binary-search-tree-to-sorted-doubly-linked-list.py‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
#https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
2+
class Solution(object):
3+
def treeToDoublyList(self, root):
4+
5+
#the helper gets you an sorted double link list that originally start at node
6+
#if you put a node's left to the helper, it will need to return the right most node of the sorted link list
7+
#if you put a node's right to the helper, it will need to return the left most node of the sorted link list
8+
#so we use hook_left to control returning right most or left most
9+
def helper(node, hook_left=True):
10+
if node is None: return None
11+
node.left = helper(node.left)
12+
node.right = helper(node.right, False)
13+
14+
if node.left:
15+
node.left.right = node
16+
if node.right:
17+
node.right.left = node
18+
19+
if hook_left:
20+
while node.right:
21+
node = node.right
22+
else:
23+
while node.left:
24+
node = node.left
25+
26+
return node
27+
28+
29+
if root is None: return None
30+
31+
#get the right most before sorted(the right most is still right most after sorted)
32+
#we need this to link the left most after sorting
33+
#we do this before sorting because, it is faster to find the right most in the tree
34+
right_most = root
35+
while right_most.right:
36+
right_most = right_most.right
37+
38+
#get the sorted double link list that originally start at root
39+
#set hook_left to False, so it will return the left most (head)
40+
root = helper(root, False)
41+
42+
#linked two end together
43+
root.left = right_most
44+
right_most.right = root
45+
46+
return root

‎diameter-of-binary-tree.py‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
#https://leetcode.com/problems/diameter-of-binary-tree/
2+
#what we want to find?
3+
#max depth that goes right add max depth that goes left
4+
#it could be from any node
5+
#so we iterate through every node to update our the diameter to max
6+
7+
class Solution(object):
8+
def diameterOfBinaryTree(self, root):
9+
self.diameter = 0
10+
11+
def traverse(node):
12+
if not node: return 0
13+
14+
#the max depth go left from this node
15+
#the max depth go right from this node
16+
left, right = traverse(node.left), traverse(node.right)
17+
18+
#update diameter if left+right is bigger
19+
self.diameter = max(self.diameter, left+right)
20+
21+
#add 1 is for the step that get to this node
22+
#max(left, right) is for the left or right path that goes to the deepest
23+
return max(left, right)+1
24+
25+
#iterate through the tree
26+
traverse(root)
27+
return self.diameter

‎first-unique-character-in-a-string.py‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
#https://leetcode.com/problems/first-unique-character-in-a-string/
2+
class Solution(object):
3+
def firstUniqChar(self, string):
4+
counter = {}
5+
6+
for char in string:
7+
if char in counter:
8+
counter[char]+=1
9+
else:
10+
counter[char] = 1
11+
12+
for i in range(len(string)):
13+
char = string[i]
14+
if counter[char]==1:
15+
return i
16+
17+
return -1

0 commit comments

Comments
 (0)