Google : LAMB分发测试7错误
我有关于Google第2级的第一个问题，问题是：
做个跟班可不全是苦差事。偶尔，当感到慷慨的时候，指挥官兰伯达会给幸运的羔羊(兰伯达的万能金钱雄鹿)。追随者可以用幸运的羊羔买第二双袜子，枕头作为他们的铺位，甚至第三天的饭！
然而，实际上分发羊羔并不容易。每个亲信队伍都有严格的资历等级，这必须得到尊重--否则，这些追随者就会反抗，你们都会再次被降职为奴才！
为了避免叛乱，你必须遵守四条关键规则: 1.最低级的追随者(资历最少的)只有一只羔羊。(队里总会有至少一名追随者) 2.如果排在他们前面的人得到的羔羊数量是他们的两倍以上，那么一个追随者就会反抗。3.如果给下两个下属的羔羊加起来的数量超过了他们得到的羔羊的数量，那么一个亲信就会反抗。(请注意，两个最低级的追随者不会有两个下属，所以这条规则不适用于他们。4.你总能找到更多的仆人--指挥官有很多雇员。如果剩下足够多的羔羊，那么在遵守其他规则的同时，还可以增加另一个亲信为最高级的，那么你就必须不断地增加并付钱给那个亲信。
请注意，您可能无法分发所有的羔羊。一只羔羊不能再细分。也就是说，所有的追随者都必须得到一个正整数的羔羊数。
编写一个名为“解决方案”( total_lambs )的函数，其中total_lambs是您试图除以的讲义中羊羔的整数。它应该返回一个整数，表示能够分享羊羔的最小和最大数目的区别(也就是说，尽可能慷慨地对待你付出的人和尽可能吝啬的人)，同时仍然遵守上述所有规则以避免叛乱。例如，如果你有10只羔羊，并且尽可能慷慨的话，你只能支付3只追随者(1，2，4只羔羊，按等级排列)，而如果你吝啬的话，你可以付给4名追随者(1，1，2和3只羔羊)。因此，解(10)应该返回4-3 = 1。
为了保持有趣的事情，指挥官Lambda改变了幸运羔羊支付的大小。您可以期望total_lambs总是小于10亿(10 ^ 9)的正整数。
我的代码：
public class Solution {
public static int solution(int total_lambs) {
// person 1 gets 1 lamb
// person 2 gets more than 1 lamb
// person 3 gets more than or = person 1 + person 2 but less or = than double person 2
// person 4 gets more than person 3 + person 2 but less than or = double person 3
return (solution_conservative(total_lambs) - solution_generous(total_lambs));
}
public static int solution_generous(int total_lambs) {
int lamb_pay_current = 0;
int person_before = 0;
//int person_before_before = 0;
int person_counter = 0;
for (int lamb_pay_cumm = 0; lamb_pay_cumm < total_lambs; lamb_pay_cumm += lamb_pay_current) {
if (!(total_lambs > 0)) {break;}
if ((total_lambs == 1)) {break;}
if ((lamb_pay_cumm == 0) && (total_lambs > 0)) {
lamb_pay_current = 1;
person_counter++;
continue;
}
if ((lamb_pay_cumm) == 1 && (total_lambs > 1)) {
lamb_pay_current = 2;
person_before = 1;
person_counter++;
continue;
}
if (person_before == 1) {
person_before = 2;
}
if (person_before * 2 + lamb_pay_cumm > total_lambs) {continue;}
lamb_pay_current = person_before * 2;
person_counter++;
// person_before_before = person_before;
person_before = lamb_pay_current;
}
if (total_lambs == 1) {return 1;}
if (!(total_lambs > 0)) {return 0;}
return person_counter;
}
public static int solution_conservative(int total_lambs) {
int lamb_pay_current = 0;
int person_before = 0;
int person_before_before = 0;
int person_counter = 0;
for (int lamb_pay_cumm = 0; lamb_pay_cumm < total_lambs; lamb_pay_cumm += lamb_pay_current) {
if (!(total_lambs > 0)) {break;}
if ((total_lambs == 1)) {break;}
if ((lamb_pay_cumm == 0) && (total_lambs > 0)) {
lamb_pay_current = 1;
person_counter++;
continue;
}
if ((lamb_pay_cumm) == 1 && (total_lambs > 1)) {
lamb_pay_current = 1;
person_before = 1;
person_counter++;
continue;
}
if (person_before == 1) {
person_before_before = 1;
}
if (person_before + person_before_before + lamb_pay_cumm > total_lambs) {continue;}
lamb_pay_current = person_before + person_before_before;
person_counter++;
person_before_before = person_before;
person_before = lamb_pay_current;
}
if (total_lambs == 1) {return 1;}
if (!(total_lambs > 0)) {return 0;}
return person_counter;
}
}我想做的是，我有两个功能。一个是找到最“慷慨”的可能方式，给每个人尽可能多的羊羔，然后再有人反抗。这个模式似乎是这样的: 1，2，4，8，16等等。I可能是错误的。另一种功能是找出最“保守”的可能方式，让每个人在叛变之前最少的数量的羔羊数量。这个模式似乎是这样的: 1，1，2，3，5，8，13等等。I也可能是错误的。
每当我做“验证Solutions.java”时，它总是失败测试#7。所有其他测试都成功了，只是这个测试失败了。我不知道7号测试是什么。
我也尝试过我所知道的关于Intellij的大部分测试，但在我看来，所有的测试都是正确的.
回答 1
Stack Overflow用户
发布于 2021-06-23 22:02:50
关于慷慨和吝啬的模式，你是对的。慷慨的道路遵循二次幂，吝啬遵循斐波那契的模式。
很难找出您的代码有什么问题。但是我认为很可能你的代码没有正确地计算出追随者的数量，特别是当剩下的羊羔可以在不违反限制的情况下被分发的时候。
- 慷慨:从2=1开始，继续使用2的力量，然后添加到羊羔中，直到你超过total_lambs为止。当你超过，确保你减去多余的从已付的羊羔，所以你得到原来的羊羔支付。另外，还可以得到最后两只可以通过以下方式很容易获得的付费羔羊：
电流功率2/2+电流功率2/4
看看是否小于或等于剩余的羔羊= total_lambs - lambs_paid，然后增加1.。
- Stingy:这是相同的方法，除了这里，您可以跟踪fibonacci系列中最后两只付费羔羊.
以下是慷慨和吝啬的施舍的一个简单的实现：
public static int solution_generous(int total_lambs) {
// Apply power of two
int power_of_two = 1;
int henchmen = 1;
int lambs_paid = 1;
while ( lambs_paid <= total_lambs ) {
power_of_two = 2*power_of_two;
lambs_paid += power_of_two;
if ( lambs_paid > total_lambs ) {
lambs_paid -= power_of_two;
power_of_two = power_of_two/2;
break;
}
henchmen++;
}
int last_one = power_of_two;
int last_before_one = power_of_two/2;
if ( last_one + last_before_one <= total_lambs - lambs_paid ) {
henchmen++;
}
return henchmen;
}
public static int solution_conservative(int total_lambs) {
//Fibonacci
int f1 = 1;
int f2 = 1;
int f12 = f1 + f2;
int henchmen = 1;
int lambs_paid = f1;
int last_two_paid = f2;
while ( lambs_paid <= total_lambs ) {
last_two_paid = f2;
f1 = f2;
f2 = f12;
f12 = f1 + f2;
lambs_paid += f1;
if ( lambs_paid > total_lambs ) {
break;
}
henchmen++;
}
if ( last_two_paid <= total_lambs - lambs_paid ) {
henchmen++;
}
return henchmen;
}https://stackoverflow.com/questions/68106172
复制相似问题
腾讯云开发者
