考虑你从家出发步行去往一处目的地,该目的地恰好离你整数单位步长(大于等于1)。你只能朝向该目的地或者背向该目的地行走,而你行走的必须为单位步长的整数倍,且要求你第N次行走必须走N步。
请就给出目的地离你距离,判断你是否可以在有限步内到达该目的地。如果可以到达的话,请计算到达目的地的最短总步数(不能到达则输出-1)。
1个整数:目的地离你距离T
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))
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); } }
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; } } }
#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; }
#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; }
极其暴力的广度优先搜索,可能会带坏小孩子
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)); } }
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); } }
如果贪心想不到,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; } } }
#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; }
#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; }
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); } }
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
#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; }
//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; }