1 – Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Solution:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
container = {}
for i, num in enumerate(nums):
if target - num in container:
return [container[target - num], i]
container[num] = i
return
2 – Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Solution:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class ListNode():
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
prev = result = ListNode(None)
n = 0
while l1 or l2 or n:
if l1:
n += l1.val
l1 = l1.next
if l2:
n += l2.val
l2 = l2.next
prev.next = ListNode(n % 10)
prev = prev.next
n //= 10
return result.next
3 – Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Solution:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
mapper = {}
start = 0
longest = 0
for i, c in enumerate(s):
if c in mapper and mapper[c] >= start:
start = mapper[c] + 1
else:
longest = max(longest, i - start + 1)
mapper[c] = i
return longest
4 – Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Solution:
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums1.extend(nums2)
nums1 = sorted(nums1)
if len(nums1) % 2 == 0:
n = len(nums1) // 2
return (nums1[n - 1] + nums1[n]) / 2
else:
n = (len(nums1) // 2) + 1
return nums1[n - 1]
5 – Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Solution:
class Solution:
def longestPalindrome(self, s: str) -> str:
longest_str = ''
n = [len(s) - 1]
for diff in range(1, len(s)):
n.append(n[0] + diff)
n.append(n[0] - diff)
for i in n:
if (min(i + 1, 2 * len(s) - 1 - i) <= len(longest_str)):
break
if i % 2 == 0:
left, right = (i // 2) - 1, (i // 2) + 1
else:
left, right = i // 2, (i // 2) + 1
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
if right - left - 1 > len(longest_str):
longest_str = s[left + 1: right]
return longest_str
6 – ZigZag Conversion
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Solution:
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1:
return s
zigzag = [[] for _ in range(numRows)]
row = 0
direction = -1
for c in s:
zigzag[row].append(c)
if row == 0 or row == numRows - 1:
direction = -direction
row += direction
return ''.join([c for r in zigzag for c in r])
7 – Reverse Integer
Given a 32-bit signed integer, reverse digits of an integer.
Solution:
class Solution:
def reverse(self, x: int) -> int:
isNegative = x < 0
x = abs(x)
reversed = 0
while x != 0:
reversed = reversed * 10 + x % 10
x //= 10
if reversed > 2**31 - 1:
return 0
else:
return reversed if not isNegative else -reversed
8 – String to Integer (atoi)
Implement atoi which converts a string to an integer.
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned.
Note:
Only the space character ‘ ‘ is considered as whitespace character.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
Solution:
class Solution:
def myAtoi(self, str: str) -> int:
str = str.strip()
isNegative = False
if str and str[0] == '-':
isNegative = True
if str and (str[0] == '+' or str[0] == '-'):
str = str[1:]
if not str:
return 0
digits = {i for i in '0123456789'}
result = 0
for c in str:
if c not in digits:
break
result = result * 10 + int(c)
if isNegative:
result = -result
result = max(min(result, 2**31 - 1), -2**31)
return result
9 – Palindrome Number
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Solution:
class Solution:
def isPalindrome(self, x: int) -> bool:
n = len(str(x)) // 2
if len(str(x)) % 2 != 0:
n = len(str(x)) // 2
return str(x)[:n] == str(x)[:n:-1]
elif len(str(x)) % 2 == 0:
return str(x)[:n] == str(x)[n:][::-1]
else:
return False
10 – Regular Expression Matching
Given an input string (s) and a pattern (p), implement regular expression matching with support for . and *.
. Matches any single character.
* Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
- s could be empty and contains only lowercase letters a-z.
- p could be empty and contains only lowercase letters a-z, and characters like
.or*.
Solution:
class Solution:
def isMatch(self, s: str, p: str) -> bool:
matched = [[False for _ in range(len(p) + 1)] for _ in range(len(s) + 1)]
matched[0][0] = True
for i in range(len(s) + 1):
for j in range(1, len(p) + 1):
pattern = p[j - 1]
if pattern == '.':
matched[i][j] = (i != 0 and matched[i - 1][j - 1])
elif pattern == '*':
star = p[j - 2]
matched[i][j] = matched[i][j - 2] or (i > 0 and matched[i - 1][j] and
(star == s[i - 1] or star == '.'))
else:
matched[i][j] = (i != 0 and matched[i - 1][j - 1] and s[i - 1] == pattern)
return matched[-1][-1]
11 – Container With Most Water
Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Solution:
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height) - 1
max_area = (right - left) * min(height[right], height[left])
while left < right:
if height[left] < height[right]:
left += 1
else:
right -= 1
max_area = max(max_area, (right - left) * min(height[right], height[left]))
return max_area
12 – Integer to Roman
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
- I can be placed before V (5) and X (10) to make 4 and 9.
- X can be placed before L (50) and C (100) to make 40 and 90.
- C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.
Solution:
class Solution:
def intToRoman(self, num: int) -> str:
mappings = [
(1000, 'M'),
(900, 'CM'),
(500, 'D'),
(400, 'CD'),
(100, 'C'),
(90, 'XC'),
(50, 'L'),
(40, 'XL'),
(10, 'X'),
(9, 'IX'),
(5, 'V'),
(4, 'IV'),
(1, 'I')
]
roman = []
for i, val in mappings:
while num >= i:
num -= i
roman.append(val)
return ''.join(roman)
13 – Roman to Integer
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
Solution:
class Solution:
def romanToInt(self, s: str) -> int:
doubles = {
'CM': 900,
'CD': 400,
'XC': 90,
'XL': 40,
'IX': 9,
'IV': 4
}
singles = {
'M': 1000,
'D': 500,
'C': 100,
'L': 50,
'X': 10,
'V': 5,
'I': 1
}
integer = 0
i = 0
while i < len(s):
if i < len(s) - 1 and s[i:i + 2] in doubles:
integer += doubles[s[i:i + 2]]
i += 2
else:
integer += singles[s[i]]
i += 1
return integer
14 – Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
Solution:
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ''
strs.sort()
first_str = strs[0]
last_str = strs[-1]
i = 0
while i < len(first_str) and i < len(last_str) and first_str[i] == last_str[i]:
i += 1
return first_str[:i]
15 – 3Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Solution:
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
results = []
nums.sort()
i = 0
while i < len(nums):
j = i + 1
k = len(nums) - 1
while j < k:
array_sum = nums[i] + nums[j] + nums[k]
if array_sum == 0:
results.append([nums[i], nums[j], nums[k]])
k -= 1
while k > j and nums[k] == nums[k + 1]:
k -= 1
j += 1
while j < k and nums[j] == nums[j - 1]:
j += 1
elif array_sum > 0:
k -= 1
while k > j and nums[k] == nums[k + 1]:
k -= 1
else:
j += 1
while j < k and nums[j] == nums[j - 1]:
j += 1
i += 1
while i < len(nums) - 2 and nums[i] == nums[i - 1]:
i += 1
return results
16 – 3Sum Closest
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Solution:
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
min_dif = 9999999
nums.sort()
for i in range(len(nums)-2):
l = i+1
r = len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
dif = s - target
if dif < 0:
l += 1
elif dif > 0:
r -= 1
else:
return s
if abs(dif) <= abs(min_dif):
min_dif = dif
res = s
return res
17 – Letter Combinations of a Phone Number
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Solution:
hash_table = {'1':'','2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
class Solution:
# @param digits, a string
# @return a string[]
def _letterCombinations(self, digits):
if len(digits) == 1:
ret = []
for char in hash_table[digits[0]]:
ret.append(char)
return ret
else:
ret = []
for char in hash_table[digits[0]]:
for elt in self._letterCombinations(digits[1:]):
ret.append(char+elt)
return ret
def letterCombinations(self, digits):
if not digits:
return []
return self._letterCombinations(digits)
18 – 4Sum
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
The solution set must not contain duplicate quadruplets.
Solution:
class Solution:
def fourSum(self, n: List[int], t: int) -> List[List[int]]:
n.sort()
if not n: return []
L, N, S, M = len(n), {j:i for i,j in enumerate(n)}, set(), n[-1]
for i in range(L-3):
a = n[i]
if a + 3*M < t: continue
if 4*a > t: break
for j in range(i+1,L-2):
b = n[j]
if a + b + 2*M < t: continue
if a + 3*b > t: break
for k in range(j+1,L-1):
c = n[k]
d = t-(a+b+c)
if d > M: continue
if d < c: break
if d in N and N[d] > k: S.add((a,b,c,d))
return S
19 – Remove Nth Node From End of List
Given a linked list, remove the n-th node from the end of list and return its head.
Solution:
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
dummy = ListNode(-1)
dummy.next = fast = head
head = dummy
while n > 0:
fast = fast.next
n -= 1
while fast != None:
fast = fast.next
dummy = dummy.next
dummy.next = dummy.next.next
return head.next
20 – Valid Parentheses
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Solution:
class Solution:
def isValid(self, s: str) -> bool:
stack = []
braces = {')':'(',']':'[','}':'{'}
for char in s:
if char in braces.values():
stack.append(char)
elif not stack or stack.pop() != braces[char]:
return False
return False if stack else True
21 – Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Solution:
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
stack=[]
while l1:
stack.append(l1.val)
l1=l1.next
while l2:
stack.append(l2.val)
l2=l2.next
stack=sorted(stack)
dummy=ListNode(-1)
while stack:
tem=ListNode(stack.pop())
tem.next=dummy.next
dummy=ListNode(-1)
dummy.next=tem
return dummy.next
22 – Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Solution:
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
p = [[] for i in range(n + 1)]
p[0].append('')
for i in range(n + 1):
for j in range(i):
p[i] += ['(' + x + ')' + y for x in p[j] for y in p[i - j - 1]]
return p[n]
23 – Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Solution:
class Solution:
def mergeKLists(self, lists: 'List[ListNode]') -> 'ListNode':
nums, dum = [], ListNode(0)
p = dum
for l in lists:
while l:
nums.append(l)
l = l.next
for i in sorted(nums, key = lambda l: l.val):
p.next = i
p = p.next
return dum.next
24 – Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list’s nodes, only nodes itself may be changed.
Solution:
class Solution(object):
def swapPairs(self, head):
if not head or not head.next: return head
dummy = ListNode(0)
dummy.next = head
cur = dummy
while cur.next and cur.next.next:
first = cur.next
sec = cur.next.next
cur.next = sec
first.next = sec.next
sec.next = first
cur = cur.next.next
return dummy.next
25 – Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Solution:
class Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
dummy = ListNode(0)
dummy.next = head
pre, cur = dummy, head
deque = []
while cur:
deque.append(cur)
cur = cur.next
if len(deque) == k:
while deque:
pre.next = deque.pop()
pre = pre.next
while deque:
pre.next = deque.pop(0)
pre = pre.next
pre.next = None
return dummy.next
26 – Remove Duplicates from Sorted Array
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
class Solution:
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return len(nums)
j = 0
for num in nums[1:]:
if num != nums[j]:
j += 1
nums[j] = num
return j+1
27 – Remove Element
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
Solution:
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
x = 0
for i in range(len(nums)):
if nums[i] != val:
nums[x] = nums[i]
x += 1
return x
28 – Implement strStr()
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Solution:
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
elif needle not in haystack:
return -1
else:
return len(haystack.split(needle)[0])
29 – Divide Two Integers
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.
Solution:
class Solution:
def divide(self, dividend, divisor) -> int:
positive = (dividend < 0) is (divisor < 0)
dividend, divisor = abs(dividend), abs(divisor)
res = 0
while dividend >= divisor:
temp, i = divisor, 1
while dividend >= temp:
dividend -= temp
res += i
i <<= 1
temp <<= 1
if not positive:
res = -res
return min(max(-2147483648, res), 2147483647)
30 – Substring with Concatenation of All Words
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Solution:
class Solution:
# @param S, a string
# @param L, a list of string
# @return a list of integer
def findSubstring(self, S, L):
if not L or not L[0]: return None
wl = len(L[0])
totl = len(L) * wl
count_tmpl = collections.defaultdict(int)
for word in L: count_tmpl[word] += 1
rtn = []
for i in range(wl):
count = copy.copy(count_tmpl)
j = i
while j < len(S)-wl+1:
count[S[j:j+wl]] -= 1
while count[S[j:j+wl]] < 0:
count[S[i:i+wl]] += 1
i += wl
j += wl
if j-i == totl: rtn.append(i)
return rtn
31 – Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
Solution:
class Solution:
def nextPermutation(self, nums):
for i in range(len(nums)-1, -1, -1):
if i-1 >=0 and nums[i] > nums[i-1]:
for j in reversed(range(i,len(nums))):
if nums[j] > nums[i-1]:
nums[i-1], nums[j] = nums[j], nums[i-1]
break
nums[i:] = nums[i:][::-1]
break
else:
nums = nums.reverse()
32 – Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Solution:
class Solution:
def longestValidParentheses(self, s):
stack, result = [(-1, ')')], 0
for i, paren in enumerate(s):
if paren == ')' and stack[-1][1] == '(':
stack.pop()
result = max(result, i - stack[-1][0])
else:
stack += (i, paren),
return result
33 – Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Solution:
class Solution:
def search(self, nums, target):
l, r = 0, len(nums)-1
while l <= r:
mid = l + (r-l)//2
if nums[mid] == target:
return mid
if nums[l] <= nums[mid]: # here should include "==" case
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else:
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return -1
34 – Find First and Last Position of Element in Sorted Array
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Solution:
class Solution:
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if target not in nums:
return [-1,-1]
l=0
r=len(nums)-1
while l<=r and l<len(nums)-1 and r>0:
if nums[l]!=target:
l+=1
if nums[r]!=target:
r-=1
if nums[l]==target and nums[r]==target:
break
if nums[l]==target:
return [l,r]
else:
return [-1,-1]
35 – Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Solution:
class Solution:
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
for i in range(len(nums)):
if target <= nums[i]:
return i
return len(nums)
36 – Valid Sudoku
Determine if a 9×9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Solution:
class Solution:
def isValidSudoku(self, board) -> bool:
row = [[x for x in y if x != '.'] for y in board]
col = [[x for x in y if x != '.'] for y in zip(*board)]
pal = [[board[i+m][j+n]
for m in range(3)
for n in range(3) if board[i+m][j+n] != '.']
for i in (0, 3, 6) for j in (0, 3, 6)]
return all(len(set(x)) == len(x) for x in (*row, *col, *pal))
37 – Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character ‘.’.
Solution:
class Solution:
col_size = 9 # len(self.board)
row_size = 9 # len(self.board[0])
block_col_size = 3
block_row_size = 3
digits = '123456789'
empty_symbol = '.'
# def solveSudoku(self, board: List[List[str]]) -> None:
def solveSudoku(self, board):
self.init(board)
self.solve()
def init(self, board):
self.board = board
# list all empty cells. a `cell` is a tuple `(row_index, col_index)`
self.empty_cells = set([(ri, ci) for ri in range(self.row_size) for ci in range(self.col_size) if self.board[ri][ci] == self.empty_symbol])
# find candidates of each cell
self.candidates = [[set(self.digits) for ci in range(self.col_size)] for ri in range(self.row_size)]
for ri in range(self.row_size):
for ci in range(self.col_size):
digit = self.board[ri][ci]
if digit != self.empty_symbol:
self.candidates[ri][ci] = set()
self.update_candidates((ri, ci), digit)
def solve(self):
# if there are no empty cells, it's solved
if not self.empty_cells:
return True
# get the cell with fewest candidates
cell = min(self.empty_cells, key=lambda cell: len(self.candidates[cell[0]][cell[1]]))
# try filling the cell with one of the candidates, and solve recursively
ri, ci = cell
for digit in list(self.candidates[ri][ci]):
candidate_updated_cells = self.fill_cell(cell, digit)
solved = self.solve()
if solved:
return True
self.unfill_cell(cell, digit, candidate_updated_cells)
# if no solution found, go back and try the next candidates
return False
def fill_cell(self, cell, digit):
# fill the cell with the digit
ri, ci = cell
self.board[ri][ci] = digit
# remove the cell from empty_cells
self.empty_cells.remove(cell)
# update the candidates of other cells
# keep a list of updated cells. will be used when unfilling cells
candidate_updated_cells = self.update_candidates(cell, digit)
return candidate_updated_cells
def unfill_cell(self, cell, digit, candidate_updated_cells):
# unfill cell
ri, ci = cell
self.board[ri][ci] = self.empty_symbol
# add the cell back to empty_cells
self.empty_cells.add(cell)
# add back candidates of other cells
for ri, ci in candidate_updated_cells:
self.candidates[ri][ci].add(digit)
def update_candidates(self, filled_cell, digit):
candidate_updated_cells = []
for ri, ci in self.related_cells(filled_cell):
if (self.board[ri][ci] == self.empty_symbol) and (digit in self.candidates[ri][ci]):
self.candidates[ri][ci].remove(digit)
candidate_updated_cells.append((ri, ci))
return candidate_updated_cells
def related_cells(self, cell):
return list(set(self.cells_in_same_row(cell) + self.cells_in_same_col(cell) + self.cells_in_same_block(cell)))
def cells_in_same_row(self, cell):
return [(cell[0], ci) for ci in range(self.col_size)]
def cells_in_same_col(self, cell):
return [(ri, cell[1]) for ri in range(self.row_size)]
def cells_in_same_block(self, cell):
block_first_cell_ri = (cell[0] // self.block_row_size) * self.block_row_size
block_first_cell_ci = (cell[1] // self.block_col_size) * self.block_col_size
return [
(block_first_cell_ri + in_block_ri, block_first_cell_ci + in_block_ci)
for in_block_ri in range(self.block_row_size)
for in_block_ci in range(self.block_col_size)
]
38 – Count and Say
The count-and-say sequence is the sequence of integers with the first five terms as following:
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.
Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.
Note: Each term of the sequence of integers will be represented as a string.
Solution:
class Solution:
def countAndSay(self, n):
"""
:type n: int
:rtype: str
"""
s = '1'
for i in range(n-1):
count = 1
temp = []
for index in range(1, len(s)):
if s[index] == s[index-1]:
count += 1
else:
temp.append(str(count))
temp.append(s[index-1])
count = 1
temp.append(str(count))
temp.append(s[-1])
s = ''.join(temp)
return s
39 – Combination Sum
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Solution:
class Solution:
def combinationSum(self, candidates, target: int):
def backtrack(candidates, nums, rem):
print(nums)
if rem == 0:
result.append(nums)
for i, cand in enumerate(candidates):
if rem >= cand:
backtrack(candidates[i:], nums+[cand], rem-cand)
candidates.sort()
result = []
backtrack(candidates, [], target)
return result
40 – Combination Sum II
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
Solution:
class Solution:
def combinationSum2(self, candidates, target):
candidates.sort()
ans = []
l = len(candidates)
def combinationSum(i, t, res):
if t == 0:
ans.append(list(res))
return
for j in range(i, l):
v = candidates[j]
if j > i and v == candidates[j - 1]:
continue
if t < v:
break
res.append(v)
combinationSum(j + 1, t - v, res)
res.pop()
combinationSum(0, target, [])
return ans
41 – First Missing Positive
Given an unsorted integer array, find the smallest missing positive integer.
Solution:
class Solution:
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
for i in range(n):
if nums[i] <= 0: nums[i] = len(nums)+1
for i in range(n):
if abs(nums[i]) <= n: nums[abs(nums[i])-1] = -abs(nums[abs(nums[i])-1])
for i in range(n):
if nums[i] > 0: return i+1
return n+1
42 – Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Solution:
class Solution:
def trap(self, height):
left = 0
right = len(height) - 1
left_max = right_max = water = 0
while left <= right:
if left_max <= right_max:
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
43 – Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Solution:
class Solution:
def multiply(self, num1, num2):
res = 0
carry1 = 1
for n1 in num1[::-1]:
carry2 = 1
for n2 in num2[::-1]:
res += int(n1)*int(n2)*carry1*carry2
carry2 *= 10
carry1 *= 10
return str(res)
44 – Wildcard Matching
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ? and *.
? Matches any single character.
* Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Note:
scould be empty and contains only lowercase letters a-z.pcould be empty and contains only lowercase letters a-z, and characters like?or*.
Solution:
class Solution:
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
res = [[None for _ in range(len(p) + 1)] for _ in range(len(s) + 1)]
res[0][0] = True
for i in range(1, len(p) + 1):
if p[i - 1] == '*':
res[0][i] = res[0][i - 1]
else:
res[0][i] = False
for i in range(1, len(s) + 1):
res[i][0] = False
for i in range(1, len(s) + 1):
for j in range(1, len(p) + 1):
if p[j - 1] == '?' or p[j - 1] == s[i - 1]:
res[i][j] = res[i - 1][j - 1]
elif p[j - 1] == '*':
res[i][j] = res[i - 1][j] or res[i][j - 1]
else:
res[i][j] = False
return res[len(s)][len(p)]
45 – Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Solution:
class Solution:
def jump(self, n) -> int:
N, t, s, f, F = [i+j for i,j in enumerate(n)], len(n) - 1, 0, 0, []
for i in range(max(N)+1):
while 1:
if N[f] >= i:
F.append(f)
break
else: f += 1
while t != 0: t, s = F[t], s + 1
return s
46 – Permutations
Given a collection of distinct integers, return all possible permutations.
Solution:
class Solution:
def permute(self, nums):
ans = [nums]
for i in range(1, len(nums)):
m = len(ans)
for k in range(m):
for j in range(i):
ans.append(ans[k][:])
ans[-1][j], ans[-1][i] = ans[-1][i], ans[-1][j]
return ans
47 – Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Solution:
class Solution:
def permuteUnique(self, nums):
perms = [[]]
for n in nums:
perms = [p[:i] + [n] + p[i:]
for p in perms
for i in range((p + [n]).index(n) + 1)]
return perms
48 – Rotate Image
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Solution:
class Solution:
def rotate(self, A):
A[:] = [[row[i] for row in A[::-1]] for i in range(len(A[0]))]
49 – Group Anagrams
Given an array of strings, group anagrams together.
Solution:
class Solution:
def groupAnagrams(self, strs):
dic = {}
for item in sorted(strs):
sortedItem = ''.join(sorted(item))
dic[sortedItem] = dic.get(sortedItem, []) + [item]
return dic.values()
50 – Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (xn).
Solution:
class Solution:
def myPow(self, x, n):
if n < 0:
x = 1 / x
n = -n
pow = 1
while n:
if n & 1:
pow *= x
x *= x
n >>= 1
return pow