贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法策略。它通常适用于以下几种情况：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，求将哪些物品装入背包可使价值总和最大。