LeetCode Recursion 2

Sort an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
func sortArray(_ nums: [Int]) -> [Int] {
if nums.count < 2 { return nums }
let i = nums.count/2, l = sortArray(Array(nums[..<i])), r = sortArray(Array(nums[i...]))
return merge(l, r)
}

private func merge(_ n1: [Int], _ n2: [Int]) -> [Int] {
var i1 = 0, i2 = 0
var arr = [Int]()
while i1 < n1.count, i2 < n2.count {
if n1[i1] < n2[i2] {
arr.append(n1[i1])
i1 += 1
} else {
arr.append(n2[i2])
i2 += 1
}
}
while i1 < n1.count {
arr.append(n1[i1])
i1 += 1
}
while i2 < n2.count {
arr.append(n2[i2])
i2 += 1
}

return arr
}
}

Validate Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
func isValidBST(_ root: TreeNode?) -> Bool {
return helper(root, Int.min, Int.max)
}

private func helper(_ node: TreeNode?, _ lower: Int, _ upper: Int) -> Bool {
guard let n = node else { return true }

if n.val <= lower || n.val >= upper {
return false
}

return helper(n.left, lower, n.val) && helper(n.right, n.val, upper)
}
}

Search a 2D Matrix II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
let n = matrix.count-1, m = matrix.first?.count ?? 0; var i = n, j = 0
while i >= 0 && j < m {
if target > matrix[i][j] {
j += 1
} else if target < matrix[i][j] {
i -= 1
} else {
return true
}
}
return false
}
}

N-Queens II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
func totalNQueens(_ n: Int) -> Int {
if n < 1 { return 0 }
return helper(n-1, Array(repeating: Array(repeating: 1, count: n), count: n)).count
}

private func helper(_ i: Int, _ board: [[Int]]) -> [[[Int]]] {
if i == 0 { return put(i, board) }
return helper(i-1, board).reduce( [[[Int]]]() ) { a, b in
a + put(i, board)
}
}

private func put(_ i: Int, _ board: [[Int]]) -> [[[Int]]] {
var boards = [[[Int]]]()
for j in 0..<board.count {
if board[i][j] == 1 {
let board = put((i,j), board)
boards.append(board)
}
}
return boards
}

private func put(_ p: (Int, Int), _ board: [[Int]]) -> [[Int]] {
let n = board.count
var board = board

for i in 0..<n { board[i][p.1] = 0 }
for j in 0..<n { board[p.0][j] = 0 }
var p0 = p.0, p1 = p.1
while p0 < n, p1 < n, p0 >= 0, p1 >= 0 {
board[p0][p1] = 0
p0 += 1; p1 += 1
}
p0 = p.0; p1 = p.1
while p0 < n, p1 < n, p0 >= 0, p1 >= 0 {
board[p0][p1] = 0
p0 += 1; p1 -= 1
}
board[p.0][p.1] = 1

return board
}
}

Robot Room Cleaner

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
func cleanRoom(_ robot: Robot) {
var visited = Set<[Int]>()
let directions = [[-1,0], [0,1], [1,0], [0,-1]]

func backtrack(_ cell: [Int] = [0,0], _ d: Int = 0) {
func goBack() {
func uTurn() { robot.turnRight(); robot.turnRight() }
uTurn(); robot.move(); uTurn()
}

visited.insert(cell)
robot.clean()
for i in 0..<4 {
let d = (d+i)%4, cell = [cell[0]+directions[d][0], cell[1]+directions[d][1]]
if !visited.contains(cell) && robot.move() {
backtrack(cell, d)
goBack()
}
robot.turnRight()
}
}

backtrack()
}
}

Sudoku Solver

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
func solveSudoku(_ board: inout [[Character]]) {
let chars: [Character] = ["1","2","3","4","5","6","7","8","9"]
var boxes = Array(repeating: Array(repeating: Set<Character>(), count: 3), count: 3), rows = (0..<9).map { Set(board[$0]) }, cols = (0..<9).map { i in Set( (0..<9).map { j in board[j][i] } )}
(0..<9).forEach { i in (0..<9).forEach { j in boxes[i/3][j/3].insert(board[i][j]) } }

func put(_ c: Character, _ i: Int, _ j: Int) {
board[i][j] = c; rows[i].insert(c); cols[j].insert(c); boxes[i/3][j/3].insert(c)
}
func restore(_ c: Character, _ i: Int, _ j: Int) {
board[i][j] = "."; rows[i].remove(c); cols[j].remove(c); boxes[i/3][j/3].remove(c)
}
func backtrack(_ k: Int = 0) -> Bool {
let i = k/9, j = k%9
if k >= 81 { return true }
if board[i][j] != "." { return backtrack(k+1) }

for c in chars.filter({ !rows[i].contains($0) && !cols[j].contains($0) && !boxes[i/3][j/3].contains($0) }) {
put(c, i, j)
if backtrack(k+1) { return true }
restore(c, i, j)
}
return false
}

backtrack()
}
}

Combinations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
func combine(_ n: Int, _ k: Int) -> [[Int]] {
if k > n { return [] }
let b = (k...n).map { [$0] }
if k == 1 { return b }

let a = combine(n-1, k-1)
var ans = [[Int]]()
for i in a {
for j in b {
if let last = i.last, let first = j.first, last < first {
ans.append(i + j)
}
}
}
return ans
}
}

Same Tree

1
2
3
4
5
6
7
8
class Solution {
func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
if let p = p, let q = q, p.val == q.val {
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}
return p == nil && q == nil
}
}

Generate Parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
func generateParenthesis(_ n: Int) -> [String] {
var ans = [String]()
func backtrack(_ s: String = "", _ l: Int = 0, _ r: Int = 0) {
if s.count == n*2 {
ans.append(s); return
}
if l < n { backtrack(s+"(", l+1, r) }
if r < l { backtrack(s+")", l, r+1) }
}
backtrack()
return ans
}
}

Binary Tree Inorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
// iteratively
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var ans = [Int]()
var stack = [root]
var p = root
while p != nil || !stack.isEmpty {
while let l = p {
stack.append(l)
p = l.left
}

if let n = stack.popLast() {
ans.append(n.val)
p = n.right
}
}
return ans
}

Binary Tree Level Order Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
func levelOrder(_ root: TreeNode?) -> [[Int]] {
var ans = [[Int]]()
helper(root, 0, &ans)
return ans
}

private func helper(_ root: TreeNode?, _ level: Int, _ ans: inout [[Int]]) {
guard let root = root else { return }
if level >= ans.count {
ans.append( [root.val] )
} else {
ans[level].append(root.val)
}

helper(root.left, level+1, &ans)
helper(root.right, level+1, &ans)
}
}

Convert Binary Search Tree to Sorted Doubly Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
func treeToDoublyList(_ root: Node?) -> Node? {
var first: Node?, last: Node?

func helper(_ root: Node?) {
guard let cur = root else { return }
helper(cur.left)
if let last = last {
last.right = cur
cur.left = last
} else {
first = cur
}
last = cur
helper(cur.right)
}

helper(root)
last?.right = first
first?.left = last

return first
}
}

Largest Rectangle in Histogram

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
func largestRectangleArea(_ heights: [Int]) -> Int {
func helper(_ i: Int, _ j: Int) -> Int {
guard i <= j else { return 0 }
var index = 0, v = Int.max
for k in i...j {
if heights[k] < v { index = k; v = heights[k] }
}
return max(v*(j-i+1), helper(i, index-1), helper(index+1, j))
}
return helper(0, heights.count-1)
}
}

Permutations

1
2
3
4
5
6
7
8
9
10
11
class Solution {
func permute(_ nums: [Int]) -> [[Int]] {
if nums.count < 2 { return [nums] }
var ans = [[Int]]()
for i in 0..<nums.count {
var arr = nums; arr.remove(at: i)
ans += permute(arr).map { [nums[i]] + $0 }
}
return ans
}
}

Letter Combinations of a Phone Number

1
2
3
4
5
6
7
8
9
class Solution {
private let dict : [Character: [String]] = ["2":["a","b","c"],"3":["d","e","f"],"4":["g","h","i"],"5":["j","k","l"],"6":["m","n","o"],"7":["p","q","r","s"],"8":["t","u","v"],"9":["w","x","y","z"]]

func letterCombinations(_ digits: String) -> [String] {
return digits.isEmpty ? [] : digits.reduce([""]) { (ans, digit) in
ans.flatMap { s in dict[digit, default: [""]].map { c in s + c } }
}
}
}

The Skyline Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
func getSkyline(_ buildings: [[Int]]) -> [[Int]] {
let n = buildings.count
if n == 0 { return [] }
if n == 1 {
return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]
}

let l = getSkyline(Array(buildings[..<(n/2)]))
let r = getSkyline(Array(buildings[(n/2)...]))

return merge(l, r)
}

private func merge(_ l: [[Int]], _ r: [[Int]]) -> [[Int]] {
let ln = l.count, rn = r.count
var lp = 0, rp = 0
var curY = 0, lY = 0, rY = 0 , output = [[Int]]()


func update(_ x: Int, _ y: Int) {
if output.isEmpty || output.last?.first != x {
output.append([x, y])
} else {
output[output.count-1][1] = y
}
}

func append(_ p: Int, _ lst: [[Int]], _ n: Int, _ curY: Int) {
var p = p, curY = curY
while p < n {
let (x, y) = (lst[p][0], lst[p][1])
p += 1
if curY != y {
update(x, y)
curY = y
}
}
}


while lp < ln && rp < rn {
let lPoint = l[lp], rPoint = r[rp]

var x = 0
if lPoint[0] < rPoint[0] {
(x, lY) = (lPoint[0], lPoint[1])
lp += 1
} else {
(x, rY) = (rPoint[0], rPoint[1])
rp += 1
}

let maxY = max(lY, rY)
if curY != maxY {
update(x, maxY)
curY = maxY
}
}

append(lp, l, ln, curY)
append(rp, r, rn, curY)

return output
}
}

Translated by gpt-3.5-turbo