[已解决]Python：每日一题 364

zltzlt

这道题算昨天的

今天的题目：

假设你在一根无限长的数轴上站在 0 的位置，终点在 target 的位置。

每次你可以选择向左或向右移动。第 n 次移动（从 1 开始）可以走 n 步。返回到达终点需要的最小移动次数。

示例 1：

输入：target = 3
输出：2
解释：
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。

示例 2：

输入：target = 2
输出：3
解释：
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

sunrise085

2020-3-31 17:53:50

1. def reachNumber(target):
   
2.     sum=0
   
3.     i=1
   
4.     a = abs(target)
   
5.     while(sum<a or (sum-a)%2!=0):
   
6.         sum+=i
   
7.         i+=1
   
8.    
   
9.     return i-1
   
10. print(reachNumber(3))
    
11. print(reachNumber(1))
    
12. print(reachNumber(2))
    
13. print(reachNumber(-3))

复制代码

跳转到最佳答案楼层

永恒的蓝色梦想

二楼

zltzlt

永恒的蓝色梦想 发表于 2020-3-31 17:29
二楼

这么快

永恒的蓝色梦想

zltzlt 发表于 2020-3-31 17:29
这么快

刚好刷出来

TJBEST

我昨天的363题做出来了，我写在这里也给测一下吧
旧 363题

1. def oldfun363(n,k):
   
2.     if n == 1:
   
3.         result = ''
   
4.         for each in range(0,k):
   
5.             result += str(each)
   
6.         return result
   
7.     result = '0'*(n-1)
   
8.     hasBeenIn = set()
   
9.     temp = 0
   
10.     M = k**n
    
11.     for each in range(0,M):
    
12.         for inner in range(k-1,-1,-1):
    
13.             tempInner = (temp*k+inner)%(M)
    
14.             if tempInner not in hasBeenIn:
    
15.                 hasBeenIn.add(tempInner)
    
16.                 result += str(inner)
    
17.                 temp = tempInner
    
18.                 break
    
19.     return result

复制代码

sunrise085

1. def reachNumber(target):
   
2.     sum=0
   
3.     i=1
   
4.     a = abs(target)
   
5.     while(sum<a or (sum-a)%2!=0):
   
6.         sum+=i
   
7.         i+=1
   
8.    
   
9.     return i-1
   
10. print(reachNumber(3))
    
11. print(reachNumber(1))
    
12. print(reachNumber(2))
    
13. print(reachNumber(-3))

复制代码

zltzlt

sunrise085 发表于 2020-3-31 17:53

176 ms

sunrise085

zltzlt 发表于 2020-3-31 17:54
176 ms

刚刚写错了
i初始值应该是1，而不应该是0
因为输入0 的话就会出现负值，而且循环会多一次
试一下现在时间多长？

TJBEST

此法不知道对不对，没严格验证

1. import math
   
2. def fun363(target):
   
3.     def mySum(n):
   
4.         return ((n+1)*n)//2
   
5.     target = abs(target)
   
6.     if target % 2 == 0:
   
7.         start = math.floor((((2*target)**(1/2))-5)/4)
   
8.         start = start if start >= 0 else 0
   
9.         for each in range(start,start+100):
   
10.             if mySum(4*each+3)>=target:
    
11.                 return 4*each+3
    
12.             if mySum(4*each+4)>=target:
    
13.                 return 4*each+4
    
14.     else:
    
15.         start = math.floor((((2*target)**(1/2))-3)/4)
    
16.         start = start if start >= 0 else 0
    
17.         for each in range(start,start+100):
    
18.             if mySum(4*each+1)>=target:
    
19.                 return 4*each+1
    
20.             if mySum(4*each+2)>=target:
    
21.                 return 4*each+2

复制代码

zltzlt

sunrise085 发表于 2020-3-31 18:03
刚刚写错了
i初始值应该是1，而不应该是0
因为输入0 的话就会出现负值，而且循环会多一次

嗯，112 ms

zltzlt

TJBEST 发表于 2020-3-31 18:17
此法不知道对不对，没严格验证

44 ms

TJBEST

zltzlt 发表于 2020-3-31 18:18
44 ms

居然对了瞎编的，没有科学验证的

_2_

有了一点思路，可能得暴力枚举

chen971130

1. def min_step(target):
   
2.     count = 1
   
3.     sum1 = 0
   
4.     while sum1 < target:
   
5.         sum1 = sum1 + count
   
6.         count += 1
   
7.     if sum1 == target:
   
8.         print(count - 1)
   
9.     else:
   
10.         number1 = (target-sum1+count-1)*2 + count - 2
    
11.         number2 = (sum1-target)*2 + count - 1
    
12.         print(min([number1,number2]))
    
13. min_step(3)

复制代码

# 思路：先一直走到target之前或之后，(或直接到target)，
# 然后分别反复移动到target(每移动一格需要前后走两步)，
# 计算各自需要的步数并比较大小。

Herry2020

def fun364(target):
    sum = 0
    n = 1
    i = 1
    while True:
        sum += i
        if sum < target:
            i += 1
            n += 1
        elif sum > target:
            sum -= 2*i
            i += 1
            n += 1
        else:
            break
    return n

print(fun364(2))

ouyunfu

1. def f364(target:int)->int:
   
2.     s,n,abs_t = 0,0,abs(target)
   
3.     while s<abs_t or (s-abs_t)%2 != 0:
   
4.         n+=1
   
5.         s+=n
   
6.     return n

复制代码

fan1993423

这道题我能想到的办法有鱼油写出来了。另外TJBEST的是用了什么公式哦

sunrise085

我把下午写的修改了一下，while循环最多需要两次

1. import math
   
2. def reachNumber(target):
   
3.     a = abs(target)
   
4.     i=int(math.sqrt(a*2))
   
5.     sum1=i*(i+1)/2
   
6.     while(sum1<a or (sum1-a)%2!=0):
   
7.         i+=1
   
8.         sum1+=i
   
9.     return i
   
10. print(reachNumber(0))
    
11. print(reachNumber(1))
    
12. print(reachNumber(2))
    
13. print(reachNumber(-11))

复制代码

archlzy

1. def fun364(targert):
   
2.     n = 0
   
3.     sum_num = 0
   
4.     target = abs(target)
   
5.     while sum_num < targert:
   
6.         n += 1
   
7.         sum_num += n
   
8.     if (sum_num - targert)%2:
   
9.         return n+1
   
10.     else:
    
11.         return n

复制代码

TJBEST

fan1993423 发表于 2020-3-31 21:04
这道题我能想到的办法有鱼油写出来了。另外TJBEST的是用了什么公式哦

数列+一元二次方程