贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法策略。它通常适用于以下几种情况：1. **最优子结构**：问题的最优解包含其子问题的最优解。2. **贪心选择性质**：通过局部最优选择，可以导致全局最优解

贪心 (1) 买卖股票的最佳时机 """ 给定一个数组 prices, 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。 """ res = 0 min_price = prices[0] for p in prices: res = max(ans, p - min_price) min_price = min(min_price, p) return res (2) 跳跃游戏 """ 给你一个非负整数数组 nums，你最初位于数组的 第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false。 """ bound = 0 for i in range(len(nums)): if i > bound: return False bound = max(bound, i+nums[i]) return True (3) 跳跃游戏 II """ 给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。返回到达 n-1 的最小跳跃次数。测试用例保证可以到达 n-1。 """ res = bound = last = 0 for i in range(len(nums)-1): bound = max(bound, i+nums[i]) if last == i: res += 1 last = bound return res (4) 划分字母区间 """ 给你一个字符串 s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。返回一个表示每个字符串片段的长度的列表。 """ hashmap = {c: i for i, c in enumerate(s)} start = end = 0 res = [] for i, c in enumerate(s): end = max(end, hashmap[c]) # [start, end] 是已遍历字符的区间 if i == end: res.append(end-start+1) start = i+1 return res 动态规划 (1) 爬楼梯 """ 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 """ if n==1 or n==2: return n a, b, temp = 1, 2, 0 for i in range(3,n+1): temp = a + b a = b b = temp return temp (2) 杨辉三角 """ 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 """ res = [[1] * (i+1) for i in range(numRows)] for i in range(2, numRows): for j in range(1, i): res[i][j] = res[i-1][j-1]+res[i-1][j] return res (3) 打家劫舍 """ 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 """ dp = [] n = len(nums) dp = [0] * (n+1) dp[0] = 0 dp[1] = nums[0] for i in range(2, n+1): dp[i] = max(dp[i-1], dp[i-2]+nums[i-1]) return dp[n] # 优化 prev = cur = 0 for n in nums: cur, prev = max(cur, prev+n), cur return cur (4) 背包问题 """ 我们有 n 件物品和一个容量为 C 的背包，记第 i 件物品的重量为 wi，价值为 vi，求将哪些物品装入背包可使价值总和最大。 - 0-1背包：如果限定每件物品最多只能选取 0或1 次，则问题称为0-1背包问题。 - 完全背包：如果每件物品最多可以选取无限次，则问题称为 完全背包问题。 """ # dp[i][j] 表示前 i 件物品放入一个容量为 j 的背包可以获得的最大价值 dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi]+vi) # 0-1 背包 dp[i][j] = max(dp[i-1][j], dp[i-1][j-k*wi]+k*vi) # 完全背包 dp[i][j] = max(dp[i-1][j], dp[i][j-wi]+vi) # 完全背包简化 (5) 完全平方数 """ 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量。 """ dp = [0] + [float('inf')] * n for i in range(1, n + 1): for j in range(1, int(sqrt(i)) + 1): dp[i] = min(dp[i], dp[i - j*j] + 1) return dp[n] (6) 零钱兑换 """ 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。 """ dp = [0] + [float('inf')] * amount for coin in coins: for j in range(coin, amount + 1): dp[j] = min(dp[j], dp[j-coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1 # 背包解法 n = len(coins) dp = [[float('inf')] * (amount + 1) for _ in range(n + 1)] dp[0][0] = 0 for i in range(1, n+1): for j in range(amount+1): if j >= coins[i-1]: dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i-1]]+1) else: dp[i][j] = dp[i-1][j] return dp[n][amount] if dp[n][amount] != float('inf') else -1 (7) 单词拆分 """ 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 """ n = len(s) dp = [False] * (n+1) dp[0] = True for i in range(n): for j in range(i+1, n+1): if dp[i] and s[i:j] in wordDict: dp[j] = True return dp[-1] (8) 最长递增子序列 """ 给你一个整数数组 nums，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 """ n = len(nums) dp = [1] * n for i in range(n): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+1) return max(dp) (10) 乘积最大子数组 """ 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 """ n = len(nums) min_dp = [0] * n max_dp = [0] * n min_dp[0] = nums[0] max_dp[0] = nums[0] for i in range(1, n): max_dp[i] = max(nums[i], max_dp[i-1]*nums[i], min_dp[i-1]*nums[i]) min_dp[i] = min(nums[i], max_dp[i-1]*nums[i], min_dp[i-1]*nums[i]) return max(max_dp) (11) 分割等和子集 """ 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 """ total = sum(nums) if total%2 == 1: return False target = total//2 if max(nums) > target: return False n = len(nums) dp = [[False] * (target+1) for _ in range(n+1)] dp[0][0] = True for i in range(1, n+1): for j in range(target+1): if j >= nums[i-1]: dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]] else: dp[i][j] = dp[i-1][j] return dp[n][target] (12) 最长有效括号 """ 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。 """ stack = [-1] res = 0 # stack[-1] 记录包含 s[i] 的连续合法的左边界 for i, ch in enumerate(s): if ch == '(': stack.append(i) elif len(stack) > 1: stack.pop() res = max(res, i - stack[-1]) else: stack[0] = i return res