今日题目：罗马数字转整数、回文链表、赎金信、Fizz Buzz、链表的中间结点、矩阵中战斗力最弱的 K 行

20220319算法题

罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符         数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做
XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 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。

给定一个罗马数字，将其转换成整数。

示例 1:

输入:  s = "III"
输出: 3

示例 2:

输入:  s = "IV"
输出: 4

示例 3:

输入:  s = "IX"
输出: 9

示例 4:

输入:  s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:
输入: s = “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

1 <= s.length <= 15
s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考罗马数字 - Mathematics 。

思路： 先建立hashMap进行键值映射，然后再从左到右遍历字符串，如果当前字符的值小于右边且不为最后一个字符，则减去当前字符的值，否则加上当前字符的值

代码

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    let hashMap = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000 }
    let sum = 0
    for (let i = 0; i < s.length; i++) {
        if (i < s.length && hashMap[s[i]] < hashMap[s[i + 1]]) {
            sum -= hashMap[s[i]]
        } else {
            sum += hashMap[s[i]]
        }
    }
    return sum
};

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入： head = [1,2,2,1]
输出： true

示例 2：

输入： head = [1,2]
输出： false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路： 先将链表转化为数组，再通过对数组的双遍历判断是否符合回文数。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    let nHead = head
    let headArray = new Array();
    while(nHead != null) {
        headArray.push(nHead.val)
        nHead = nHead.next 
    }
    let i = 0, j = headArray.length-1
    while(i < j){
        if(headArray[i] != headArray[j])
            return false
        i++
        j--
    }
    return true
};

赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入： ransomNote = "a", magazine = "b"
输出： false

示例 2：

输入： ransomNote = "aa", magazine = "ab"
输出： false

示例 3：

输入： ransomNote = "aa", magazine = "aab"
输出： true

提示：

1 <= ransomNote.length, magazine.length <= 105
ransomNote 和 magazine 由小写英文字母组成

思路： 首先判断ransomNote的长度是否大于magazine的长度，如果大于直接返回false，否则，计算magazine中的所有的字母的数量，再通过与ransomNote比较每个字母的数量是否满足判断是否能够构成

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    if(ransomNote.length > magazine.length)
        return false
    const words = new Array(26).fill(0)
    for(let s of magazine) {
        words[s.charCodeAt() - 'a'.charCodeAt()]++
    }
    for(let s of ransomNote) {
        words[s.charCodeAt() - 'a'.charCodeAt()]--
        if(words[s.charCodeAt() - 'a'.charCodeAt()] < 0)
            return false
    }
    return true
};

Fizz Buzz

给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（ 下标从 1 开始
）返回结果，其中：

answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数。
answer[i] == "Fizz" 如果 i 是 3 的倍数。
answer[i] == "Buzz" 如果 i 是 5 的倍数。
answer[i] == i （以字符串形式）如果上述条件全不满足。

示例 1：

输入： n = 3
输出： ["1","2","Fizz"]

示例 2：

输入： n = 5
输出： ["1","2","Fizz","4","Buzz"]

示例 3：

输入： n = 15
输出： ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

提示：

1 <= n <= 104

思路： 简单的if-else if-else判断，直接循环即可得到答案

代码

/**
 * @param {number} n
 * @return {string[]}
 */
var fizzBuzz = function(n) {
    let res = []
    for(let i = 1; i <= n; i++) {
        let str = null
        if(i % 5 == 0 && i % 3 == 0) {
            str = "FizzBuzz"
        }else if(i % 3 == 0) {
            str = "Fizz"
        }else if(i % 5 == 0){
            str = "Buzz"
        }else {
            str = "" + i
        }
        res.push(str)
    }
    return res
};

链表的中间节点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入： [1,2,3,4,5]
输出： 此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入： [1,2,3,4,5,6]
输出： 此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。

思路： 先将链表转换为数组，再根据取数组的中间索引，再根据索引得到结果

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let nHead = head
    let middle = null
    const array = []
    let i = 0
    while(nHead != null) {
        array.push(nHead.val)
        nHead = nHead.next
    }
    if(array.length % 2 == 0){
        middle = array.length / 2
    }else {
        middle = Math.floor(array.length / 2)
    }
    nHead = head
    while(nHead) {
        if(i == middle)
            return nHead
        nHead = nHead.next
        i++
    }
};

矩阵中战斗力最弱的k行

给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。

请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。

如果第 _ i_ 行的军人数量少于第 _ j_ 行，或者两行军人数量相同但 _ i_ 小于 j ，那么我们认为第
_ i_ 行的战斗力比第 _ j_ 行弱。

军人总是排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。

示例 1：

输入： mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
输出： [2,0,3]
解释：
每行中的军人数目：
行 0 -> 2 
行 1 -> 4 
行 2 -> 1 
行 3 -> 2 
行 4 -> 5 
从最弱到最强对这些行排序后得到 [2,0,3,1,4]

示例 2：

输入： mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
输出： [0,2]
解释：
每行中的军人数目：
行 0 -> 1 
行 1 -> 4 
行 2 -> 1 
行 3 -> 1 
从最弱到最强对这些行排序后得到 [0,2,3,1]

提示：

m == mat.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[i][j] 不是 0 就是 1

思路： 用hashMap存储每一行的战斗力，再用hashMap的值对hashMap进行排序,得到的key就是答案

/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {number[]}
 */
var kWeakestRows = function(mat, k) {
    const array = {}
    const res = []
    for(let i in mat) {
        let sum = 0
        for(let j of mat[i]) {
            sum += j
        }
        array[i] = sum
    }
    keys = Object.keys(array).sort((a, b) => {
        return array[a] - array[b]
    })
    for(let i = 0; i<k; i++) {
        res.push(parseInt( keys[i]))
    }
    return res
};