讨论/技术交流/求助|请教一道题/

给定一个整数target, 从0开始可以进行两种操作:
+5 和 -3,求能构成target的最小步数,不能构成返回-1。
感觉在leetcode做过类似,有老铁能帮忙找下吗?或者说说思路。

毫无思路。

5

数学题。

设最终 +5 和 -3 的次数为 x、y。那么就是在 5x-3y=target,x、y 为自然数的条件下,求 min(x+y)。

显然 x 和 y 同步增长,所以任选 x 或 y 从 0 开始遍历看是否有解即可。

为了方便,选 y 从 0 开始遍历,target 不断 +3 直到 target>=0 且 target 为 5 的倍数即可。

进一步的,为了节省时间,如果 target<0,直接先加 (-target-1)//3+1 个 3 使 target>=0。然后根据模 5 的余数判断再加几个 3 即可。时间复杂度 O(1)。

展开全部 35 讨论