---
# System prepended metadata

title: Leetcode

---

# 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
    
```