本文主要是介绍[华为OD] C卷 田忌赛马 DFS 200，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
给定两个只包含数字的数组a, b,调整数组a里面数字的顺序，使得尽可能多的a[i] >b[i]。
数组a和b中的数字各不相同。
输出所有可以达到最优结果的a数组的数量
输入描述
输入的第一行是数组a中的数字，其中只包含数字，每两个数字之间相隔一个空格，a数组大
小不超过10
输入的第二行是数组b中的数字，其中只包含数字，每两个数字之间相隔一个空格，b数组大
小不超过10
输出描述
输出所有可以达到最优结果的a数组数量
示例1：
输入：
11 8 20
10 137
输出：
1
说明：
最优结果只有一个，a =[11,20,8],故输出1
示例2：
输入：
11 12 20
10 13 7
输出：
2
说明：
有两个a数组的排列可以达到最优结果［ 12,20,11］ 和[11,20,12］ ,故输出2。
题解：
首先最优解。这个可以参考letcode这个题目：. - 力扣（LeetCode）
田忌赛马。
这边因为数组大小不超过10，所以可以采用DFS暴利解法，把所有的数据都拿到比较，然后找出最优解的个数就可以了。
关于DFS，可以看下这个视频，就能理解了。dfs(迷宫求解代码实现）_哔哩哔哩_bilibili
代码
import java.util.*;public class OverCountNum {private static Map<Integer, Integer> countMap = new HashMap<>();private static List<Integer> countList = new ArrayList<>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);String aNumString[] = sc.nextLine().split(" ");String bNumString[] = sc.nextLine().split(" ");int aNum[] = new int[aNumString.length];int bNum[] = new int[bNumString.length];int aLength = aNumString.length;int bLength = bNumString.length;int visit[] = new int[aLength];for (int i = 0; i < aLength; i++) {aNum[i] = Integer.valueOf(aNumString[i]);visit[i] = 0;}for (int i = 0; i < bLength; i++) {bNum[i] = Integer.valueOf(bNumString[i]);}int result[] = new int[aLength];dfs(0,result,aNum,bNum,aLength,visit);Collections.sort(countList);System.out.println(countMap.get(countList.get(countList.size()-1)));}private static void dfs(int currentPos, int[] result, int[] aNum, int[] bNum, int aLength, int[] visit) {if (currentPos == aLength) {countCountMap(result,bNum);return;}int i = 0;while (i < aLength) {if (i >= aLength) {break;}if (visit[i] == 0) {visit[i] = 1;result[currentPos] = aNum[i];dfs(currentPos + 1, result, aNum, bNum, aLength, visit);visit[i] = 0;}i++;}}private static void countCountMap(int[] result, int[] bNum) {int count = 0;for (int i = 0; i < result.length; i++) {if (result[i] > bNum[i]) {count++;}}if (countMap.containsKey(count)) {countMap.put(count, countMap.get(count) + 1);} else {countMap.put(count, 1);}if (!countList.contains(count)) {countList.add(count);}}
}
验证：
这篇关于[华为OD] C卷 田忌赛马 DFS 200的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
