问一道面经题

确实是个数学题，参考 刷题网其无似

1. int minStep(int target) {
   
2.         int step = 0;
   
3.         int sum = 0;
   
4.         while (sum < target) {
   
5.             step++;
   
6.             sum += 5;
   
7.         }
   
8.         while ((sum - target) % 3 != 0) {
   
9.             step++;
   
10.             sum += 5;
    
11.         }
    
12.         step += (sum-target)/3;
    
13.         return step;
    
14.     }

复制代码

smartczy 发表于 2021-3-30 22:07
老哥太秀了。
问下这个结论是怎么得出来的？

我觉得是因为 (5x-t) + (x+t) = 6x，6x整除3所以他们的余数互补。

我之前面华为的时候也面了一个差不多的..我就不明白国内这么喜欢面数学题到底是为了什么..哪里可以得到码农能力的signal..

请看我的解法

1. static int ms1(int target){
   
2.   int dict[] = {0, 2 + 3, 1 + 1, 3 + 4, 2 + 2};
   
3.   return dict[target % 5] + target / 5;
   
4. }
   
5. int main()
   
6. {
   
7.   std::cout << ms1(10);
   
8.   return 0;
   
9. }

复制代码

其实任何一个数，前面都是固定的，只要考虑5的余数部分就好了。1，2，3，4，这几个如果能走到，前面贯予5的倍数即可。
就是把一个数拆分成两部分。 5*n + x =target.
x取值，只有0，1，2，3，4. 走到0的步数就是0， 1的步数是5*2 - 3*3 = 5步。
这样任意一个target，就是先整初，这个是第一部分的步数 + 剩余余数的步数

其实这算一道贪心题，target直接按照模5分类，走法是固定的

看到最短最快bfs