程序员面试金典---23

整数英语的表示

思路：三位一写。

/**
 * @param {number} num
 * @return {string}
 */
var numberToWords = function(num) {
    const singles = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"];
    const teens = ["Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"];
    const tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"];
    const thousands = ["", "Thousand", "Million", "Billion"];

    // 判断
    const recursion = (cur, num) => {
        if(num === 0) return
        else if(num < 10){
            cur.push(singles[num] + " ")
        }else if(num < 20){
            cur.push(teens[num - 10] + " ")
        }else if(num < 100){
            cur.push(tens[Math.floor(num / 10)] + " ")
            recursion(cur, num % 10)
        }else{
            cur.push(singles[Math.floor(num / 100)] + " Hundred ")
            recursion(cur, num % 100)
        }
    }

    if(num === 0){
        return "Zero"
    }

    const sb = []

    for(let i = 3, unit = 1000000000; i >= 0; i--, unit = Math.floor(unit / 1000)){
        const curNum = Math.floor(num / unit)
        if(curNum !== 0){
            num -= curNum * unit
            const cur = []
            recursion(cur,curNum)
            cur.push(thousands[i] + " ") 
            sb.push(cur.join(''))
        }
    }
    return sb.join('').trim()
};

生存人数

思路：差分数组

/**
 * @param {number[]} birth
 * @param {number[]} death
 * @return {number}
 */
var maxAliveYear = function(birth, death) {
    let len = birth.length
    let a = new Array(2003).fill(0)
    // 左加一右减一
    for(let i = 0; i < len; i++){
        let x = birth[i], y = death[i]
        a[x] += 1
        a[y + 1] -= 1
    }
    // 前缀和求解
    let max = 0
    let idx = 0
    let sum = 0
    for(let i = 1900; i <= 2000; i++){
        sum += a[i]
        if(max < sum){
            max = sum
            idx = i
        }
    }
    return idx
};