[已解决]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

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))

跳转到最佳答案楼层

永恒的蓝色梦想

二楼

zltzlt

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

这么快

永恒的蓝色梦想

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

刚好刷出来

TJBEST

我昨天的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

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))

zltzlt

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

176 ms

sunrise085

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

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

TJBEST

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

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

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

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([number1,number2]))
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

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

fan1993423

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

sunrise085

我把下午写的修改了一下，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

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

TJBEST

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

数列+一元二次方程