2024-01-06：用 go 语言，在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧
在桥上有一些石子，青蛙很讨厌踩在这些石子上
由于桥的长度和青蛙一次跳过的距离都是正整数
我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0...L
其中 L 是桥的长度，坐标为 0 的点表示桥的起点，坐标为 L 的点表示桥的终点
青蛙从桥的起点开始，不停的向终点方向跳跃
一次跳跃的距离是 S 到 T 之间的任意正整数（包括 S,T）
当青蛙跳到或跳过坐标为 L 的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度 L，青蛙跳跃的距离范围[S,T]，
以及桥上石子的位置。
你的任务是确定青蛙要想过河，最少需要踩到的石子数。
来自华为社招笔试。
答案 2024-01-06：
来自左程云。
灵捷3.5
大体步骤如下：
1.读入桥的长度 L、跳跃的最小距离 S、最大距离 T 和石子的位置数组。
2.如果起点和终点相同，即 S 等于 T，则遍历石子数组，计算能够整除 S 的石子数量，并输出结果。
3.否则，将石子位置数组排序，并计算可以减少的最小跳跃距离 cut，该值等于 S 和 T 之间的最小值。
4.初始化距离数组 distance，并将最小距离初始值设为 0。同时设置一个 stone 数组，记录可能存在石子的位置。
5.遍历石子位置数组，计算每个石子之间的距离，并将距离标记在 distance 数组中，同时在 stone 数组中将对应位置设为 true。
6.更新桥的长度为 distance 数组中的最后一个数和 cut 的较小值。
7.初始化 dp 数组，长度为桥的长度加一，并将每个位置的初始值设为 MAXN。
8.动态规划求解 dp 数组，计算最少需要踩到的石子数。
9.遍历 distance 数组的最后一个数加一到桥的长度 l，取 dp 数组中的最小值，即为最少需要踩到的石子数。
10.输出结果。
总的时间复杂度是 O(m log m + l * t)，其中 m 是石子数量，l 是桥的长度，t 是最大跳跃距离；
总的额外空间复杂度是 O(l + t)。
go 完整代码如下：
package main
import ( "fmt" "sort")
const ( MAXN = 101 MAXL = 100001 MAXK = 201)
var ( arr [MAXN]int distance [MAXN]int dp [MAXL]int stone [MAXL]bool reach [MAXK]bool l, s, t, m, cut int)
func main() { inputs := []int{10, 2, 3, 5, 2, 3, 5, 6, 7} ii := 0 l = inputs[ii] ii++ s = inputs[ii] ii++ t = inputs[ii] ii++ m = inputs[ii] ii++
for i := 1; i <= m; i++ { arr[i] = inputs[ii] ii++ } if s == t { ans := 0 for i := 1; i <= min(l, m); i++ { if arr[i]%s == 0 { ans++ } } fmt.Println(ans) } else { sort.Ints(arr[1 : m+1]) cut = reduce(s, t) for i := 1; i <= m; i++ { distance[i] = distance[i-1] + min(arr[i]-arr[i-1], cut) stone[distance[i]] = true } l = min(l, distance[m]+cut) for i := 1; i <= l; i++ { dp[i] = MAXN } for i := 1; i <= l; i++ { for j := max(i-t, 0); j <= i-s; j++ { dp[i] = min(dp[i], dp[j]+boolToInt(stone[i])) } } ans := MAXN for i := distance[m] + 1; i <= l; i++ { ans = min(ans, dp[i]) } fmt.Println(ans) }}
func reduce(s int, t int) int { for i := range reach { reach[i] = false } cnt := 0 ans := 0 for i := 0; i < MAXK; i++ { for j := i + s; j < min(i+t+1, MAXK); j++ { reach[j] = true } if !reach[i] { cnt = 0 } else { cnt++ } if cnt == t { ans = i break } } return ans}
func min(a, b int) int { if a < b { return a } return b}
func max(a, b int) int { if a > b { return a } return b}
func boolToInt(b bool) int { if b { return 1 } return 0}
复制代码
c++完整代码如下：
#include <iostream>#include <algorithm>using namespace std;
const int MAXN = 101;const int MAXL = 100001;const int MAXK = 201;
int arr[MAXN];int distance0[MAXN];int dp[MAXL];bool stone[MAXL];bool reach[MAXK];
int l, s, t, m, cut;
int reduce(int s, int t) { fill(reach, reach + MAXK, false); int cnt = 0; int ans = 0; for (int i = 0; i < MAXK; i++) { for (int j = i + s; j < min(i + t + 1, MAXK); j++) { reach[j] = true; } if (!reach[i]) { cnt = 0; } else { cnt++; } if (cnt == t) { ans = i; break; } } return ans;}
int main() { int inputs[] = { 10, 2, 3, 5, 2, 3, 5, 6, 7 }; int ii = 0; l = inputs[ii++]; s = inputs[ii++]; t = inputs[ii++]; m = inputs[ii++];
for (int i = 1; i <= m; i++) { arr[i] = inputs[ii++]; } if (s == t) { int ans = 0; for (int i = 1; i <= min(l, m); i++) { if (arr[i] % s == 0) { ans++; } } cout << ans << endl; } else { sort(arr + 1, arr + m + 1); cut = reduce(s, t); for (int i = 1; i <= m; i++) { distance0[i] = distance0[i - 1] + min(arr[i] - arr[i - 1], cut); stone[distance0[i]] = true; } l = min(l, distance0[m] + cut); for (int i = 1; i <= l; i++) { dp[i] = MAXN; } for (int i = 1; i <= l; i++) { for (int j = max(i - t, 0); j <= i - s; j++) { dp[i] = min(dp[i], dp[j] + (stone[i] ? 1 : 0)); } } int ans = MAXN; for (int i = distance0[m] + 1; i <= l; i++) { ans = min(ans, dp[i]); } cout << ans << endl; } return 0;}
复制代码
c 语言代码如下：
#include <stdio.h>#include <stdbool.h>
#define MAXN 101#define MAXL 100001#define MAXK 201
int arr[MAXN];int distance[MAXN];int dp[MAXL];bool stone[MAXL];bool reach[MAXK];int l, s, t, m, cut;
int min(int a, int b) { return a < b ? a : b;}
int max(int a, int b) { return a > b ? a : b;}
int reduce(int s, int t) { for (int i = 0; i < MAXK; i++) { reach[i] = false; } int cnt = 0; int ans = 0; for (int i = 0; i < MAXK; i++) { for (int j = i + s; j < (i + t + 1 < MAXK ? i + t + 1 : MAXK); j++) { reach[j] = true; } if (!reach[i]) { cnt = 0; } else { cnt++; } if (cnt == t) { ans = i; break; } } return ans;}
void sortInts(int* arr, int size) { for (int i = 0; i < size - 1; i++) { for (int j = 0; j < size - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } }}
void printAns(int ans) { printf("%d\n", ans);}
int main() { int inputs[] = { 10, 2, 3, 5, 2, 3, 5, 6, 7 }; int ii = 0; l = inputs[ii++]; s = inputs[ii++]; t = inputs[ii++]; m = inputs[ii++];
for (int i = 1; i <= m; i++) { arr[i] = inputs[ii++]; } if (s == t) { int ans = 0; for (int i = 1; i <= min(l, m); i++) { if (arr[i] % s == 0) { ans++; } } printAns(ans); } else { sortInts(arr + 1, m); cut = reduce(s, t); for (int i = 1; i <= m; i++) { distance[i] = distance[i - 1] + min(arr[i] - arr[i - 1], cut); stone[distance[i]] = true; } l = min(l, distance[m] + cut); for (int i = 1; i <= l; i++) { dp[i] = MAXN; } for (int i = 1; i <= l; i++) { for (int j = max(i - t, 0); j <= i - s; j++) { dp[i] = min(dp[i], dp[j] + (stone[i] ? 1 : 0)); } } int ans = MAXN; for (int i = distance[m] + 1; i <= l; i++) { ans = min(ans, dp[i]); } printAns(ans); } return 0;}
复制代码
评论