LeetCode题目：
分治:
class Solution {
func myPow(_ x: Double, _ n: Int) -> Double {
var x = x, n = n
var res = 1.0
if x == 0 { return 0 }
if n < 0 {
x = 1 / x
n = -n
}
while n != 0 {
if n & 1 == 1 { res = res * x }
x = x * x
n = n >> 1
}
return res
}
}
回溯:
class Solution {
func subsets(_ nums: [Int]) -> [[Int]] {
var res = Array<Array<Int>>()
var cur = Array<Int>()
dfs(level: 0, max: nums.count, nums: nums, res: &res, cur: &cur)
return res
}
func dfs(level: Int, max: Int, nums: [Int], res: inout [[Int]], cur: inout [Int]){
if level == max {
res.append(cur)
return
}
cur.append(nums[level])
dfs(level: level + 1, max: max, nums: nums, res: &res, cur: &cur)
cur.removeLast()
dfs(level: level + 1, max: max, nums: nums, res: &res, cur: &cur)
}
}
class Solution {
func letterCombinations(_ digits: String) -> [String] {
if digits == "" { return [] }
var digitsArray = Array<String>()
for i in digits {
digitsArray.append(String(i))
}
let numDict: Dictionary<String, Array<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"]]
var res = Array<String>()
var curStr = ""
dfs(digitsArray: digitsArray, numDict: numDict, res: &res, curStr: &curStr, index: 0)
return res
}
func dfs(digitsArray: Array<String>, numDict: Dictionary<String, Array<String>>, res: inout Array<String>, curStr: inout String, index: Int) {
if index == digitsArray.count {
res.append(curStr)
return
}
let lettersArray = numDict[digitsArray[index]]
for i in 0..<lettersArray!.count {
curStr.append(lettersArray![i])
dfs(digitsArray: digitsArray, numDict: numDict, res: &res, curStr: &curStr, index: index + 1)
curStr.removeLast()
}
}
}
class Solution {
var cols = Set<Int>()
var pie = Set<Int>()
var na = Set<Int>()
func solveNQueens(_ n: Int) -> [[String]] {
var res = Array<Array<Int>>()
let cur = Array<Int>()
backtracking(n: n, row: 0, res: &res, cur: cur)
return finalResult(res: res, n: n)
}
func backtracking(n: Int, row: Int, res: inout Array<Array<Int>>, cur: Array<Int>) {
if row == n {
res.append(cur)
return
}
for col in 0..<n {
if cols.contains(col) || pie.contains(row + col) || na.contains(row - col) { continue }
cols.insert(col)
pie.insert(row + col)
na.insert(row - col)
backtracking(n: n, row: row + 1, res: &res, cur: cur + [col])
cols.remove(col)
pie.remove(row + col)
na.remove(row - col)
}
}
func finalResult(res: Array<Array<Int>>, n: Int) -> Array<Array<String>> {
var resArray = Array<Array<String>>()
for i in res {
var tempArray = Array<String>()
for j in i {
var tempStr = ""
for k in 0..<i.count {
if k == j {
tempStr.append("Q")
} else {
tempStr.append(".")
}
}
tempArray.append(tempStr)
}
resArray.append(tempArray)
}
return resArray
}
}
贪心
class Solution {
func findContentChildren(_ g: [Int], _ s: [Int]) -> Int {
let sortedG = g.sorted(by: <)
var sortedS = s.sorted(by: <)
var res = 0
for g in sortedG {
for (indexs, s) in sortedS.enumerated() {
if s >= g {
res += 1
sortedS.remove(at: indexs)
break
}
continue
}
}
return res
}
}
-DP
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
let prices = [0] + prices
var dpArr = Array(repeating: Array(repeating: 0, count: 2), count: prices.count)
dpArr[0][0] = 0
dpArr[0][1] = Int(-1000000)
for i in 1...prices.count - 1 {
for j in 0...1 {
if j == 0 {
dpArr[i][j] = max(dpArr[i - 1][1] + prices[i], dpArr[i - 1][0])
} else {
dpArr[i][j] = max(dpArr[i - 1][0] - prices[i], dpArr[i - 1][1])
}
}
}
return dpArr[prices.count - 1][0]
}
}
-贪心
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
var everyProfit = 0
var res = 0
for (index, i) in prices.enumerated() {
if index == prices.count - 1 {
break
}
everyProfit = prices[index + 1] - i
if everyProfit > 0 {
res += everyProfit
}
}
return res
}
}
-DP
class Solution {
func canJump(_ nums: [Int]) -> Bool {
guard nums.count > 1 else {
return true
}
if nums.count == 2 {
return nums.first! >= 1 ? true : false
}
if nums.first! == 0 {
return false
}
var dpArr = nums
var res = 0
for i in 1..<nums.count - 1 {
dpArr[i] = max(dpArr[i - 1], i + nums[i])
if dpArr[i] == i {
return false
}
res = max(res, dpArr[i])
}
return (res >= nums.count - 1) ? true : false
}
}
-贪心
class Solution {
func canJump(_ nums: [Int]) -> Bool {
if nums.count == 1 {
return true
}
var cover = 0
var i = 0
while cover < nums.count - 1 {
if i > cover {
return false
}
cover = max(i + nums[i], cover)
i += 1
}
return true
}
}
-DP
class Solution {
func jump(_ nums: [Int]) -> Int {
if nums.count == 1 {
return 0
}
if nums.count == 2 {
return 1
}
var dpArr = Array(repeating: 10000000, count: nums.count)
dpArr[0] = 0
var cover = nums.first!
for i in 1..<nums.count {
if cover > nums.count - 1 {
cover = nums.count - 1
}
for j in i...cover {
dpArr[j] = min(dpArr[i - 1] + 1, dpArr[j])
}
cover = max(cover, i + nums[i])
}
return dpArr.last!
}
}
-贪心
class Solution {
var level = 0
func jump(_ nums: [Int]) -> Int {
guard nums.count > 1 else {
return 0
}
var cover = 0
var i = 0
while cover < nums.count - 1 {
cover = max(cover, i + nums[i])
i += 1
}
level += 1
jump(Array(nums[0...i - 1]))
return level
}
}
class Solution {
func lemonadeChange(_ bills: [Int]) -> Bool {
var fiveRem = 0
var tenRem = 0
var twlRem = 0
for i in bills {
switch i {
case 5:
fiveRem += 1
case 10:
guard fiveRem > 0 else {
return false
}
fiveRem -= 1
tenRem += 1
case 20:
if tenRem > 0 && fiveRem > 0 {
tenRem -= 1
fiveRem -= 1
twlRem += 1
continue
}
if tenRem == 0 && fiveRem >= 3 {
fiveRem -= 3
twlRem += 1
continue
}
return false
default:
return false
}
}
return true
}
}
二分查找
class Solution {
func search(_ nums: [Int], _ target: Int) -> Int {
guard nums.contains(target) else {
return -1
}
var left = 0, right = nums.count - 1
while left <= right {
let mid = left + (right - left) / 2
if nums[mid] == target { return mid }
if nums[mid] >= nums[left] {
// 左边有序且升序
if target < nums[mid] && target >= nums[left] {
right = mid - 1
} else {
left = mid + 1
}
}else if nums[mid] < nums[right] {
// 右边有序且升序
if target > nums[mid] && target <= nums[right] {
left = mid + 1
} else {
right = mid - 1
}
}
}
return right
}
}
-无脑查找
class Solution {
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
for arr in matrix {
if arr.contains(target) {
return true
}
}
return false
}
}
-二分查找
class Solution {
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
guard matrix.count != 0 else {
return false
}
var left = 0, right = matrix.count * matrix.first!.count - 1
while left <= right {
let mid = left + (right - left) / 2
if matrix[firstIndex(num: mid, matrix: matrix)][secondIndex(num: mid, matrix: matrix)] == target {
// mid == target
return true
}
if matrix[firstIndex(num: mid, matrix: matrix)][secondIndex(num: mid, matrix: matrix)] < target {
// mid < target
left = mid + 1
} else {
right = mid - 1
}
}
return false
}
func firstIndex(num: Int, matrix: [[Int]]) -> Int {
return num / matrix.first!.count
}
func secondIndex(num: Int, matrix: [[Int]]) -> Int {
return num % matrix.first!.count
}
}
class Solution {
func findMin(_ nums: [Int]) -> Int {
var left = 0, right = nums.count - 1, minNnum = nums[left]
while left <= right {
let mid = left + (right - left) / 2
if nums[mid] >= nums[left] {
// 左有序且升序，那么左边最小值就是nums[left]
minNnum = min(nums[left], minNnum)
left = mid + 1
} else if nums[mid] <= nums[right] {
// 右有序且升序，那么右边最小值就是nums[mid]
minNnum = min(nums[mid], minNnum)
right = mid - 1
}
}
return minNnum
}
}
-常规思路
class Solution {
func mySqrt(_ x: Int) -> Int {
var res = 0
while res * res < x {
res += 1
}
return res * res > x ? res - 1 : res
}
}
-二分查找
class Solution {
func mySqrt(_ x: Int) -> Int {
var left = 0, right = x
while left <= right {
let mid = left + (right - left) / 2
if mid * mid == x {
return mid
} else if mid * mid < x {
left = mid + 1
} else {
right = mid - 1
}
}
return right
}
}
-牛顿迭代
class Solution {
func mySqrt(_ x: Int) -> Int {
if x == 0 { return 0 }
var C = Double(x), x0 = Double(x)
while true {
let x1 = 0.5 * (x0 + C / x0)
if abs(x1 - x0) < 1e-7 {
break
}
x0 = x1
}
return Int(x0)
}
}
class Solution {
func isPerfectSquare(_ num: Int) -> Bool {
var left = 0, right = num
while left <= right {
let mid = left + (right - left) / 2
if mid * mid == num {
return true
} else if mid * mid < num {
left = mid + 1
} else {
right = mid - 1
}
}
return right * right == num ? true : false
}
}
class Solution {
func majorityElement(_ nums: [Int]) -> Int {
return majorityElementRec(nums, 0, nums.count - 1)
}
//! 求解出 数组[left,right] 区间的多数元素
func majorityElementRec(_ nums: [Int], _ left: Int, _ right: Int) -> Int {
//! 递归基
if left == right {
return nums[left]
}
let mid = (left+right)/2
//! 求解出左边和右边区间的多数元素
let leftNumber = majorityElementRec(nums,left,mid)
let rightNumer = majorityElementRec(nums, mid + 1, right)
//! 如果左右区间的多数元素一样，那么代表已经找到了
if leftNumber == rightNumer {
return leftNumber
}
//! 不一样，那么我们需要计算 两个多数元素的个数，进行比较再选出多数元素
let leftCount = countInRange(nums, leftNumber, left, right)
let rightCount = countInRange(nums, rightNumer, left, right)
return leftCount > rightCount ? leftNumber : rightNumer
}
//! 计算多数元素出现的个数
func countInRange(_ nums: [Int], _ majority: Int, _ left: Int, _ right: Int) -> Int {
var count = 0
for i in left...right {
if nums[i] == majority {
count += 1
}
}
return count
}
}
BFS
class Solution {
func levelOrder(_ root: TreeNode?) -> [[Int]] {
var res = Array<Array<Int>>()
bfs(root: root, res: &res)
return res
}
func bfs(root: TreeNode?, res: inout Array<Array<Int>>) {
if root == nil { return }
var queue = Array<TreeNode?>()
queue = [root]
var temp = Array<Int>()
temp.append(root!.val)
while !queue.isEmpty {
res.append(temp)
temp.removeAll()
for _ in 0..<queue.count {
let currentNode = queue.removeFirst()
if let left = currentNode?.left {
queue.append(left)
temp.append(left.val)
}
if let right = currentNode?.right {
queue.append(right)
temp.append(right.val)
}
}
}
}
}
class Solution {
func minMutation(_ start: String, _ end: String, _ bank: [String]) -> Int {
guard bank.contains(end) else {
return -1
}
var queue = Array<String>()
var visited = Set<String>()
queue.append(start)
visited.insert(start)
var res = 1
while !queue.isEmpty {
for _ in 0..<queue.count {
let cur = queue.removeFirst()
for gen in bank {
if canBeNextWord(cur: cur, str: gen) {
queue.append(gen)
visited.insert(gen)
if gen == end {
return res
}
}
}
}
res += 1
}
return -1
}
func canBeNextWord(cur: String, str: String) -> Bool {
var difCount = 0
for (index, _) in cur.enumerated() {
if cur[cur.index(cur.startIndex, offsetBy: index)] != str[str.index(str.startIndex, offsetBy: index)] {
difCount += 1
}
}
return difCount == 1 ? true : false
}
}
class Solution {
func largestValues(_ root: TreeNode?) -> [Int] {
var res = Array<Int>()
bfs(root: root, res: &res)
return res
}
func bfs(root: TreeNode?, res: inout Array<Int>) {
guard let root = root else {
return
}
var queue = Array<TreeNode?>()
queue.append(root)
var temp = Array<Int>()
temp.append(root.val)
while !queue.isEmpty {
res.append(temp.max()!)
temp.removeAll()
for _ in 0..<queue.count {
let currentNode = queue.removeFirst()
if let left = currentNode!.left {
queue.append(left)
temp.append(left.val)
}
if let right = currentNode!.right {
queue.append(right)
temp.append(right.val)
}
}
}
}
}
class Solution {
func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
if !wordList.contains(endWord) { return 0 }
let wordListSet: Set<String> = Set.init(wordList)
var beginSet = Set<String>(), endSet = Set<String>(), visited = Set<String>()
var len = 1
beginSet.insert(beginWord)
endSet.insert(endWord)
while !beginSet.isEmpty && !endSet.isEmpty {
// 交换 要搞小的
if beginSet.count > endSet.count {
let tempSet = beginSet
beginSet = endSet
endSet = tempSet
}
var tempSet = Set<String>()
for word in beginSet{
var curArray = Array(word)
for i in 0..<curArray.count {
for c in "abcdefghijklmnopqrstuvwxyz" {
let temp = curArray[i]
curArray[i] = c
let target = String(curArray)
if endSet.contains(target) {
return len + 1
}
if !visited.contains(target) && wordListSet.contains(target) {
tempSet.insert(target)
visited.insert(target)
}
curArray[i] = temp
}
}
}
beginSet = tempSet
len += 1
}
return 0
}
}
-单向BFS 超时看print就知道思路了。
class Solution {
func findLadders(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> [[String]] {
if !wordList.contains(endWord) { return [] }
var wordListSet: Set<String> = Set.init(wordList)
wordListSet.insert(beginWord)
var wordIdDict: Dictionary<String, String> = Dictionary<String, String>()
var idWordDict: Dictionary<String, String> = Dictionary<String, String>()
for (index, word) in wordListSet.enumerated() {
wordIdDict.updateValue("\(index)", forKey: word)
idWordDict.updateValue(word, forKey: "\(index)")
}
var visited = Set<String>()
var queue = Array<String>()
var line = Set<Array<String>>()
let endWordId = wordIdDict[endWord]
line.insert([wordIdDict[beginWord]!])
queue.append(beginWord)
var resArray = Array<Array<String>>()
while !queue.isEmpty {
let count = queue.count
for _ in 0..<count {
let cur = queue.removeFirst()
visited.insert(cur)
for str in wordListSet.subtracting(visited) {
if canBeNextWord(cur: cur, str: str) {
for arr in line {
if arr.last == wordIdDict[cur] {
let temp = arr + [wordIdDict[str]!]
line.insert(temp)
if wordIdDict[str] == endWordId {
resArray.append(temp)
}
}
}
if !queue.contains(str) {
queue.append(str)
}
}
}
}
}
var res = Array<Array<String>>()
resArray.sort { (a, b) -> Bool in
a.count < b.count
}
for arr in resArray {
if arr.count == resArray.first?.count {
res.append(arr)
}
}
var finalRes = Array<Array<String>>()
for resArr in res {
var temp = Array<String>()
for str in resArr {
temp.append(idWordDict[str]!)
}
finalRes.append(temp)
}
return finalRes
}
func canBeNextWord(cur: String, str: String) -> Bool {
var difCount = 0
for (index, _) in cur.enumerated() {
if cur[cur.index(cur.startIndex, offsetBy: index)] != str[str.index(str.startIndex, offsetBy: index)] {
difCount += 1
}
}
return difCount == 1 ? true : false
}
}
DFS
class Solution {
func numIslands(_ grid: [[Character]]) -> Int {
var mutableGrid = grid
var count = 0
guard grid.count != 0 else {
return 0
}
let row = grid.count
let col = grid.first?.count
for r in 0..<row {
for c in 0..<col! {
if mutableGrid[r][c] == "1" {
count += 1
dfs(r: r, c: c, mutableGrid: &mutableGrid)
}
}
}
return count
}
func dfs(r: Int, c: Int, mutableGrid: inout [[Character]]) {
if r < 0 || c < 0 || r > mutableGrid.count - 1 || c > ((mutableGrid.first?.count)! - 1) || mutableGrid[r][c] == "0" {
return
}
mutableGrid[r][c] = "0"
dfs(r: r - 1, c: c, mutableGrid: &mutableGrid)
dfs(r: r + 1, c: c, mutableGrid: &mutableGrid)
dfs(r: r, c: c - 1, mutableGrid: &mutableGrid)
dfs(r: r, c: c + 1, mutableGrid: &mutableGrid)
}
}
class Solution {
func updateBoard(_ board: [[Character]], _ click: [Int]) -> [[Character]] {
var mutableBoard = board
let row = click[0], col = click[1]
let dRow = [-1, 1, 0, 0, -1, 1, -1, 1], dCol = [0, 0, -1, 1, -1, -1, 1, 1]
if mutableBoard[row][col] == "M" {
mutableBoard[row][col] = "X"
} else {
dfs(row: row, col: col, mutableBoaed: &mutableBoard, dRow: dRow, dCol: dCol)
}
return mutableBoard
}
func dfs(row: Int, col: Int, mutableBoaed: inout [[Character]], dRow: [Int], dCol: [Int]) {
if row < 0 || col < 0 || row > mutableBoaed.count - 1 || col > mutableBoaed.first!.count - 1 || mutableBoaed[row][col] == "B" || mutableBoaed[row][col] == "M" {
return
}
let (haveBomb, bombCount) = hasBomb(row: row, col: col, mutableBoaed: mutableBoaed, dRow: dRow, dCol: dCol)
if haveBomb {
mutableBoaed[row][col] = Character("\(bombCount)")
return
} else {
mutableBoaed[row][col] = "B"
}
// 上
dfs(row: row - 1, col: col, mutableBoaed: &mutableBoaed, dRow: dRow, dCol: dCol)
// 下
dfs(row: row + 1, col: col, mutableBoaed: &mutableBoaed, dRow: dRow, dCol: dCol)
// 左
dfs(row: row, col: col - 1, mutableBoaed: &mutableBoaed, dRow: dRow, dCol: dCol)
// 右
dfs(row: row, col: col + 1, mutableBoaed: &mutableBoaed, dRow: dRow, dCol: dCol)
// 左斜上
dfs(row: row - 1, col: col - 1, mutableBoaed: &mutableBoaed, dRow: dRow, dCol: dCol)
// 左斜下
dfs(row: row + 1, col: col - 1, mutableBoaed: &mutableBoaed, dRow: dRow, dCol: dCol)
// 右斜上
dfs(row: row - 1, col: col + 1, mutableBoaed: &mutableBoaed, dRow: dRow, dCol: dCol)
// 右斜下
dfs(row: row + 1, col: col + 1, mutableBoaed: &mutableBoaed, dRow: dRow, dCol: dCol)
}
func hasBomb(row: Int, col: Int, mutableBoaed: [[Character]], dRow: [Int], dCol: [Int]) -> (Bool, Int) {
var bombCount = 0
for i in 0..<dRow.count {
if row + dRow[i] < 0 || row + dRow[i] > mutableBoaed.count - 1 || col + dCol[i] < 0 || col + dCol[i] > mutableBoaed.first!.count - 1 {
continue
}
if mutableBoaed[row + dRow[i]][col + dCol[i]] == "M" {
bombCount += 1
}
}
if bombCount != 0 {
return (true, bombCount)
} else {
return (false, 0)
}
}
}
class Solution {
func robotSim(_ commands: [Int], _ obstacles: [[Int]]) -> Int {
var currentDirection = "North"
var coordinate = (x:0, y:0)
var obstaclesSet = Set<Array<Int>>()
var maxDistance = 0
for i in obstacles {
obstaclesSet.insert(i)
}
for i in commands {
switch i {
case -1:
currentDirection = solveDirection(currentDirection: currentDirection, turnTo: -1)
case -2:
currentDirection = solveDirection(currentDirection: currentDirection, turnTo: -2)
case 1...9:
coordinate = solveCoordinate(currentDirection: currentDirection, steps: i, coordinate: coordinate, obstaclesSet: obstaclesSet, maxDistance: &maxDistance)
default:
break
}
}
return maxDistance
}
func solveCoordinate(currentDirection: String, steps: Int, coordinate: (x:Int, y:Int), obstaclesSet: Set<Array<Int>>, maxDistance: inout Int) -> (Int, Int) {
var resCoordinate = coordinate
switch currentDirection {
case "North":
// +Y
for _ in 1...steps {
if obstaclesSet.contains([resCoordinate.x, resCoordinate.y + 1]) {
maxDistance = max(resCoordinate.x * resCoordinate.x + resCoordinate.y * resCoordinate.y, maxDistance)
return resCoordinate
}
resCoordinate.y += 1
maxDistance = max(resCoordinate.x * resCoordinate.x + resCoordinate.y * resCoordinate.y, maxDistance)
}
case "East":
for _ in 1...steps {
if obstaclesSet.contains([resCoordinate.x + 1, resCoordinate.y]) {
maxDistance = max(resCoordinate.x * resCoordinate.x + resCoordinate.y * resCoordinate.y, maxDistance)
return resCoordinate
}
resCoordinate.x += 1
maxDistance = max(resCoordinate.x * resCoordinate.x + resCoordinate.y * resCoordinate.y, maxDistance)
}
case "South":
for _ in 1...steps {
if obstaclesSet.contains([resCoordinate.x, resCoordinate.y - 1]) {
maxDistance = max(resCoordinate.x * resCoordinate.x + resCoordinate.y * resCoordinate.y, maxDistance)
return resCoordinate
}
resCoordinate.y -= 1
maxDistance = max(resCoordinate.x * resCoordinate.x + resCoordinate.y * resCoordinate.y, maxDistance)
}
case "West":
for _ in 1...steps {
if obstaclesSet.contains([resCoordinate.x - 1, resCoordinate.y]) {
maxDistance = max(resCoordinate.x * resCoordinate.x + resCoordinate.y * resCoordinate.y, maxDistance)
return resCoordinate
}
resCoordinate.x -= 1
maxDistance = max(resCoordinate.x * resCoordinate.x + resCoordinate.y * resCoordinate.y, maxDistance)
}
default:
break
}
return resCoordinate
}
func solveDirection(currentDirection: String, turnTo: Int) -> String {
var resDirection = ""
switch currentDirection {
case "North":
turnTo == -1 ? (resDirection = "East") : (resDirection = "West")
case "East":
turnTo == -1 ? (resDirection = "South") : (resDirection = "North")
case "South":
turnTo == -1 ? (resDirection = "West") : (resDirection = "East")
case "West":
turnTo == -1 ? (resDirection = "North") : (resDirection = "South")
default:
break
}
return resDirection
}
}
