关于算法:38外观数列-算法leetode附思维导图-全部解法300题

36次阅读

共计 1845 个字符,预计需要花费 5 分钟才能阅读完成。

零 题目:算法(leetode,附思维导图 + 全副解法)300 题之(38)外观数列

码农三少,一个致力于编写极简、但齐全题解(算法)的博主

一 题目形容



二 解法总览(思维导图)

三 全副解法

1 计划 1

1) 代码:

// 计划 1“相似斐波那切数列,应用 2 个变量”// 思路:// 1)状态初始化
// 2)循环解决 n-1 次,一直解决 pre、now 值
// 2.1)依据 pre 值,计算出 now 值
// 2.2)将 now 值 赋值给 pre 值,now 置为 '',接着进行下一次循环解决 ——> 依据 pre 值,计算出 now 值
// 3)返回后果 pre 值 
var countAndSay = function(n) {
    // 1)状态初始化
    let pre = '1',
        now = '';

    // 2)循环解决 n-1 次,一直解决 pre、now 值
    for (let i = 0; i < n - 1; i++) {
        // 2.1)依据 pre 值,计算出 now 值
        const preLength = pre.length;
        let count = 1;
        for (let j = 0; j < preLength; j++) {if (pre[j] === pre[j + 1]) {count++;}
            else {now += count + '' + pre[j];
                count = 1;
            }
        }

        // 2.2)将 now 值 赋值给 pre 值,now 置为 '',接着进行下一次循环解决 ——> 依据 pre 值,计算出 now 值
        pre = now;
        now = '';
    }

    // 3)返回后果 pre 值 
    return pre;
}

2 计划 2

1) 代码:

// 计划 2“递归 - 普通法”var countAndSay = function(n) {const dfs = (n) => {
        // 1)递归进口
        if (n === 1) {return '1';}

        // 2)递归主体
        return dfs(n-1).replace(/(\d)\1*/g, item =>`${item.length}${item[0]}`);
    };

    return dfs(n);
}

3 计划 3

1) 代码:

// 计划 3“递归 - 简洁法”var countAndSay = function(n) {if (n === 1) {return '1';}
    
    return countAndSay(n-1).replace(/(\d)\1*/g, item =>`${item.length}${item[0]}`);
}

4 计划 4

1) 代码:

// 计划 4“正则 + 循环法”// 思路:// 1)状态初始化
// 2)循环解决:一直联合正则匹配状况,应用 replace 函数对 resStr 进行更新
// 2.1)注(外围):'111221'.match(/(\d)\1*/g),输入 ['111', '22', '1'] 
// 这样看上面代码就容易很多了,item 顺次为 '111', '22', '1'。// 3)返回后果 resStr 
var countAndSay = function(n) {
    // 1)状态初始化
    let resStr = '1';

    // 2)循环解决:一直联合正则匹配状况,应用 replace 函数对 resStr 进行更新
    for (let i = 1; i < n; i++){// 2.1)注(外围):'111221'.match(/(\d)\1*/g),输入 ['111', '22', '1'] 
        // 这样看上面代码就容易很多了,item 顺次为 '111', '22', '1'。resStr = resStr.replace(/(\d)\1*/g, item =>`${item.length}${item[0]}`);
    }

    // 3)返回后果 resStr 
    return resStr;
};

5 计划 5

1) 代码:

// 计划 5“JS 装 X 法:正则 + 递归 --> 1 行代码”// 思路:// countAndSay(3) = countAndSay(2).replace(...)
//     = countAndSay(1).replace(...).replace(...)
//     = 1.replace(...).replace(...).replace(...)
var countAndSay = function(n) {
    // 注:了解如下正文,代码就很容易了
    // countAndSay(3) = countAndSay(2).replace(...)
        // = countAndSay(1).replace(...).replace(...)
        // = 1.replace(...).replace(...).replace(...)
    return n == 1 ? '1' : countAndSay(n-1).replace(/(\d)\1*/g, item =>`${item.length}${item[0]}`);
};

正文完
 0