圣诞节仍在学习，真是扎心了啊老铁们。

分饼干（排序贪心）

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

思路：每个要把饼干尽可能多的分配给更多的小朋友，就应该给最小的小朋友刚刚好的分量，如果没有，就分配多一点的分量。只有这样才能让更多的小朋友被分到饼干，意即贪心思想。先排序，再分饼干。
AC代码如下

class LeetCode455 {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int j=0;
        for (int i = 0; i <g.length ; i++,j++) {
            //找到最适合分给小朋友的那块饼干
            while (j<s.length&&s[j]<g[i]){
                j++;
            }
            if (j>=s.length){
                //没有饼干可以再分给这个小朋友了。返回。
                return i;
            }
        }
        //所有小朋友都分到了饼干。
        return g.length;
    }
}

切蛋糕（回溯）

切分酥饼的时候，要求切分后每一块上面的草莓个数都不相同。假设切分出来的 NN 块酥饼上要各有 “ 1~N 个（共 N(N+1)÷2 个草莓）”。

但这里要追加一个条件，那就是 “一定要使相邻的两块酥饼上的数字之和是平方数”。

举个例子，假设 N＝4 时采用如图 11 的切法。这时，虽然 1+3＝4 得到的是平方数，但 “1 和 4” “2 和 3” “2 和 4” 的部分都不满足条件（图 1）。

图 1 不满足条件的切法示例
编写cutCake函数。如果有答案返回答案数组，没有则返回空。
AC代码如下

class CutCake{
    public int[] cutCake(int n){
        int[] res = new int[n];
        int[] originalNum = new int[n];
        for (int i = 0; i <n ; i++) {
            originalNum[i]=i+1;
        }
        //System.out.println(Arrays.toString(originalNum));
        res[0]=1;
        boolean[] isUsed = new boolean[n];
        Arrays.fill(isUsed,false);
        isUsed[0]=true;
        if(cutCakeBfs(originalNum,1,res,isUsed)){
            System.out.println("There is an answer");
            return res;
        }
        return new int[0];

    }
    public boolean cutCakeBfs(int[] originalNum,int i,int[] res,boolean[] isUsed){
            for (int j = 1; j <originalNum.length ; j++) {
                if (!isUsed[j]){
                    if (isSqrtNumber(originalNum[j]+res[i-1])){
                        //保存现场
                        int temp=res[i];
                        res[i]=originalNum[j];
                        isUsed[j]=true;
                        if (i==res.length-1){
                            if (isSqrtNumber(res[res.length-1]+res[0])){
                                return true;
                            }
                        }
                        if(cutCakeBfs(originalNum,i+1,res,isUsed)){
                            return true;
                        }
                        //还原
                        res[i]=temp;
                        isUsed[j]=false;
                    }
                }
            }

        return false;
    }
    public boolean isSqrtNumber(int number){
        //有待优化。只需要初始化一次列表即可。
        HashSet<Integer> sqrts = new HashSet<>();
        for (int i = 2; i <=8 ; i++) {
            sqrts.add(i*i);
        }
        return sqrts.contains(number);
    }

}