讨论/技术交流/求助丨回文数变换(360笔试题)/
求助丨回文数变换(360笔试题)

求助!!!

  最近笔试遇到了一个算法题,不会写,也没找到同类型的题。希望各位路过的大佬,可以帮帮我这个菜鸡。

题目

  所谓回文数就是一个数字,从左边读和从右边读的结果都是一样的,例如12321。
  现在有一个只包含1、2、3、4的数字,你可以通过在任意位置增加一位数字或者删除一位数字来将其变换成一个回文数。但是增加或删除不同数字所需要的代价是不一样的。
  已知增加和删除每个数字的代价如下:

  • 增加一个 1,代价:100;删除一个 1,代价:120。
  • 增加一个 2,代价:200;删除一个 2,代价:350。
  • 增加一个 3,代价:360;删除一个 3,代价:200。
  • 增加一个 4,代价:220;删除一个 4,代价:320。

  请问如何通过最少的代价将一个数字变换为一个回文数。当然,如果一个数字本身已经是一个回文数(包括一位数,例如:2),那么变换的代价为 0。

输入描述
  单组输入。输入一个由1、2、3、4组成的正整数,正整数位数<=100位。【提示:采用字符串输入】

输出描述
  输出一个整数,表示将输入数字变换为一个回文数所需的最少代价。

样例

  输入:12322

  输出:300

提示

  增加一个 1 并增加一个 2,将输入正整数变为 1223221 或者 2123212,所需代价最小,为:100+200=300。

3
共 19 个回复

是牛客笔试题

牛客里也有这题吗

我当时也是这么写的,但是只能过9%,看牛客很多人也只能过9%,不知道哪里写的不对,还是有什么很怪的测试用例

暂时想到一个思路,没代码…

首先要知道,增加1和删除1的效果是一模一样的,那么只需要选取小花费的,也就是说,我们只考虑增加1,增加2,删除3,增加4,这4个操作。

其次,对每个位置的数做默认中心点的情况,计算出代价,保存一个最小值。

时间复杂度,O(n*n),对每个数都遍历一遍,所以是n个n。

DP、贪心

对不起我也不知道,我是在笔试的时候遇到过这种题

我当时没写出来,回去和同学讨论出了这个解法

大佬,是不是今天下午的360笔试啊,这道题是不是AC了。

Java写的一个版本,用动态规划写

import java.util.Scanner;

/**
 * @author GongZiWei
 * @create 2021-04-17 14:47
 */
public class Main {
    private static int res;//定义结果集
    private static int[][] dp = new int[100][100];//定义动态规划矩阵
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String string = in.nextLine();
        char[] str = string.toCharArray();
        int[] add = {0,100, 200, 360, 220};//添加及删除的开销,前面加个0是为了从1开始
        int[] del = {0,120, 350, 200, 320};

        //dp[i][j]表示从序号i到j变成回文串时的最小代价,而dp[i][j]可以由dp[i+1][j]和dp[i][j-1]得到
        //如果第i个字符和第j个字符不同,那么dp[i][j]可由dp[i+1][j]删除第i个字符,或者在字符串最末尾添加第i个字符得到,
        //也可以由dp[i][j-1]删除第j个字符,或者在最左侧添加第j个字符得到。
        for (int j = 1; j < str.length; j++) {
            for (int i = j-1; i >= 0 ; i--) {
                if (str[i] == str[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    int temp1 = Math.min(dp[i + 1][j] + del[str[i] - '0'],
                                         dp[i + 1][j] + add[str[i] - '0']);
                    int temp2 = Math.min(dp[i][j - 1] + del[str[j] - '0'],
                                         dp[i][j - 1] + add[str[j] - '0']);
                    dp[i][j] = Math.min(temp1, temp2);

                }
            }
        }
        System.out.println(dp[0][str.length - 1]);

    }
}