目的地最短步数

[编程题]目的地最短步数

热度指数：5334 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

考虑你从家出发步行去往一处目的地，该目的地恰好离你整数单位步长（大于等于1）。你只能朝向该目的地或者背向该目的地行走，而你行走的必须为单位步长的整数倍，且要求你第N次行走必须走N步。

请就给出目的地离你距离，判断你是否可以在有限步内到达该目的地。如果可以到达的话，请计算到达目的地的最短总步数(不能到达则输出-1)。

输入描述:

1个整数：目的地离你距离T

输出描述:

1个整数：最短总步数（进行了多少次行走）

示例1

输入

输出

说明

距离目的地2， 需要3步：朝向走1，背向走2，朝向走3

算法知识视频讲解

Python

我不想当大白菜

层次遍历，每次有加和减i两个选项，将其结果送到队列中。
使用层次遍历的原因：方便设定终止条件，如果当前层所有的位置和下一步的步数和都大于N的话，就再也不会走到指定的位置了。

from collections import deque
N = int(input())

que = deque([(0,1)])
while que:
    # 标记当前层是不是还有小于N的值
    SMALLER = False
    for _ in range(len(que)):
        cur_pos,step = que.popleft()
        if cur_pos == N:
            print(step-1)
            exit()
        if cur_pos+ step <= N:
            SMALLER = True
        que.append([cur_pos+step,step+1])
        que.append([cur_pos-step,step+1])
    if not SMALLER:
        print(-1)
        break

发表于 2020-07-23 19:38:17 回复(0)

Python

贾志统

def func3(T):
    i = 1
    while True:
        s = i*(i+1) >> 1
        if s >= T and (s-T)&1 == 0:
            print(i)
            return
        i += 1
T = int(input())
func3(T)

发表于 2019-08-27 11:38:27 回复(0)

Python

欧巴禾

n = int(input()) if n==1:  if n not in [1, -1]:  print(-1) else:  print(1) else:  numbers = [1, -1]
    step = 2  while n not in numbers:  comb = [] for number in numbers:  comb.append(number-step)
            comb.append(number+step)
        numbers = comb
        step+=1  print(step-1)

发表于 2019-08-24 10:29:19 回复(0)

Python

雷凌云

"""
广度优先遍历算法
[0]             第0层，
[1, -1]         第1层，上层的结果 +1，-1
[3, -1, 1, -3]  第2层，上层的结果 +2，-2
...             第i层，上层的结果 +i，-i
"""
def BFS(n):
    bfs = set([0])
    i = 0
    while True:
        i += 1
        pre = bfs.copy()
        bfs = set()
        for num in pre:
            if num+i==n or num-i==n:
                return i
            else:
                bfs.add(num+i)
                bfs.add(num-i)
n = int(input())
print(BFS(n))

发表于 2019-08-21 22:31:43 回复(0)

Python

ElonB

""""
计算全部正向走之和，若需要背向走则减2*x，即超过t偶数步
"""
if __name__ == "__main__":
    t = int(input().strip())
    s = i = 0
    while True:
        i += 1
        s += i
        if s >= t and (s - t) % 2 == 0:
            break
    print(i)

发表于 2019-07-11 22:16:08 回复(0)