首页 > 代码库 > 微软2017校招笔试题2 composition
微软2017校招笔试题2 composition
题目
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.
给定一个由小写字母组成的字符串，规定某些字符不能相邻。求最少需要删除多少个字符使得剩下的字符串中不存在那些规定不能相邻的字符相邻。
解法
字符串中的字符只有26种可能，去除某些字符剩余的字符串只能以a-z这些字符结尾，如果记录 dp[c]表示以 字符 c+‘a‘ 结尾的字符串的最长长度，则可以有递推公式
dp[ch] = max(dp[ch], dp[t] + 1) t为a-z，且t和ch可以相邻。这样，在从头到尾扫描完一遍字符串，得到dp数组之后，最少需要删除的字符的个数就等于 n(原来字符串长度) - max(dp[c]).
#include<stdio.h> #include<string>#include<iostream>#include<algorithm>#include<functional>#include<queue>#include<vector>#include<set>#include<list>#include<unordered_map>#include<unordered_set>#include<stack>#include<map>#include<algorithm>#include<string.h>using namespace std;char str[1000005];int dp[26];int n;bool table[26][26];int main(){ scanf("%d", &n); scanf("%s", str); memset(dp, -1, sizeof(dp)); int k; scanf("%d", &k); char word[4]; for (int i = 0; i < k; i++){ scanf("%s", word); table[word[0] - ‘a‘][word[1] - ‘a‘] = true; table[word[1] - ‘a‘][word[0] - ‘a‘] = true; } for (int i = 0; i < n; i++){ int cur = str[i] - ‘a‘; int tmp = 1; for (int j = 0; j < 26; j++){ if (table[cur][j]) continue; tmp = max(tmp, dp[j] + 1); } dp[cur] = tmp; } int tmp = 0; for (int i = 0; i < 26; i++) tmp = max(tmp, dp[i]); printf("%d\n", n - tmp); return 0;}
微软2017校招笔试题2 composition
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。