文章/答案/技术大牛

发布

社区首页 >专栏 >2023-09-10：用go语言编写。作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 p

2023-09-10：用go语言编写。作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 p

福大大架构师每日一题

发布于 2023-09-19 07:40:33

19900

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2023-09-10：用go语言编写。作为项目经理，你规划了一份需求的技能清单 req_skills，

并打算从备选人员名单 people 中选出些人组成一个「必要团队」

（编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。

所谓「必要团队」，就是在这个团队中，

对于所需求的技能列表 req_skills 中列出的每项技能，

团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：

例如，团队 team = [0, 1, 3] 表示掌握技能分别为

people[0]，people[1]，和 people[3] 的备选人员。

请你返回任一规模最小的必要团队，团队成员用人员编号表示。

你可以按任意顺序返回答案，题目数据保证答案存在。

输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]。

输出：[0,2]。

来自左程云。

答案2023-09-10：

大体步骤如下：

1.首先，我们对 reqSkills 进行排序，获得排序后的技能列表。这是为了后续方便进行比较。例如，将 ["java", "nodejs", "reactjs"] 排序为 ["java", "nodejs", "reactjs"]。

2.初始化变量 n 为 reqSkills 的长度，变量 m 为 people 的长度，并创建一个长度为 m 的整数数组 statuses 用于记录每个人的技能状态。

3.对于每个人，我们通过比较技能列表和排序后的 reqSkills 列表，来确定他们掌握的技能状态。首先，将该人的技能列表排序。然后使用双指针法，一个指针指向排序后的 reqSkills 列表，另一个指针指向该人的技能列表。比较两个指针指向的技能，如果相等，则表示该人掌握了该技能，将对应的状态位置为1，并将两个指针都向后移动一位；如果 reqSkills[p1] 小于 skill[p2]，则将指向 reqSkills 的指针向后移动一位；否则将指向技能列表的指针向后移动一位。重复这个过程直到其中一个指针超出范围。

4.将每个人的技能状态记录在 statuses 数组中。

5.创建一个二维数组 dp，其中 dp[i][j] 表示从第 i 个人开始，技能状态为 j 时，所需的最小团队人数。初始化 dp 数组的所有元素为 -1。

6.调用递归函数 process，该函数的参数包括：people 数组，技能列表的长度 n，当前处理的人员下标 i，当前的技能状态 status，以及 dp 数组。

7.在递归函数 process 中，首先判断当前技能状态是否已经满足所有需求，即 status 是否等于 (1<<n)-1。如果满足，则返回0表示不需要再增加人员。

8.接下来，判断是否已经遍历了所有人员，即 i 是否等于 people 数组的长度。如果是，说明无法满足所有需求，并返回一个较大的值，这里使用 1<<31-1 来表示无穷大。

9.然后，判断 dp 数组中是否已经记录了当前人员和技能状态的最小团队人数，如果是，直接返回该值。

10.在递归函数中，我们有两个递归调用，第一个是继续尝试从下一个人员开始不增加人员的情况，即调用 process(people, n, i+1, status, dp)，将返回的值保存在变量 p1 中。

11.第二个递归调用是尝试从下一个人员开始增加当前人员的情况，即调用 process(people, n, i+1, status|people[i], dp)，将返回的值保存在变量 p2 中。注意，这里的参数 status|people[i] 表示将当前人员的技能状态添加到当前技能状态中。

12.如果 p2 不等于 1<<31-1，说明可以满足当前需求，将 p2+1 指代的团队人数保存在变量 ans 中，否则将 ans 设置为 p1。

13.将 ans 保存在 dp 数组中以便下次使用，并返回 ans。

14.在主函数中，根据返回的最小团队人数 size，创建一个大小为 size 的整数数组 ans 和一个指示 ans 数组下标的变量 ansi。

15.初始化变量 i 为0，status 为0，用于记录当前处理的人员下标和技能状态。

16.如果 status 不等于 (1<<n)-1，即还没有满足所有需求，执行循环。在循环中，判断两个条件：如果 i+1 等于 m，说明已经遍历到了最后一个人员；如果 dp[i][status] 不等于 dp[i+1][status]，表示从当前人员开始增加人员可以满足当前需求。

17.如果满足上述两个条件之一，将 i 添加到 ans 数组中，并将 ansi 自增1。然后将当前人员的技能状态添加到当前技能状态中。

18.无论是否满足条件，将 i 自增1。

19.执行完循环后，返回 ans 数组作为结果。

总的时间复杂度为O(m * (2^n))，额外空间复杂度为O(m * (2^n))。

go完整代码如下：

package main

import (
    "fmt"
    "sort"
)

func smallestSufficientTeam(reqSkills []string, people [][]string) []int {
    sort.Strings(reqSkills)
    n := len(reqSkills)
    m := len(people)
    statuses := make([]int, m)
    for i := 0; i < m; i++ {
        skillStatus := 0
        skill := people[i]
        sort.Strings(skill)
        p1, p2 := 0, 0
        for p1 < n && p2 < len(skill) {
            compare := reqSkills[p1] == skill[p2]
            if compare {
                skillStatus |= 1 << p1
                p1++
                p2++
            } else if reqSkills[p1] < skill[p2] {
                p1++
            } else {
                p2++
            }
        }
        statuses[i] = skillStatus
    }

    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, 1<<n)
        for j := 0; j < 1<<n; j++ {
            dp[i][j] = -1
        }
    }

    size := process(statuses, n, 0, 0, dp)
    ans := make([]int, size)
    ansi := 0
    i := 0
    status := 0
    for status != (1<<n)-1 {
        if i+1 == m || dp[i][status] != dp[i+1][status] {
            ans[ansi] = i
            ansi++
            status |= statuses[i]
        }
        i++
    }
    return ans
}

func process(people []int, n, i, status int, dp [][]int) int {
    if status == (1<<n)-1 {
        return 0
    }
    if i == len(people) {
        return 1<<31 - 1
    }
    if dp[i][status] != -1 {
        return dp[i][status]
    }
    p1 := process(people, n, i+1, status, dp)
    p2 := 1<<31 - 1
    next2 := process(people, n, i+1, status|people[i], dp)
    if next2 != 1<<31-1 {
        p2 = 1 + next2
    }
    ans := min(p1, p2)
    dp[i][status] = ans
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    reqSkills := []string{"java", "nodejs", "reactjs"}
    people := [][]string{{"java"}, {"nodejs"}, {"nodejs", "reactjs"}}

    result := smallestSufficientTeam(reqSkills, people)
    fmt.Println(result)
}

在这里插入图片描述

rust完整代码如下：

fn smallest_sufficient_team(req_skills: Vec<String>, people: Vec<Vec<String>>) -> Vec<i32> {
    let n = req_skills.len();
    let m = people.len();
    let mut statuses = vec![0; m];
    for (i, skill) in people.iter().enumerate() {
        let mut skill_status = 0;
        let mut sorted_skill = skill.clone();
        sorted_skill.sort();
        let mut p1 = 0;
        let mut p2 = 0;
        while p1 < n && p2 < sorted_skill.len() {
            match req_skills[p1].cmp(&sorted_skill[p2]) {
                std::cmp::Ordering::Less => p1 += 1,
                std::cmp::Ordering::Greater => p2 += 1,
                std::cmp::Ordering::Equal => {
                    skill_status |= 1 << p1;
                    p1 += 1;
                    p2 += 1;
                }
            }
        }
        statuses[i] = skill_status;
    }

    let mut dp = vec![vec![-1; 1 << n]; m];
    let size = process(&statuses, n, 0, 0, &mut dp);
    let mut ans = vec![0; size as usize];
    let mut ansi = 0;
    let mut i = 0;
    let mut status: i32 = 0;

    while status != (1 << n) - 1 {
        if i + 1 == m || dp[i][status as usize] != dp[i + 1][status as usize] {
            ans[ansi] = i as i32;
            ansi += 1;
            status |= statuses[i as usize];
        }
        i += 1;
    }

    ans
}

fn process(people: &[i32], n: usize, i: usize, status: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
    if status == (1 << n) - 1 {
        return 0;
    }

    if i == people.len() {
        return i32::MAX;
    }

    if dp[i][status as usize] != -1 {
        return dp[i][status as usize];
    }

    let p1 = process(people, n, i + 1, status, dp);
    let mut p2 = i32::MAX;
    let next2 = process(people, n, i + 1, status | people[i], dp);
    if next2 != i32::MAX {
        p2 = 1 + next2;
    }

    let ans = p1.min(p2);
    dp[i][status as usize] = ans;
    ans
}

fn main() {
    let req_skills = vec![
        "java".to_string(),
        "nodejs".to_string(),
        "reactjs".to_string(),
    ];
    let people = vec![
        vec!["java".to_string()],
        vec!["nodejs".to_string()],
        vec!["nodejs".to_string(), "reactjs".to_string()],
    ];
    let result = smallest_sufficient_team(req_skills, people);
    println!("{:?}", result);
}

在这里插入图片描述

c++完整代码如下：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cmath>

using namespace std;

int process(const vector<int>& people, int n, int i, int status, unordered_map<int, int>& dp) {
    if (status == (1 << n) - 1) {
        return 0;
    }
    if (i == people.size()) {
        return INT_MAX;
    }
    int key = (i << n) | status;
    if (dp.find(key) != dp.end()) {
        return dp[key];
    }
    int p1 = process(people, n, i + 1, status, dp);
    int p2 = INT_MAX;
    int next2 = process(people, n, i + 1, status | people[i], dp);
    if (next2 != INT_MAX) {
        p2 = 1 + next2;
    }
    int ans = min(p1, p2);
    dp[key] = ans;
    return ans;
}

vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
    unordered_map<string, int> skillMap;
    int count = 0;
    for (const string& skill : req_skills) {
        skillMap[skill] = count++;
    }
    int n = count;
    int m = people.size();
    vector<int> statuses(m);
    for (int i = 0; i < m; i++) {
        int skillStatus = 0;
        const vector<string>& skills = people[i];
        for (const string& skill : skills) {
            skillStatus |= 1 << skillMap[skill];
        }
        statuses[i] = skillStatus;
    }
    unordered_map<int, int> dp;
    int size = process(statuses, n, 0, 0, dp);
    vector<int> ans;
    int i = 0, status = 0;
    while (status != (1 << n) - 1) {
        if (i + 1 == m || dp[i << n | status] != dp[(i + 1) << n | status]) {
            ans.push_back(i);
            status |= statuses[i];
        }
        i++;
    }
    return ans;
}

int main() {
    vector<string> req_skills = { "java", "nodejs", "reactjs" };
    vector<vector<string>> people = { {"java"}, {"nodejs"}, {"nodejs", "reactjs"} };

    vector<int> team = smallestSufficientTeam(req_skills, people);
    cout << "Team members: ";
    for (int member : team) {
        cout << member << " ";
    }
    cout << endl;

    return 0;
}

在这里插入图片描述

c完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* data;
    int size;
    int capacity;
} IntArray;

IntArray* createIntArray() {
    IntArray* arr = (IntArray*)malloc(sizeof(IntArray));
    arr->data = NULL;
    arr->size = 0;
    arr->capacity = 0;
    return arr;
}

void append(IntArray* arr, int value) {
    if (arr->size >= arr->capacity) {
        int newCapacity = arr->capacity == 0 ? 1 : arr->capacity * 2;
        int* newData = (int*)malloc(sizeof(int) * newCapacity);
        if (arr->data != NULL) {
            memcpy(newData, arr->data, sizeof(int) * arr->size);
            free(arr->data);
        }
        arr->data = newData;
        arr->capacity = newCapacity;
    }
    arr->data[arr->size++] = value;
}

void destroyIntArray(IntArray* arr) {
    if (arr != NULL) {
        if (arr->data != NULL) {
            free(arr->data);
        }
        free(arr);
    }
}

int findSkillIndex(char** skills, int skillsSize, char* target) {
    for (int i = 0; i < skillsSize; i++) {
        if (strcmp(skills[i], target) == 0) {
            return i;
        }
    }
    return -1;
}

void smallestSufficientTeam(char** req_skills, int req_skillsSize, char*** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnArray) {
    char** skills = (char**)malloc(sizeof(char*) * req_skillsSize);
    for (int i = 0; i < req_skillsSize; i++) {
        skills[i] = _strdup(req_skills[i]);
    }

    int n = req_skillsSize;
    int m = peopleSize;
    int* statuses = (int*)malloc(sizeof(int) * m);

    for (int i = 0; i < m; i++) {
        int skillStatus = 0;
        for (int j = 0; j < peopleColSize[i]; j++) {
            int skillIndex = findSkillIndex(skills, req_skillsSize, people[i][j]);
            if (skillIndex != -1) {
                skillStatus |= 1 << skillIndex;
            }
        }
        statuses[i] = skillStatus;
    }

    int** dp = (int**)malloc(sizeof(int*) * m);
    for (int i = 0; i < m; i++) {
        dp[i] = (int*)malloc(sizeof(int) * (1 << n));
        for (int j = 0; j < (1 << n); j++) {
            dp[i][j] = -1;
        }
    }

    int size = process(statuses, n, 0, 0, dp);

    *returnSize = size;
    *returnArray = (int*)malloc(sizeof(int) * size);
    int index = 0;
    int i = 0;
    int status = 0;

    while (status != (1 << n) - 1) {
        if (i + 1 == m || dp[i][status] != dp[i + 1][status]) {
            (*returnArray)[index++] = i;
            status |= statuses[i];
        }
        i++;
    }

    for (int i = 0; i < m; i++) {
        free(dp[i]);
    }
    free(dp);

    for (int i = 0; i < req_skillsSize; i++) {
        free(skills[i]);
    }
    free(skills);
    free(statuses);
}

int process(int* people, int n, int i, int status, int** dp) {
    if (status == (1 << n) - 1) {
        return 0;
    }
    if (i == n) {
        return INT_MAX;
    }
    if (dp[i][status] != -1) {
        return dp[i][status];
    }

    int p1 = process(people, n, i + 1, status, dp);

    int p2 = INT_MAX;
    int next2 = process(people, n, i + 1, status | people[i], dp);
    if (next2 != INT_MAX) {
        p2 = 1 + next2;
    }

    int ans = p1 < p2 ? p1 : p2;
    dp[i][status] = ans;
    return ans;
}

int main() {
    char* req_skills[] = { "java", "nodejs", "reactjs" };
    int req_skillsSize = sizeof(req_skills) / sizeof(req_skills[0]);

    char** people[] = {
        (char* []) {
"java"
},
  (char* []) {
"nodejs"
},
(char* []) {
"nodejs", "reactjs"
}
    };
    int peopleSize = sizeof(people) / sizeof(people[0]);
    int peopleColSize[] = { 1, 1, 2 };

    int returnSize;
    int* returnArray;

    smallestSufficientTeam(req_skills, req_skillsSize, people, peopleSize, peopleColSize, &returnSize, &returnArray);

    printf("Smallest Sufficient Team:\n");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", returnArray[i]);
    }
    printf("\n");

    free(returnArray);

    return 0;
}