题解 | #牛群喂食#

牛群喂食

https://www.nowcoder.com/practice/591c222d73914c1ba031a660db2ef73f

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param candidates int整型一维数组
     * @param target int整型
     * @return int整型二维数组
     */
    private final List<List<Integer>> list = new ArrayList<List<Integer>>();
    public int[][] cowCombinationSum (int[] candidates, int target) {
        dfs(candidates, target, 0, 0, new ArrayList<Integer>());
        int length = list.size();
        int[][] result = new int[length][];
        for (int i = 0; i < length; i++) {
            List<Integer> l = list.get(i);
            int[] arr = new int[l.size()];
            for (int j = 0; j < l.size(); j++) {
                arr[j] = l.get(j);
            }
            result[i] = arr;
        }
        return result;
    }

    public void dfs(int[] candidates, int target, int index, int sum,
                    List<Integer> currentList) {
        if (sum == target) {
            // 当和等于目标值时,将当前路径添加到全局列表中
            list.add(new ArrayList<Integer>(currentList));
            return;
        }
        // 当前索引超过数组长度或当前和大于目标值 终止条件
        if (index >= candidates.length || sum > target) {
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            if (currentList.size() > 0) {
                // 判断当前元素是否小于等于前一个元素,如果是,则跳过该元素,避免重复组合
                int pre = currentList.get(currentList.size() - 1);
                if (pre > candidates[i]) {
                    continue;
                }
            }
            // 将当前元素添加到路径中
            currentList.add(candidates[i]);
            sum += candidates[i];
            // 递归搜索下一个位置
            dfs(candidates, target, index, sum, currentList);
            // 回溯删除最后一个元素
            currentList.remove(currentList.size() - 1);
            // 回溯还原当前和
            sum -= candidates[i];
        }
    }
}

知识点:

1.递归+回溯

2.集合转数组

3.数组遍历

4.数学模拟

解题分析:

1. 当和等于目标值时,将当前路径添加到全局列表中

2.当前索引超过数组长度或当前和大于目标值 终止条件

3.判断当前元素是否小于等于前一个元素,如果是,则跳过该元素,避免重复组合(穷举的剪枝操作)

4.将当前元素添加到路径中

5.递归搜索下一个位置

6.回溯删除最后一个元素

7.回溯还原当前和

编程语言:

Java

全部评论

相关推荐

迷茫的大四🐶:自信一点,我认为你可以拿到50k,低于50k完全配不上你的能力,兄弟,不要被他们骗了,你可以的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务