跳到主要内容

数字题库

题一、求平方根​

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。正数的平方根有两个，只输出其中的正数平方根。如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

示例1:

输入: x = 4
输出: 2

方案A、二分查找​

思路: 由于 x 平方根的整数部分 ans 是满足 k2 ≤ x 的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。

实现:

function mySqrt(x){
    let left = 0;
    let right = x;
    let result = -1;
    while(left <= right){
        let middle = (left + right) >> 1;
        if(middle * middle <= x){
            result = middle;
            left = middle + 1;
        }else{
            right = middle - 1;
        } 
    }
    return result;
}

题二、回文数​

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

  • 例如, 121 是回文，而 123 不是。

示例1:

输入：x = 121
输出：true

示例2:

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

方案A、反转一半数字​

思路:

  • 反转后半部分的数字: 整个过程我们不断将原始数字除以 10，然后给反转后的数字乘上 10,所以，当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了

  • 临界情况:

    • 所有负数都不可能是回文，例如: -123 不是回文，因为 - 不等于 3。所以我们可以对所有负数返回 false。

    • 除了 0 以外，所有个位是 0 的数字不可能是回文，因为最高位不等于 0

实现

function isPalindrome(x){
    if(x<0 || (x % 10 === 0 && x !== 0)){
        return false;
    }
    let revertedNumber = 0;
    while (x > revertedNumber) {
        revertedNumber = revertedNumber * 10 + x % 10;
        x = (x / 10) >> 0;
    }
    return x === revertedNumber || x === (revertedNumber / 10) >> 0;
}

题三、罗马数字转整数​

罗马数字包含以下七种字符: 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

方案A、模拟​

思路:

  • 罗马数字中小的数字在大的数字的右边: 那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可

  • 罗马数字中存在小的数字在大的数字的左边的情况: 根据规则需要减去小的数字

实现

function romanToInt(s){
    const map = new Map([
        ["I",1],
        ["V",5],
        ["X",10],
        ["L",50],
        ["C",100],
        ["D",500],
        ["M",1000]
    ]);
    let result = 0;
    const {length} = s;
    for(let i=0;i<length;i++){
        const value = map.get(s[i]);
        if(i<length-1 && value < map.get(s[i+1])){
            result -= value;
        }else{
            result += value;
        }
    }
    return result;
}