55. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
123>输入：nums = [2,3,1,1,4]>输出：true>解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
123>输入：nums = [3,2,1,0,4]>输出：false>解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
要成功跳跃，即每一步要落点在不等于0且下一次条约距离足够远的点，正向去做非常复杂，因此，正难则反…反过来思考。从最后一个节点开始，从后往前寻找能到达它的结点，重复此步骤，更新跳跃者的位置，如果在此位置前无法找到一个节点能到达此位置，说明跳跃会失败返回False…如果跳跃者位置更新到了下标为0的节点，说明跳跃成功，返回True 这里从后往前找到第一个能到达此 ...
139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
123>输入: s = "leetcode", wordDict = ["leet", "code"]>输出: true>解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
1234>输入: s = "applepenapple", wordDict = ["apple", "pen"]>输出: true>解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" " ...
153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
123>输入：nums = [3,4,5,1,2]>输出：1>解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
123>输入：nums = [4,5,6,7,0,1,2]>输出：0>解释：原数 ...
118. 杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
12>输入: numRows = 5>输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
12>输入: numRows = 1>输出: [[1]]
把杨辉三角的每一排左对齐：
$$ [1][1,1][1,2,1][1,3,3,1][1,4,6,4,1] $$
递推公式：
$$c[i][j]=c[i−1][j−1]+c[i−1][j]$$
12345678class Solution(object): def generate(self, numRows): c = [[1] * (i + 1) for i in range(numRows)] for i in range(2, numRows): for j in range(1, i): # 左 ...
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例 1:
12345678910111213141516>输入：>["MinStack","push","push","push","getMin","pop","top","getMin"]>[[],[-2],[0],[-3],[],[],[],[]]>输出：>[null,null,null,null,-3,null,0,-2]>解释：>MinStack minStack = new MinStack();&g ...
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
1234>输入：[1,2,3,1]>输出：4>解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
1234>输入：[2,7,9,3,1]>输出：12>解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
定义子问题：
原问题是 “从全部房子中能偷到的最大金额”，将问题的规模缩小，子问题就是 “从 k 个房子中能偷到的最大金额 ”，用 f(k) 表示。
假设有n个房子，那么偷到第k个房子（不偷第K个 ...
215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
12>输入: [3,2,1,5,6,4], k = 2>输出: 5
示例 2:
12>输入: [3,2,3,1,2,4,5,5,6], k = 4>输出: 4
主要使用归并排序
哨兵划分： 以数组某个元素（一般选取首元素）为基准数，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。递归： 对 左子数组 和 右子数组 递归执行 哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
...
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
12>输入: nums = [1,1,1,2,2,3], k = 2>输出: [1,2]
示例 2:
12>输入: nums = [1], k = 1>输出: [1]
提示：
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
方法一：使用库函数
12345class Solution(object): def topKFrequent(self, nums, k): count = collections.Counter(nums) res = [item[0] for item in count.most_common(k)] return res
方法二：使用堆排序
1234567891011121314 ...
33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
12>输入：nums = [4,5,6,7,0,1,2], target = 0>输出：4
示例 2：
12>输入：nums = [4,5,6,7,0,1,2], target = 3>输出：-1
示例 3：
12>输入：nums = [1] ...
322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
123>输入：coins = [1, 2, 5], amount = 11>输出：3 >解释：11 = 5 + 5 + 1
示例 2：
12>输入：coins = [2], amount = 3>输出：-1
示例 3：
12>输入：coins = [1], amount = 0>输出：0
这道题目和完全平方数一样也是完全背包问题，唯一的区别就是考虑一下边界问题以及什么时候返回空值
由于我们只需要考虑最后一位，如果dp数组中最后一位无法通过物品凑得，那么它的值就不会改变（和初始值一样）这样只需要判断最后得到的是否为初始值即可知道能否成功兑换
代码：
123456789101112class Solution(object): def coinChange(self, c ...
