拼多多笔试题目一

以下是拼多多前端笔试题中的编程题及答案：

1. 三数之和

题目：给定一个包含N个整数的数组A，找出所有不同的组合(i,j,k)，使得A[i]+A[j]+A[k]=0。
答案：

function threeSum(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum === 0) {
                result.push([nums[i], nums[left], nums[right]]);
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

解析：排序后使用双指针法，固定一个数，移动左右指针寻找另外两个数，通过去重避免重复解。

2. 字符串去重并排序

题目：找出字符串"AABBCAZDFEH"中重复的字符并按顺序输出。
答案：

function findDuplicates(str) {
    const charCount = {};
    for (const char of str) {
        charCount[char] = (charCount[char] || 0) + 1;
    }
    return Object.keys(charCount)
        .filter(char => charCount[char] > 1)
        .sort()
        .join('');
}

解析：统计字符频率后筛选出重复字符并排序。

3. 字符串全排列

题目：输入"abc"，输出所有排列组合：“abc,acb,bca,bac,cab,cba”。
答案：

function permute(str) {
    const result = [];
    const backtrack = (current, remaining) => {
        if (remaining.length === 0) {
            result.push(current);
            return;
        }
        for (let i = 0; i < remaining.length; i++) {
            const nextChar = remaining[i];
            const newRemaining = remaining.slice(0, i) + remaining.slice(i + 1);
            backtrack(current + nextChar, newRemaining);
        }
    };
    backtrack('', str);
    return result.join(',');
}

解析：使用回溯法生成所有排列组合。

4. 字符串替换

题目：替换字符串中的占位符，如str = "嘿, $1问我今天是星期$2么"，data = ['张三', '三']，输出"嘿, 张三问我今天是星期三么"。
答案：

function replacePlaceholders(str, data) {
    return str.replace(/\$(\d+)/g, (match, index) => data[index - 1] || match);
}

解析：使用正则表达式匹配$数字格式的占位符，并替换为对应数据。

5. 数组扁平化

题目：将嵌套数组展平为一维数组，如[1, [2, [3, 4]]]变为[1, 2, 3, 4]。
答案：

function flatten(arr) {
    return arr.reduce((acc, val) => 
        Array.isArray(val) ? acc.concat(flatten(val)) : acc.concat(val), []);
}

解析：使用递归和reduce方法处理嵌套数组。

6. 最长公共前缀

题目：找出多个路径的最长公共前缀，如输入['aa/bb/sd', 'aa/bb/wwewer', 'aa/bb/ddfff']，输出'aa/bb'。
答案：

function longestCommonPrefix(strs) {
    if (!strs.length) return '';
    let prefix = strs[0];
    for (const str of strs) {
        while (str.indexOf(prefix) !== 0) {
            prefix = prefix.slice(0, prefix.length - 1);
            if (!prefix) return '';
        }
    }
    return prefix;
}

解析：以第一个字符串为基准，逐步缩短前缀直到所有字符串匹配。

7. 任务调度（依赖排序）

题目：根据任务依赖关系安排执行顺序，确保每个任务的前置任务都先完成。
答案：

function taskScheduling(tasks, dependencies) {
    const inDegree = {};
    const adj = {};
    tasks.forEach(task => {
        inDegree[task] = 0;
        adj[task] = [];
    });
    dependencies.forEach(([pre, cur]) => {
        inDegree[cur] = (inDegree[cur] || 0) + 1;
        adj[pre].push(cur);
    });
    const queue = tasks.filter(task => inDegree[task] === 0);
    const result = [];
    while (queue.length) {
        const task = queue.shift();
        result.push(task);
        adj[task].forEach(neighbor => {
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        });
    }
    return result.length === tasks.length ? result : [];
}

解析：使用拓扑排序，通过入度数组和邻接表处理依赖关系。

8. 积木搭建（动态规划）

题目：用N个积木搭金字塔，每个积木高1，需满足上层积木边长更小且重量不超过下层的7倍。求最大高度。
答案：

function maxPyramidHeight(bricks) {
    bricks.sort((a, b) => a.length - b.length || a.weight - b.weight);
    const n = bricks.length;
    const dp = Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (bricks[j].weight * 7 >= bricks[i].weight) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Math.max(...dp);
}

解析：先按边长排序，再用动态规划计算以每个积木为顶的最大高度。