LeetCode 596, 13, 2

596. 超过5名学生的课

题目链接

596. 超过5名学生的课

表

• 表Courses的字段为student和class。

要求

• 查询 至少有5个学生 的所有班级。
• 以 任意顺序 返回结果表。

知识点

1. count()：统计个数的函数。
2. group by：按照某些字段进行分组。
3. 子查询：将查询的结果作为表进行查询。

思路

对班级的要求为至少有5个学生，那么就先查询每个班级的学生数，然后再返回学生数大于等于5的班级。

代码

select
    class
from
    (
        select
            count(*) num,
            class
        from
            Courses
        group by
            class
    ) c
where
    num >= 5

13. 罗马数字转整数

题目链接

13. 罗马数字转整数

标签

哈希表 数学 字符串

罗马数字与阿拉伯数字

映射

规则

罗马数字中 小的数字在大的数字的右边 。但也存在特例，例如 4 不写做 $IIII$，而是 $IV$。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 $IX$。这个特殊的规则只适用于以下六种情况：

• $I$ 可以放在 $V$ (5) 和 $X$ (10) 的左边，来表示 4 和 9。
• $X$ 可以放在 $L$ (50) 和 $C$ (100) 的左边，来表示 40 和 90。
• $C$ 可以放在 $D$ (500) 和 $M$ (1000) 的左边，来表示 400 和 900。

思路

可以这样理解罗马数字：当小的数字放在左边时，表示给大的数减去这个小的数(即$IV$表示4)；当小的数字放在右边，或两个数一样大时，表示加上这个小的数(即$VI$表示6，$III$表示3)。

例如，对于$MCMXCIV$，从第一位开始看，第一位是$M(1000)$，$M(1000)$比$C(100)$大，所以给结果res加上1000。看第二位$C(100)$，$C(100)$比$M(1000)$小，所以给结果res减去100。看第三位$M(1000)$，$M(1000)$比$X(10)$大，所以给结果res加上1000。看第四位$X(10)$，$X(10)$比$C(100)$小，所以给结果res减去10。看第五位$C(100)$，$C(100)$比$I(1)$大，所以给结果res加上100。看第六位$I(1)$，$I(1)$比$V(5)$小，所以给结果res减去1。看第七位$V(5)$，由于它是最后一位，所以直接给结果res加上5。

代码

class Solution {
    private static final Map<Character, Integer> mapper = new HashMap<>(); // 罗马数字对阿拉伯数字的映射
    static { // 使用静态代码块初始化映射数组
        mapper.put('I', 1);
        mapper.put('V', 5);
        mapper.put('X', 10);
        mapper.put('L', 50);
        mapper.put('C', 100);
        mapper.put('D', 500);
        mapper.put('M', 1000);
    }
    public int romanToInt(String s) {
        int res = 0;
        char[] roman = s.toCharArray();
        int n = roman.length;
        for (int i = 0; i < n; i++) {
            int value = mapper.get(roman[i]);
            if (i < n - 1 && value < mapper.get(roman[i + 1])) { // 左边的数字小
                res -= value;
            } else { // 左边的数字不小 或 是最后一个数字
                res += value;
            }
        }
        return res;
    }
}

2. 两数相加

题目链接

2. 两数相加

标签

递归 链表 数学

思路

熟悉 加法 是解决本题的关键，也是解决 高精度 问题的关键。

加法：

• 从最低位（也就是个位）开始计算，如果两数之和大于等于10，则将大于10的部分（即对10取余）留在当前位，并且给更高位加1；否则就将两数之和留在当前位。
• 如果有一个数的某一位没有值，则给它这位补0。直到两个数都在某一位上没有值。例如100 + 1可以理解为100 + 001。
• 两个数加起来的位数可能比较大值的位数还大，所以遍历完两个数后应该再看一下它们最高位的和是否大于10，如果大于10，则再添一位，这位的数字是1（因为0～9之间的两个数之和如果大于10，则一定是10～18之间的数）。例如90 + 20 = 110，其中90是二位数，而110是三位数。

本题还是使用了 哨兵节点指向结果链表头部 的处理方式，没有直接使用一个指针head被赋值为结果链表头部，这样可以省去对head是否为空的判断。

代码

使用被赋值为结果链表头部的指针

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, curr = null;
        boolean biggerThan10 = false;
        while (l1 != null || l2 != null) { // 直到两个链表都为空
            int v1 = (l1 == null ? 0 : l1.val); // 如果这一位没有值，就补0
            int v2 = (l2 == null ? 0 : l2.val); // 如果这一位没有值，就补0
            int sum = v1 + v2 + (biggerThan10 ? 1 : 0); // 这位的求和与上一位有关，如果上一位的和比10大，得再加1
            biggerThan10 = (sum >= 10);
            
            // 更新当前节点
            if (head == null) {
                head = curr = new ListNode(sum % 10); // 这位留下来的值必定比10小
            } else {
                curr.next = new ListNode(sum % 10); // 这位留下来的值必定比10小
                curr = curr.next;
            }
            
            if (l1 != null) {
                l1 = l1.next; // 如果l1不是空，则更新它
            }
            if (l2 != null) {
                l2 = l2.next; // 如果l2不是空，则更新它
            }
        }

        // 如果最高位的和大于10，则再添一位
        if (biggerThan10) {
            curr.next = new ListNode(1);
        }
        return head;
    }
}

哨兵节点指向结果链表头部

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode sentinal = new ListNode(-1); // 哨兵节点指向结果，返回哨兵节点的next
        ListNode curr = sentinal;
        boolean biggerThan10 = false;
        while (l1 != null || l2 != null) { // 直到两个链表都为空
            int v1 = (l1 == null ? 0 : l1.val); // 如果这一位没有值，就补0
            int v2 = (l2 == null ? 0 : l2.val); // 如果这一位没有值，就补0
            int sum = v1 + v2 + (biggerThan10 ? 1 : 0); // 这位的求和与上一位有关，如果上一位的和比10大，得再加1
            biggerThan10 = (sum >= 10); // 判断这位的和是否大于10
            curr.next = new ListNode(sum % 10); // 这位留下来的值必定比10小

            curr = curr.next; // 更新当前节点
            if (l1 != null) {
                l1 = l1.next; // 如果l1不是空，则更新它
            }
            if (l2 != null) {
                l2 = l2.next; // 如果l2不是空，则更新它
            }
        }

        // 如果最高位的和大于10，则再添一位
        if (biggerThan10) {
            curr.next = new ListNode(1);
        }
        return sentinal.next;
    }
}