322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
**输入：coins = [1, 2, 5], amount = 11输出：**3
**解释：**11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3输出：-1
示例 3：
**输入：**coins = [1], amount = 0
**输出：**0
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 2(31) - 1
0 <= amount <= 10(4)
与完全平方数类似，我们需要依次减去对应的面额，来取最小值
注意范围的判断和不满足条件时-1的取值
12345678910111213141516171819class Solution {public: int coinChange(vector< ...
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]输出: [0]
提示:
1 <= nums.length <= 10(4)
-2(31) <= nums[i] <= 2(31) - 1
数组分为两部分，双指针分别维护两部分，左指针指向最后一个非零元素应该存放的位置，右指针不断查找非零元素，找到就放到左指针的位置，再更新左指针
因为是按顺序查找的非零元素所以相对顺序不变
123456789101112131415class Solution {public: void moveZeroes(vector<int> &nums) { int l = 0, r = 0; int s = nums.size(); while (r < s) &# ...
279. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
**输入：n = 12输出：**3
**解释：**12 = 4 + 4 + 4
示例 2：
**输入：n = 13输出：**2
**解释：**13 = 4 + 9
提示：
1 <= n <= 10(4)
dp[i]表示和为i时的答案
dp[n]的话就要不断减完全平方数，然后取最小的dp[ n-j*j ]
1234567891011121314class Solution {public: int numSquares(int n) { vector<int> dp(n + 1); for (int i = 1; i <= n; i++) { int mid = INT_MAX; for (int j = 1; j * j ...
240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1：
**输入：**matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
**输出：**true
示例 2：
**输入：**matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
**输出：**false
提示：
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10(9) <= matrix[i][j] <= 10(9)
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10(9) <= target < ...
239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
**输入：**nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
**输入：**nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 10(5)
-10(4) <= nums[i] <= 10(4)
1 <= k <= nums.length
只保留滑动窗口中的最大值，说明位于前面的还小的元素在后续一定是用不到的
...
238. 除了自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
提示：
2 <= nums.length <= 10(5)
-30 <= nums[i] <= 30
输入 保证 数组 answer[i] 在 32 位 整数范围内
**进阶：**你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
首先考虑两个数组分别记录前缀积和后缀积，最后把两数组相乘即可
因为ans不算额外空间，所以我们可以先把前缀积存在ans中
最后一个变量记录当前需要的后缀积即可
1234567891011 ...
