LeetCode 596, 13, 2

596. 超过5名学生的课
- 题目链接
- 表
- 要求
- 知识点
- 思路
- 代码
13. 罗马数字转整数
- 题目链接
- 标签
- 罗马数字与阿拉伯数字
- - 映射
  - 规则
- 思路
- 代码
2. 两数相加
- 题目链接
- 标签
- 思路
- 代码
- - 使用被赋值为结果链表头部的指针
  - 哨兵节点指向结果链表头部

596. 超过5名学生的课

题目链接

596. 超过5名学生的课

表

表Courses的字段为student和class。

要求

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

知识点

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

思路

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

代码

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

13. 罗马数字转整数

题目链接

13. 罗马数字转整数

罗马数字与阿拉伯数字

映射

罗马数字	阿拉伯数字
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

规则

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

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

思路

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

例如，对于 $M C M X C I V$ ，从第一位开始看，第一位是 $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;
    }
}

秒客网

LeetCode 596, 13, 2

目录

596. 超过5名学生的课

题目链接

表

要求

知识点

思路

代码

13. 罗马数字转整数

题目链接

标签

罗马数字与阿拉伯数字

映射

规则

思路

代码

2. 两数相加

题目链接

标签

思路

代码

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

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

相关文章