2020.7.5

Priority 剑指 Offer 59 - I. 滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。 示例: 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 -[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

方法一

public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; if (n * k == 0) return new int[0]; int[] output = new int[n - k + 1]; for (int i = 0; i < n - k + 1; i++) { int max = Integer.MIN_VALUE; for (int j = i; j < k + i; j++) { max = Math.max(max, nums[j]); } output[i] = max; } return output; } func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] { if nums.isEmpty {return [Int]()} // if n * k == 0 {return [Int]()} var output = [Int]() for i in stride(from: 0, to: nums.count - k + 1, by: 1) { var maxValue = Int.min for j in stride(from: i, to: k + i, by: 1) { maxValue = max(maxValue, nums[j]) } output.append(maxValue) } return output } func maxSlidingWindow1(_ nums: [Int], _ k: Int) -> [Int] { if nums.isEmpty {return [Int]()} // if n * k == 0 {return [Int]()} var output = [Int]() for i in 0..<nums.count - k + 1 { var maxValue = Int.min for j in i..<k + i { maxValue = max(maxValue, nums[j]) } output.append(maxValue) } return output }

方法二:

//MARK: 通过MaxQueue的方式 extension SlidingWindowMaximum { func maxSlidingWindow12(_ nums: [Int], _ k: Int) -> [Int] { if k <= 0 {return []} var result = [Int]() let windowCount = min(nums.count, k) var slidingWindow = [Int]() var maxWindow = [Int]() for i in 0..<windowCount { slidingWindow.append(nums[i]) while maxWindow.count > 0 && maxWindow.last! < nums[i] { maxWindow.removeLast() } maxWindow.append(nums[i]) } result.append(maxWindow.first!) for i in stride(from: k, to: nums.count, by: 1) { // dequeue if maxWindow.count > 0 && maxWindow.first == slidingWindow.first { maxWindow.removeFirst() } if slidingWindow.count > 0 { slidingWindow.removeFirst() } // enqueue slidingWindow.append(nums[i]) while maxWindow.count > 0 && maxWindow.last! < nums[i] { maxWindow.removeLast() } maxWindow.append(nums[i]) result.append(maxWindow.first!) } return result } func maxSlidingWindow11(_ nums: [Int], _ k: Int) -> [Int] { if nums.count < 0 || k <= 0 { return [] } var result = [Int]() let maxQueue = MaxQueue_ByArray() let windowCount = min(k, nums.count) for i in 0..<windowCount { maxQueue.pushToBack(nums[i]) } result.append(maxQueue.maxValue()) for i in stride(from: k, to: nums.count, by: 1) { let _ = maxQueue.popFromFront() maxQueue.pushToBack(nums[i]) result.append(maxQueue.maxValue()) } return result } } class MaxQueue_ByArray { var queue: [Int] var deque: [Int] init() { queue = [Int]() deque = [Int]() } func pushToBack(_ val: Int) { queue.append(val) while deque.count > 0 && deque.last! < val { deque.removeLast() } deque.append(val) } func popFromFront() -> Int { if queue.count == 0 { return -1 } if deque.first == queue.first { deque.removeFirst() } return queue.removeFirst() } func maxValue() -> Int { return deque.first ?? -1 } }

Review 322 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 示例 1: 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2: 输入: coins = [2], amount = 3 输出: -1 说明: 你可以认为每种硬币的数量是无限的。 1.stride(through: 5, by: 1) // 1,2,3,4,5 1.stride(to: 5, by: 1) // 1,2,3,4 for i in stride(from: 1, to: amount, by: 1) 未取到amount的数

方法一

func coinChange(_ coins: [Int], _ amount: Int) -> Int { // 错误的原因count写为了amount最后返回的是mem[amount]因为有0所以,所以mem[amount]越界了 //var mem = [Int](repeating: amount + 1, count: amount) 错误 var mem = [Int](repeating: amount + 1, count: amount + 1) mem[0] = 0 for i in stride(from: 1, through: amount, by: 1) { // 注意这里用到第是to,记没有到达coins.count,只到达了coins.count - 1 for j in stride(from: 0, to: coins.count, by: 1) { if coins[j] <= i { mem[i] = min(mem[i], 1 + mem[i - coins[j]]) } } } return mem[amount] > amount ? -1 : mem[amount] } func coinChange_temp(_ coins: [Int], _ amount: Int) -> Int { // 错误的原因count写为了amount最后返回的是mem[amount]因为有0所以,所以mem[amount]越界了 //var mem = [Int](repeating: amount + 1, count: amount) 错误 var mem = [Int](repeating: amount + 1, count: amount + 1) mem[0] = 0 for i in stride(from: 1, through: amount, by: 1) { for coin in coins { if coin <= i { mem[i] = min(mem[i], 1 + mem[i - coin]) } } } return mem[amount] > amount ? -1 : mem[amount] }

方法二: dfs

// [5, 2, 1] func coinChange_fast(_ coins: [Int], _ amount: Int) -> Int { guard coins.count > 0 else { return -1 } let coins = coins.sorted(by: >) var result = Int.max let upIndex = coins.count - 1 // [3] 2 func dfs(_ i: Int, _ amount: Int, _ count: Int) { let currentCoin = coins[i] if i < upIndex { var k = amount / currentCoin // 当前最大面值数 /* 为什么k >= 0 呢,因为比如coins = [4, 1], amount = 3 显示3/4 = 0, 虽然从3这个位置达不到4就还可以选择看下一个元素1能否达到4这个位置,所以可以去到k == 0, 为什么count + k < result, 比如coins = [5, 4, 1],amount = 5时 当 i = 0, k = 1时 下探dfs(1, 5 - (1 * 5) == 0, 0 + 1), 那么dfs(2, 0, 1)时 i = 2 curr = 1, i == upIndex,(ps: 这里i = 1时相等于 dfs(1, 0, 1)没有变只是i变为1进入下一层dfs(2, 0, 1)) 那么result = 1 + 0, 往上走, 当i = 0, k = 0时, 0 + 0 < 1 , 所以dfs(1, 5, 0), curr = 4, k = 5/4 = 1, 那么 1 + 0 < 1显然不符合count + k < result, 所以结束当前的while不用再dfs后面的值,因为前面已经是最小的结果了, */ while k >= 0, (count + k) < result { dfs(i + 1, amount - k * currentCoin, count + k) k -= 1 // 前面的k已经有了结果,再遍历比k小的看是否用到的面值最少 } }else { if amount % currentCoin == 0 { result = min(result, count + amount / currentCoin) } /* 如果当前的i已经是数组中的最后一个元素位置,那么就要求结果,因为最后一个level再进行dfs越界,同时如果处于最后一个位置,就应该知道结果了 如果当前的金额amount可以被当前面值的整除,如coins = [5] ,amount = 10, 那么result = count(到当前这一层的硬币数) + amount / coin 如果当前金额amount不能被当前面值整除, 如coins = [3], amount = 2 则result 还是Int.max 找不到. */ } } return result == Int.max ? -1 : result }

45. 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 说明: 假设你总是可以到达数组的最后一个位置

方法一

每次在可跳范围内选择可以使得跳的更远的位置。 注意一个细节，就是 for 循环中，i < nums.length - 1，少了末尾。因为开始的时候边界是第 0 个位置，steps 已经加 1 了。如果最后一步刚好跳到了末尾，此时 steps 其实不用加 1 了。如果是 i < nums.length，i 遍历到最后的时候，会进入 if 语句中，steps 会多加 1。

func jump(_ nums: [Int]) -> Int { var maxPosition = 0 var end = 0 var steps = 0 for i in 0..<nums.count - 1 { //找能跳的最远的 maxPosition = max(i + nums[i], maxPosition) if i == end { // 遇到边界，就更新边界，并且步数加一 end = maxPosition steps += 1 } } return steps }

方法二

最终要到达最后一个位置，然后我们找前一个位置，遍历数组，找到能到达它的位置，离它最远的就是要找的位置。然后继续找上上个位置，最后到了第 0 个位置就结束了。 至于离它最远的位置，其实我们从左到右遍历数组，第一个满足的位置就是我们要找的。

func jump2(_ nums: [Int]) -> Int { var position = nums.count - 1 var steps = 0 while position != 0 { for i in 0..<position { if i + nums[i] > position { position = i steps += 1 break } } } return steps }