N-Queens – Python 3 (Week 19 – 02)
Solution 1
class Solution:
"""
@param: n: The number of queens
@return: All distinct solutions
"""
def solveNQueens(self, n):
# write your code here
result = []
self.dfs(n, [], result)
return result
def dfs(self, n, cols, result):
row = len(cols)
if row == n:
result.append(self.draw_chessboard(cols))
return
for col in range(n):
if not self.is_valid(cols, row, col):
continue
cols.append(col)
self.dfs(n, cols, result)
cols.pop()
def is_valid(self, cols, row, col):
for r, c in enumerate(cols):
if c == col:
return False
if r - c == row - col or r + c == row + col:
return False
return True
def draw_chessboard(self, cols):
n = len(cols)
board = []
for i in range(n):
row = ['Q' if j == cols[i] else '.' for j in range(n)]
board.append(''.join(row))
return board
Time O(s*n^2). Space O(s).
Solution 2
Improve time complexity to O(s*n). Because n is small, can not improve a lot.
class Solution:
"""
@param: n: The number of queens
@return: All distinct solutions
"""
def solveNQueens(self, n):
# write your code here
result = []
visited = {
'col': set(),
'sum': set(),
'diff': set(),
}
self.dfs(n, [], result, visited)
return result
def dfs(self, n, cols, result, visited):
row = len(cols)
if row == n:
result.append(self.draw_chessboard(cols))
return
for col in range(n):
if not self.is_valid(cols, visited, col):
continue
cols.append(col)
visited['col'].add(col)
visited['sum'].add(row + col)
visited['diff'].add(row - col)
self.dfs(n, cols, result, visited)
visited['col'].remove(col)
visited['sum'].remove(row + col)
visited['diff'].remove(row - col)
cols.pop()
def is_valid(self, cols, visited, col):
row = len(cols)
if col in visited['col']:
return False
if row + col in visited['sum']:
return False
if row - col in visited['diff']:
return False
return True
def draw_chessboard(self, cols):
n = len(cols)
board = []
for i in range(n):
row = ['Q' if j == cols[i] else '.' for j in range(n)]
board.append(''.join(row))
return board
Split String – Python 3 (Week 19 – 01)
class Solution:
"""
@param: : a string to be split
@return: all possible split string array
"""
def splitString(self, s):
# write your code here
result = []
self.dfs(s, [], result)
return result
def dfs(self, s, path, result):
if s == '':
result.append(path[:])
return
for i in range(2):
if i + 1 <= len(s):
path.append(s[:i+1])
self.dfs(s[i+1:], path, result)
path.pop()
Kth Largest Element – Python 3 (Week 18 – 12)
class Solution:
"""
@param n: An integer
@param nums: An array
@return: the Kth largest element
"""
def kthLargestElement(self, k, A):
# write your code here
if not A or k < 1 or k > len(A):
return None
return self.partition(A, 0, len(A) - 1, len(A) - k)
def partition(self, A, start, end, k):
if start == end:
return A[k]
left, right = start, end
pivot = A[(start + end) // 2]
while left <= right:
while left <= right and A[left] < pivot:
left += 1
while left <= right and A[right] > pivot:
right -= 1
if left <= right:
A[left], A[right] = A[right], A[left]
left += 1
right -= 1
if k <= right:
self.partition(A, start, right, k)
if k >= left:
self.partition(A, left, end, k)
return A[k]
O(n) time, O(1) extra memory.
Partition Array – Python 3 (Week 18 – 11)
class Solution:
"""
@param nums: The integer array you should partition
@param k: An integer
@return: The index after partition
"""
def partitionArray(self, nums, k):
# write your code here
if not nums or not k:
return 0
left, right = 0, len(nums)
while left <= right:
while left <= right and nums[left] < k:
left += 1
while left <= right and nums[right] >= k:
right -= 1
if left <= right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return left
3Sum – Python 3 (Week 18 – 10)
class Solution:
"""
@param numbers: Give an array numbers of n integer
@return: Find all unique triplets in the array which gives the sum of zero.
"""
def threeSum(self, numbers):
# write your code here
numbers.sort()
results = []
length = len(numbers)
for i in range(length - 2):
if i > 0 and numbers[i] == numbers[i - 1] or numbers[i] > 0:
continue
self.find_two_sum(numbers, i + 1, length - 1, -numbers[i], results)
return results
def find_two_sum(self, numbers, start, end, target, results):
left, right = start, end
while left < right:
if numbers[left] + numbers[right] == target:
results.append([-target, numbers[left], numbers[right]])
left += 1
right -= 1
while left < right and numbers[left] == numbers[left - 1]:
left += 1
while left < right and numbers[right] == numbers[right + 1]:
right -= 1
elif numbers[left] + numbers[right] > target:
right -= 1
else:
left += 1
Sort Colors II – Python 3 (Week 18 – 09)
class Solution:
"""
@param colors: A list of integer
@param k: An integer
@return: nothing
"""
def sortColors2(self, colors, k):
# write your code here
self.quickSort(colors, 1, k, 0, len(colors) - 1)
def quickSort(self, colors, color_from, color_end, index_from, index_end):
if color_from == color_end or index_from == index_end:
return
color = (color_from + color_end) // 2
left, right = index_from, index_end
while left <= right:
while left <= right and colors[left] <= color:
left += 1
while left <= right and colors[right] > color:
right -= 1
if left <= right:
colors[left], colors[right] = colors[right], colors[left]
left += 1
right -= 1
self.quickSort(colors,color_from, color, index_from, right)
self.quickSort(colors,color + 1, color_end, left, index_end)
Two Sum II – Input array is sorted – Python 3 (Week 18 – 08)
class Solution:
"""
@param nums: an array of Integer
@param target: target = nums[index1] + nums[index2]
@return: [index1 + 1, index2 + 1] (index1 < index2)
"""
def twoSum(self, nums, target):
# write your code here
if not nums or target is None:
return None
l, r = 0, len(nums) - 1
while l < r:
value = nums[l] + nums[r]
if value == target:
return [l + 1, r + 1]
if value < target:
l += 1
else:
r -= 1
return None
Sort Integers II – Python 3 ( Week 18 – 07)
Solution 1 quick sort Time O(nlogn). Space O(1).
class Solution:
"""
@param A: an integer array
@return: nothing
"""
def sortIntegers2(self, A):
# write your code here
self.quickSort(A, 0, len(A) - 1)
def quickSort(self, A, start, end):
if start >= end:
return
left, right = start, end
pivot = A[(start + end) // 2]
while left <= right:
while left <= right and A[left] < pivot:
left += 1
while left <= right and A[right] > pivot:
right -= 1
if left <= right:
A[left], A[right] = A[right], A[left]
left += 1
right -= 1
self.quickSort(A, start, right)
self.quickSort(A, left, end)
Solution 2 merge sort Time O(nlogn). Space O(n).
class Solution:
"""
@param A: an integer array
@return: nothing
"""
def sortIntegers2(self, A):
# write your code here
if len(A) <= 1:
return A
temp = [0] * len(A)
self.mergeSort(A, 0, len(A) - 1, temp)
def mergeSort(self, A, start, end, temp):
if start >= end:
return
self.mergeSort(A, start, (start + end) // 2, temp)
self.mergeSort(A, (start + end) // 2 + 1, end, temp)
self.merge(A, start, end, temp)
def merge(self, A, start, end, temp):
index, left, middle, right = start, start, (start + end) // 2, (start + end) // 2 + 1
while left <= middle and right <= end:
if A[left] <= A[right]:
temp[index] = A[left]
index += 1
left += 1
else:
temp[index] = A[right]
index += 1
right += 1
while left <= middle:
temp[index] = A[left]
index += 1
left += 1
while right <= end:
temp[index] = A[right]
index += 1
right += 1
for i in range(start, end + 1):
A[i] = temp[i]
Remove Duplicate Numbers in Array – Python 3 ( Week 18 – 06)
Solution 1 O(n) time, O(n) space
class Solution:
# @param {int[]} nums an array of integers
# @return {int} the number of unique integers
def deduplication(self, nums):
# Write your code here
d, result = {}, 0
for num in nums:
if num not in d:
d[num] = True
nums[result] = num
result += 1
return result
Solution 2 O(nlogn) time, O(1) space
class Solution:
# @param {int[]} nums an array of integers
# @return {int} the number of unique integers
def deduplication(self, nums):
# Write your code here
n = len(nums)
if n == 0:
return 0
nums.sort()
result = 1
for i in range(1, n):
if nums[i - 1] != nums[i]:
nums[result] = nums[i]
result += 1
return result
步步发财 