Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1877287
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2388
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(184)

文章存档

2021年(26)

2020年(56)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: C/C++

2018-05-05 23:38:17

输入:一个字符串ring首尾相连,表示一个圆盘的戒指,每个位置上都有一个字母与之对应,另一个字符串表示需要组合成的序列key。
要求:通过旋转ring来逐个匹配key中的字符,如果当前匹配成功,按下按钮,进行下一个字符的匹配,其中ring每旋转过一个字符,记录步数+1, 按下按钮步数+1。
输出:完全匹配key后,整个过程最少的步数
初一见整个题目莫名想起了电影《飞鹰计划》呢。。。
言归正传,第一感觉就是暴力dfs,求最小,但是感觉会超时,果不其然,提交了下面的代码之后,跑到第50个用例就不行了。。。

点击(此处)折叠或打开

  1. int findRotateSteps(string ring, string key){
  2.     int r_len = ring.length(), k_len = key.length(), i, j;
  3.     if(r_len == 0|| k_len == 0) return 0;
  4.     vector<vector<int>> dist(r_len, vector<int>(r_len, 0));
  5.     for(i = 0; i < r_len; i++)
  6.         for(j = i; j < r_len; j++)
  7.             dist[i][j]=dist[j][i]=min(j-i, i-j+r_len)+1;
  8.     return helper(ring, key, r_len, k_len, 0, 0, 0, dist);
  9. }
  10. int helper(string ring, string key, int r_len, int k_len, int r_idx, int k_idx, int cur_steps, vector<vector<int>>& dist){
  11.     if(k_idx == k_len)
  12.         return cur_steps;
  13.     int res = INT_MAX;
  14.     for(int i = 0; i < r_len; i++){
  15.         if(ring[i]==key[k_idx])
  16.             res = min(res, helper(ring, key, r_len, k_len, i, k_idx+1, cur_steps+dist[r_idx][i], dist));
  17.     }
  18.     return res;
  19. }
脑壳疼。。。
想了半天,想到用dp,创建二维数组dist,其中每个元素的初始值设置为INT_MAX
其中dist[i][j]表示:使用ring[j]来匹配到key[i]时所用的最短步骤,递推如下:
dist[i][j] = min(dist[i][j], dist[i-1][k]+min(abs(k-j), ring.length()-abs(k-j))+1)条件是{dist[i-1][k]!=INT_MAX,0<=k AC代码如下:

点击(此处)折叠或打开

  1. int findRotateSteps(string ring, string key){
  2.     int r_len = ring.length(), k_len = key.length(), i, j, k;
  3.     if(r_len == 0|| k_len == 0) return 0;
  4.     vector<vector<int>> dist(k_len, vector<int>(r_len, INT_MAX));
  5.     for( i = 0; i < r_len; i++)
  6.         if(ring[i]==key[0])dist[0][i]=min(i, r_len-i)+1;
  7.     for(i = 1; i < k_len; i++){
  8.         vector<int> temp(dist[i-1]);
  9.         for(j = 0; j < r_len; j++){
  10.             if(temp[j]!=INT_MAX){
  11.                 for(k = 0; k < r_len; k++){
  12.                     if(ring[k]==key[i]){
  13.                         dist[i][k]=min(dist[i][k], temp[j]+min(abs(j-k), r_len-abs(j-k))+1);
  14.                     }
  15.                 }
  16.             }
  17.         }
  18.     }
  19.     int res = INT_MAX;
  20.     for(i = 0; i < r_len;i++)
  21.         res = min(res, dist[k_len-1][i]);
  22.     return res;
  23. }




阅读(2124) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~