每日一题（回溯）

①、题目

饼干：

力扣https://leetcode.cn/problems/assign-cookies/

路径：

力扣https://leetcode.cn/problems/all-paths-from-source-to-target/

---

②、解题

饼干：

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        //尽量满足胃口小的小孩，并在此基础上尽量用小的饼干
        Arrays.sort(g);
        Arrays.sort(s);
        int answer=0;
        
        for (int i=0,j=0; i < g.length && j < s.length; j++) {
            if (g[i]<=s[j]){
                answer++;
                i++;
            }
        }
        
    return answer;
    }
}

 路径：

class Solution {
    private int[][] graph;
    private List<List<Integer>> answer=new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        this.graph=graph;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(0);
        dfc(0,list);
        return answer;
    }

    private void dfc(int a,List<Integer> temp){
        //来到第n-1个节点：满足，终止
        if (a==graph.length-1)
            //不能直接将temp添加，否则此后temp变化，answer里面也跟着变
            //因为二者指向同一个地址
            answer.add(new ArrayList<Integer>(temp));

        for (int i = 0; i < graph[a].length; i++) {
            temp.add(graph[a][i]);
            dfc(graph[a][i],temp);
            //回溯：
            temp.remove(temp.size()-1);

        }

    }
}

---

③、运行截图

 

 

---