2020.7.4

Review

121. 买卖股票的最佳时机

方法一:暴力法: 时间复杂度O(n^2), 空间复杂度O(1)

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。 注意：你不能在买入股票前卖出股票。 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

func maxProfit(_ prices: [Int]) -> Int { if prices.isEmpty {return 0} var maxProfit = 0 for i in 1..prices.count - 1 { for j in i..prices.count { if prices[j] > prices[i - 1] { let difValue = prices[j] - prices[i - 1] maxProfit = maxProfit > difValue ? maxProfit : difValue } } } return maxProfit }

方法二:时间复杂度O(n), 空间复杂度O(1)

func maxProfit(_ prices: [Int]) -> Int { if prices.isEmpty { return 0 } var maxProfit = 0 var minValue = Int.max for i in 0..<prices.count { if prices[i] < minValue { minValue = prices[i] }else if prices[i] - minValue > maxProfit { maxProfit = prices[i] - minValue } } return maxProfit }

122. 买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 示例 2: 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。 示例 3: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

方法一

//[7,1,5,3,6,4] func maxProfitII(_ prices: [Int]) -> Int { if prices.isEmpty { return 0 } var maxProfit = 0 var minPrice = Int.max for i in 0..<prices.count { if prices[i] < minPrice { minPrice = prices[i] }else if (prices[i] > minPrice) { maxProfit += prices[i] - minPrice minPrice = prices[i] } } return maxProfit }

方法二

func maxProfitII1(_ prices: [Int]) -> Int { var maxProfit = 0 for i in 1..<prices.count { if prices[i] - prices[i - 1] > 0 { maxProfit += prices[i] - prices[i - 1] } } return maxProfit }

55. 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1: 输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。 示例 2: 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

/* 伪代码 int reach = 0, n = size() for (int i = 0; i < n; i++) { if (i > reach) { // 假如当前遍历的i已经超过了reach, 表明这个位置是我们跳不到的,因为i已经遍历到了我们已经到达最远位置更靠后的i的位置上, 直接返回false, 如果不是这种情况,就表示当前位置是我们可以到的,并且我们可以在这个位置上继续向前跳远 return false; } reach = Math.max(i + A[i], reach); } // 从i = 0到i = 1全部都遍历到了 return true */ func canJump(_ nums: [Int]) -> Bool { if nums.isEmpty { return false } var reach = 0 for i in 0..<nums.count { if i > reach { return false } reach = max(i + nums[i], reach) } return true }

方法二:

func canJumpI(_ nums: [Int]) -> Bool { if nums.count <= 1 { return true } var lastPosition = nums.count - 1 for i in (0..<nums.count).reversed() { if i + nums[i] >= lastPosition { lastPosition = i } } return lastPosition == 0 }

方法三(1):低效的回溯

思想,比如[2,3,1,1,4],从第0个位置开始,最远跳(该位置索引 + 该位置元素值),比如当前索引为0,值为2,那么最远可以跳2步,当然也可以跳1步,如果选择跳1步(相同的回溯步骤)返回false那么就选择跳2步的直到返回true,如果跳1步和跳2步都返回false,那么表示无法到达最后的位置 if canJumpFromPosition(nextPosition, nums) { return true } 注意这一步不能写为 if canJumpFromPosition(nextPosition, nums) { return true }else { return false } 如果这样写了,那么表示选择了第一步返回false,后面的第二步,第三步,就不能再试了,所以这不返回false 就表示,可以通过其他选择路径看看是否可以返回true,有一种位置返回true的那么就一肯定能到达, 如果全部选择都试过都不能返回true,最后就返回false,表示任何种走法都不能到达nums.count -1这个位置

func canJump_backtrace(_ nums: [Int]) -> Bool { return canJumpFromPosition(0, nums); } func canJumpFromPosition(_ position: Int, _ nums: [Int]) -> Bool { if position == nums.count - 1 { return true } let furthestJump = min(position + nums[position], nums.count - 1) for nextPosition in stride(from: position + 1, through: furthestJump, by: 1) { if canJumpFromPosition(nextPosition, nums) { // 注意点 return true } } return false }

方法三(2)

class JampGame { enum Index { case Good case Bad case Ugly } var memo = [Index]() func canJumpFormUpToBottom_dp(_ nums: [Int]) -> Bool { memo = [Index](repeating: .Ugly, count: nums.count) memo[nums.count - 1] = .Good // return canJumpFormPosition_dp(0, nums) return canJumpFormBottomToUp_dp(nums) } //MARK: 自顶向下动态规划 func canJumpFormPosition_dp(_ position: Int, _ nums: [Int]) -> Bool { if memo[position] != .Ugly { return memo[position] == .Good } let furthestPosition = min(position + nums[position], nums.count - 1) for nextPosition in stride(from: position + 1, to: furthestPosition, by: 1) { if canJumpFormPosition_dp(nextPosition, nums) { memo[nextPosition] = .Good return true } } memo[position] = .Bad return false } // [2,3,1,1,4] //MARK: 自底向上动态规划 func canJumpFormBottomToUp_dp(_ nums: [Int]) -> Bool { for i in stride(from: nums.count - 2, to: 0, by: -1) { let furthestPosition = min(i + nums[i], nums.count - 1) for j in stride(from: i + 1, to: furthestPosition, by: 1) { if memo[j] == .Good { memo[i] = .Good break } } } return memo[0] == .Good } }

33. 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 你可以假设数组中不存在重复的元素。 你的算法时间复杂度必须是 O(log n) 级别。 示例 1: 输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4 示例 2: 输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1

方法一 第一种方式就是先找到有序区域，再划分的方式

// 数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] [7, 0, 1, 2, 4, 5, 6] // MARK: 先找有序区域再划分 func search1(_ nums: [Int], _ target: Int) -> Int { if nums.isEmpty {return -1} if nums.count == 1 { return nums[0] == target ? 0 : -1 } var left = 0 var right = nums.count - 1 while left <= right { let mid = left + (right - left) / 2 if nums[mid] == target { return mid } // 1 先找有序区域 // 2 再确定target所在区域 if nums[mid] >= nums[0] { // 1 左边是有序的 if target >= nums[0] && target < nums[mid] { right = mid - 1 //2 目标在左边有序的部分 }else { left = mid + 1 } }else { // 1 右边是有序的 if nums[mid] < target && target <= nums[right] { left = mid + 1 // 2 目标在有序的部分 }else { right = mid - 1 } } } return -1 }

方法一 第二种方式是找到旋转的位置，然后分段去二分查找

func search(_ nums: [Int], _ target: Int) -> Int { // 找旋转点的方式, 突变点的前面是升序,突变点开始到结尾是升序包括突变点本身 // 所以要注意 前一个是end: rotatedIndex - 1,后一个是start: rotatedIndex let rotatedIndex = findRotatedIndex(nums) var result = binarySearch(nums, start: 0, end: rotatedIndex - 1, target: target) if result != -1 {return result } result = binarySearch(nums, start: rotatedIndex, end: nums.count - 1, target: target) return result } func findRotatedIndex(_ nums: [Int]) -> Int { var left = 0 var right = nums.count - 1 // 防止没有旋转的数组,即本身就是升序 if nums[left] < nums[right] { return left } while left <= right { let mid = left + (right - left) / 2 if nums[mid] > nums[mid + 1] { return mid + 1 } if nums[mid - 1] > nums[mid] { return mid } if nums[mid] > nums[0] { left = mid + 1 } if nums[mid] < nums[0] { right = mid - 1 } } return left } func binarySearch(_ nums: [Int], start: Int, end: Int, target: Int) -> Int { //[0, 1, 2, 3, 4, 5] var left = start, right = end while (left <= right) { let mid = left + (right - left) / 2 if nums[mid] == target { return mid }else if (nums[mid] > target) { right = mid - 1 }else if (nums[mid] < target) { left = mid + 1 } } return -1 }