2024-01-06：用go语言，在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧在桥上有一些石子，青蛙很讨厌踩在

福大大架构师每日一题

发布于 2024-01-11 18:21:22

1690

发布于 2024-01-11 18:21:22

文章被收录于专栏：福大大架构师每日一题

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 数组，计算最少需要踩到的石子数。

• 对于每个位置 i，从 i-s 到 i-t 之间的位置 j，取 dp[j] 的最小值，再加上是否有石子的判断 boolToInt(stone[i])。

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;
}