前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【一天一大 lee】自由之路 (难度:困难) - Day20201111

【一天一大 lee】自由之路 (难度:困难) - Day20201111

作者头像
前端小书童
发布2020-11-19 14:54:30
3350
发布2020-11-19 14:54:30
举报
文章被收录于专栏:前端小书童

题目:

视频游戏“辐射4”中,任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘,并使用表盘拼写特定关键词才能开门。

给定一个字符串 ring,表示刻在外环上的编码;给定另一个字符串 key,表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

最初,ring 的第一个字符与12:00方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐,然后按下中心按钮,以此逐个拼写完 key 中的所有字符。

旋转 ring 拼出 key 字符 key[i] 的阶段中:

您可以将 ring 顺时针或逆时针旋转一个位置,计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐,并且这个字符必须等于字符 key[i] 。如果字符 key[i] 已经对齐到12:00方向,您需要按下中心按钮进行拼写,这也将算作 1 步。按完之后,您可以开始拼写 key 的下一个字符(下一阶段), 直至完成所有拼写。

示例:

自由之路

代码语言:javascript
复制
输入: ring = "godding", key = "gd"
输出: 4
解释:
 对于 key 的第一个字符 'g',已经在正确的位置, 我们只需要1步来拼写这个字符。 
 对于 key 的第二个字符 'd',我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
 当然, 我们还需要1步进行拼写。
 因此最终的输出是 4。

提示:

  • ring 和 key 的字符串长度取值范围均为 1 至 100;
  • 两个字符串中都只有小写字符,并且均可能存在重复字符;
  • 字符串 key 一定可以由字符串 ring 旋转拼出。

抛砖引玉

思路:

整理下题意:

  • 指针index在ring字符串的索引0位置,index在ring中允许顺时针逆时针切换(首尾可连贯切换),切换一次计步数1
  • 当指针所对应的元素在key中,拷贝元素计步数1
  • 返回切换指针拼凑key的最小步数
  1. key中一个字符key[i]到另外一个字符key[i+1]的步数取决于ring中两个字符间的距离,设其为dp[i]
  2. 如果ring中没有重复元素,则每个dp[i]最小,最后得到的dp[key.length -1]也一定是最小的, 但是题目没有限制ring中没有重复元素,就会存在其中一些dp[x]不是最小但是最后组合却最小的情况。 那么还需要记录每次更新指针后到达的不同ring索引的步数,则dp[i][j]表示指针到达key的i索引、ring的j索引所需要的步数
  • 记录ring中每个字符所在索引的集合用于计算步数
  • 计算key切换指针所需步数:key对着字符在ring中的索引j,要到达ring中索引k
    • 顺时针:|j-k|
    • 逆时针:n-|j-k|

抛砖引玉

代码语言:javascript
复制
/**
 * @param {string} ring
 * @param {string} key
 * @return {number}
 */
var findRotateSteps = function(ring, key) {
 let m = key.length,
  n = ring.length,
  map = new Map()
 // 记录ring中每个字符的索引
 for (let i = 0; i < n; i++) {
  if (map.has(ring[i])) {
   map.get(ring[i]).push(i)
  } else {
   map.set(ring[i], [i])
  }
 }
 let dp = Array.from({ length: m }, () => Array(n).fill(Number.MAX_VALUE)),
  // 第一个字符在ring中的索引集合
  indexList = map.get(key.charAt(0));
 // 从ring索引0到达key的第一个字符的步数,顺时针i,逆时针n-i
 indexList.forEach(i => {
  dp[0][i] = Math.min(i, n - i) + 1;
 })
 for (let i = 1; i < m; i++) {
  indexList = map.get(key.charAt(i))
  indexList.forEach(j => {
   // 从key的第i-1个元素到第i个元素所需步数
   map.get(key.charAt(i - 1)).forEach(k => {
    // key的第i-1个元素在ring中指针位置j,顺时针|j-k|,逆时针n-|j-k|
    const perNum = Math.min(Math.abs(j - k), n - Math.abs(j - k)) + 1;
    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + perNum);
   })
  })
 }
 // 回到key指针到达m-1的最小集合
 return dp[m - 1].reduce((pre, cur) => Math.min(pre, cur));
};
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-11-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 前端小书童 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目:
  • 抛砖引玉
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档