手记

碰到几道挺有意思的题目,一起看看吧

第一题:斐波那契数列。

  题目描述:斐波那契数列。即:1、1、2、3、5、8、13、21…求第N个数,输入正整数,如输入是8,输出是21,并打印该完整数列。
  这时候第一联想就是递归。

// the first solution
//  简单版递归
const Fibonacci_0 = index => {

    if (index <= 2) return 1;
    return Fibonacci_0(index - 1) + Fibonacci_0(index - 2);
}
console.log(Fibonacci_0(8));

  第二种方式是通过指针偏移的方式,来不断的将前面两个值相加。

//  the second solution
//  指针偏移
const Fibonacci = index => {

    if (index <= 0 || index !== Math.floor(index)) { throw "请输入正整数"; }
    
    if (index <= 2) {

        return index === 1 ? { res: 1, sequence: [1] } : { res: 1, sequence: [1, 1] }
    }

    let res = 0, i = 1, j = 1, p = 2, sequence = [1, 1];

    while( ++ p <= index) {
        res = i + j;
        sequence.push(res);
        i = j;
        j = res;
    }
    return { res: res, sequence: sequence };
}

第二题 质因数

  题目描述,输出某个范围内的素数。
  素数,是除了1与它本身以外,再也找不到任何一个数能将其整除。比如2、3、5、7……而4则除了1跟其本身4之外,还有2可以将其整除。

const getPrimeNumber_20190514 = (min, max) => {

    let res = [];

    for ( let i = min; i <= max; i ++ ) {
        
        for ( var k = 2; k <= Math.floor(i / 2); k ++ ) {
            
            if ( i % k === 0 ) break;
        }
        k === ( Math.floor(i / 2) + 1 ) && res.push( i );
    }
    return res;
}
console.log(getPrimeNumber_20190514(1, 20));

第三题 约瑟夫环问题

  题目描述:编号为1到100的一百个人围成一圈,以12341234的方式进行报数,数到4的人自动退出圈子,剩下的人围成新的圈子并由退出去的那个人下一位同学作为新起点并继续报数,问最后剩下的人编号为几?
  如果是1000个人,或者10000个人呢?
  比如说[1, 2, 3, 4, 5]五个伙伴在玩这个游戏,并设置数到2的人出局。接下来的情况会是:
  第一轮:[1, 3, 5],2与4号出局
  第二轮:[3],由于第一轮5的报数为1,接下来1号报到数就为2,同样最终到5号报的数也是2。1号和5号相继出局。

  最终的赢家是3号。

  看看代码实现:

const JosephRing = (totalNumbers, key) => {

    //  生成编号
    let nums = Array.from({ length: totalNumbers }, (item, index) => index + 1),
        
    //  初始指针
        k = key;
    
    while (nums.length > 1) {
            
        k > nums.length ? k %= nums.length : null;

        k === 0 ? key < nums.length ? k = 1 : k = nums.length : null;

        nums = [...nums.slice(0, k - 1), ...(nums.slice(k, nums.length))];

        console.log(nums);

        k += key - 1;
    }
}
console.log(JosephRing(10, 4));

  这里其实主要就是要不断的调整新的起点,同时需要兼顾队伍是一个圆圈,也就是到末尾之后又会接着从开头继续报数。
  最终可以看到每出局一位同学剩余的其他人重新组合而成的数组。

  当然为了使展示的结果更加直观,这里采用的是数组重组的方式,每出局一位,则整个数组需要重新切片并又重新concat回来,非常浪费性能。
  下图是测试了100000人的圆环报数为4时出局的chrome进程资源消耗,注意这是将代码中console.log(nums);注释掉的前提下。

第四题 随机生成指定长度字符串

  题目描述:随机生成指定长度字符串。如输入8,则随意输出abc12dfe,字符范围限制在字母与数字。

//  the first solution
const createFixLengthString_0 = len => {

    let res = '';
    while ( len -- ) {

        res += Math.floor(Math.random() * 36).toString(36);
    } 
    return res;
}
console.log(createFixLengthString_0(8));

  第一种方式有缺陷,因为所产生的字符串不包括大写字母,此时可以通过一种变通的方式,来完成。比如通过JavaScript的toUpperCase(),其实最终的转码你会发现几乎就是一个base64,当然你也可以称之为base62。

//  the second solution
const createFixLengthString = len => {

    let res = '', random;

    while (len--) {
        random = Math.floor(Math.random() * 62);
        res += random >= 36 ? (random - 26).toString(36).toUpperCase() : random.toString(36);
    }
    return res;
}
console.log(createFixLengthString(8));

第五题 阶乘

  题目描述:计算一个正整数的阶乘,比如输入:4,则输出:1 * 2 * 3 * 4 = 24。

const factorial = num => {
    
    let res = 1;
    while ( num ) {
        res *= num --;
    }
    return res;
}
console.log(factorial(4))
1人推荐
随时随地看视频
慕课网APP