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
公众号ID：tiankonguse-code