题解 | #牛吃草问题# java
牛吃草问题
https://www.nowcoder.com/practice/c6e33216019a4ea9bf4015e9868dd225
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ public int totalNCow (int n) { // write code here int[] cols = new int[n]; // 记录每一行中放置牛的列索引 Arrays.fill(cols, -1); int[] count = new int[1]; backtrack(cols, 0, count); return count[0]; } private void backtrack(int[] cols, int row, int[] count) { int n = cols.length; if (row == n) { // 放置的牛的数量等于 n,说明找到一个有效的放置方案 count[0]++; return; } for (int col = 0; col < n; col++) { if (isValid(cols, row, col)) { cols[row] = col; // 尝试将牛放置在当前位置 backtrack(cols, row + 1, count); // 继续放置下一头牛 cols[row] = -1; // 回溯,将当前位置的牛移除,尝试下一个位置 } } } private boolean isValid(int[] cols, int row, int col) { for (int i = 0; i < row; i++) { if (cols[i] == col || Math.abs(cols[i] - col) == Math.abs(i - row)) { return false; // 当前位置与前面已放置的牛存在冲突,不满足条件 } } return true; // 当前位置满足条件,可以放置牛 } }
编程语言是Java。
该题考察的知识点是回溯法
回溯法函数backtrack
用于搜索所有可能的放置方案。在每一行中,通过遍历列的索引来尝试将牛放置在不冲突的位置上。如果当前位置满足条件,就将牛放置在该位置,然后继续递归地放置下一头牛。当放置的牛的数量等于n时,说明找到一个有效的放置方案,将结果计数器count加1并返回。如果尝试的位置不满足条件,就进行回溯,将当前位置的牛移除,尝试下一个位置。
函数isValid
用于检查当前位置是否满足条件,即在同一列或同一对角线上没有其他已放置的牛。