# Leetcode
## Python tips:
The following evaluates to `False` when used in `if` statements:
- `0`, `False`, `None`, `[]`, `''`
Other tips:
```python
# Null (in C: NULL or 0, in C++ 11: nullptr)
a = None
# Loops
for i in range(50):
pass
while condition:
pass
# Sorting
a.sort()
a.sort(key=lambda x:x[1])
a.sort(key=lambda x:x[1], reverse=True)
sorted(a) # returns a copy
# Reverse
a.reverse()
reversed(a) # returns a copy
# convert string in base n to int
int("0101001", 2)
# Power
5.2e3 == 5200 # as a constant
a ** 3 # power
import math
math.pow(a, 3) # same as a ** 3
# Set
a = set()
a.add(1)
a.add(2)
a.add(3)
a.remove(1)
if 2 in a:
print('2 is in a')
print('here are some things in a')
for i in a:
print(i)
# Increment
i += 1 # i++ is not allowed
# List
a = [1, 2]
a.append(3)
a.append(4)
for i in range(len(a)):
print(a[i]) # loop index
for i in range(1, len(a)):
print(a[i]) # loop starting from 1
for x in a:
print(x) # loop element
for i in range(len(a) - 1, -1, -1): # range(start, stop, step)
print(a[i]) # loop index backward
a.insert(index, element)
# List comprehension
a = [i for i in range(5)] # [0, 1, 2, 3, 4]
a = [[0 for j in range(2)] for i in range(2)] # [[0, 0], [0, 0]]
a = [0] * 5 #[0, 0, 0, 0, 0]
a = {i: i*2 for i in range(5)}
# Slicing
# (This also works for strings and tuples)
a = [1, 2, 3, 4]
a[2:] # [3, 4]
a[:2] # [1, 2]
a[1:3] # [2, 3]
a[-1] # 4
a[::-1] # return reversed copy
#priority queue
>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')
heapq.nlargest(n, iterable[, key])
heapq.nsmallest(n, iterable[, key])
# Tuple
a = (1, 2)
b, c = a # b = 1, c = 2
# tuples are immutable
# a[1] = 5 is NOT allowed
# Ternary operator
a if condition else b
# Fraction (rational number)
from fractions import Fraction # Python 2
a = Fraction(2, 3) # numerator, denominator
a + 5 # support arithmetics
a < 5 # support comparison
a.numerator, a.denominator # access
# deep copy
from copy import deepcopy
a = [[0, 1], [2, 3]]
b = deepcopy(a)
a[0][1] = 4
b[0][1] # 1
# split and join
a = "a b c"
b = a.split()# split by space return list. can split(",")
string_name.join(iterable) #string name is the join thing(like - , ""), iterable is something like list
"".join(b) #abc
a = {}
b = []
del a[key]
del b[index]
b.remove(value) #doesn't return anything
b.pop(index) #return value
#list concatenating
list_a = [1, 2, 3, 4]
list_b = [5, 6, 7, 8]
list_c = list_a + lis_b
print list_c # Output: [1, 2, 3, 4, 5, 6, 7, 8]
# Queue
from queue import Queue
q = Queue()
q.put(1)
q.put(2)
q.get() # 1
q.get() # 2
q.empty() # True
# counter
collection.Counter()
# create map with for loop in side
ind = {c: i for i, c in enumerate(order)}
```
Library && function
```python
string_name.isalnum()
# checks whether all the characters in a
# given string is alphanumeric or not
string.lower()
string.upper()
float('-inf')
float('inf'))
binary = int("0101",2)
bin(binary) # convert back to string with 0b
string.zfill(len)
#adds zeros (0) at the beginning of the string,
# until it reaches the specified length.
```
## Problems
### Two sum (#1)
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
```python
class Solution(object):
def twoSum(self, nums, target):
if len(nums) <= 1:
return False
buff_dict = {}
for i in range(len(nums)):
if nums[i] in buff_dict:
return [buff_dict[nums[i]], i]
else:
buff_dict[target - nums[i]] = i
```
### Add two numbers (#2)
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
```python
class Solution:
# @return a ListNode
def addTwoNumbers(self, l1, l2):
carry = 0
root = n = ListNode(0)
while l1 or l2 or carry:
v1 = v2 = 0
if l1:
v1 = l1.val
l1 = l1.next
if l2:
v2 = l2.val
l2 = l2.next
carry, val = divmod(v1+v2+carry, 10)
n.next = ListNode(val)
n = n.next
return root.next
```
### Longest Substring Without Repeating Characters (#3)
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
```python
class Solution:
# @return an integer
def lengthOfLongestSubstring(self, s):
start = maxLength = 0
usedChar = {}
for i in range(len(s)):
if s[i] in usedChar and start <= usedChar[s[i]]:
start = usedChar[s[i]] + 1
else:
maxLength = max(maxLength, i - start + 1)
usedChar[s[i]] = i
return maxLength
```
### Median of two sorted arrays (#4)
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
```python
def median(A, B):
m, n = len(A), len(B)
if m > n:
A, B, m, n = B, A, n, m
if n == 0:
raise ValueError
imin, imax, half_len = 0, m, (m + n + 1) / 2
while imin <= imax:
i = (imin + imax) / 2
j = half_len - i
if i < m and B[j-1] > A[i]:
# i is too small, must increase it
imin = i + 1
elif i > 0 and A[i-1] > B[j]:
# i is too big, must decrease it
imax = i - 1
else:
# i is perfect
if i == 0: max_of_left = B[j-1]
elif j == 0: max_of_left = A[i-1]
else: max_of_left = max(A[i-1], B[j-1])
if (m + n) % 2 == 1:
return max_of_left
if i == m: min_of_right = B[j]
elif j == n: min_of_right = A[i]
else: min_of_right = min(A[i], B[j])
return (max_of_left + min_of_right) / 2.0
```
### ZigZag conversion
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
```python
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if numRows == 1 or numRows >= len(s):
return s
L = [''] * numRows
index, step = 0, 1
for x in s:
L[index] += x
if index == 0:
step = 1
elif index == numRows -1:
step = -1
index += step
return ''.join(L)
```
Tips:
```python
L = [''] * numRows # ['','',''] if numRows = 3
''.join(L)
```
### Reverse Integer
Input: -123
Output: -321
```python
def reverse(self, x):
s = cmp(x, 0)
r = int(`s*x`[::-1])
return s*r * (r < 2**31)
```
Tips:
```python
r = int(`s*x`[::-1])
s = cmp(x, 0) #cmp(a,b) a<b return -1, = return 0, > return 1
```
### String to Integer (atoi)
```python
class Solution(object):
def myAtoi(self, s):
"""
:type str: str
:rtype: int
"""
###better to do strip before sanity check (although 8ms slower):
#ls = list(s.strip())
#if len(ls) == 0 : return 0
if len(s) == 0 : return 0
ls = list(s.strip())
sign = -1 if ls[0] == '-' else 1
if ls[0] in ['-','+'] : del ls[0]
ret, i = 0, 0
while i < len(ls) and ls[i].isdigit() :
ret = ret*10 + ord(ls[i]) - ord('0')
i += 1
return max(-2**31, min(sign * ret,2**31-1))
```
Tips:
```python
s.strip() #remove the leading and trailing whitespaces
s.replace(" ","") #remve all whitesspaces
del ls[0] # delete element from list and dict
s.isdigit() #if the entire string is digit
ord(ls[i]) #function returns the ASCII code of the character.
chr(97) #function returns character represented by a ASCII number.
== #can directly compare string using != >= <= ==..
```
### Container with most water (#11)
```python
def maxArea(self, height):
L, R, width, res = 0, len(height) - 1, len(height) - 1, 0
for w in range(width, 0, -1):
if height[L] < height[R]:
res, L = max(res, height[L] * w), L + 1
else:
res, R = max(res, height[R] * w), R - 1
return res
```
### Reverse Words in a String III (#557)
```python
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
a = s.split()
b = map(lambda x: "".join(list(x)[::-1]), a)
return " ".join(b)
```
Tips:
```python
list(string) can split string to char list
[::-1] reverse list
```
Sign in with Wallet
Connect another wallet