Python：每日一题 364
本帖最后由 zltzlt 于 2020-3-31 17:45 编辑这道题算昨天的
今天的题目：
假设你在一根无限长的数轴上站在 0 的位置，终点在 target 的位置。
每次你可以选择向左或向右移动。第 n 次移动（从 1 开始）可以走 n 步。返回到达终点需要的最小移动次数。
示例 1：
输入：target = 3
输出：2
解释：
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。
示例 2：
输入：target = 2
输出：3
解释：
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。
{:10_298:}欢迎大家一起答题！{:10_298:} 二楼 永恒的蓝色梦想 发表于 2020-3-31 17:29
二楼
{:10_282:}这么快 zltzlt 发表于 2020-3-31 17:29
这么快
刚好刷出来{:10_297:} 我昨天的363题做出来了，我写在这里也给测一下吧
旧 363题
def oldfun363(n,k):
if n == 1:
result = ''
for each in range(0,k):
result += str(each)
return result
result = '0'*(n-1)
hasBeenIn = set()
temp = 0
M = k**n
for each in range(0,M):
for inner in range(k-1,-1,-1):
tempInner = (temp*k+inner)%(M)
if tempInner not in hasBeenIn:
hasBeenIn.add(tempInner)
result += str(inner)
temp = tempInner
break
return result 本帖最后由 sunrise085 于 2020-3-31 18:03 编辑
def reachNumber(target):
sum=0
i=1
a = abs(target)
while(sum<a or (sum-a)%2!=0):
sum+=i
i+=1
return i-1
print(reachNumber(3))
print(reachNumber(1))
print(reachNumber(2))
print(reachNumber(-3)) sunrise085 发表于 2020-3-31 17:53
176 ms zltzlt 发表于 2020-3-31 17:54
176 ms
刚刚写错了
i初始值应该是1，而不应该是0
因为输入0 的话就会出现负值，而且循环会多一次
试一下现在时间多长？ 此法不知道对不对，没严格验证
import math
def fun363(target):
def mySum(n):
return ((n+1)*n)//2
target = abs(target)
if target % 2 == 0:
start = math.floor((((2*target)**(1/2))-5)/4)
start = start if start >= 0 else 0
for each in range(start,start+100):
if mySum(4*each+3)>=target:
return 4*each+3
if mySum(4*each+4)>=target:
return 4*each+4
else:
start = math.floor((((2*target)**(1/2))-3)/4)
start = start if start >= 0 else 0
for each in range(start,start+100):
if mySum(4*each+1)>=target:
return 4*each+1
if mySum(4*each+2)>=target:
return 4*each+2 sunrise085 发表于 2020-3-31 18:03
刚刚写错了
i初始值应该是1，而不应该是0
因为输入0 的话就会出现负值，而且循环会多一次
嗯，112 ms TJBEST 发表于 2020-3-31 18:17
此法不知道对不对，没严格验证
44 ms zltzlt 发表于 2020-3-31 18:18
44 ms
居然对了{:5_109:}瞎编的，没有科学验证的 有了一点思路，可能得暴力枚举 def min_step(target):
count = 1
sum1 = 0
while sum1 < target:
sum1 = sum1 + count
count += 1
if sum1 == target:
print(count - 1)
else:
number1 = (target-sum1+count-1)*2 + count - 2
number2 = (sum1-target)*2 + count - 1
print(min())
min_step(3)
# 思路：先一直走到target之前或之后，(或直接到target)，
# 然后分别反复移动到target(每移动一格需要前后走两步)，
# 计算各自需要的步数并比较大小。 本帖最后由 Herry2020 于 2020-3-31 20:16 编辑
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)) def f364(target:int)->int:
s,n,abs_t = 0,0,abs(target)
while s<abs_t or (s-abs_t)%2 != 0:
n+=1
s+=n
return n 这道题我能想到的办法有鱼油写出来了。另外TJBEST的是用了什么公式哦 我把下午写的修改了一下，while循环最多需要两次
import math
def reachNumber(target):
a = abs(target)
i=int(math.sqrt(a*2))
sum1=i*(i+1)/2
while(sum1<a or (sum1-a)%2!=0):
i+=1
sum1+=i
return i
print(reachNumber(0))
print(reachNumber(1))
print(reachNumber(2))
print(reachNumber(-11))
本帖最后由 archlzy 于 2020-3-31 21:27 编辑
def fun364(targert):
n = 0
sum_num = 0
target = abs(target)
while sum_num < targert:
n += 1
sum_num += n
if (sum_num - targert)%2:
return n+1
else:
return n fan1993423 发表于 2020-3-31 21:04
这道题我能想到的办法有鱼油写出来了。另外TJBEST的是用了什么公式哦
数列+一元二次方程