题目描述：
汪仔和他朋友，分别做选择题，选择题有 n 道，汪仔做的答案用 str1 表示，朋友做的答案用 str2 表示，现在给定一个 K 值，K 值指的是朋友的答案与真正的答案（这些题的真实答案，你不知道）相比较时，对的个数。求：小明的答案，与真实的答案相比较，最多能对几个？最少能对几个？
输入：
n 表示题目个数，k 表示朋友的答案正确的个数，str1 表示汪仔的答案，str2 表示汪仔朋友的答案。
返回值用给定的内部类表示。
示例2：
输入：
3, 1, "ABC", "DDD"
输出：
[0, 2]
说明：汪仔最少对 0 道，最多对 2 道，因为朋友 "DDD" 对了 1 道，所以正确答案里面至少有一个 D，而汪仔一个 D 都没有，所以最多对 2 道。
思路一：
一拿到题，就想的是用枚举、DFS深搜遍历的方法，穷举正确答案，将穷举的正确答案，与汪仔朋友的答案比较，当朋友正确个数刚好为 K 时，我们可以假设这个答案就是有效的正确答案，再用这个穷举的答案与小明的答案挨个比较，将得到的正确个数与已知结果比较，比最小值小，则更新最小值；比最大值大，则更新最大值。
错误的方法：这种方法 没有AC！！！（时间复杂度太高了，4^n 的穷举情况，复杂度太高）
class Interval { int start; int end; } public class souGou1 { public static Interval interval = new Interval(); //保存结果的类对象 public static void main(String[] args) { Interval res = solve(3,1,"ABC","DDD"); //测试数据 System.out.println(res.start); System.out.println(res.end); } public static Interval solve (int n, int k, String str1, String str2) { char[] chars = new char[n]; //用来穷举的答案数组 for(int i = 0; i < str1.length(); i++) chars[i] = 'A'; interval.start = Integer.MAX_VALUE; //汪仔最少的答案个数, 初始设置为一个很大的数 interval.end = 0; //汪仔最多的答案个数, 初始设置为一个很小的数 if(str1.equals(str2)){ //当汪仔的答案与朋友的一模一样时，最小最大都为k interval.start = k; interval.end = k; return interval; } DFS(chars,str1.toCharArray(),str2.toCharArray(),k,0); //深搜穷举 return interval; } public static void DFS(char[] chars, char[] str1, char[] str2, int k, int idx){ //chars表示穷举的答案，str1汪仔的答案，str2朋友的答案，k 朋友对的个数，idx表示穷举到哪一个下标了 if(idx == chars.length){ //穷举的一次答案 int count = 0, ansCount = 0; // count 表示朋友的正确个数，ansCount表示汪仔的正确个数 for(int i = 0; i < str2.length; i++){ if(chars[i] == str2[i]) count++; if(chars[i] == str1[i]) ansCount++; } if(count != k) return; //当朋友的正确个数与题目给的 k 值不相等，说明这个穷举的答案无效，返回 if (ansCount < interval.start) interval.start = ansCount; if(ansCount > interval.end) interval.end = ansCount; return; } chars[idx] = 'A'; // 当前的 idx 位置上，穷举 A,B,C,D 四个可能的答案 DFS(chars,str1,str2,k,idx+1); if(interval.start == 0 && interval.end == chars.length) return; //减枝 chars[idx] = 'B'; DFS(chars,str1,str2,k,idx+1); if(interval.start == 0 && interval.end == chars.length) return; //减枝 chars[idx] = 'C'; DFS(chars,str1,str2,k,idx+1); if(interval.start == 0 && interval.end == chars.length) return; //减枝 chars[idx] = 'D'; DFS(chars,str1,str2,k,idx+1); } }
但是：提交 OJ，显示通过率只有 40%，这种办法没有 AC ！
思路二：
将汪仔的答案，与朋友的答案比较，记录他们的答案中，相同的个数 count ，利用这个 count 与 k 即可直接求得结果。求最大值，当 k <= count 时，汪仔最多对： k + (n - count) 道；当 k > count 时，汪仔最多对：count + n - k 道。同理，求最小值，计算 k - (n - count) 的值，当结果 <= 0 时，最小值 = 0；当结果 > 0时，最小值 = k - (n - count) . 这个推导式有点绕，很不容易想明白。
正确方法：直接利用关系推导式，直接得出结果！
class Interval { int start; int end; } public class souGou1 { public static void main(String[] args) { Interval res = solve(3,3,"ABC","ABC"); //测试数据 System.out.println(res.start); System.out.println(res.end); } public static Interval solve (int n, int k, String str1, String str2) { Interval res = new Interval(); int count = 0, min, max; //正确的答案个数最小值、最大值 for(int i = 0; i < n; i++){ if(str1.charAt(i) == str2.charAt(i)) count++; //记录相等的个数 count } int tmp = k - (n - count); min = tmp <= 0? 0 : tmp; // 得到最小值 if(k <= count) max = k + (n - count); // 最大值分类讨论 else max = count + n - k; res.start = min; //写入对象中 res.end = max; return res; // 返回结果 } }