阅读 406

前端工程师的 LeetCode 之旅 - 夜喵 23




01
统计最大组的数目



题目描述【Easy】


给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和(每一位上的数字相加),然后把数位和相等的数字放到同一个组中。
请你统计每个组中的数字数目,并返回数字数目并列最多的组有多少个。
示例:
输入:n = 13
输出:4
解释:总共有 9 个组,将 1 到 13 按数位求和后这些组分别是:[1,10],[2,11],[3,12],[4,13],[5],[6],[7],[8],[9]。总共有 4 个组拥有的数字并列最多。



第一步:利用 JavaScript 中的 Map 数据结构统计各个数位和的个数。

第二步:找出最大的数位和的个数。

第三步:找出拥有最大个数的数位和的个数。

时间复杂度 O(n),空间复杂度 O(n)。




02
构造 K 个回文字符串



题目描述【Medium】


给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串 。
如果你可以用 s 中所有字符构造 k 个回文字符串,那么请你返回 True ,否则返回 False 。
示例:
输入:s = 'annabelle', k = 2
输出:true
解释:可以用 s 中所有字符构造 2 个回文字符串。
一些可行的构造方案包括:'anna' + 'elble','anbna' + 'elle','anellena' + 'b'



一个字符串为回文字符串有以下两种状态:

  • 字符串长度为偶数时,需要保证各字符的数量为偶数

  • 字符串长度为奇数时,需要保证只有一个字符的数量为奇数

那么,同样需要用 Map 数据结构统计各个字符的个数。

得到各个字符的数量之后,该字符串能被分割几组回文子字符串取决于奇数字符的个数,同时最多不可能超过字符串本身的长度。(单个字符作为一个回文子字符串)

时间复杂度 O(n),空间复杂度 O(n)。




03
圆和矩形是否有重叠



题目描述【Medium】


给你一个以 (radius, x_center, y_center) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2),其中 (x1, y1) 是矩形左下角的坐标,(x2, y2) 是右上角的坐标。
如果圆和矩形有重叠的部分,请你返回 True ,否则返回 False 。
换句话说,请你检测是否 存在 点 (xi, yi) ,它既在圆上也在矩形上(两者都包括点落在边界上的情况)。
示例:
输入:radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
输出:true
解释:圆和矩形有公共点 (1,0)



本道题主要考察数学知识,圆与矩形相交有如下两种情况:

  • 圆在矩形四周相交

  • 圆在矩形四个弧相交

时间复杂度 O(1),空间复杂度 O(1)。




04
厨师做菜顺序的最大喜爱和



题目描述【Hard】


一个厨师收集了他 n 道菜的满意程度 satisfaction ,这个厨师做出每道菜的时间都是 1 单位时间。
一道菜的 「喜爱时间」系数定义为烹饪这道菜以及之前每道菜所花费的时间乘以这道菜的满意程度,也就是 time[i]*satisfaction[i] 。
请你返回做完所有菜 「喜爱时间」总和的最大值为多少。
你可以按 任意 顺序安排做菜的顺序,你也可以选择放弃做某些菜来获得更大的总和。
示例:
输入:satisfaction = [-1,-8,0,5,-9]
输出:14
解释:去掉第二道和最后一道菜,最大的喜爱时间系数和为 (-1*1 + 0*2 + 5*3 = 14) 。每道菜都需要花费 1 单位时间完成。



本道题比较简单,采用贪心策略,所以需要先排序,然后在统计的过程筛选最大和值即可。

时间复杂度 O(nlogn),空间复杂度 O(1)。




05
往期精彩回顾









关注下面的标签,发现更多相似文章
评论