LeetCode 1193, 45, 48

目录

• 1193. 每月交易 I
• • 题目链接
  • 表
  • 要求
  • 知识点
  • 思路
  • 代码
• 45. 跳跃游戏 II
• • 题目链接
  • 标签
  • 思路
  • 代码
• 48. 旋转图像
• • 题目链接
  • 标签
  • 要求
  • 思路
  • 代码

1193. 每月交易 I

题目链接

1193. 每月交易 I

表

• 表Transactions的字段为id，country，state，amount和trans_date。

要求

• 编写一个 sql 查询来查找每个月和每个国家/地区的事务数及其总金额、已批准的事务数及其总金额。
• 以 任意顺序 返回结果表。

知识点

1. date_format()：将日期按照指定的格式返回。例如date_format('2020-01-12', '%Y-%m')表示将日2020-01-12按2020-01的格式返回。
2. group by：根据字段的值进行分组，后面可以跟多个字段。
3. conut()：统计个数的函数。要注意的一个点是count(0)的结果不一定是0，它与count(*)的结果相同。
4. sum()：求和的函数。
5. 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

题目链接

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. 旋转图像

题目链接

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;
            }
        }
    }
}