拼多多学霸批算法工程师笔试题经验

1. a数组中除了一个数之外严格升序, 在b数组中找一个最大的数替换a数组中违反升序的数

思路: 违反升序的数可能有两个, 如1, 3, 8, 7, 10中替换掉8或者7都可以, 两种情况都遍历一下即可

def exchange(nums1, nums2):
    poses = []
    for i in range(len(nums1)):
        if not(i == 0 or nums1[i] > nums1[i-1]) or \
           not(i == len(nums1)-1 or nums1[i] < nums1[i+1]):
            left = None if i == 0 else nums1[i-1]
            right = None if i == len(nums1)-1 else nums1[i+1]
            poses.append((i, left, right))

    res = None
    max_num = None
    for pos, left, right in poses:
        for n in nums2:
            if (left is None or n > left) and (right is None or n < right) and (max_num is None or n > max_num):            
                res = nums1.copy()
                res[pos] = n
                max_num = n

    return res

2. 判断单词能否首尾相接成环

用的回溯去做的, 只过了0.95. 看别人的解法好像是判断首尾字母的出现次数即可.

import sys

def is_used(used, i):
    return (1 & (used >> i)) != 0

def set_used(used, i):
    mask = 0b1 << i
    used = used | mask
    return used

def cancel_used(used, i):
    mask = 0b1 << i
    mask = ~mask
    used = used & mask
    return used

def backtrack(words, used, curr, length, memo):    
    if length == len(words):
        memo[(curr, used)] = curr[0] == curr[-1]
        return memo[(curr, used)]

    if (curr, used) in memo:
        return memo[(curr, used)]

    res = False
    for i in range(len(words)):
        if is_used(used, i) is True:
            continue

        if len(curr) == 0 or words[i][0] == curr[-1]:
            used = set_used(used, i)
            temp_curr = curr[0] + words[i][-1] if len(curr) != 0 else words[i]
            res = backtrack(words, used, temp_curr, length+1, memo)
            used = cancel_used(used, i)
            if res is True:
                break

    memo[(curr, used)] = res
    return res

line = sys.stdin.readline().strip()
words = line.split(' ')

used = 0
memo = {}

res = backtrack(words, used, '', 0, memo)
if res is True:
    print('true')
else:
    print('false')

3. 任务排序, 存在依赖关系, 求平均耗时最小的执行顺序.

思路: 使用小顶堆存储当前可以执行的任务, 每次出堆后更新依赖次数, 依赖次数为0的任务加入到堆中.

#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <climits>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
using namespace std;

struct Task {
    int index, time;
    Task(): index(0), time(0) {}
};

bool comp(const Task &a, const Task &b) {
    return a.time != b.time ? a.time > b.time : a.index > b.index;
}

int main() {
    ifstream fin("input.txt");
    cin.rdbuf(fin.rdbuf());


    int N, M, a, b, t;
    cin >> N >> M;
    vector<vector<bool>> G(N, vector<bool>(N, false));
    vector<int> depend(N, 0);
    vector<Task> tasks(N);

    for(int i = 0; i < N; i++) {
        cin >> t;
        tasks[i].index = i+1;
        tasks[i].time = t;
    }

    for(int i = 0; i < M; i++) {
        cin >> a >> b;
        G[b-1][a-1] = true;
        depend[b-1]++;
    }

    vector<int> res;
    vector<Task> heap;
    vector<bool> visited(N, false);
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(!visited[j] && depend[j] == 0) {
                visited[j] = true;
                heap.push_back(tasks[j]);
                push_heap(heap.begin(), heap.end(), comp);
            }
        }

        auto t = heap.front();
        pop_heap(heap.begin(), heap.end(), comp);
        heap.pop_back();
        res.push_back(t.index);

        for(int j = 0; j < N; j++)
            if(!visited[j] && G[j][t.index - 1]) {
                depend[j]--;
            }
    }

    cout << res[0];
    for(int i = 1; i < N; i++)
        cout << " " << res[i];

    return 0;
}

4. 堆积木, 上面的积木长度必须小于下面的积木. 上面积木的总重不能超过底层积木重量的7倍.

思路: 用dp[i][h]记录以第i块积木为底, 高为h的积木塔的最低重量.

#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <climits>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
using namespace std;

struct Node{
    int l, w;
    Node(): l(0), w(0) {}
};

bool comp(const Node &a, const Node &b) {
    return a.l != b.l ? a.l < b.l : a.w < b.w;
}

int main() {
    ifstream fin("input.txt");
    cin.rdbuf(fin.rdbuf());


    int N, w, l;
    cin >> N;
    vector<Node> nodes(N);
    for(int i = 0; i < N; i++) {
        cin >> l;
        nodes[i].l = l;
    }
    for(int i = 0; i < N; i++) {
        cin >> w;
        nodes[i].w = w;
    }

    sort(nodes.begin(), nodes.end(), comp);


    int res = 1;
    vector<vector<int>> dp(N, vector<int>(N+1, -1));
    dp[0][1] = nodes[0].w;

    for(int i = 1; i < N; i++) {
        dp[i][1] = nodes[i].w;
        for(int h = 2; h <= N; h++) {
            for(int j = i-1; j >= 0; j--) {
                if(dp[j][h-1] != -1 && nodes[i].w * 7 >= dp[j][h-1] && (dp[i][h] == -1 or nodes[i].w + dp[j][h-1] < dp[i][h])) {
                    res = max(res, h);
                    dp[i][h] = nodes[i].w + dp[j][h-1];
                }
            }
        }
    }

    cout << res << endl;

    return 0;
}