Java 题解 | #牛群排队#
牛群排队
https://www.nowcoder.com/practice/8d8ae3937cd5466eb330ca484ca5ed80
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型二维数组 */ public int[][] cow_permute (int[] nums) { // write code here List<List<Integer>> res = new ArrayList<>(); List<Integer> numList = new ArrayList<>(); for (int num : nums) { numList.add(num); } Collections.sort(numList); backTracking(numList, new ArrayList<>(), res); int[][] ans = new int[res.size()][nums.length]; for (int i = 0; i < res.size(); i++) { for (int j = 0; j < nums.length; j++) { ans[i][j] = res.get(i).get(j); } } return ans; } private void backTracking(List<Integer> nums, List<Integer> list, List<List<Integer>> res) { if (list.size() == nums.size()) { res.add(new ArrayList<>(list)); return; } for (int i = nums.size() - 1; i >= 0; i--) { if (list.contains(nums.get(i))) { continue; } list.add(nums.get(i)); backTracking(nums, list, res); list.remove(list.size() - 1); } } }
编程语言是Java。
该题考察的知识点是回溯算法,通过递归和回溯的方式生成给定数组的全排列。
代码简短的文字解释如下:
- 将传入的整型数组转换为列表形式,并进行排序。
- 创建一个空的列表 res 用于存储结果。
- 调用 backTracking 方法进行回溯,传入原始列表 nums、一个空列表作为当前排列的中间结果,以及结果列表 res。
- 在 backTracking 方法中,首先判断如果中间结果列表长度等于原始列表长度,说明已经生成了一个完整的排列,将其加入结果列表中,然后返回。
- 遍历原始列表 nums,从后往前依次取出数字。如果当前数字已经在中间结果列表中,则跳过。
- 将当前数字添加到中间结果列表中。
- 递归调用 backTracking 方法,继续生成下一个数字的排列。
- 每次递归返回后,将中间结果列表的最后一个数字移除,以便尝试下一个数字的组合。
- 最后将结果列表 res 转换为二维数组,并返回结果。