Curz酥 2022-07-29 14:59 采纳率: 90.9%
浏览 51
已结题

一道算法题怎么实现?

题目链接:http://oj.saikr.com/contest/20/problem/F

简单来说就是给两个字符串A和B,最少经过几次操作后,可以使A字符串变成B字符串。每个操作指的是:在A串中移动一个字母,且只能将字母移动到字符串头。 比如A串是DACB,B串是ABCD,那么操作步骤是DACB-CDAB-BCDA-ABCD,最少需要移动3次。

还有个样例是:A串是SIAJOIWUGB,B串是
IBUSJGWAOI,最少需要移动7次。

  • 写回答

2条回答 默认 最新

  • 可爱小坤坤 2022-07-29 15:56
    关注

    用个标记为, 然后做字符串分割,

    
      @Test
        void test0() {
    //        String s0 = "SIAJOIWUGB";
    //        String s1 = "IBUSJGWAOI";
            String s0 = "DACB";
            String s1 = "ABCD";
            System.out.println("从[" + s0 + "]到[]" + s1 + "]需要移动" + algorithm(s0, s1) + "次");
        }
    private int algorithm(String s0, String s1) {
            // 追踪需要的移动计数
            int count = 0;
            // 字符串长度
            int length = s1.length();
            // 角标标志
            int mark = length - 1;
            // 按照目标字符串长度进行遍历
            for (int i = 0; i < length; i++) {
                // 从目标字符串开始倒序查找
                char charAt = s1.charAt(length - 1 - i);
                int index = s0.lastIndexOf(charAt);
                // 当 查到的索引在记号之前的时候, 说明索引后面的每个字母都需要移动
                if (index < mark) {
                    // 计算索引后面有几个字母
                    count += mark - index;
                    // 更新 记号
                    mark = index - 1;
                }
                // 当记号为0 的时候 表面全部检查完毕,其余字母通过移动即可归为
                if (index == 0) {
                    break;
                }
            }
            return count;
        }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 9月16日
  • 已采纳回答 9月8日
  • 修改了问题 7月29日
  • 创建了问题 7月29日

悬赏问题

  • ¥50 swiftui @query 报错
  • ¥50 怎么解决刷卡或扫码后,点击软件输入框,win10屏幕键盘不会自动弹出的问题
  • ¥15 如何使用arcgispro的训练深度模型,发现water和nowater精度为0?(相关搜索:深度学习)
  • ¥20 matlab作业不太懂呀有问题能给个代码吗
  • ¥15 自制电路图为何无法驱动ESP01S?
  • ¥15 前端加access数据库
  • ¥15 ARCGIS 多值提取到点 ERROR 999999
  • ¥15 mysql异常断电, [MY-011971] [InnoDB]
  • ¥15 uni.onBluetoothDeviceFound熄屏不运行
  • ¥15 求PHDA糖尿病并发症数据集,有偿