问一道面经题

问一道面经题，面完半天 还是没想明白起始点为0, 给一个目标数 int target， 每一步可以+5 也可以-3， 求0到target的最小步数。
例如： target = 10, 那么最小步数为 2步： 0 -> 5 -> 10

本来想用dp不过想想好像又不是，就用了最土的办法 lol ( while loop, 大于target -3， 小于target +5， 等于target 返回步数，还考虑了一下无法走到target的条件， 面试完想半天才发现一定会走到target。。。。不用考虑。。。。)

感觉应该不会这么简单粗暴，但又想不出什么解决办法，也没搜到类似面经。。。。。郁闷。。。。

x//5+{0, 5, 2, 7, 4}[x mod 5]
应该类似这种方法 有几个数字可能可以优化一下 没仔细推敲 如果能继续优化的话可能还有边界要考虑

补充内容 (2021-03-30 15:15 +08:00):
x就是target
每5个数就是一个循环
完全可以根据前5个数把之后的所有情况推导出来

请看我的解法

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，就是先整初，这个是第一部分的步数 + 剩余余数的步数

根据lz描述，我可能 用Bfs吧，用一个hashset记录已经visited过得点数，避免重复，如果 queue front  是target ，返回步数

beckswu 发表于 2021-3-30 12:55
根据lz描述，我可能 用Bfs吧，用一个hashset记录已经visited过得点数，避免重复，如果 queue front  是targ ...

好像真的可以！看来这轮妥妥挂了 。。。

可以bfs，面试一般还要你优化的。dp就可以，因为最远距离就是[target -5, target +3]，开一个长度为target + 3的数组。可以考虑dp[i]为起始点到i的最短距离，每次更新dp[i]就可以了。lz面试的是哪个组啊？

1. 额，这是一道数学题吧。。
   
2. 设x次+5，y次-3，t = target, 那 5x - 3y = t, y = (5x-t)/3.所以总operation数是 x + y = (8x - t)/3， 限制条件是 x >=0 且 x >= t/5。
   
3. 那x >= max(0, [(t-1)/5] + 1). 然后要求5x - t被3整除，也就是x+t被3整除，所以试一下最多3个数就行
   
4. 
   
5. int calc(int t) {
   
6.     return t > 0 ? (t - 1) / 5 : t / 5 - 1;
   
7. }
   
8. 
   
9. int minOpr(int target) {
   
10.     int x = max(0, calc(target) + 1);
    
11.     while((x + target) % 3) ++ x;
    
12.     return (8 * x - target) / 3;
    
13. }
    

复制代码

ginger852 发表于 2021-3-30 13:18
可以bfs，面试一般还要你优化的。dp就可以，因为最远距离就是[target -5, target +3]，开一个长度为target  ...

具体忘记了 估计general的 说北京苏州都有职位  不过应该跟我无关了……😭

tamaimasenako 发表于 2021-3-30 13:20
[mw_shl_code=cpp,true]额，这是一道数学题吧。。
设x次+5，y次-3，t = target, 那 5x - 3y = t, y = (5x- ...

我就是想往这个方向想的 然后没想明白lol

tamaimasenako 发表于 2021-3-30 13:20
[mw_shl_code=cpp,true]额，这是一道数学题吧。。
设x次+5，y次-3，t = target, 那 5x - 3y = t, y = (5x- ...

这个解法就很秀

tamaimasenako 发表于 2021-3-30 13:20
[mw_shl_code=cpp,true]额，这是一道数学题吧。。
设x次+5，y次-3，t = target, 那 5x - 3y = t, y = (5x- ...

老哥太秀了。
问下这个结论是怎么得出来的？

也就是x+t被3整除，所以试一下最多3个数就行