java超难编程题 挑战一下吧 大神帮吗发代码

描述
Alice writes an English composition with a length of N characters. However, her teacher requires that M illegal pairs of characters cannot be adjacent, and if 'ab' cannot be adjacent, 'ba' cannot be adjacent either.

In order to meet the requirements, Alice needs to delete some characters.

Please work out the minimum number of characters that need to be deleted.

输入
The first line contains the length of the composition N.

The second line contains N characters, which make up the composition. Each character belongs to 'a'..'z'.

The third line contains the number of illegal pairs M.

Each of the next M lines contains two characters ch1 and ch2,which cannot be adjacent.

For 20% of the data: 1 ≤ N ≤ 10

For 50% of the data: 1 ≤ N ≤ 1000

For 100% of the data: 1 ≤ N ≤ 100000, M ≤ 200.

输出
One line with an integer indicating the minimum number of characters that need to be deleted.
图片说明
样例提示
Delete 'a' and 'd'.

6个回答

自己顶一下 求大神发java代码 或者说思路啊

很简单的题目,你不会做一定是上课没有听。基础知识基本技能还是要掌握的。

一个循环=》 search 查找,找到的话删除返回的索引的那个字符, 循环,完了,

huashikui
人家叫我大花猫 要保证删除的是最少的啊 不是删了就完了
接近 4 年之前 回复

解释见代码注释,明白dp表示的啥应该就能理解了
方法一:TLE
import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String str = scanner.next();
int m = scanner.nextInt();
boolean[][] concurrency = new boolean[26][26];
for (int i = 0; i < m; i++) {
String str1 = scanner.next();
concurrency[str1.charAt(0) - 'a'][str1.charAt(1) - 'a'] = true;
concurrency[str1.charAt(1) - 'a'][str1.charAt(0) - 'a'] = true;
}
solve(str, concurrency);
}
public static void solve(String str, boolean[][] concurrency) {
int n = str.length();
int[] dp = new int[n]; // dp[i]表示以i结尾的最长子满足条件子序列的长度
Arrays.fill(dp, 1);
char[] chars = str.toCharArray();
int res = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (!concurrency[chars[i] - 'a'][chars[j] - 'a']) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(dp[i], res);
}
System.out.println(n - res);
}
}

方法二:AC

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String str = scanner.next();
int m = scanner.nextInt();
boolean[][] concurrency = new boolean[26][26];
for (int i = 0; i < m; i++) {
String str1 = scanner.next();
concurrency[str1.charAt(0) - 'a'][str1.charAt(1) - 'a'] = true;
concurrency[str1.charAt(1) - 'a'][str1.charAt(0) - 'a'] = true;
}
solve(str, concurrency);
}
public static void solve(String str, boolean[][] concurrency) {
int n = str.length();
int[][] dp = new int[n][26]; // dp[i][j]表示前i个字符的子串以('a' + j)结尾的最长子序列长度
char[] chars = str.toCharArray();
dp[0][chars[0] - 'a'] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < 26; j++) {
dp[i][j] = dp[i - 1][j];
}
int curIndex = chars[i] - 'a';
dp[i][curIndex] = 1;
for (int k = 0; k < 26; k++) {
if (!concurrency[k][curIndex]) {
dp[i][curIndex] = Math.max(dp[i][curIndex], dp[i - 1][k] + 1);
}
}
}
int res = 0;
for (int i = 0; i < 26; i++) {
res = Math.max(res, dp[n - 1][i]);
}
System.out.println(n - res);
}
}

楼上的答案也是神了,注意看题好吧2333
既然要求最少删除次数,那么其实是求这个串中的最长满足条件的子序列长度,用n减去即可。
那么设f(i)表示以第i个位置的字母为首的最长合法子序列长度,f(i)=max(f(j)+1),其中j为i之后的且满足条件的字符。
因为对每个字母的转移只需要转移到离i最近的位置,故总复杂度为O(26n)。
至于找最近的字符,将每个字母的位置排序,转移的时候顺便移动标记即可。

u012345506
wynist 回复祈祷爱绝缘: 删除之后得到的串必然是原串的一个合法子序列,所以只需要求出最长的合法子序列x,结果即为n-x。对于你给出的bbbbabbbb,显然求得的是bbbbbbbb。
接近 4 年之前 回复
dfsdffe
祈祷爱绝缘 感觉好像,是我理解错了?0 0找到一个C写的代码,和你说的好像一样。http://blog.csdn.net/u014737310/article/details/52782482
接近 4 年之前 回复
dfsdffe
祈祷爱绝缘 楼上两个回答确实很神。。但是吧,我英语不大好还是你太大意了,我怎么感觉你好像理解错题意了,哈哈哈。题目的要求应该是让删除最少数量的字母,使得这个串满足条件,而不是直接把不合法的全都删了。按你这样说,在字符串中间出现了不合法字符组合,你直接把一半的内容全删了不合适吧。。比如:bbbbabbbb,不合法字符组合是ab,应该只需要删掉a就可以了,不知道我理解的对不对。。
接近 4 年之前 回复

http://hihocoder.com/discuss/question/3960

感觉这个大神的代码才是靠谱的,好多人题意都理解错了还到处贴代码,也是醉了。。
像这个大神说的,dp[i][j] 表示将前i个字符搞成满足条件的子序列而且最后一个字符是j,最少需要删的个数,这样更新就可以了。到最后把需要删除的最少的个数输出就是正确答案。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问