C语言/数据结构贪心算法题解：字符串趋同——逐位统计最高频率求最小修改代价

问题描述小明的学校正在举办一场“字符串趋同”游戏每个班级需要将自己的字符串通过最少次数的字符修改操作变得完全相同。每位同学初始有一个由小写字母组成的字符串每次操作可以选择任意一位同学修改其字符串中的任意一个字符可以改为任意小写字母。但是每次修改的代价为1不同位置的修改代价独立计算。作为班级的算法小能手小明需要设计一个高效的算法来计算让所有字符串趋同的最小总代价。注意最终所有字符串必须完全相同可以是任意由小写字母组成的字符串不限于原始字符串之一且长度保持不变不允许增删字符只能修改。要求设计一个时间复杂度为 O(n * m) 的算法其中 n 是字符串数量m 是每个字符串的长度假设所有字符串长度相同。尽量减少额外空间的使用以体现算法优化能力。测试样例样例1输入strs [abc, adc, aec]输出2解释对于每个位置独立计算最小修改代价位置0所有字符都是 a不需要修改代价0位置1字符有 b,d,e出现次数最多的是任意字符但频率均为1最小代价为 3 - 1 2即需要修改2个字符位置2所有字符都是 c不需要修改代价0 总最小代价为 0 2 0 2。样例2输入strs [a, b, c]输出2解释只有一个位置字符为 a,b,c每个字符出现1次。最小代价为 3 - 1 2即需要修改2个字符。样例3输入strs [hello, hello, hello]输出0解释所有字符串已经相同每个位置字符都相同修改代价均为0。约束条件1 ≤ strs.length ≤ 1001 ≤ strs[i].length ≤ 100所有字符串长度相同字符串仅由小写英文字母组成提示考虑对字符串的每个位置独立处理。对于每个位置统计该位置上所有字符的出现频率选择出现频率最高的字符作为目标字符则该位置的最小修改代价为 n - max_frequency其中 n 是字符串数量。总最小代价是所有位置的最小修改代价之和。程序代码#include stdio.h#include stdlib.h#include string.hint minCost(char** strs, int strsSize) {if (strsSize 1) return 0;int n strsSize;int m strlen(strs[0]);int totalCost 0;// 逐位处理for (int j 0; j m; j) {int count[26] {0};// 统计该位置各字符频率for (int i 0; i n; i) {count[strs[i][j] - a];}// 找最大频率int maxFreq 0;for (int k 0; k 26; k) {if (count[k] maxFreq) {maxFreq count[k];}}// 该位置代价 n - maxFreqtotalCost n - maxFreq;}return totalCost;}int main() {char* strs1[] {abc, adc, aec};printf(%d\n, minCost(strs1, 3)); // 2char* strs2[] {a, b, c};printf(%d\n, minCost(strs2, 3)); // 2char* strs3[] {hello, hello, hello};printf(%d\n, minCost(strs3, 3)); // 0return 0;}#include stdio.h #include stdlib.h #include string.h int minCost(char** strs, int strsSize) { if (strsSize 1) return 0; int n strsSize; int m strlen(strs[0]); int totalCost 0; // 逐位处理 for (int j 0; j m; j) { int count[26] {0}; // 统计该位置各字符频率 for (int i 0; i n; i) { count[strs[i][j] - a]; } // 找最大频率 int maxFreq 0; for (int k 0; k 26; k) { if (count[k] maxFreq) { maxFreq count[k]; } } // 该位置代价 n - maxFreq totalCost n - maxFreq; } return totalCost; } int main() { char* strs1[] {abc, adc, aec}; printf(%d\n, minCost(strs1, 3)); // 2 char* strs2[] {a, b, c}; printf(%d\n, minCost(strs2, 3)); // 2 char* strs3[] {hello, hello, hello}; printf(%d\n, minCost(strs3, 3)); // 0 return 0; }运行结果