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
...
300. 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
123>输入：nums = [10,9,2,5,3,7,101,18]>输出：4>解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
12>输入：nums = [0,1,0,3,2,3]>输出：4
示例 3：
12>输入：nums = [7,7,7,7,7,7,7]>输出：1
使用单调栈和二分查找结合解体
单调栈用来维护一个严格递增的序列，二分查找用于快速定位第一个破坏当前序列递增顶的序列，并且找到后替换以维持栈的单调性
这里主要用到的策略：
nums[i] > stack[-1]：栈顶元素比当前元素小，直接放在栈的顶部，是不是不破坏单调栈的单调递增特性
nums[i] <= stack[-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 ...
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] ...
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 ...
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
12>输入：nums = [5,7,7,8,8,10], target = 8>输出：[3,4]
示例 2：
12>输入：nums = [5,7,7,8,8,10], target = 6>输出：[-1,-1]
示例 3：
12>输入：nums = [], target = 0>输出：[-1,-1]
基本思路也很简单，主要就是通过两次查询分别找到首尾的位置
1234567891011121314151617181920212223242526272829303132333435class Solution(object): def searchRange(self, nums, target): if no ...
394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
12>输入：s = "3[a]2[bc]">输出："aaabcbc"
示例 2：
12>输入：s = "3[a2[c]]">输出："accaccacc"
示例 3：
12>输入：s = "2[abc]3[cd]ef">输出："abcabccdcdcdef"
示例 4：
12>输入：s = "abc3[cd]xyz">输出："abccdcdcdxyz& ...
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
12>输入: nums = [1,3,5,6], target = 5>输出: 2
示例 2:
12>输入: nums = [1,3,5,6], target = 2>输出: 1
示例 3:
12>输入: nums = [1,3,5,6], target = 7>输出: 4
最简单的二分法：
1234567891011class Solution(object): def searchInsert(self, nums, target): left , right = 0, len(nums) - 1 while (left <= right): mid = (left + right) / 2 if (nums[mid] < target): ...
45. 跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
1234>输入: nums = [2,3,1,1,4]>输出: 2>解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
12>输入: nums = [2,3,0,1,4]>输出: 2
把该问题比喻为入职，数组下标是公司级别(入职门槛)，对应的值是公司级别之上的级别成长空间。你想用最少的跳槽次数入职最高级的公司
数组[2,3,1,2,4,2,3]
下标 0 1 2 3 4 5 6
最开始你没有工作，你的水 ...
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
123>输入：nums1 = [1,3], nums2 = [2]>输出：2.00000>解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
123>输入：nums1 = [1,2], nums2 = [3,4]>输出：2.50000>解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
困难题
目前还做不明白，只会先合并之后再取出中位数：
123456789101112131415161718192021222324252627class Solution(object): def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[in ...
