Welcome to LeaCoder's Blog!
持之以恒终有收获，自律自强方至成功-
《MySQL必知必会》学习笔记（1-8）
《MySQL必知必会》学习笔记 目录
-
LeetCode-72--编辑距离(Edit-Distance)
72. 编辑距离
72. 编辑距离 给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符 示例 1: 输入: word1 = "horse", word2 = "ros" 输出: 3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 示例 2: 输入: word1 = "intention", word2 = "execution" 输出: 5 解释: intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')Python3 实现
动态规划
#@author:leacoder #@des: 动态规划 编辑距离 class Solution: def minDistance(self, word1: str, word2: str) -> int: len1 = len(word1) len2 = len(word2) ''' 动态规划 step1: 状态 首先只定义一维 DP[i] 不能有效简化问题的处理 使用 二维 DP[i][j]，表示 word1 的 i 个字母 与 word2 的 第 j 个字母 相同 需要的操作步骤数 将最对 word1 处理 转化为 对 word1 和 word2 均处理 word1 插入一个字符 DP[i-1][j] + 1 -> DP[i][j] word1 删除一个字符 = word2 插入一个字符 DP[i][j-1] + 1 -> DP[i][j] word1 替换一个字符 = word1 word2 都替换一个字符 DP[i-1][j-1] + 1 -> DP[i][j] step2: 动态方程 DP[i][j] A、 word1 的 i 个字母 与 word2 的 第 j 个字母 相同 DP[i][j] = DP[i-1][j-1] #不操作 B、不相同,需要进行 插入 删除 或者 替换操作 DP[i][j] = min(DP[i-1][j] + 1,DP[i][j-1] + 1,DP[i-1][j-1]+1) ''' DP = [[0 for _ in range(len2+1)] for _ in range(len1+1)] # 初始 for i in range(len1+1): DP[i][0] = i for j in range(len2+1): DP[0][j] = j for i in range(1,len1+1): for j in range(1,len2+1): if word1[i - 1] == word2[j -1]: DP[i][j] = DP[i-1][j-1] else: DP[i][j] = min(DP[i-1][j] + 1,DP[i][j-1] + 1,DP[i-1][j-1]+1) return DP[len1][len2]
GitHub链接： https://github.com/lichangke/LeetCode
个人Blog: https://lichangke.github.io/
欢迎大家来一起交流学习
-
LeetCode-322--零钱兑换(Coin-Change)
322. 零钱兑换
322. 零钱兑换 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 示例 1: 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2: 输入: coins = [2], amount = 3 输出: -1 说明: 你可以认为每种硬币的数量是无限的。Python3 实现
动态规划
# @author:leacoder # @des: 动态规划 零钱兑换 class Solution: def coinChange(self, coins: List[int], amount: int) -> int: if amount < 0 : return -1 DP = [amount + 1]*(amount + 1) #DP[i] 表示 总金额 为 i 时的最少硬币数，极限情况硬币数为 amount 不可能为 amount + 1 DP[0] = 0 # 初始 下面 DP[i - coin] 中 i - coin = 0时 for i in range(1,amount+1): # 总金额 1 到 amount 的循环 for coin in coins: # 不同面额遍历 if coin <= i: # 面额小于总金额 DP[i] = min(DP[i],DP[i - coin] + 1) # DP方程 类似70. 爬楼梯； if DP[amount] == amount+1: return -1 else: return DP[amount]
GitHub链接： https://github.com/lichangke/LeetCode
个人Blog: https://lichangke.github.io/
欢迎大家来一起交流学习
-
LeetCode-300--最长上升子序列(Longest-Increasing-Subsequence)
-
LeetCode-188--买卖股票的最佳时机-IV(Best-Time-to-Buy-and-Sell-Stock-IV)
188. 买卖股票的最佳时机 IV
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 输入: [2,4,1], k = 2 输出: 2 解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。 示例 2: 输入: [3,2,6,5,0,3], k = 2 输出: 7 解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。Python3 实现
动态规划
买卖股票的最佳时机 系列问题 通用型 解法 ，LeetCode 121 123 均可参考此方法
# @author:leacoder # @des: 动态规划 买卖股票的最佳时机 IV(通用型) class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: n = len(prices) if n<=1: return 0 if k>int(n/2): # 会超时 #k = int(n/2) return self.greedy(prices) # 使用贪心 maxprof = 0 profit = [[[0 for _ in range(2)] for _ in range(k+1)] for _ in range(0,len(prices))] # DP[ii][kk][0] 第ii天完成kk次操作无股票 DP[ii][kk][1]第ii天完成kk次操作有股票 prices[ii] 第ii天股票价格 for i in range(0,k+1): profit[0][i][0] = 0 # 第 1 天 操作i 次 没有股票，所以初始值为 0 profit[0][i][1] = - prices[0] # 第 1 天 操作i 次 有股票， 所以初始值为 - prices[ii] for ii in range(1,len(prices)): # 天数 for kk in range(0, k + 1): # 交易次数 if kk == 0: # profit[ii][kk][0] = profit[ii - 1][kk][0] # 0 次交易 今天利润 == 前一天利润 else: # 今天完成kk次操作无股票 max(前一天无股票今天不交易，前一天有股票今天卖出) 买卖一次算一笔交易 故 profit[ii - 1][kk - 1][1] + prices[ii] profit[ii][kk][0] = max(profit[ii - 1][kk][0], profit[ii - 1][kk - 1][1] + prices[ii]) # 今天完成kk次操作有股票 max(前一天有股票今天不交易，前一天无股票今天买入) profit[ii][kk][1] = max(profit[ii - 1][kk][1], profit[ii - 1][kk][0] - prices[ii]) maxprof = max(maxprof, profit[ii][kk][0]) return maxprof def greedy(self,prices: List[int]) -> int: max = 0 for i in range(1,len(prices)): if prices[i]>prices[i-1]: max += prices[i] - prices[i-1] return max
GitHub链接： https://github.com/lichangke/LeetCode
个人Blog: https://lichangke.github.io/
欢迎大家来一起交流学习
-
LeetCode-123--买卖股票的最佳时机-III(Best-Time-to-Buy-and-Sell-Stock-III)
123. 买卖股票的最佳时机 III
123. 买卖股票的最佳时机 III 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 输入: [3,3,5,0,0,3,1,4] 输出: 6 解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 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。Python3 实现
动态规划
# @author:leacoder # @des: 动态规划 买卖股票的最佳时机 III(通用型) class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 # 三维数组 # profit[ii][kk][jj] # ii 第 ii 天， kk 股票操作了几次 ， jj 是否有股票 # 最多可以完成 两笔 交易： kk 可以为 0 1 2 次操作 ， jj可以为 0 ，1 0 没有股票 1有股票 profit = [[[0 for _ in range(2)] for _ in range(3)] for _ in range(len(prices))] # 第一天 初始化 for k in range(3): #最多可以完成 两笔 交易 故range(3) profit[0][k][0] = 0 # 第 1 天 操作 k 次 没有股票，所以初始值为 0 profit[0][k][1] = - prices[0] # 第 1 天 操作i 次 有股票， 所以初始值为 - prices[0] # 注意 买 卖 都进行一次算一次操作 k + 1,单独 买入 不算完成一次操作 for i in range(1,len(prices)): # 第 i 天 0 次交易 没有股票最大利润 = 第 i-1 天 0 次交易 没有股票最大利润 profit[i][0][0] = profit[i-1][0][0] # 第 i 天 0 次交易 有股票最大利润 = max(第 i-1 天 0 次交易 有股票最大利润 , 第 i-1 天 0 次交易 无股票最大利润 - 当天股票价格prices[i]（买入）) profit[i][0][1] = max(profit[i-1][0][1],profit[i-1][0][0] - prices[i]) # 第 i 天 1 次交易 无股票最大利润 = max(第 i-1 天 1次交易 无股票最大利润 , 第 i-1 天 0 次交易 有股票最大利润 + 当天股票价格prices[i]（卖出）) profit[i][1][0] = max(profit[i-1][1][0],profit[i-1][0][1] +prices[i] ) # 第 i 天 1 次交易 有股票最大利润 = max(第 i-1 天 1 次交易 有股票最大利润 , 第 i-1 天 1 次交易 无股票最大利润 - 当天股票价格prices[i]（买入）) profit[i][1][1] = max(profit[i-1][1][1],profit[i-1][1][0] - prices[i]) # 第 i 天 2 次交易 无股票最大利润 = max(第 i-1 天 2次交易 无股票最大利润 , 第 i-1 天 1 次交易 有股票最大利润 + 当天股票价格prices[i]（卖出）) profit[i][2][0] = max(profit[i-1][2][0],profit[i-1][1][1] + prices[i] ) end = len(prices) - 1 return max(profit[end][0][0],profit[end][1][0],profit[end][2][0])
GitHub链接： https://github.com/lichangke/LeetCode
个人Blog: https://lichangke.github.io/
欢迎大家来一起交流学习
Recent Posts
Tags