time: 2020-9-25
O(n)
func reverseList(_ head: ListNode?) -> ListNode? {
let dummy = ListNode(-1)
var cur = head
while cur != nil {
let next = cur?.next
cur?.next = dummy.next
dummy.next = cur
cur = next
}
return dummy.next
}get O(1) put O(1)
class LRUCache {
private let capacity: Int
private var cache: [Int: LRUNode] = [:]
private var list = LRUList()
init(_ capacity: Int) {
self.capacity = capacity
}
func get(_ key: Int) -> Int {
guard capacity > 0 else { return -1 }
guard let node = cache[key] else { return -1 }
list.move2Head(node)
return node.value
}
func put(_ key: Int, _ value: Int) {
guard capacity > 0 else { return }
if let node = cache[key] {
node.value = value
list.move2Head(node)
return
}
if cache.count == capacity {
guard let last = list.removeTail() else { return }
cache[last.key] = nil
}
let newNode = LRUNode(key, value)
list.add2Head(newNode)
cache[key] = newNode
}
}
private class LRUList {
private let head = LRUNode(-1, -1)
private let tail = LRUNode(-1, -1)
init() {
head.next = tail
}
func add2Head(_ node: LRUNode) {
node.next = head.next
node.prev = head
head.next?.prev = node
head.next = node
}
func move2Head(_ node: LRUNode) {
remove(node)
add2Head(node)
}
func removeTail() -> LRUNode? {
guard !isEmpty else { return nil }
let lastTail = tail.prev!
remove(lastTail)
return lastTail
}
private func remove(_ node: LRUNode) {
guard !isEmpty else { return }
node.prev?.next = node.next
node.next?.prev = node.prev
node.prev = nil
node.next = nil
}
private var isEmpty: Bool {
head.next === tail
}
}
private class LRUNode {
var key: Int
var value: Int
var next: LRUNode?
weak var prev: LRUNode?
init(_ key: Int, _ value: Int) {
self.key = key
self.value = value
}
}// 深度优先
func preorderTraversal(_ root: TreeNode?) -> [Int] {
var res = [Int]()
func helper(_ p: TreeNode?) {
guard let p = p else { return }
res.append(p.val)
helper(p.left)
helper(p.right)
}
helper(root)
return res
}
// 迭代 O(n) O(h)
func preorderTraversal(_ root: TreeNode?) -> [Int] {
var res = [Int]()
guard let root = root else { return res }
var stack = [root]
while let node = stack.popLast() {
res.append(node.val)
if let right = node.right {
stack.append(right)
}
if let left = node.left {
stack.append(left)
}
}
return res
}// 深度优先
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var res = [Int]()
func dfs(_ r: TreeNode?) {
guard let r = r else { return }
dfs(r.left)
res.append(r.val)
dfs(r.right)
}
dfs(root)
return res
}
// 迭代
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var root = root
var res = [Int]()
var stack = [TreeNode]()
while !stack.isEmpty || root != nil {
while root != nil {
stack.append(root!)
root = root?.left
}
if let top = stack.popLast() {
res.append(top.val)
root = top.right
}
}
return res
} // 深度优先
func postorderTraversal(_ root: TreeNode?) -> [Int] {
var res = [Int]()
func dfs(_ r: TreeNode?) {
guard let r = r else { return }
dfs(r.left)
dfs(r.right)
res.append(r.val)
}
dfs(root)
return res
}
// 迭代
func postorderTraversal(_ root: TreeNode?) -> [Int] {
var res = [Int]()
guard let root = root else { return res }
var stack = [root]
while let node = stack.popLast() {
if let ln = node.left {
stack.append(ln)
}
if let rn = node.right {
stack.append(rn)
}
res.append(node.val)
}
return res.reversed()
}func threeOrders(_ root: TreeNode?) -> [[Int]] {
var preRes = [Int]()
var inRes = [Int]()
var postRes = [Int]()
func order(_ r: TreeNode?) {
guard let r = r else { return }
preRes.append(r.val)
order(r.left)
inRes.append(r.val)
order(r.right)
postRes.append(r.val)
}
order(root)
return [preRes, inRes, postRes]
}func hasCycle(_ head: ListNode?) -> Bool {
var slow = head
var fast = head
while fast?.next != nil {
slow = slow?.next
fast = fast?.next?.next
if slow === fast {
return true
}
}
return false
}寻找第K大
func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
var nums = nums
var low = 0, high = nums.count - 1
let target = nums.count - k
while true {
let index = partitionHelper(&nums, low, high)
if index == target {
return nums[index]
} else if index < target {
low = index + 1
} else {
high = index - 1
}
}
return -1
}
private func partitionHelper(_ a: inout [Int], _ low: Int, _ high: Int) -> Int {
// 注意：测试用例中包括极端case（a数组为已排好序的n位数组）
// 如果不使用随机数选择，会导致时间复杂度退化为 O(n^2)
let x = Int.random(in: low...high)
a.swapAt(x, high)
let pivot = a[high]
var i = low
for j in low..<high {
if a[j] < pivot {
a.swapAt(i, j)
i += 1
}
}
a.swapAt(i, high)
return i
} func getLeastNumbers(_ arr: [Int], _ k: Int) -> [Int] {
if k == 0 || arr.count == 0 {
return []
}
var arr = arr
return quickSearch(&arr, 0, arr.count - 1, k - 1)
}
private func quickSearch(_ arr: inout [Int], _ low: Int, _ high: Int, _ target: Int) -> [Int] {
let p = getPartition(&arr, low, high)
if p == target {
return [Int](arr[...p])
}
return p > target ?
quickSearch(&arr, low, p - 1, target) :
quickSearch(&arr, p + 1, high, target)
}
private func getPartition(_ arr: inout [Int], _ low: Int, _ high: Int) -> Int {
// 此处通过随机数选择，避免出现已排序数组的极端case
let x = Int.random(in: low...high)
arr.swapAt(x, high)
let pivot = arr[high]
var i = low
for j in low..<high {
if arr[j] < pivot {
arr.swapAt(i, j)
i += 1
}
}
arr.swapAt(i, high)
return i
}class MyQueue {
var addStack = [Int]()
var deleteStack = [Int]()
init() {
}
func push(_ value: Int) {
addStack.append(value)
}
func pop() -> Int {
guard let last = deleteStack.popLast() else {
guard !addStack.isEmpty else { return -1 }
while let top = addStack.popLast() {
deleteStack.append(top)
}
return deleteStack.popLast()!
}
return last
}
func peek() -> Int {
guard let last = deleteStack.last else {
guard !addStack.isEmpty else { return -1 }
while let top = addStack.popLast() {
deleteStack.append(top)
}
return deleteStack.last!
}
return last
}
func empty() -> Bool {
return addStack.isEmpty && deleteStack.isEmpty
}
}class MyStack {
var queue = [Int]()
init() {
}
func push(_ value: Int) {
queue.append(value)
var size = queue.count
while size > 1 {
queue.append(queue.removeFirst())
size -= 1
}
}
func pop() -> Int {
guard !empty() else { return -1 }
return queue.removeFirst()
}
func top() -> Int {
guard !empty() else { return -1 }
return queue.first!
}
func empty() -> Bool {
return queue.isEmpty
}
} func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
let dummy = ListNode(-1)
dummy.next = head
var fast: ListNode? = dummy
var count = n
while count > 0 {
fast = fast?.next
count -= 1
}
var slow: ListNode? = dummy
while fast?.next != nil {
slow = slow?.next
fast = fast?.next
}
slow?.next = slow?.next?.next
return dummy.next
}注意，这个是正序链表，需要考虑结果反转
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var l1 = l1
var l2 = l2
var stack1 = [ListNode]()
var stack2 = [ListNode]()
while l1 != nil || l2 != nil {
if let n1 = l1 {
stack1.append(n1)
}
if let n2 = l2 {
stack2.append(n2)
}
l1 = l1?.next
l2 = l2?.next
}
let dummy = ListNode(-1)
var carry = 0
while !stack1.isEmpty || !stack2.isEmpty || carry > 0 {
var sum = 0
if let n1 = stack1.popLast() {
sum += n1.val
}
if let n2 = stack2.popLast() {
sum += n2.val
}
sum += carry
carry = sum / 10
let newNode = ListNode(sum % 10)
newNode.next = dummy.next
dummy.next = newNode
}
return dummy.next
} func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var l1 = l1
var l2 = l2
var stack1 = [ListNode]()
var stack2 = [ListNode]()
while l1 != nil || l2 != nil {
if let n1 = l1 {
stack1.append(n1)
}
if let n2 = l2 {
stack2.append(n2)
}
l1 = l1?.next
l2 = l2?.next
}
let dummy = ListNode(-1)
var carry = 0
while !stack1.isEmpty || !stack2.isEmpty || carry > 0 {
var sum = 0
if let n1 = stack1.popLast() {
sum += n1.val
}
if let n2 = stack2.popLast() {
sum += n2.val
}
sum += carry
carry = sum / 10
let newNode = ListNode(sum % 10)
newNode.next = dummy.next
dummy.next = newNode
}
return dummy.next
}也可以使用 hash set 检测，但空间 O(n)
func hasCycle(_ head: ListNode?) -> Bool {
var slow = head
var fast = head
while fast?.next != nil {
slow = slow?.next
fast = fast?.next?.next
if slow === fast {
return true
}
}
return false
}func detectCycle(_ head: ListNode?) -> ListNode? {
var slow = head
var fast = head
while true {
slow = slow?.next
fast = fast?.next?.next
if fast?.next == nil {
return nil
}
if slow === fast {
break
}
}
slow = head
while slow !== fast {
slow = slow?.next
fast = fast?.next
}
return slow
}func lengthOfLongestSubstring(_ s: String) -> Int {
var start = 0
var end = 0
var res = 0
var set: Set<Character> = []
let chars = Array(s)
while end < chars.count {
if !set.contains(chars[end]) {
set.insert(chars[end])
res = max(res, end - start + 1)
end += 1
} else {
set.remove(chars[start])
start += 1
}
}
return res
}func lengthOfLongestSubstring(_ s: String) -> Int {
let chars = Array(s)
var start = 0
var end = 0
var map = [Character: Int]()
var ans = 0
while end < chars.count {
let curChar = chars[end]
if let index = map[curChar] {
start = max(start, index)
}
ans = max(ans, end - start + 1)
map[curChar] = end + 1
end += 1
}
return ans
}依据公式: l1 + c + l2 = l2 + c + l1
其中 l1 为 headA 节点的特有部分长度，l2 为 headB 节点的特有部分长度，c 为 双方公共长度
func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
var p = headA
var q = headB
while p !== q {
if p == nil {
p = headB
} else {
p = p?.next
}
if q == nil {
q = headA
} else {
q = q?.next
}
}
return p
}func isValid(_ s: String) -> Bool {
let map: [Character: Character] = ["(": ")", "[": "]", "{": "}"]
let chars = Array(s)
var stack = [Character]()
for c in chars {
if map[c] != nil {
stack.append(c)
} else {
guard let x = stack.popLast(), map[x] == c else {
return false
}
}
}
return stack.isEmpty
} func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var l1 = l1
var l2 = l2
let dummy = ListNode(-1)
var cur: ListNode? = dummy
while l1 != nil && l2 != nil {
if l1!.val < l2!.val {
cur?.next = l1
l1 = l1?.next
} else {
cur?.next = l2
l2 = l2?.next
}
cur = cur?.next
}
cur?.next = l1 != nil ? l1 : l2
return dummy.next
} func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
guard let l1 = l1 else { return l2 }
guard let l2 = l2 else { return l1 }
if l1.val < l2.val {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l1, l2.next)
return l2
}
} func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
var lists = lists
let dummy = ListNode(-1)
var cur: ListNode? = dummy
while true {
var minNode: ListNode?
var minIndex = -1
for i in 0..<lists.count {
guard lists[i] != nil else { continue }
if minNode == nil || lists[i]!.val < minNode!.val {
minNode = lists[i]
minIndex = i
}
}
guard minIndex != -1 else { break }
cur?.next = minNode
cur = cur?.next
lists[minIndex] = lists[minIndex]?.next
}
return dummy.next
} func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
return mergeHelper(lists, 0, lists.count - 1)
}
func mergeHelper(_ lists: [ListNode?], _ low: Int, _ high: Int) -> ListNode? {
// 一定记得边界返回条件
guard low <= high else { return nil }
if low == high {// 记得返回头结点边界条件
return lists[low]
}
let mid = low + (high - low) >> 1
let l1 = mergeHelper(lists, low, mid)
let l2 = mergeHelper(lists, mid + 1, high)
return merge2list(l1, l2)
}
func merge2list(_ h1: ListNode?, _ h2: ListNode?) -> ListNode? {
guard let h1 = h1 else { return h2 }
guard let h2 = h2 else { return h1 }
if h1.val < h2.val {
h1.next = merge2list(h1.next, h2)
return h1
} else {
h2.next = merge2list(h1, h2.next)
return h2
}
}
- 排序、排序、排序！
- 三指针，第一个指针对应的值一定小于等于0
- 三个指针都要去重，并且保证 lb < rb
- sum 三种条件都要移动指针，否则会死循环
func threeSum(_ nums: [Int]) -> [[Int]] {
var nums = nums
nums.sort()
guard nums.count >= 3 else { return [] }
var res = [[Int]]()
for i in 0..<nums.count {
let p = nums[i]
guard p <= 0 else { break }
if i > 0 && p == nums[i - 1] { continue }
var lb = i + 1
var rb = nums.count - 1
while lb < rb {
let sum = p + nums[lb] + nums[rb]
if sum == 0 {
res.append([p, nums[lb], nums[rb]])
while lb < rb && nums[lb] == nums[lb + 1] { lb += 1 }
while lb < rb && nums[rb] == nums[rb - 1] { rb -= 1 }
lb += 1
rb -= 1
} else if (sum < 0) {
lb += 1
} else {
rb -= 1
}
}
}
return res
}func levelOrder(_ root: TreeNode?) -> [[Int]] {
guard let root = root else { return [] }
var queue = [root]
var res = [[Int]]()
while !queue.isEmpty {
let size = queue.count
var row = [Int]()
for _ in 0..<size {
let top = queue.removeFirst()
row.append(top.val)
if let left = top.left {
queue.append(left)
}
if let right = top.right {
queue.append(right)
}
}
res.append(row)
}
return res
} func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
guard let root = root else { return [] }
var res = [[Int]]()
var queue = [root]
var reverse = false
while !queue.isEmpty {
let size = queue.count
var rows = [Int]()
for _ in 0..<size {
let top = queue.removeFirst()
rows.append(top.val)
if let ln = top.left {
queue.append(ln)
}
if let rn = top.right {
queue.append(rn)
}
}
rows = reverse ? rows.reversed() : rows
res.append(rows)
reverse = !reverse
}
return res
} func maxDepth(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 }
return max(maxDepth(root.left), maxDepth(root.right)) + 1
}func maxProfit(_ prices: [Int]) -> Int {
var minPrice = Int.max
var maxProfit = 0
for p in prices {
if p < minPrice {
minPrice = p // 尝试确认最低点
} else {
maxProfit = max(maxProfit, p - minPrice) // 尝试确认最大利润
}
}
return maxProfit
}
- 找中点
- 反转后半段
- 前后是否相等
func isPalindrome(_ head: ListNode?) -> Bool {
// 找中点
var slow = head
var fast = head
while fast?.next?.next != nil {
slow = slow?.next
fast = fast?.next?.next
}
let reversedHead = slow?.next
let dummy = ListNode(-1)
var cur = reversedHead
while cur != nil {
let temp = cur?.next
cur?.next = dummy.next
dummy.next = cur
cur = temp
}
var p = head
var q = dummy.next
while p != nil && q != nil {
if p!.val != q!.val { return false }
p = p?.next
q = q?.next
}
return true
}通过移位，使正整数 x 都处在 x - 1下标的位置，方便统计谁没到
func minNumberDisappeared(_ arr: [Int]) -> Int {
var arr = arr
for i in 0..<arr.count {
if arr[i] > 0 && arr[i] <= arr.count {
arr.swapAt(arr[i] - 1, i)
}
}
for i in 0..<arr.count {
if arr[i] != i + 1 {
return i + 1
}
}
return arr.count + 1
}注意内存溢出
func reverse(_ x: Int) -> Int {
var x = x
var res = 0
while x != 0 {
let mod = x % 10
x /= 10
res = res * 10 + mod
}
return res < Int32.min || res > Int32.max ? 0 : res
}此处需要注意和力扣二分查找的条件不同
func upperBound(_ n: Int,_ v: Int, _ a: [Int]) -> Int {
guard n > 0 else { return n + 1 }
guard v <= a[n - 1] else { return n + 1 }
var left = 0, right = n - 1
while left < right {
let mid = left + (right - left) >> 1
if a[mid] < v {
left = mid + 1
} else {
right = mid
}
}
return left + 1
}func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var map = [Int: Int]()
for i in 0..<nums.count {
if let idx = map[target - nums[i]] {
return [idx, i]
}
map[nums[i]] = i;
}
return []
}func firstUniqChar(_ s: String) -> Character {
let chars = Array(s)
var map = [Character: Bool]()
for c in chars {
map[c] = map[c] != nil ? false : true
}
for c in chars {
if let v = map[c], v == true { return c }
}
return " "
}控制边界，依次向内收缩
func spiralOrder(_ matrix: [[Int]]) -> [Int] {
var res = [Int]()
guard !matrix.isEmpty && !matrix[0].isEmpty else { return res }
let rows = matrix.count
let cols = matrix[0].count
var left = 0, right = cols - 1, top = 0, bottom = rows - 1
while left <= right && top <= bottom {
var col = left
while col <= right {
res.append(matrix[top][col])
col += 1
}
var row = top + 1
while row <= bottom {
res.append(matrix[row][right])
row += 1
}
if left < right && top < bottom {
col = right - 1
while col > left {
res.append(matrix[bottom][col])
col -= 1
}
row = bottom
while row > top {
res.append(matrix[row][left])
row -= 1
}
}
top += 1
bottom -= 1
left += 1
right -= 1
}
return res
}func isBalanced(_ root: TreeNode?) -> Bool {
guard let root = root else { return true }
return abs(maxHeightHelper(root.left) - maxHeightHelper(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right)
}
func maxHeightHelper(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 }
return max(maxHeightHelper(root.left), maxHeightHelper(root.right)) + 1
}注意：此题目和牛客的条件不太一样
func pathSum(_ root: TreeNode?, _ sum: Int) -> [[Int]] {
var res = [[Int]]()
func dfs(_ r: TreeNode?, _ path: [Int], _ s: Int) {
guard let r = r else { return }
if r.left == nil && r.right == nil && s == r.val {
res.append(path + [r.val])
return
}
dfs(r.left, path + [r.val], s - r.val)
dfs(r.right, path + [r.val], s - r.val)
}
dfs(root, [], sum)
return res
} func sumNumbers(_ root: TreeNode?) -> Int {
var res = 0
func helper(_ r: TreeNode?, _ sum: Int) {
guard let r = r else { return }
if r.left == nil && r.right == nil {
res += (sum * 10 + r.val)
return
}
helper(r.left, sum * 10 + r.val)
helper(r.right, sum * 10 + r.val)
}
helper(root, 0)
return res
} func hasPathSum(_ root: TreeNode?, _ sum: Int) -> Bool {
var has = false
func dfs(_ r: TreeNode?,_ s: Int) {
guard let r = r, !has else { return }
if r.left == nil && r.right == nil && s == r.val {
has = true
return
}
dfs(r.left, s - r.val)
dfs(r.right, s - r.val)
}
dfs(root, sum)
return has
}func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
// 预处理
var dict = [Int: Int]()
for i in 0..<inorder.count {
dict[inorder[i]] = i
}
func helper(_ preRoot: Int, _ inLeft: Int, _ inRight: Int) -> TreeNode? {
if inLeft > inRight { return nil }
let root = TreeNode(preorder[preRoot])
let mid = dict[preorder[preRoot]]!
root.left = helper(preRoot + 1, inLeft, mid - 1)
root.right = helper(preRoot + （mid - inLeft + 1）, mid + 1, inRight)
return root
}
return helper(0, 0, inorder.count - 1)
} func merge(_ intervals: [[Int]]) -> [[Int]] {
var res = [[Int]]()
guard !intervals.isEmpty else { return res }
let intervals = intervals.sorted() { $0[0] < $1[0] }
res.append(intervals[0])
for i in 1..<intervals.count {
let lastIndex = res.count - 1
if res[lastIndex][1] < intervals[i][0] {
res.append(intervals[i])
} else {
res[lastIndex][1] = max(res[lastIndex][1], intervals[i][1])
}
}
return res
} func merge(_ intervals: [Interval]) -> [Interval] {
var intervals = intervals
var res = [Interval]()
guard !intervals.isEmpty else { return res }
intervals.sort { $0.start < $1.start }
res.append(intervals[0])
for i in 0..<intervals.count {
if intervals[i].start <= res.last!.end {
res.last!.end = max(intervals[i].end, res.last!.end)
} else {
res.append(intervals[i])
}
}
return res
}func multiply(_ num1: String, _ num2: String) -> String {
guard num1 != "0" && num2 != "0" else { return "0" }
var res = [Int](repeating: 0, count: num1.count + num2.count)
let chars1 = Array(num1)
let chars2 = Array(num2)
for i in (0..<chars1.count).reversed() {
for j in (0..<chars2.count).reversed() {
let n1 = chars1[i].wholeNumberValue!
let n2 = chars2[j].wholeNumberValue!
let sum = res[i + j + 1] + n1 * n2
res[i + j + 1] = sum % 10
res[i + j] += sum / 10
}
}
var s = ""
for i in 0..<res.count {
if i == 0 && res[i] == 0 { continue }
s += String(res[i])
}
return s
}func permuteUnique(_ nums: [Int]) -> [[Int]] {
var res = [[Int]]()
let nums = nums.sorted()
var visited = [Bool](repeating: false, count: nums.count)
func dfs(_ row: [Int]) {
if row.count == nums.count {
res.append(row)
return
}
for i in 0..<nums.count {
guard !visited[i] else { continue }
if i > 0 && nums[i - 1] == nums[i] && !visited[i - 1] {
// 剪枝
continue
}
visited[i] = true
dfs(row + [nums[i]])
visited[i] = false
}
}
dfs([Int]())
return res
}func hammingWeight(_ n: Int) -> Int {
var res = 0
var n = n
while n != 0 {
res += n & 1
n >>= 1
}
return res
}M 为 1 的个数
func hammingWeight(_ n: Int) -> Int {
var n = n
var res = 0
while n != 0 {
n &= n - 1
res += 1
}
return res
}func rotate(_ nums: inout [Int], _ k: Int) {
guard k != 0 else { return }
let n = nums.count
let k = k % n
reverse(&nums, 0, n - 1)
reverse(&nums, 0, k - 1)
reverse(&nums, k, n - 1)
}
func reverse(_ a: inout [Int], _ left: Int, _ right: Int) {
var left = left
var right = right
while left < right {
a.swapAt(left, right)
left += 1
right -= 1
}
}func findPeakElement(_ nums: [Int]) -> Int {
guard !nums.isEmpty else { return -1 }
var left = 0
var right = nums.count - 1
while left < right {
let mid = left + (right - left) >> 1
if nums[mid] < nums[mid + 1] {
left = mid + 1
} else {
right = mid
}
}
return left
}func moveZeroes(_ nums: inout [Int]) {
var lastNonZero = 0
for index in 0..<nums.count {
if nums[index] != 0 {
if index != lastNonZero {
nums.swapAt(lastNonZero, index)
}
lastNonZero += 1
}
}
}func trailingZeroes(_ n: Int) -> Int {
var n = n
var res = 0
while n != 0 {
res += n / 5
n /= 5
}
return res
}func trap(_ heights: [Int]) -> Int {
var stack = [Int]()
var sumArea = 0
for i in 0..<heights.count {
// 单调递减栈
while let top = stack.last, heights[top] < heights[i] {
_ = stack.popLast()!
guard let leftBar = stack.last else { break }
let h = min(heights[leftBar], heights[i]) - heights[top]
let area = h * (i - leftBar - 1)
sumArea += area
}
stack.append(i)
}
return sumArea
}func trap(_ heights: [Int]) -> Int {
var left = 0, right = heights.count - 1
var maxLeft = 0, maxRight = 0
var ans = 0
while left < right {
if heights[left] < heights[right] {
if heights[left] >= maxLeft {
maxLeft = heights[left]
} else {
ans += (maxLeft - heights[left])
}
left += 1
} else {
if heights[right] >= maxRight {
maxRight = heights[right]
} else {
ans += (maxRight - heights[right])
}
right -= 1
}
}
return ans
}正则表达式匹配