1193. 每月交易 I
题目链接
表
- 表
Transactions的字段为id，country，state，amount和trans_date。
要求
- 编写一个 sql 查询来查找每个月和每个国家/地区的事务数及其总金额、已批准的事务数及其总金额。
- 以 任意顺序 返回结果表。
知识点
date_format()：将日期按照指定的格式返回。例如date_format('2020-01-12', '%Y-%m')表示将日2020-01-12按2020-01的格式返回。group by：根据字段的值进行分组，后面可以跟多个字段。conut()：统计个数的函数。要注意的一个点是count(0)的结果不一定是0，它与count(*)的结果相同。sum()：求和的函数。if：根据条件返回不同的值。要注意的一个点是判断两个值是否相等的表达式只需要写一个等号，例如num = 3表示判断num是否等于3。
思路
题目要求找到每个月、每个国家/地区的数据，所以要按照月份month和国家的名字country进行分组，然后统计事务数、对金额进行求和、统计批准的(state = 'approved')事务数、对批准的事务的金额进行求和。
代码
select
date_format(trans_date, '%Y-%m') month,
country,
count(*) trans_count,
count(if(state = 'approved', 1, null)) approved_count, # 注意：null 不能写成0
sum(amount) trans_total_amount,
sum(if(state = 'approved', amount, 0)) approved_total_amount
from
Transactions
group by
month,
country
45. 跳跃游戏 II
题目链接
标签
贪心 数组 动态规划
思路
本题可以使用贪心的思想，要想跳的次数最小，就每步都尽可能跳得远一点，但这道题没有这么简单，要求深刻理解无法贪心的情况——局部最优解的总和不是全局最优解。
但是每步都跳得最远不一定就会得到最小跳跃次数，例如对于这个数组nums = [3, 4, 1, 1, 1, 1]，如果按照每步都跳得最远，那么第一步就是从下标为0的位置跳到下标为3的位置，然后再跳2次就到终点了，共跳了3次。显然对于这样的数组有更优解——第一步从下标为0的位置跳到下标为1的位置，第二步从下标为1的位置跳到下标为5的位置，共跳了2次。这就是贪心的错误用法，要使用贪心就得每次选择都是局部最优解，然后合起来才是全剧最优解。不过可以通过改变贪心的策略，从而得到全局最优解。
先思考为什么不能每次都选择局部最优解，答案是太着急了，考虑得不周全，比如说没有考虑到跳1个下标的情况。所以我们需要使用两个变量来记录能够跳跃的最远下标farAble和上一个能够跳跃的最远下标farEd，遍历整个数组(实际上不需要遍历最后一个值，因为如果已经跳到最后一个值的位置了，就已经满足条件了)，每次都需要更新能够跳跃的最远值farAble，然后只有在 当前下标 = 上一个能够跳跃的最远下标farEd 时，才将 上一个能够跳跃的最远下标farEd 更新为 能够跳跃的最远下标farAble，并且让跳跃步数加一，直到跳跃到最后一个下标。
解释一下为什么 跳跃的最小步数steps 恰好等于 上一个能够跳跃的最远下标farEd 的改变次数：因为每次改变farEd都意味着找到了这个局部和下一个局部联合的最优解，也就是说够冷静了，该跳了。这样以此类推，找到的就是全局的最优解。
代码
class Solution {
public int jump(int[] nums) {
int farEd = 0; // 上一个能够跳跃的最远下标
int farAble = 0; // 能够跳跃的最远下标，不一定从上一个能够跳跃的最远下标
int steps = 0; // 跳跃所需的最少步数
for (int i = 0; i < nums.length - 1; i++) {
farAble = Math.max(farAble, i + nums[i]); // 更新能够跳跃的最远下标
if (i == farEd) { // 如果下标遍历到上一个能够跳跃的最远下标，则更新它，并且让步数加一
farEd = farAble;
steps++;
}
}
return steps;
}
}
48. 旋转图像
题目链接
标签
数组 数学 矩阵
要求
- 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请 不要 使用另一个矩阵来旋转图像。
思路
这道题属于是做过就会，没做过很难想，所以建议不想看证明就把这种解法记住。
对于将一个矩阵顺时针旋转90度，可以使用先主对角线反转再水平翻转的方法。至于证明，可以去看看力扣的官方题解，建议从方法一开始看，看到方法三，然后就能理解题解中的公式了。
代码
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// 主对角线翻转
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int t = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = t;
}
}
// 水平翻转
for (int i = 0; i < n; i++) {
for (int j = 0; j < n >> 1; j++) {
int t = matrix[i][j];
matrix[i][j] = matrix[i][n - j - 1];
matrix[i][n - j - 1] = t;
}
}
}
}
