首页 > 试题广场 >

目的地最短步数

[编程题]目的地最短步数
  • 热度指数:5330 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
考虑你从家出发步行去往一处目的地,该目的地恰好离你整数单位步长(大于等于1)。你只能朝向该目的地或者背向该目的地行走,而你行走的必须为单位步长的整数倍,且要求你第N次行走必须走N步。
请就给出目的地离你距离,判断你是否可以在有限步内到达该目的地。如果可以到达的话,请计算到达目的地的最短总步数(不能到达则输出-1)。

输入描述:
1个整数:目的地离你距离T


输出描述:
1个整数:最短总步数(进行了多少次行走)
示例1

输入

2

输出

3

说明

距离目的地2, 需要3步:朝向走1,背向走2,朝向走3
"""
广度优先遍历算法
[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)
whileTrue:
    try:
        T =eval(input())
        i =1
        S =0
        while1:
            S+=i
            #思路,假定一直正向走,则每次都是S+=i,若一直正向走到不了目的地,则至少需要一次反向走,
            #假设第j次是反向走的,则总距离减去2*j,必定是个偶数,即不管有多少次反向走,减去的距离都是个偶数,
            #则只需要在一直正向走的基础上,找到第一个偶数能够等于正向走的总距离S减去T,即为最短路径
            ifS>=T and(S-T)%2==0:
                print(i)
                break
            i+=1
    except:
        break
发表于 2018-11-29 09:04:58 回复(4)

https://leetcode.com/problems/reach-a-number/

这道题是 leetcode 754 原题

//先一直向前走,使得sum>=target,如果步数小于这个数是不可能到达的
//当sum>target后,再考虑能否将之前的步伐反向来恰好到达目的地
//也就是说,从最小的可能步数出发,每次加一并检查是否可行

public int reachNumber(int target) {  int step = 0;
    int sum = 0;
    while(sum<target){
        step++;
        sum += step;
    }
    //此时sum>=target
    //sum==target的话不用说,很完美
    //sum>target的话,就要考虑,能不能之前走过的某一步改为向后倒退
    //倒退操作会使得 sum-even_number    (这个even number = 2*该步步长)
    //如果(sum-target)%2==0,就说明sum多出来的长度,可以通过将之前的 向前的步伐 改为 向后的步伐 来使得sum==target
    //但是, (sum-target)%2可能不为0,此时不能通过改变步伐方向来完成。意味着我们需要再往前走(最多再走两次)
    while( (sum-target)%2!=0 ){
        step++;
        sum += step;
    }
    return step;
}
//后续:为什么说最多再走两次?
//首先, (sum-target)为奇数才需要继续走
//下一次步长可能为奇数或者偶数,如果为奇数,那么就完成了,此时(sum-target)%2==0
//                             如果为偶数,此时(sum-target)仍然是奇数,但是再下一次步长为奇数,此时(sum-target)%2==0

贴上线上测试通过的完整程序:
import java.util.*;

public class Main{

    public static int reachNumber(int target) {  
        int step = 0;
        int sum = 0;
        while(sum<target){
            step++;
            sum += step;
        }
        while( (sum-target)%2!=0 ){
            step++;
            sum += step;
        }
        return step;
    }
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int step = reachNumber(n);
        System.out.println(step);
    }
}
编辑于 2019-08-12 21:08:59 回复(0)
当n*(n+1)/2==t时,则只需要走n步即可
当n*(n+1)/2>t时
    当n*(n+1)/2-t为偶数时,只需走n步即可,例如两者之差为2,则第一步为负数即可,原理:(x+y)-(x-y) == 2*y(必然是偶数)
    当n*(n+1)/2-t为奇数时==>继续走一或两步,目的就是凑出偶数,原理同上,例如:t=25,则n=7是sum=28,sum+8+9-t=45-25=20,20/2=10(比如-3和-7,或者-2或-8)
        当n为偶数时,再加上n+1(奇数),即n*(n+1)/2-t+(n+1)就为偶数
        当n为奇数时,再加上n+1(偶数)仍然为奇数,因此还需要再加上n+2(奇数),此时n*(n+1)/2-t+(n+1)+(n+2)为偶数
int func(int target) {
    int i = 1;
    while(i*(i+1)<2*target){
        i++;
    }
    if(i*(i+1)/2==target)return i;
    if((i*(i+1)/2-target)%2==0){
        return i;
    }else{
        if(i%2==0){
            return i+1;
        }else{
            return i+2;
        }
    }
}


发表于 2019-10-24 15:50:55 回复(0)
#include <iostream>
#include <deque>
#include <unordered_set>

using namespace std;

int bfs(int target) {
  deque<int> q{{0}};
  
  int steps = 0;
  while (not q.empty()) {
    size_t s = q.size();
    while (s--) {
      int curr = q.front(); q.pop_front();
      if (curr == target) return steps;
      for (int nxt : {curr - steps - 1, curr + steps + 1}) {
        q.emplace_back(nxt);
      }
    }
    ++steps;
  }
  
  return -1;
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int t;
  cin >> t;
  cout << bfs(t);
  return 0;
}

发表于 2021-08-05 19:36:40 回复(0)
#include "iostream"
#include "vector"
#include "algorithm"
#include "set"
using namespace std;


int dfs(int n) {
	vector<set<int>> s(2);
	int d = 0;    //奇偶层, 这样避免了拷贝的麻烦
	int i = 0;
	s[1 - d].insert(0);
	while (1) {
		i += 1;
		for (int num : s[1 - d]) {
			if (num + i == n || num - i == n) {
				return i;
			}
			else {
				s[d].insert(num + i);
				s[d].insert(num - i);
			}
		}
		
		d = 1 - d;
		s[d].clear();
	}
}
int main() {
	int t;
	cin >> t;
	int step = dfs(t);
	 

		
	cout << step << endl;
	system("pause");
	return 0;
}

发表于 2020-06-08 16:24:00 回复(0)

极其暴力的广度优先搜索,可能会带坏小孩子

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static int func(int T){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        for(int i=1;i<Integer.MAX_VALUE;i++){
            int size = queue.size();
            for(int j=0;j<size;j++){
                int num = queue.poll();
                if(num==T) return i-1;
                queue.add(num+i);
                queue.add(num-i);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        System.out.println(func(T));
    }
}
发表于 2020-04-29 18:24:12 回复(0)
根本不存在不能达到的情况
a,i,j = int(input()),1,2
while i < a&nbs***bsp;(i + a) % 2:
    i,j = i + j,j + 1
print(j - 1)

发表于 2020-03-14 19:15:09 回复(0)
Java解法
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int target = scanner.nextInt();
        int sum =0;
        int j=1;
        //target和sum同奇偶
        for (; (sum - target)%2==1 || sum < target; j++) {
            sum+=j;
        }
        System.out.println(j-1);
    }
}



发表于 2020-03-01 13:15:32 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main() {
    int T;
    while (cin >> T) {
        int sum = 0, i = 0;
        while (sum < T) sum += ++i;
        cout << i + (((sum - T) % 2 == 0) ? 0 : ((i + 1) % 2 == 1) ? 1 : 2) << endl;
    }
    return 0;
}

发表于 2019-08-05 10:35:55 回复(0)

如果贪心想不到,BFS还能续一波命

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import static java.lang.System.in;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        int n = sc.nextInt();
        que.add(new Node(0, 0));
        //bfs搜索
        Node temp;
        int ans = 0;
        while (true) {
            temp = que.poll();
            if (temp.pos == n) {
                ans = temp.times;
                break;
            }
            que.offer(new Node(temp.pos + temp.times + 1, temp.times + 1));
            que.offer(new Node(temp.pos - temp.times - 1, temp.times + 1));
        }
        System.out.println(ans);
    }
    public static Queue<Node> que = new LinkedList();
    private static class Node{
        int pos;
        int times;
        public Node(int pos, int times) {
            this.pos = pos;
            this.times = times;
        }
    }
}
发表于 2019-08-04 22:32:48 回复(1)
#include <bits/stdc++.h>
using namespace std;

struct P{
    int x, t, s;
    P(int x, int t, int s):x(x),t(t),s(s){}
};

int BFS(int T){
    queue<P> q;
    q.push(P(0,0,1));
    while(!q.empty()){
        P p = q.front();
        q.pop();
        if(p.x == T)
            return p.t;
        q.push(P(p.x+p.s, p.t+1, p.s+1));
        q.push(P(p.x-p.s, p.t+1, p.s+1));
    }
    return -1;
}

int main(){
    int T;
    while(cin>>T)
        cout<<BFS(T)<<endl;
    return 0;
} 

发表于 2019-07-09 22:29:33 回复(0)
#include<stdio.h>
#include<iostream>
using namespace std;

int main()
{
        int T;            //目的地距离
        cin>>T;
        int walkLength=0;   //累积行走距离
        for(int i=1; ;i++)
        {
              walkLength+=i;
              if(walkLength>= T && (walkLength-T)%2==0 )
            {
                     cout<<i;
                     return 0;
            }
        }

}

看了其他人的答案写的,应该这么理解:后退的原因是累积的行走距离可能会大于需要走的距离,所以需要后退,假设第i-1步没有超出距离,第i步超出了距离x,如果x是个偶数就好办了,我在第x/2步中选择后退就行了,其余的行走计划按照原样,那么这样一个新的行走计划正好比原始计划要往后退x的长度,正好到达终点;若x是个奇数,那么继续往前走,直到超出的距离为一个偶数为止,需要后退哪一步与前面的计算方法相同。
当超出的距离为偶数时,实际行走方案就已经知道了,即在原始行走计划的基础上,将x/2步从前进改为后退即可,总步数是不变的

具体这样为什么是最少步数不理解(算法特别菜,希望大神指教),但是这样确实可以求得一个解
编辑于 2018-12-03 20:55:17 回复(0)
#include <cstdio>  using namespace std;  int main() { int n, ans = 0;  scanf("%d", &n);  for (int i = 1;; i++) {
        ans += i;  if (ans >= n && (ans - n) % 2 == 0) {
            printf("%d\n", i);  break;  }
    } return 0; }

发表于 2018-11-26 21:51:53 回复(0)
#include <iostream>
using namespace std;
int main(void){
    int T, i, sum = 1;
    cin>>T;
    for(i = 2; (sum-T)&1 || sum < T ; ++i)
        sum += i;
    cout<<i-1<<endl;
    return 0;
}
不用贪心,不用BFS!
根据题意画出一棵二叉树,根节点值为0,表示到家的距离
第二层,向左向右走一步,从左往右子节点值为-1,1,即±{1}
第三层,向左向右走两步,从左往右子节点值为-3,1,-1,3,即±{1,3}
第四层,向左向右走三步,从左往右子节点值为-6,0,2,4,-4,2,0,6,即±{0,2,4,6}
...
归纳总结,第i层,设sum=1+2+3+...+i-1,sum为奇数,第i层所到达的范围为[-sum,sum]内的所有奇数,sum为偶数,第i层所到达的范围为[-sum,sum]内的所有偶数
sum可以无穷大,所以总是能够达到的
现在求最短步数,即T出现的最早的一层i,这需要两个条件:
  1. T和sum同奇偶
  2. sum≥T
根据上述结论计算sum即可,注意循环退出后i-1才是正确答案
编辑于 2019-08-15 21:20:36 回复(3)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 只要 sum 比 target 大,而且差值为偶数就可以了;
 * 假设a为正向移动步数,b为负向移动步数,有 a - b = target,sum = a+b;
 * 则有 sum - target == 2b;故sum与b成正比
 * 一定是可以走到的:因为 反一步+ 正一步 步长加一
 */
public class Solution14_目的地的最短步数 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int sum = 0;
        int step = 1;
        while (n > sum || (sum - n) % 2 != 0) {
            sum += step;
            step++;
        }
        System.out.println(step - 1);
    }
}
发表于 2019-08-16 18:22:18 回复(0)
  • 层次遍历,每次有加和减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)
#include<iostream>
using namespace std;
int main(){
    long long T;
    cin>>T;
    long long i=1;
    while(i*(i+1)/2<T) i++;
    if(T==i*(i+1)/2) cout<<i;
    else{
        while((i*(i+1)/2-T)%2==1) i++;
        cout<<i;
    }
}
发表于 2020-07-21 22:07:43 回复(0)
分享一个c++写法
#include<iostream>
#include<queue>
using namespace std;
int cur_num = 0;
int num_steps =0;
queue<int> q;
int bfs(int target)
{
    q.push(0);
    int step = 1;
    while(!q.empty())
    {
        int tmp_n = q.size();
        for(int i = 0;i<tmp_n;i++)
        {
            int tmp = q.front();
            q.pop();
            if(tmp == target)
                return step-1;
            q.push(tmp+step);
            q.push(tmp-step);
        }
        step++;
    }
    return -1;
}
int main()
{
    int target;
    cin>>target;
    int ans = bfs(target);
    cout<<ans<<endl;
    return 0;
}

发表于 2020-06-26 10:28:46 回复(0)
//BFS
#include<iostream>
(720)#include<queue>

using namespace std;

int main(void) {
	int N;
	int step = 1;
	cin >> N;
	queue<int> q;
	q.push(0);
	while (!q.empty()) {
		int n = q.size();
		for (int i = 0; i < n; i++) {
			int index = q.front();
			q.pop();
			if (index + step == N) {
				cout << step << endl;
				
				return 0;
			}
			
			
			q.push(index + step);

			if (index - step == N) {
				cout << step << endl;
				
				return 0;
			}
			
			
			
			q.push(index - step);
			
		}
		step++;
	}
	cout << -1 << endl;
	
	return 0;
}

发表于 2020-05-12 15:48:07 回复(0)