3 solutions

  • 1
    @ 2024-10-12 1:37:14

    编辑距离问题，Java代码如下：

    import java.util.*;

public class Main {
    static Set<Character> GROUP1 = new HashSet<>(Arrays.asList('w', 'i', 'r', 'e', 'l', '@', 'c', 'o', 'm'));
    static Set<Character> GROUP2 = new HashSet<>(Arrays.asList('h', 'f', 'v', '#', 'g', 'b', 't', 's'));


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String word1 = in.nextLine();
        String word2 = in.nextLine();

        int res = 0;

        // dp[i][j]:word1的前i-1个字符和word2的前j-1个字符相等需要的步骤
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];

        // 初始化 dp 数组
        for (int i = 0; i <= word1.length(); i++) {
            dp[i][0] = i * 3;
        }
        for (int j = 0; j <= word2.length(); j++) {
            dp[0][j] = j * 3;
        }


        // 遍历
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                char c1 = word1.charAt(i - 1);
                char c2 = word2.charAt(j - 1);

                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 插入或删除
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 3;

                    // 处理替换操作
                    int replaceCost = getReplaceCost(c1, c2);
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + replaceCost);
                }
            }
        }
        res = dp[word1.length()][word2.length()];
        System.out.println(res);
        in.close();
    }

    // 获取两个字符替换的成本
    static int getReplaceCost(char c1, char c2) {
        boolean inGroup1C1 = GROUP1.contains(c1);
        boolean inGroup1C2 = GROUP1.contains(c2);
        boolean inGroup2C1 = GROUP2.contains(c1);
        boolean inGroup2C2 = GROUP2.contains(c2);

        if (inGroup1C1 && inGroup1C2) {
            return 1; // 同组替换
        } else if (inGroup2C1 && inGroup2C2) {
            return 1; // 同组替换
        } else if ((inGroup1C1 && inGroup2C2) || (inGroup2C1 && inGroup1C2)) {
            return 2; // 不同组替换
        } else {
            return 3; // 其他
        }
    }
}
    • 0
      @ 2024-10-25 16:29:11 
      s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0]*(m+1) for _ in range(n+1)]
w1 = 'wirel@com'
w2 = 'hfv#gbts'
def cal(a,b):
    if a == b:
        return 0
    elif (a in w1 and b in w1) or (a in w2 and b in w2):
        return 1
    elif (a in w1 and b in w2) or (a in w2 and b in w1):
        return 2
    else:
        return 3
def main():        #dp需要优化 但是加上main()函数可以加快速度
    for i in range(n+1):
        for j in range(m+1):
            if i==0 and j==0:
                dp[i][j]=0
            elif i==0:
                dp[i][j]=j*3
            elif j==0:
                dp[i][j]=i*3
            else:
                dp[i][j]=(i+j)*3

    for i in range(1,n+1):
        for j in range(1,m+1):
            dp[i][j] = min(dp[i][j],dp[i-1][j],dp[i][j-1])+3
            dp[i][j] = min(dp[i][j],dp[i-1][j-1]+cal(s[i-1],t[j-1]))
    print(dp[n][m])
if __name__ == '__main__':
    main()
      • 0
        @ 2024-10-17 21:55:41

        题目大意

        给定两个字符串 a 和 b，可以通过删除、插入和替换三种操作将字符串 a 转换为字符串 b。要求计算将字符串 a 转换为字符串 b 的最小代价

        思路

        该问题类似于编辑距离问题，因此可以考虑使用动态规划来解决。我们定义 dp[i][j] 表示将字符串 a 的前 i 个字符转换为字符串 b 的前 j 个字符的最小代价。

        边界情况 当 i 或 j 为 0 时，表示其中一个字符串为空，此时只能通过插入或删除操作将一个字符串转换为另一个。每次插入或删除的代价是 3，因此 dp[i][j] 的值为 (i + j) * 3。

        状态转移 状态转移可以分为三种情况：

        删除操作：将 a[i] 删除，那么转换成字符串 b 的代价为 dp[i-1][j] + 3。

        插入操作：向 a 中插入一个字符 b[j]，那么转换代价为 dp[i][j-1] + 3。

        替换操作：将 a[i] 替换为 b[j]，代价为 dp[i-1][j-1] + cal(a[i], b[j])。这里 cal 函数用于计算字符 a[i] 和 b[j] 的替换代价。

        计算替换代价 cal cal(a, b) 是用于计算两个字符替换代价的函数，规则如下： \\ 1.如果两个字符相同，替换代价为 0； \\ 2.如果两个字符都在字符串 s1（"wirel@com"）中，或者都在字符串 s2（"#hfv#gbts"）中，则替换代价为 1； \\ 3.如果一个字符在 s1 中，另一个字符在 s2 中，替换代价为 2； \\ 4.如果两个字符都不在上述字符集中，替换代价为 3；

        题目分析

        本题的目标是计算两个基站名字的相似度，可以通过动态规划方法来解决，类似于编辑距离问题。在编辑距离问题中，允许对字符串进行三种操作：增、删、改，每种操作都有不同的代价。题目要求通过最少的操作将一个基站名字转换为另一个基站名字，并输出最小得分。

        具体来说：

        • 插入一个字符，代价是 3 分；
        • 删除一个字符，代价也是 3 分；
        • 替换一个字符，替换的代价根据给定的分组规则不同，可能是 1 分、2 分或 3 分。

        解决思路

        动态规划是解决此类问题的有效方法。我们可以定义 dp[i][j] 表示将字符串 a 的前 i 个字符转换为字符串 b 的前 j 个字符的最小代价。

        边界条件

        1. 当 i 为 0 时，表示 a 是空字符串，此时只能通过插入操作将 b 的前 j 个字符依次插入进来，代价为 j * 3。
        2. 当 j 为 0 时，表示 b 是空字符串，此时只能通过删除操作将 a 的前 i 个字符依次删除，代价为 i * 3。

        状态转移方程

        对于任意的 dp[i][j]，可以通过三种操作转移得到：

        1. 删除操作：将 a[i] 删除，代价为 dp[i-1][j] + 3；
        2. 插入操作：向 a 中插入一个字符 b[j]，代价为 dp[i][j-1] + 3；
        3. 替换操作：将 a[i] 替换为 b[j]，代价为 dp[i-1][j-1] + cal(a[i], b[j])，其中 cal 是计算替换代价的函数。

        替换代价的计算（函数 cal）

        • 如果两个字符相同，替换代价为 0；
        • 如果两个字符都在组 s1（"wirel@com"）中，或者都在组 s2（"#hfv#gbts"）中，替换代价为 1；
        • 如果一个字符在组 s1，另一个字符在组 s2，替换代价为 2；
        • 如果两个字符都不在任何组内，替换代价为 3。

        动态规划表的初始化

        首先，我们将 dp 数组初始化为 (i+j)*3，表示在最坏的情况下，通过删除和插入操作将两个字符串互相转换的代价。

        动态规划的填表过程

        从 dp[1][1] 开始，通过上面三种操作的最小代价来更新 dp[i][j]。对于每个位置 (i, j)，我们根据前面已经计算好的状态，选择代价最小的一种操作来更新。

        复杂度分析

        • 时间复杂度：由于我们使用了双重循环填表，每次操作的时间复杂度是常数级别，因此总的时间复杂度为 O(n * m)，其中 n 是字符串 a 的长度，m 是字符串 b 的长度。
        • 空间复杂度：使用了一个大小为 2005 x 2005 的二维数组 dp，因此空间复杂度为 O(n * m)。

        代码如下

        cpp

        #include <bits/stdc++.h>
using namespace std;
string a, b;
int n, m;
// dp 表，用于存储从 a 到 b 的最小转换代价
int dp[2005][2005];
// 字符集，用于判断字符之间的替换代价
string s1 = "wirel@com", s2 = "#hfv#gbts";

// 计算字符 a 和 b 之间的替换代价
int cal(char a, char b) {
	// 如果两个字符相等，代价为 0
	if (a == b) return 0;
	// 如果两个字符都在 s1 中或都在 s2 中，代价为 1
	if (s1.find(a) != string::npos && s1.find(b) != string::npos) {
		return 1;
	}
	else if (s2.find(a) != string::npos && s2.find(b) != string::npos) {
		return 1;
	}
	// 如果一个字符在 s1 中，另一个字符在 s2 中，代价为 2
	else if (s2.find(a) != string::npos && s1.find(b) != string::npos) {
		return 2;
	}
	else if (s1.find(a) != string::npos && s2.find(b) != string::npos) {
		return 2;
	}
	// 其他情况下，代价为 3
	else {
		return 3;
	}
}

int main() {
	cin >> a >> b;
	n = a.length();
	m = b.length();
	a = ' ' + a;
	b = ' ' + b;
	
	// 初始化 dp 数组
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			// 如果 i 和 j 都为 0，即两个空字符串之间的代价为 0
			if (!i && !j)
				dp[i][j] = 0;
			// 如果 i 为 0，表示将空字符串变为 b 的前 j 个字符，代价为 j * 3（即插入 j 个字符）
			else if (!i)
				dp[i][j] = j * 3;
			// 如果 j 为 0，表示将 a 的前 i 个字符变为空字符串，代价为 i * 3（即删除 i 个字符）
			else if (!j)
				dp[i][j] = i * 3;
			// 否则初始化为 (i+j) * 3
			else
				dp[i][j] = (i + j) * 3;
		}
	}
	
	// 动态规划过程
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			// 计算 dp[i][j] 时，首先考虑插入和删除操作，选择三种操作中的最小值并加上代价 3
			dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i][j]}) + 3;
			// 然后考虑替换操作，使用 cal 函数计算替换代价
			dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + cal(a[i], b[j]));
		}
	}
	
	// 输出将字符串 a 转换为字符串 b 的最小代价
	cout << dp[n][m];
}

        python

        # 字符集，用于判断字符之间的替换代价
s1 = "wirel@com"
s2 = "#hfv#gbts"

# 计算字符 a 和 b 之间的替换代价
def cal(a, b):
    # 如果两个字符相等，代价为 0
    if a == b:
        return 0
    # 如果两个字符都在 s1 中或都在 s2 中，代价为 1
    if (a in s1 and b in s1) or (a in s2 and b in s2):
        return 1
    # 如果一个字符在 s1 中，另一个字符在 s2 中，代价为 2
    elif (a in s1 and b in s2) or (a in s2 and b in s1):
        return 2
    # 其他情况下，代价为 3
    else:
        return 3

def main():
    # 输入两个字符串
    a = input().strip()
    b = input().strip()

    # 获取字符串的长度
    n = len(a)
    m = len(b)

    # 初始化 dp 数组，大小为 (n+1) x (m+1)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # 初始化 dp 数组
    for i in range(n + 1):
        for j in range(m + 1):
            # 如果 i 和 j 都为 0，即两个空字符串之间的代价为 0
            if i == 0 and j == 0:
                dp[i][j] = 0
            # 如果 i 为 0，表示将空字符串变为 b 的前 j 个字符，代价为 j * 3（即插入 j 个字符）
            elif i == 0:
                dp[i][j] = j * 3
            # 如果 j 为 0，表示将 a 的前 i 个字符变为空字符串，代价为 i * 3（即删除 i 个字符）
            elif j == 0:
                dp[i][j] = i * 3
            # 否则初始化为 (i+j) * 3
            else:
                dp[i][j] = (i + j) * 3

    # 动态规划过程
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 计算 dp[i][j] 时，首先考虑插入和删除操作，选择三种操作中的最小值并加上代价 3
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i][j]) + 3
            # 然后考虑替换操作，使用 cal 函数计算替换代价
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + cal(a[i - 1], b[j - 1]))

    # 输出将字符串 a 转换为字符串 b 的最小代价
    print(dp[n][m])

if __name__ == "__main__":
    main()

        java

        import java.util.Scanner;

public class Main {
    static String s1 = "wirel@com";  // 用于判断字符替换代价的字符集 s1
    static String s2 = "#hfv#gbts";  // 用于判断字符替换代价的字符集 s2
    static int[][] dp = new int[2005][2005];  // dp 数组，存储最小转换代价

    // 计算字符 a 和 b 之间的替换代价
    public static int cal(char a, char b) {
        // 如果两个字符相等，代价为 0
        if (a == b) return 0;
        // 如果两个字符都在 s1 中或都在 s2 中，代价为 1
        if (s1.indexOf(a) != -1 && s1.indexOf(b) != -1) {
            return 1;
        } else if (s2.indexOf(a) != -1 && s2.indexOf(b) != -1) {
            return 1;
        }
        // 如果一个字符在 s1 中，另一个字符在 s2 中，代价为 2
        else if (s2.indexOf(a) != -1 && s1.indexOf(b) != -1) {
            return 2;
        } else if (s1.indexOf(a) != -1 && s2.indexOf(b) != -1) {
            return 2;
        }
        // 其他情况下，代价为 3
        else {
            return 3;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入两个字符串
        String a = sc.nextLine();
        String b = sc.nextLine();

        int n = a.length();
        int m = b.length();

        // 初始化 dp 数组
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                // 如果 i 和 j 都为 0，即两个空字符串之间的代价为 0
                if (i == 0 && j == 0) {
                    dp[i][j] = 0;
                }
                // 如果 i 为 0，表示将空字符串变为 b 的前 j 个字符，代价为 j * 3（即插入 j 个字符）
                else if (i == 0) {
                    dp[i][j] = j * 3;
                }
                // 如果 j 为 0，表示将 a 的前 i 个字符变为空字符串，代价为 i * 3（即删除 i 个字符）
                else if (j == 0) {
                    dp[i][j] = i * 3;
                }
                // 否则初始化为 (i+j) * 3
                else {
                    dp[i][j] = (i + j) * 3;
                }
            }
        }

        // 动态规划过程
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 计算 dp[i][j] 时，首先考虑插入和删除操作，选择三种操作中的最小值并加上代价 3
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i][j]) + 3;
                // 然后考虑替换操作，使用 cal 函数计算替换代价
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + cal(a.charAt(i - 1), b.charAt(j - 1)));
            }
        }

        // 输出将字符串 a 转换为字符串 b 的最小代价
        System.out.println(dp[n][m]);
    }
}
        • 1

        2024.10.9-秋招(留学生)-第1题-无线基站名字相似度

        Information

        ID
        139
        Time
        1000ms
        Memory
        256MiB
        Difficulty
        5
        Tags
        # Submissions
        524
        Accepted
        59
        Uploaded By
        1. About
        2. Contact Us
        3. Privacy
        4. Terms of Service
        5. Copyright Complaint
        6. Language
        7. Legacy mode
        8. Theme
        2. 湘ICP备2023007293号
        3. Worker 0, 23ms
        4. Powered by Hydro v4.14.1 Community