春招学习第一天。(1/30)
圣诞节仍在学习,真是扎心了啊老铁们。
分饼干(排序贪心)
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 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); } }