1733. Minimum Number of People to Teach

Leetcode link

题目简介

题目给了我们三个参数：

• n：代表有多少种语言
• languages：是一个二维数组，代表每一种语言有多少个人会
• friendships：也是一个二维数组，在同一个数组元素内的人表示是朋友

题目要求我们选择一种语言去教人，使得所有朋友都能够互相使用相同语言沟通

要求我们得出最少教多少个人就能够符合要求

解题思路

这道题需要分成三个步骤来解：

1. 先通过遍历所有的朋友，找出有多少人是需要被教新的语言的（只要朋友双方没有共同语言就需要将两个人都列入需要教学的范围）
2. 在所有需要教学的人中，找出他们共同会最多的语言
3. 用所有需要教学的人，减去会最多语言的人数，就是需要教学的最少人数了

Javascript

/**
 * @param {number} n
 * @param {number[][]} languages
 * @param {number[][]} friendships
 * @return {number}
 */
var minimumTeachings = function (n, languages, friendships) {
      // 计算需要被教学的人
    const userToTeach = new Set()
    for (const [u1, u2] of friendships) {
        const hasCommonLang = languages[u1 - 1].some(lang => languages[u2 - 1].includes(lang))
        if (!hasCommonLang) {
            userToTeach.add(u1)
            userToTeach.add(u2)
        }
    }

      // 计算最多人会的语言与其会的人数
    const langCount = new Array(n+1).fill(0)
    let mostKnownLangCount = 0

    for(const user of userToTeach) {
        for(const lang of languages[user - 1]) {
            langCount[lang]++
            mostKnownLangCount = Math.max(langCount[lang], mostKnownLangCount)
        }
    }

        // 所有需要被教学的人，减去最多人会的语言的人数
    return userToTeach.size - mostKnownLangCount
}