腾讯云前端一面面经

算法题

大数相加

代码

function addBigNum(str1, str2){
    let res = '',
        c = 0;
    const str1Arr = str1.split(''),
        str2Arr = str2.split('');
    while(str1Arr.length || str2Arr.length || c){
        const num1 = str1Arr.length ? str1Arr.pop() : 0,
              num2 = str2Arr.length ? str2Arr.pop() : 0;
        c += num1 + num2;
        res = (c % 10) + res;
        c = c > 9;
    }
    return res.replace(/^0+/,'');
}

最大子序和

给定一个数组，找到一个具有最大和的连续子数组，返回其最大和。示例如下
输入：

1,-2,4,5,-1,1

输出：

最大子数组：

[4,5]

代码

function largestSum(arr) {
    if (!arr) return null;
    const len = arr.length;
    if (!len) return Number.MIN_SAFE_INTEGER;
    let sum = arr[0];
    let res = sum;
    for (let i = 1; i < len; i++) {
        if (sum < 0) sum = arr[i];
        else sum = sum + arr[i];
        res = Math.max(res, sum);
    }
    return res;
}

console.log(largestSum([1,2,4,5,-1,1]));

子字符串匹配

给定两个字符串 s 和 t，其中 t 是 s 的子字符串。s的子字符串是字符都取自s，并且保持在s中的位置的相对顺序，但不需要是连续的。比如，s="abcdef"，t="bd"。

要求找出 t 在 s 中匹配的子字符串数量。

比如：

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
rabbbit rabbbit rabbbit

[输入]

"babgbag" "bag"

[输出]

[输入]

"rabbbit" "rabbit"

[输出]

[输入]

"xslledayhxhadmctrliaxqpokyezcfhzaskeykchkmhpyjipxtsuljkwkovmvelvwxzwieeuqnjozrfwmzsylcwvsthnxujvrkszqwtglewkycikdaiocglwzukwovsghkhyidevhbgffoqkpabthmqihcfxxzdejletqjoxmwftlxfcxgxgvpperwbqvhxgsbbkmphyomtbjzdjhcrcsggleiczpbfjcgtpycpmrjnckslrwduqlccqmgrdhxolfjafmsrfdghnatexyanldrdpxvvgujsztuffoymrfteholgonuaqndinadtumnuhkboyzaqguwqijwxxszngextfcozpetyownmyneehdwqmtpjloztswmzzdzqhuoxrblppqvyvsqhnhryvqsqogpnlqfulurexdtovqpqkfxxnqykgscxaskmksivoazlducanrqxynxlgvwonalpsyddqmaemcrrwvrjmjjnygyebwtqxehrclwsxzylbqexnxjcgspeynlbmetlkacnnbhmaizbadynajpibepbuacggxrqavfnwpcwxbzxfymhjcslghmajrirqzjqxpgtgisfjreqrqabssobbadmtmdknmakdigjqyqcruujlwmfoagrckdwyiglviyyrekjealvvigiesnvuumxgsveadrxlpwetioxibtdjblowblqvzpbrmhupyrdophjxvhgzclidzybajuxllacyhyphssvhcffxonysahvzhzbttyeeyiefhunbokiqrpqfcoxdxvefugapeevdoakxwzykmhbdytjbhigffkmbqmqxsoaiomgmmgwapzdosorcxxhejvgajyzdmzlcntqbapbpofdjtulstuzdrffafedufqwsknumcxbschdybosxkrabyfdejgyozwillcxpcaiehlelczioskqtptzaczobvyojdlyflilvwqgyrqmjaeepydrcchfyftjighntqzo... "rwmimatmhydhbujebqehjprrwfkoebcxxqfktayaaeheys"

[输出]

543744000

代码，注释部分未优化路径，

// function searchWord(s, t) {
//     const sLen = s.length, tLen = t.length;
//     const dp = new Array(sLen + 1);
//     for (let i = 0; i <= sLen; i++) {
//         dp[i] = new Array(tLen + 1).fill(0);
//     }
//     dp[0][0] = 1;
//     for (let i = 1; i <= sLen; i++) {
//         dp[i][0] = 1;
//         for (let j = 1; j <= tLen; j++) {
//             if (s[i - 1] === t[j - 1]) {
//                 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
//             } else {
//                 dp[i][j] = dp[i - 1][j];
//             }
//         }
//     }
//     return dp[sLen][tLen];
// }
function searchWord(s, t) {
    const sLen = s.length, tLen = t.length;
    const dp = new Array(tLen + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i <= sLen; i++) {
        let pre = 1;
        for (let j = 1; j <= tLen; j++) {
            let temp = dp[j];
            if (s[i - 1] === t[j - 1]) {
                dp[j] += pre;
            }
            pre = temp;
        }
    }
    return dp[tLen];
}
const s = "rabit", t = "rabbit";
console.log(searchWord(s, t));