Leetcode 第 166 场比赛回顾

零、背景

这次比赛比较简单。

一、整数的各位积和之差

题意:给一个整数 n,求这个整数「各位数字之积」与「各位数字之和」的差。

思路:按照题意模拟计算即可。

二、用户分组

题意:有 n 个用户,每个用户属于一个分组。

告诉你每个用户所属分组的分组总人数,求对用户进行划分,满足分组的个数要求。

例如:输入时 [3,3,3,3,3,1,3] ,我们可以划分为 [[5],[0,1,2],[3,4,6]]

第5个人所属分组大小为1,只能自己一个组,剩下人三个人一组即可。

思路:贪心。

各种尺寸大小的分组分别维护一个容器,循环加入用户。

当一个分组满了的时候,就得到一个分组。

三、最小除数

题意:给一个数组和一个目标 threshold, 问是否存在一个整数 x,使得数组里面所有数字向上整除 x的结果之和小于目标 threshold 。

如果存在,求最小的除数 x。

例如:数组为 [1,2,5,9] ,目标为 6

如果除数取 x=1 ,结果和是 17=1+2+5+9 ,不满足要求。

如果除数取 x=4 ,结果和是 7=1+1+2+3 ,依旧不满足要求。

而对于 x=5 ,结果和是 5=1+1+1+2 ,满足要求。

思路:分析题意,可以发现最优答案之前的数组都不满足,最后的都满足。

所以可以二分答案,然后判断是否满足,找到最小的即可。

四、使矩阵反转全部为0

题意:给一个 0/1 矩阵,翻转一个位置时,上下左右的位置都需要反转。

问是否可以通过一系列反转,使得矩阵全为0。

如果存在,求最小反转次数。

思路:最优值问题,典型的 BFS 问题。

搜索的过程中,涉及到反转以及恢复反转。

我们可以通过异或运算符来做到完美反转。

反转矩阵的过程中,中间形成的矩阵可能会多次遇到,我们需要保存下遇到过得矩阵防止重复搜索。

由于矩阵比较小(最多9个值),可以使用矩阵位压缩的方法来记录即可。

之后,就可以进行 BFS 搜索了。

五、最后

这次题比较简单,都是基础题,不多说了。

-EOF-

本文公众号:天空的代码世界

个人微信号:tiankonguse

QQ算法群:165531769(不止算法)

知识星球:不止算法

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章