ITKeyword,专注技术干货聚合推荐

注册 | 登录

leetCode周赛81解题报告 JavaScript

xingbinice 分享于

2021腾讯云限时秒杀,爆款1核2G云服务器298元/3年!(领取2860元代金券),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1062

2021阿里云最低价产品入口+领取代金券(老用户3折起),
入口地址https://www.aliyun.com/minisite/goods

推荐:LeetCode解题报告-

题目: 3 个数和问题 Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0 Find all unique triplets in the array whi

比赛地址 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: 2Explanation: 2 people friend request each other. Example 2: Input: [16,17,18]Output: 2Explanation: 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 abilit

推荐:Leetcode Triangle 解题报告

Leetcode Triangle

http://oj.leetcode.com/problems/triangle/ 一道动态规划的经典题,POJ 1163 也是同一类型题,唯一区别在于Leetcode求最小值,POJ 1163求最

y 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;

var maxp = m[difficulty[0]];

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;};

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: 3Explanation: 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: 4Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 1. Example 3: Input: [[1, 1], [1, 1]]Output: 4Explanation: 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);};

推荐:LeetCode解题报告--

Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 原题出处:https://leetcode.com/problems/reverse-integer/

比赛地址 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 uppercas

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。