读题
首先读数据范围, 0 <= n , k <= 1e5, 由此可以简单判断时间复杂度应当控制在O(nlogn)以内。
粗略读一下题目, 从起点n移动到终点k, 所花费的最少次数, 每次移动有三种方法。
其中x-1仅当当前位置在终点右侧时使用。
解题一, 验证算法, O(n^2 )
刚开始为了偷懒往贪心上去想, 仔细想了想还是dp做法比较安全。
首先, 是dp表示的内容, 因为 可能从k-1的地方开始做公交, 而且当x>k的时候, 只能通过步行, 因此将dp[i]表示为, 从终点k出发, 到达当前位置x的最小步数。
令dp:=make([]int,(k<<1)+10), 即将dp数组长度设置为终点的两倍, 因为有 所以dp数组需要设置的稍微大一点。
接着是状态转移方程：
即当x>k时, 只能通过步行从k转移到x, eg: 从k -> k+1 -> k+2
当x<k时, 需要选择步行或是公交, 因为存在往回走的情况, 所以需要考虑三种, 不往回走分为公交和步行, 往回走一定为步行, 综上, 暂时可以写出O(n^2)级别的验证算法。
代码：
package activity
// findFriends 寻友之旅
// n,k 范围[0,1e5]
// dp, O(n2)
func findFriends(n, k int) (ans int) {
const INF int = 0x3f3f3f3f
min := func(a, b int) int {
if a < b {
return a
}
return b
}
//需要注意的case, 题目未给出n,k的大小关系
if n >= k {
//在公交反方向, 只能步行
//或者n=k,俩人家在一起
return n - k
}
dp := make([]int, (k<<1)+10)
for i := 0; i < len(dp); i++ {
dp[i] = INF
}
dp[k] = 0
//先处理从右侧到终点的情况
for i := k + 1; i < len(dp); i++ {
dp[i] = dp[i-1] + 1
}
for i := k - 1; i >= n; i-- {
dp[i] = min(dp[i+1], dp[i<<1]) + 1
for j := (i + 1) >> 1; j < i; j++ {
dp[i] = min(dp[i], dp[j*2]+i-j+1)
}
}
return dp[n]
}
解题2, 线性dp, O(n)
想复杂了, 没有好好分析情况。
以dp[i]存储从n到i的最短步数, 则状态转移方程如下：
最终返回dp[k],需要注意奇数时的情况, 可能会有两张情况, 需要格外注意。
eg: 1,2,3,4,5,6,7,8,9,10
dp[5] = dp[3]+2, 3->6->5
dp[5] = dp[2]+2, 2->4->5
因为dp[k]的值仅在遍历时更新一次, 并且遍历到k时, 所需要的元素均已经更新过, 因此, 遍历范围为(n,k]。
代码
package activity
// findFriends 寻友之旅
// n,k 范围[0,1e5]
// dp, O(n)
func findFriends(n, k int) (ans int) {
const INF int = 0x3f3f3f3f
min := func(a, b int) int {
if a < b {
return a
}
return b
}
//需要注意的case, 题目未给出n,k的大小关系
if n >= k {
//在公交反方向, 只能步行
//或者n=k,俩人家在一起
return n - k
}
dp := make([]int, (k<<1)+10)
for i := n - 1; i >= 0; i-- {
dp[i] = dp[i+1] + 1
}
for i := n + 1; i < len(dp); i++ {
dp[i] = INF
}
for i := n + 1; i <= k; i++ {
dp[i] = min(dp[i-1]+1, dp[i])
if i%2 == 0 {
dp[i] = min(dp[i], dp[i>>1]+1)
} else {
dp[i] = min(dp[i], dp[(i+1)>>1]+2)
dp[i] = min(dp[i], dp[(i-1)>>1]+2)
}
}
return dp[k]
}
测试代码
package activity
import (
"math/rand"
"testing"
"time"
)
func TestFindFriends(t *testing.T) {
cnt := 0
for i := 0; i < 1e2; i++ {
rand.Seed(time.Now().UnixNano() + int64(i))
n := rand.Intn(1e5)
rand.Seed(time.Now().UnixNano() + int64(i*100))
k := rand.Intn(1e5)
ans := findFriendsEval(n, k)
test := findFriends(n, k)
t.Log("====================================================")
t.Logf("当前第%v轮, 当前的n为%v, k为%v, 答案为%v", i+1, n, k, ans)
if ans != test {
cnt++
t.Errorf("当前轮次出现错误, 测试结果为%v,正确答案为%v", test, ans)
}
}
}
对应目录结构
-->activity
-->activity-->findFriends.go
-->activity-->findFriends_test.go
本文内容不用于商业目的，如涉及知识产权问题，请权利人联系51Testing小编(021-64471599-8017)，我们将立即处理
