「每日LeetCode」2020年9月7日

本文最后更新于：2023年3月19日 晚上

Lt455.分发饼干、Lt575.分糖果、Lt628.三个数的最大乘积

455.分发饼干

Category Difficulty Likes Dislikes
algorithms Easy (55.51%) 196 -

Tags
greedy
Companies
Unknown
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值  g 这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 s。如果 s >= g，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
注意：
你可以假设胃口值为正。
一个小朋友最多只能拥有一块饼干。
示例  1:

1
2
3
4
5
6
输入: [1,2,3], [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例  2:

1
2
3
4
5
6
输入: [1,2], [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

Discussion | Solution

思路

贪心算法。将孩子和饼干排序，分别设置两个指针指向第一个。判断两个指针指向的饼干尺寸是否大于等于孩子的胃口，是的话，满足的孩子数量加一，如果小于这块饼干可以直接抛弃。直到两个指针其中一个遍历完数组结束循环，表示饼干没有了或孩子全部满足了。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
 * @lc app=leetcode.cn id=455 lang=javascript
 *
 * [455] 分发饼干
 */

// @lc code=start
/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function (g, s) {
  const childs = g.sort((a, b) => Number(a) - Number(b));
  const cookies = s.sort((a, b) => Number(a) - Number(b));
  let child = 0;
  let cookie = 0;
  while (child < childs.length && cookie < cookies.length) {
    if (childs[child] <= cookies[cookie]) {
      child++;
    }
    cookie++;
  }
  return child;
};
// @lc code=end

执行结果：
通过
显示详情
执行用时：120 ms, 在所有  JavaScript  提交中击败了 55.10%的用户
内存消耗：40.6 MB, 在所有  JavaScript  提交中击败了 11.47%的用户

575.分糖果

Category Difficulty Likes Dislikes
algorithms Easy (67.49%) 82 -

TagsCompanies
给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
示例 1:

1
2
3
4
输入: candies = [1,1,2,2,3,3]
输出: 3
解析: 一共有三种种类的糖果，每一种都有两个。
     最优分配方案：妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。

示例 2 :

1
2
3
输入: candies = [1,1,2,3]
输出: 2
解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1]，妹妹有两种不同的糖果，弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。

注意:

  1. 数组的长度为[2, 10,000]，并且确定为偶数。
  2. 数组中数字的大小在范围[-100,000, 100,000]内。

Discussion | Solution

思路

使用哈希表建立每个糖果及数量，按数量升序生成数组，遍历数组直到结果数组到达糖果总数的一半。每个糖果分类里取一个，就跳到下一个分类，如果没有下一个分类，就在当前分类取到上限。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
 * @lc app=leetcode.cn id=575 lang=javascript
 *
 * [575] 分糖果
 */

// @lc code=start
/**
 * @param {number[]} candies
 * @return {number}
 */
var distributeCandies = function (candies) {
  const map = new Map();
  let i = 0;
  for (const item of candies) {
    map.set(item, map.get(item) ? map.get(item) + 1 : 1);
  }
  const sortArr = [...map.entries()].sort((a, b) => a[1] - b[1]);
  const res = [];
  while (res.length < candies.length / 2) {
    res.push(sortArr[i][0]);
    if (sortArr[i + 1]) {
      i++;
    }
  }
  return [...new Set(res)].length;
};
// @lc code=end
1
2
3
4
Accepted
205/205 cases passed (248 ms)
Your runtime beats 24.65 % of javascript submissions
Your memory usage beats 10 % of javascript submissions (54.9 MB)

628.三个数的最大乘积

Category Difficulty Likes Dislikes
algorithms Easy (50.43%) 164 -

Tags
array | math
Companies
Unknown
给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1:

1
2
输入: [1,2,3]
输出: 6

示例 2:

1
2
输入: [1,2,3,4]
输出: 24

注意:

  1. 给定的整型数组长度范围是[3,10]，数组中所有的元素范围是[-1000, 1000]。
  2. 输入的数组中任意三个数的乘积不会超出 32 位有符号整数的范围。

Discussion | Solution

思路

将数组降序排序以后。若数组全为正数，则最大为前三个数的乘积。若数组存在负数，最大的乘积要么是前三个数的乘积，要么是两个最小的负数相乘再乘以最大的正数，即最后两个乘第一个

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * @lc app=leetcode.cn id=628 lang=javascript
 *
 * [628] 三个数的最大乘积
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumProduct = function (nums) {
  nums.sort((a, b) => Number(b) - Number(a));
  return Math.max(
    nums[0] * nums[1] * nums[2],
    nums[0] * nums[nums.length - 2] * nums[nums.length - 1]
  );
};
// @lc code=end
1
2
3
4
Accepted
83/83 cases passed (160 ms)
Your runtime beats 23.4 % of javascript submissions
Your memory usage beats 15.23 % of javascript submissions (42.6 MB)