LeetCode 第23场双周赛

一看最后一题就6分,感觉今天稳了🙃排名183 / 2037

第一题:统计最大组的数目

难度简单

题目描述

给你一个整数 n 。请你先求出从 1n 的每个整数 10 进制表示下的数位和(每一位上的数字相加),然后把数位和相等的数字放到同一个组中。

请你统计每个组中的数字数目,并返回数字数目并列最多的组有多少个。

示例 1:

示例 2:

示例 3:

示例 4:

提示:

  • 1 <= n <= 10^4

题目链接

https://leetcode-cn.com/problems/count-largest-group/

思路:

  ① 统计1~n每个数字的数位和并把相同的放在一起计次;
  ② 找出次数最多的;
  ③ 统计次数最多的出现了几次。   

代码:

第二题:构造 K 个回文字符串

难度中等

题目描述

给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串

如果你可以用 s 中所有字符构造 k 个回文字符串,那么请你返回 True ,否则返回 False

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

提示:

  • 1 <= s.length <= 10^5
  • s 中所有字符都是小写英文字母。
  • 1 <= k <= 10^5

题目链接

https://leetcode-cn.com/problems/construct-k-palindrome-strings/

思路:

  注意要用上所有字符
  ① 统计每个字母的出现次数;
  ② 出现奇数次的字母必须单独放在一个回文串中,因此最少的回文串数目 = 出现奇数次的字母个数
  ③ 最多的回文串数目 = s的字母数
  ④ 判断k是否在最少的回文串数目最多的回文串数目之间即可。

代码:

第三题:圆和矩形是否有重叠

难度中等

题目描述

给你一个以 (radius, x_center, y_center) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2),其中 (x1, y1) 是矩形左下角的坐标,(x2, y2) 是右上角的坐标。

如果圆和矩形有重叠的部分,请你返回 True ,否则返回 False 。

换句话说,请你检测是否 存在 点 (xi, yi) ,它既在圆上也在矩形上(两者都包括点落在边界上的情况)。

示例 1:

示例 2:

示例 3:

示例 4:

提示:

  • 1 <= radius <= 2000
  • -10^4 <= x_center, y_center, x1, y1, x2, y2 <= 10^4
  • x1 < x2
  • y1 < y2

题目链接

https://leetcode-cn.com/problems/circle-and-rectangle-overlapping/

思路:

  ① 检测矩形的四个顶点是否在圆中;
  ② 圆是否与矩形的四条边相交(圆是否与线段相交,通过判断圆心是否在以该线段为中心,圆的半径r为边长的矩形内);
  ③ 圆心是否在矩形内。
  如果①②③都不满足,则返回False

代码:

第四题:做菜顺序

难度困难

题目描述

一个厨师收集了他 n 道菜的满意程度 satisfaction ,这个厨师做出每道菜的时间都是 1 单位时间。

一道菜的 「喜爱时间」系数定义为烹饪这道菜以及之前每道菜所花费的时间乘以这道菜的满意程度,也就是 time[i]*satisfaction[i]

请你返回做完所有菜 「喜爱时间」总和的最大值为多少。

你可以按 任意 顺序安排做菜的顺序,你也可以选择放弃做某些菜来获得更大的总和。

示例 1:

示例 2:

示例 3:

示例 4:

提示:

  • n == satisfaction.length
  • 1 <= n <= 500
  • -10^3 <= satisfaction[i] <= 10^3

题目链接

https://leetcode-cn.com/problems/reducing-dishes/

思路:

  因为可以调换顺序,尽量后做满意度大的菜。
  遍历所有可能的做菜数(即0~n),满意度大的先做,满意度小的后做,计算总的喜爱时间,如果比之前的最大喜爱时间更大就更新最大喜爱时间

代码: