网站制作的公司有哪些,wordpress修改html代码,上海公司名字查询,中国互联网协会投诉平台455 分配cookies
小白渣翻译#xff1a;
假设你是一位很棒的父母#xff0c;想给你的孩子一些饼干。但是#xff0c;你最多应该给每个孩子一块饼干。
每个孩子 i 都有一个贪婪因子 g[i] #xff0c;这是孩子满意的 cookie 的最小大小#xff1b;每个 cookie j 都有一个…455 分配cookies
小白渣翻译
假设你是一位很棒的父母想给你的孩子一些饼干。但是你最多应该给每个孩子一块饼干。
每个孩子 i 都有一个贪婪因子 g[i] 这是孩子满意的 cookie 的最小大小每个 cookie j 都有一个大小 s[j] 。如果 s[j] g[i] 我们可以将 cookie j 分配给孩子子 i 。你的目标是最大化内容子项的数量并输出最大数量。
例子 这里是小白理解 思考1这题目描述很诡异另外就是限制也会诡异导致我们感觉就是一道简单的array题目但是乍一看确实不太懂他的意思。
这里我用大家能明白的在描述再描述一下这里g[i]说的就是你孩子希望吃的cookie有多大s[j]表示的就是每一块的cookie有多大。
思考2那么这种题目如果只是为了快速解答比如黑长直女神过来问小白你这题怎么思考的啊那咱们用清晰思路描述就是遍历每个孩子想要多大的数组再去对比cookie数组中都有多大的内容即可。 黑长直OS小伙子可以啊这不仅逻辑感人阅读理解也有俩下子
真正面试环节
面试官你可以解答这道”分配饼干“的题目吗来满足这些熊孩子
小白嘿嘿这不巧了么这不是 public int findContentChildren(int[] g, int[] s) {// 初始化满足要求的孩子数量int count 0;// 遍历 cookie 数组for (int i 0; i s.length; i) {// 尝试将当前饼干分配给 g 数组中的每个孩子for (int j 0; j g.length; j) {// 如果分配成功那么满足要求的孩子数量加 1if (g[j] s[i]) {count;break;}}}return count;}小明OK完事儿等着面试官来表扬自己吧。他肯定会说小子你是个好手工位都给你准备好了工资你说了算。
面试官嗯你这个要是g 和 s 给了 3 ∗ 1 0 4 3 * 10^4 3∗104个数是不是会影响性能
小明OS今年这个找工市场人言洛阳花似锦偏我来时不逢春。。。不是这谁能生 3 ∗ 1 0 4 3 * 10^4 3∗104个孩子去
好吧逼我拿出压箱底的东西是吧。的确这个算法是偏慢既然是贪心的熊孩子那就试试用贪心算法试试
public int findContentChildren(int[] g, int[] s) {// 数组s的长度即cookies的数量int cookiesNums s.length;// cookies为零返回0if(cookiesNums 0) return 0;// 对 g 与 s 数组进行排序Arrays.sort(g);Arrays.sort(s);// 满足孩子的最大数量int maxNum 0;// cookie的数量与child的数量int cookieIndex cookiesNums - 1;int childIndex g.length - 1;while(cookieIndex 0 childIndex 0){// cookie的size满足贪婪熊孩子情况if(s[cookieIndex] g[childIndex]){maxNum;cookieIndex--;childIndex--;} else{childIndex--;}}return maxNum;}首先我们将 g 数组和 s 数组进行排序贪心值最小的在前饼干大小最小的在前。然后我们从 g 数组的头部开始遍历从 s 数组的头部开始遍历。如果当前孩子的贪心值小于当前饼干的大小那么我们满足该孩子的要求并将该孩子从 g 数组中删除。否则我们无法满足该孩子的要求。重复步骤 3 和步骤 4直到 g 数组为空。
好了时间复杂度O(nlogN)了下一面继续 编码道路漫漫只要先看脚下的路徐徐前进即可。
