leetCode周赛82解题报告 JavaScript

比赛地址
https://leetcode.com/contest/weekly-contest-82

 

824. Goat Latin

A sentence S is given, composed of words separated by spaces. Each word consists of lowercase and uppercase letters only.

We would like to convert the sentence to "Goat Latin" (a made-up language similar to Pig Latin.)

The rules of Goat Latin are as follows:

• If a word begins with a vowel (a, e, i, o, or u), append "ma" to the end of the word.
  For example, the word 'apple' becomes 'applema'.
   
• If a word begins with a consonant (i.e. not a vowel), remove the first letter and append it to the end, then add "ma".
  For example, the word "goat" becomes "oatgma".
   
• Add one letter 'a' to the end of each word per its word index in the sentence, starting with 1.
  For example, the first word gets "a" added to the end, the second word gets "aa" added to the end and so on.

Return the final sentence representing the conversion from S to Goat Latin. 

 

Example 1:

Input: "I speak Goat Latin"
Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

Example 2:

Input: "The quick brown fox jumped over the lazy dog"
Output: "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

 

Notes:

• S contains only uppercase, lowercase and spaces. Exactly one space between each word.
• 1 <= S.length <= 100.

 

单词首字母若是辅音放至最后，首字母原音保持不变，然后每个单词后添加ma、maa、maaa... 

简单难度没什么可说

 

/**
 * @param {string} S
 * @return {string}
 */
var toGoatLatin = function(S) {
    var s = S.split(" ");
    var cur = "ma";
    var vo = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
    var ans = [];
    for (var i = 0; i < s.length; i++) {
        if (s[i]) {
            cur += "a";
            if (vo.has(s[i][0])) {
                ans.push(s[i] + cur);
            }
            else {
                ans.push(s[i].substring(1) + s[i][0] + cur);
            }
        }
    }
    return ans.join(" ");
};

 

 

 

 

 

825. Friends Of Appropriate Ages

Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person. 

Person A will NOT friend request person B (B != A) if any of the following conditions are true:

• age[B] <= 0.5 * age[A] + 7
• age[B] > age[A]
• age[B] > 100 && age[A] < 100

Otherwise, A will friend request B.

Note that if A requests B, B does not necessarily request A.  Also, people will not friend request themselves.

How many total friend requests are made?

Example 1:

Input: [16,16]
Output: 2
Explanation: 2 people friend request each other.

Example 2:

Input: [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Example 3:

Input: [20,30,100,110,120]
Output: 
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

 

Notes:

• 1 <= ages.length <= 20000.
• 1 <= ages[i] <= 120.

 

题意是找出所有满足条件的数对的数量，第三个条件其实可以无视。

由于题目限定了年龄范围是1～120，可以以年龄计数的方式完成计算。

题目标注难度是中等，但给人感觉简单。

 

/**
 * @param {number[]} ages
 * @return {number}
 */
var numFriendRequests = function(ages) {
    var counts = new Array(121).fill(0);
    for (var i = 0; i < ages.length; i++) {
        counts[ages[i]]++; // 统计所有年龄的人数
    }
    var ans = 0;
    for (var i = 0; i < ages.length; i++) {
        for (var j = Math.floor(ages[i] * 0.5 + 7) + 1; j <= ages[i]; j++) {
            if (counts[j] > 0) {
                ans += counts[j];
                if (j == ages[i]) { // 若是自己年龄也满足，则减1
                    ans--;
                }
            }
        }
    }
    return ans;
};

 

 

 

 

 

826. Most Profit Assigning Work

We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job. 

Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i]. 

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if 3 people attempt the same job that pays $1, then the total profit will be $3.  If a worker cannot complete any job, his profit is $0.

What is the most profit we can make?

Example 1:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100 
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get profit of [20,20,30,30] seperately.

Notes:

• 1 <= difficulty.length = profit.length <= 10000
• 1 <= worker.length <= 10000
• difficulty[i], profit[i], worker[i]  are in range [1, 10^5]

 

题意是每种工作有着特定的难度和利润，给出每个工人最高能完成的工作的难度，求出所有人的最高利润。

中等难度，但是坑比较多，躺了几回：

1.difficulty和profit数组可能是乱序的，所以需要排序；

2.可能存在两个难度一样、但是利润不一样的工作；

3.由于数据量是10000，所以时间复杂度o(n^2)的算法会超时；

/**
 * @param {number[]} difficulty
 * @param {number[]} profit
 * @param {number[]} worker
 * @return {number}
 */
var maxProfitAssignment = function(difficulty, profit, worker) {
    // 工作难度和利润的映射
    var m = {};
    for (var i = 0; i < difficulty.length; i++) {
        m[difficulty[i]] = m[difficulty[i]] ? Math.max(m[difficulty[i]], profit[i]) : profit[i]; // 可能存在两个难度一样、但是利润不一样的工作
    }
    difficulty.sort((a,b)=>a-b);
    // 工作难度排序之后去掉那些难度高但是利润低的工作
    var newlen = 1;
    for (var i = 1; i < difficulty.length; i++) {
        if (m[difficulty[newlen - 1]] < m[difficulty[i]]) {
            difficulty[newlen++] = difficulty[i];
        }
    }
    difficulty.length = newlen; // 截断数组
    var ans = 0;
    // 由于o(n^2)的算法会超时，需要对worker的难度排序，并以lastj记录最后一次选择的难度，达到提速效果
    worker.sort((a,b)=>a-b);
    var lastj = 0;
    for (var i = 0; i < worker.length; i++) {
        var maxp = 0;
        for (var j = lastj; j < difficulty.length && difficulty[j] <= worker[i]; j++) {
            if (maxp < m[difficulty[j]]) {
                maxp = m[difficulty[j]];
                lastj = j;
            }
        }
        ans += maxp;
    }
    return ans;
};

 看了官方题解的代码，比较简短精炼一些，思路相仿，如下：

/**
 * @param {number[]} difficulty
 * @param {number[]} profit
 * @param {number[]} worker
 * @return {number}
 */
var maxProfitAssignment = function(difficulty, profit, worker) {
    var jobs = difficulty.map((v,i)=>[v, profit[i]]).sort((a,b)=>a[0]-b[0]);
    worker.sort((a,b)=>a-b);
    var ans = 0;
    var maxp = 0; // 由于worker和jobs都是排序过的，能力高的人不会比前面的人利润低，一个变量记录即可
    for (var i = 0, j = 0; i < worker.length; i++) { // j的初始化在外层，内循环不变
        while (j < jobs.length && worker[i] >= jobs[j][0]) {
            maxp = Math.max(maxp, jobs[j++][1]);
        }
        ans += maxp;
    }
    return ans;
};

 

 

 

 

827. Making A Large Island

In a 2D grid of 0s and 1s, we change at most one 0 to a 1.

After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

Example 1:

Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 1.

Example 3:

Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 1.

 

Notes:

• 1 <= grid.length = grid[0].length <= 50.
• 0 <= grid[i][j] <= 1.

 

题意是提供一张01地图，1代表陆地，你可以将任意一个0的位置填充为1，求出你填充之后的最大陆地面积。

难度困难，用深度搜索dfs实现。

/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestIsland = function(grid) {
    var n = grid.length;
    var count = 0;
    var flag = 1;
    var dfs = function(i, j) {
        if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] == 0 || grid[i][j] == flag) {
            return;
        }
        grid[i][j] = flag;
        count++;
        // 每个点往四个方向拓展
        dfs(i, j + 1);
        dfs(i + 1, j);
        dfs(i, j - 1);
        dfs(i - 1, j);
    }
    var ans = 0;
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            if (grid[i][j] === 0) { //找到0的位置
                flag++; // 每次计算将陆地填充为flag
                grid[i][j] = 1; // 暂时填充为1
                // 计算以(i,j)位置拓展的陆地面积有多大，全局count为计算结果
                count = 0;
                dfs(i, j); 
                ans = Math.max(ans, count);
                grid[i][j] = 0; // 还原为0
            }
        }
    }
    // 若ans=0表示整个地图都是1，不需要填充
    return ans > 0 ? ans : (n * n);
};

 分析上面解法，遍历所有0所需时间是n^2，为每个0拓展陆地的时间是n^2，所以整体方案的时间复杂度是o(n^4)，其实可以事先计算好每块陆地的面积（时间为n^2），然后可以以常量时间计算每个0四周陆地的面积，将嵌套的循环改为两个步骤进行计算，从而将时间复杂度优化至o(n^2)，优化后的代码如下：

/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestIsland = function(grid) {
    var n = grid.length;
    var count = 0;
    var flag = 1;
    var xs = [0,0,1,-1];
    var ys = [1,-1,0,0];
    var dfs = function(i, j) {
        if (i < 0 || i >= n || grid[i][j] !== 1) {
            return;
        }
        grid[i][j] = flag;
        count++;
        // 每个点往四个方向拓展
        for (var d = 0; d < 4; d++) {
            dfs(i + xs[d], j + ys[d]);
        }
    }
    var areas = [0, 0]; // 所有的地块的面积;
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                // 将新陆地填充为flag
                flag++; 
                count = 0;
                dfs(i, j); 
                areas[flag] = count; // 记录flag地块对应的陆地面积
            }
        }
    }
    var ans = 0;
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            if (grid[i][j] === 0) { //找到0的位置
                var adjacents = [];
                for (var d = 0; d < 4; d++) {
                    if (i + xs[d] >= 0 && i + xs[d] < n) {
                        var f = grid[i + xs[d]][j + ys[d]];
                        if (f && adjacents.indexOf(f) == -1) {
                            adjacents.push(f); // 找出这个0四个方向相邻的陆地
                        }
                    }
                }
                // 0四周相邻陆地之和
                var cur = adjacents.reduce((pre, f)=>pre+areas[f], 1);
                ans = Math.max(ans, cur);
            }
        }
    }
    // 若ans=0表示整个地图都是1，不需要填充
    return ans > 0 ? ans : (n * n);
};