罗马数字转整数、Fizz Buzz和计数质数

罗马数字转整数

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

分别对应的数值为:1 ,5,10,50,100,500,1000 。

例如, 罗马数字 3 写做 III,即为三个并列的 1。12 写做 XII,即为 X+II。 26 写做 XXVII, 即为 XX+V+I。

通常情况下,不能出现超过连续三个相同的罗马数字并且罗马数字中小的数字在大的数字的右边。但也存在特例,例如 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 到 3999 的范围内。

示例

输入:"III"
输出:3
输入:"IV"
输出:4
输入:"LVIII"
输出:58
输入:"MCMXCIV"
输出:1994

方法一 遍历

思路

先遍历特殊值,如果有特殊值,先累加特殊值,然后用正则去掉特殊值,再遍历剩余的数字。

代码

const romanToIntOne = function (num) {
const roman = {
IV: 4,
IX: 9,
XL: 40,
XC: 90,
CD: 400,
CM: 900
};
const list = {
I: 1,
V: 5,
X: 10,
L: 50,
C: 100,
D: 500,
M: 1000
};
let result = 0;
// 先遍历特殊值
for (const key in roman) {
// 检测输入值是否含有特殊值
if (num.includes(key)) {
// 用正则去掉特殊值
const reg = new RegExp(key);
num = num.replace(reg, '');
result += roman[key];
}
}
for (const i of num) {
// 累加正常罗马数
result += list[i];
}
return result;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    上述解法中,每个数字都被遍历了一次,时间复杂度跟数字的个数 nn 线性相关,因此为 O(n)O(n)

  • 空间复杂度:O(1)O(1)

方法二 switch + includes 法

思路

先遍历所有罗马数字进行累加,对于特殊数字的循环,比如:5+1=6,而实际是 4,相差 2,所以需要在结果上减去 2,以此类推。

代码

const romanToIntTwo = function (num) {
let result = 0;
for (const c of num) {
switch (c) {
case 'I':
result += 1;
break;
case 'V':
result += 5;
break;
case 'X':
result += 10;
break;
case 'L':
result += 50;
break;
case 'C':
result += 100;
break;
case 'D':
result += 500;
break;
case 'M':
result += 1000;
break;
}
}
// 减去特殊组合
if (num.includes('IV') || num.includes('IX')) result -= 2;
if (num.includes('XL') || num.includes('XC')) result -= 20;
if (num.includes('CD') || num.includes('CM')) result -= 200;
return result;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

  • 空间复杂度:O(1)O(1)

Fizz Buzz

写一个程序,输出从 1 到 n 数字的字符串表示。

  1. 如果 n 是 3 的倍数,输出“Fizz”;

  2. 如果 n 是 5 的倍数,输出“Buzz”;

  3. 如果 n 同时是 3 和 5 的倍数,输出 “FizzBuzz”。

示例

n = 15,
返回:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]

方法一 遍历

思路

很简单,只需要判断 1 - n 的每个数字是否能被 3、5、15 整除,输出对应的字符串即可。

详解

  1. 第一步,申请一个数组 arr,用于存放每个数字转换后字符串。

  2. 第二步,循环遍历 1n1-n 的每个数字。如果该数字能被15整除(即取余为0),则该数字对应的字符串为 "FizzBuzz";如果能被3整除,则为 "Fizz";如果能被5整除,则为 "Buzz";否则,为该数字即可。

代码

/**
* @param {number} n
* @return {string[]}
*/
const fizzBuzz = (n) => {
const arr = [];
for (let i = 1; i <= n; i += 1) {
if (i % 15 === 0) { // 被15整除
arr.push('FizzBuzz');
} else if (i % 3 === 0) { // 被3整除
arr.push('Fizz');
} else if (i % 5 === 0) { // 被5整除
arr.push('Buzz');
} else {
arr.push(i.toString());
}
}
return arr;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    上述解法中,每个数字都被遍历了一次,时间复杂度跟数字的个数 nn 线性相关,因此为 O(n)O(n)

  • 空间复杂度:O(n)O(n)

    上述解法中,申请了大小为 nn 的数组空间,空间复杂度跟数字的个数 n 线性相关,因此为 O(n)O(n)

方法二:字符串累加

思路

这种方法也很简单,因为 15 的倍数输出 FizzBuzz,正好是 3 的倍数输出的 Fizz 拼接上 5 的倍数输出的 Buzz,所以只需要单独写 2 个 if 判断,将字符串拼接即可。

详解

  1. 第一步,申请一个数组 arr,用于存放每个数字转换后字符串。

  2. 第二步,循环遍历 1n1-n 的每个数字。定义一个空字符串 str,用于临时存放字符串拼接的结果。如果能被3整除,则 str 追加字符串 "Fizz";如果能被5整除,则 str 追加字符串 "Buzz";同时能被3和5整除的话,str 的值就为 "FizzBuzz" 了;否则,为该数字即可。

代码

/**
* @param {number} n
* @return {string[]}
*/
const fizzBuzz = (n) => {
const arr = [];
for (let i = 1; i <= n; i += 1) {
let str = '';
if (i % 3 === 0) {
str += 'Fizz';
}
if (i % 5 === 0) {
str += 'Buzz';
}
if (i % 3 !== 0 && i % 5 !== 0) {
str += i;
}
arr.push(str);
}
return arr;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    上述解法中,每个数字都被遍历了一次,时间复杂度跟数字的个数 nn 线性相关,因此为 O(n)O(n)

  • 空间复杂度:O(n)O(n)

    上述解法中,申请了大小为 nn 的数组空间,空间复杂度跟数字的个数 nn 线性相关,因此为 O(n)O(n)

计数质数

统计所有小于非负整数 n 的质数的数量。

示例

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

方法一 暴力法

思路

首先回顾质数的定义,质数是指在大于 1 的自然数中,除了 1 和它本身以外不再有其他因数的自然数。所以,我们可以根据定义直接从 2 开始直到 n 根据定义判断每一个数字是否为质数。

详解

  1. 首先我们定义一个方法 isPrime 用于判断一个自然数是否为质数,根据乘法交换律,判断其是否有因子的边界为 n 的平方根即可。

  2. 循环从 2 到 n 判断是否为质数,将数量存入 count 计数器中。

代码

function isPrime (n) {
// 判断是否为质数
if (n === 2 || n === 3) {
return true;
}
if (n % 6 !== 1 && n % 6 !== 5) {
return false;
}
const sqrtN = Math.sqrt(n); // 根据乘法交换律,判断边界为平方根即可
for (let i = 3; i <= sqrtN; i += 2) {
if (n % i === 0) {
return false;
}
}
return true;
}
function countPrimes (n) { // 返回质数数量
let count = 0;
for (let i = 2; i < n; i++) {
if (isPrime(i)) { // 循环判断
count++;
}
}
return count;
}

复杂度分析

  • 时间复杂度: O(nn)O(n*√n) 外层需要判断 nn 个数是否质数,判断为质数是需要进行 n√n 次计算

  • 空间复杂度:O(1)O(1) 使用了常数个变量,即为 O(1)O(1)

方法二 埃拉托斯特尼筛法

思路

给出要筛选数值的范围 n,找出 √𝑛 以内的素数 p1, p2..., p𝑘。先用 2 去筛,即把 2 留下,把 2 的倍数剔除掉;再用下一个素数,也就是 3 筛,把 3 留下,把 3 的倍数剔除掉;接下去用下一个素数 5 筛,把 5 留下,把 5 的倍数剔除掉;不断重复下去……不断的剔除不需要比对的元素;每计算一个数,都要把它的倍数去掉。到了n,数一下留下了几个数。

详解

1.Uint8Array 数组类型表示一个8位无符号整型数组,创建时内容被初始化为 0。创建完后,可以以对象的方式或使用数组下标索引的方式引用数组中的元素;

2.arr 用来记录“已经找过的数的倍数”。内层循环中,一次把找过数的倍数,对应的 arr 下标元素设置为 true,这样外循环时不会计数;

3.外层循环用来计数,如果 arr 数组对应值是 false,即表示为质数,则计数器 count 加一,最终获取所有质数数量。

代码

const countPrimes = function (n) {
let count = 0;
const arr = new Uint8Array(n);
for (let i = 2; i < n; i++) {
if (!arr[i - 1]) {
count++;
for (let j = i * i; j <= n; j += i) {
arr[j - 1] = true;
}
}
}
return count;
};

复杂度分析

  • 时间复杂度: O(nloglogn)O(nloglogn)

    对每一个ii,要划掉n/i n/i 个数, 要进行 n/in/i 次运算,全部加起来,就是 nn (从 1 到 √𝑛 之间的 1/i 之和)简单讲就是 (从 1 到 nn 之间的 1/i1/i 之和) 约等于 loglog (对所有 k 从 1 到 n 之间的 1/k 之和), 后者是logn log n, 所以前者就是 loglognloglog n;最外层需要判断 nn 次 ;所以最终时间复杂度为O(nloglogn)O(n loglog n)

  • 空间复杂度:O(n)O(n)

    上述解法中,申请了大小为 nn 的数组空间,空间复杂度跟数字的个数 nn 线性相关,因此为 O(n)O(n)