谷歌 Foobar power_hungry

问题描述 投票:4回答:3

你好,我需要帮助我的一个谷歌foobar问题,这是我目前得到的。

package com.google.challenges;
import java.math.BigInteger;

public class Answer{


    public static String answer (int[] xs){
        BigInteger result = new BigInteger("1");
        int xsLen = xs.length, pos = 0;
        int[] negatives = new int[xsLen];
        if (xsLen == 1){
            return Integer.toString(xs[0]);
        }
        // Split the input up into pos/negative. Pos get put onto the final value, as they don't need anything else.
        // they are all useful. negative to onto seperate array and get sorted later
        for (int n = 0;n < xsLen;n++){
            int val = xs[n];
            if (val == 0){
                continue;
            }
            if (val > 0){
                result = result.multiply(new BigInteger(Integer.toString(val)));
            } else {
                negatives[pos] = val;
                pos++;
            }
        }
        // even number of negatives means a full product will always be positive.
        // odd number means that we discard the smallest number to maximise the result.
        if ((pos % 2) == 0){
            // even number, so add to result
            for (int i = 0;i < pos;i++){
                result = result.multiply(new BigInteger(Integer.toString(negatives[i])));
            }
        } else {
            // sort then discard the minimum
            int min = -1000; int mPos = -1;
            for (int i = 0;i < pos;i++){
                if(negatives[i] > min){
                    min = negatives[i];
                    mPos = i;
                }
            }
            for (int j = 0;j < pos;j++){
                if(j == mPos){
                    continue;
                }
                result = result.multiply(new BigInteger(Integer.toString(negatives[j])));
            }
        }

        // done, return the string;
        return result.toString();
    }
}

问题是这样的。

你需要弄清楚在任何给定的阵列中,哪些组面板可以脱机维修,同时仍然保持每个阵列的最大功率输出,要做到这一点,你首先需要弄清楚每个阵列的最大输出到底是多少。写一个函数 answer(xs),它接收一个整数列表,代表阵列中每个面板的功率输出水平,并返回这些数字的某个非空子集的最大乘积。因此,例如,如果一个数组包含的面板的功率输出水平为[2,-3,1,0,-5],那么最大乘积将通过取子集来找到:xs[0]=2,xs[1]=-3,xs[4]=-5,给出乘积2*(-3)*(-5)=30。 所以答案([2,-3,1,0,-5])将是 "30"。

每个太阳能电池板阵列至少包含1块且不超过50块电池板,每块电池板的功率输出水平的绝对值不会大于1000(有些电池板故障严重,以至于消耗能量,但你知道电池板的稳波器的一个技巧,可以让你把两块负输出的电池板组合起来,产生其功率值的倍数的正输出)。最终的产品可能会非常大,所以把答案作为数字的字符串表示。

语种

要提供一个Python解决方案,请编辑solution.py要提供一个Java解决方案,请编辑solution.java。

测试案例

Inputs:
    (int list) xs = [2, 0, 2, 2, 0]
Output:
    (string) "8"

Inputs:
    (int list) xs = [-2, -3, 4, -5]
Output:
    (string) "60"

我已经做了2天了,真的很想知道答案,这样我就可以知道自己做错了什么,可以改进了! 谢谢你的阅读,希望你能回答:)

computer-science
3个回答
3
投票

你需要处理某些情况。

你的数组有1到50个整数元素 从-1000到1000. 如果你的输入是这样的: [0, 0, -43, 0]. 在这种情况下。

    if (xsLen == 1){
        return Integer.toString(xs[0]);
    }

没道理啊。(你不可能有一个负的答案).在这种情况下,你的答案应该是0。

解决这个问题的关键是认识到你可以将两个负整数相乘得到一个正数。BigInteger很有用,因为你的最终答案可能会变得非常非常大。

我实现这个解决方案的方式是,我将每个非零整数相乘,并将其值存储为一个BigInteger结果变量。然而,我保留了另一个变量来跟踪 "最大负整数"。最后用结果除以 "最大负整数 "变量,你就有了答案。

我保留了一个正整数和一个负整数......。希望这能帮到你。


1
投票

你的代码很好,但只是你必须做一个小的补充,如果数组中的所有元素都是零或负数,那么它应该返回0.所以这里是代码。

package com.google.challenges;
import java.math.BigInteger;

public class Answer {

public static String answer (int[] xs){
    BigInteger result = new BigInteger("1");
    int xsLen = xs.length, pos = 0,ng=0;
    int[] negatives = new int[xsLen];
    if (xsLen == 1){
        return Integer.toString(xs[0]);
    }

    for (int n = 0;n < xsLen;n++){
        int val = xs[n];
        if (val == 0){
            continue;
        }
        if (val > 0){
            result = result.multiply(new BigInteger(Integer.toString(val)));
            ng++;
        } else {
            negatives[pos] = val;
            pos++;
        }
    }
    if(ng==0)
    {
        int l=0;
        return Integer.toString(l);
    }
    if ((pos % 2) == 0){

        for (int i = 0;i < pos;i++){
            result = result.multiply(new BigInteger(Integer.toString(negatives[i])));
        }
    } else {

        int min = -1000; int mPos = -1;
        for (int i = 0;i < pos;i++){
            if(negatives[i] > min){
                min = negatives[i];
                mPos = i;
            }
        }
        for (int j = 0;j < pos;j++){
            if(j == mPos){
                continue;
            }
            result = result.multiply(new BigInteger(Integer.toString(negatives[j])));
        }
    }


    return result.toString();
}
}

0
投票

试着写出满足这些测试用例或类似的代码。{-2} -> -2

{2,3,2,2} -> 24

{-2,-2,-3} -> 6

{-2,-2,-2,-3} -> 24.

{-2,-2,0,0,-2,-3} -> 24

{2,3,0,0,2,2} -> 24

{-2,-2,0,0,2,3} -> 24

{0,0} -> 0

而且在foobar挑战中,返回的结果大小将10^50也是可能的。

所以也建议使用String实现一个产品。

import java.util.Arrays;

public class Main{

public static String result(int[] xs) {

/ System.out.println("Hello World"); int i = 0,j;

    String pwr = "1";

    Arrays.sort(xs);
    while(i < xs.length && xs[i] < 0 ){
        i++;
    }
    if(i != 0){
        if (i == 1){
            if(xs[xs.length - 1] == 0){
                pwr = "0";
            } else if (xs.length == 1){
                return Arrays.valueOf(xs[0]);
            }
        }
        else if(i % 2 == 0){
            for (j = 0; j < i ;j++ ) {
                pwr = multiply(pwr, String.valueOf(xs[j]));
            }
        } else {
            for (j = 0; j < i - 1; j++ ) {
                pwr = multiply(pwr, String.valueOf(xs[j]));
            }
        }
    } else {
        if(xs[xs.length - 1] == 0){
            pwr = "0";
        }
    }

    for(;i < xs.length; i++){
        if(xs[i] != 0)
            pwr = multiply(pwr, String.valueOf(xs[i]));
    }


    return (pwr);     
}

public static String multiply(String num1, String num2){
                String tempnum1 = num1; 
                String tempnum2 = num2; 

                // Check condition if one string is negative 
                if(num1.charAt(0) == '-' && num2.charAt(0)!='-') 
                { 
                    num1 = num1.substring(1); 
                } 
                else if(num1.charAt(0) != '-' && num2.charAt(0) == '-') 
                { 
                    num2 = num2.substring(1); 
                } 
                else if(num1.charAt(0) == '-' && num2.charAt(0) == '-') 
                { 
                    num1 = num1.substring(1); 
                    num2 = num2.substring(1); 
                } 
                String s1 = new StringBuffer(num1).reverse().toString(); 
                String s2 = new StringBuffer(num2).reverse().toString(); 

                int[] m = new int[s1.length()+s2.length()]; 

                        // Go from right to left in num1 
                for (int k = 0; k < s1.length(); k++)  
                { 
                    // Go from right to left in num2 
                    for (int j = 0; j < s2.length(); j++)  
                    { 
                        m[k+j] = m[k+j]+(s1.charAt(k)-'0')*(s2.charAt(j)-'0'); 

                    } 
                } 


                String product = new String(); 
                // Multiply with current digit of first number 
                // and add result to previously stored product 
                // at current position.  
                for (int l = 0; l < m.length; l++) 
                { 
                    int digit = m[l]%10; 
                    int carry = m[l]/10; 
                    if(l+1<m.length) 
                    { 
                        m[l+1] = m[l+1] + carry; 
                    } 
                    product = digit+product; 

                } 

                // ignore '0's from the right 
                while(product.length()>1 && product.charAt(0) == '0') 
                { 
                    product = product.substring(1); 
                } 

                // Check condition if one string is negative 
                if(tempnum1.charAt(0) == '-' && tempnum2.charAt(0)!='-') 
                { 
                    product = new StringBuffer(product).insert(0,'-').toString(); 
                } 
                else if(tempnum1.charAt(0) != '-' && tempnum2.charAt(0) == '-') 
                { 
                    product = new StringBuffer(product).insert(0,'-').toString(); 
                } 
                else if(tempnum1.charAt(0) == '-' && tempnum2.charAt(0) == '-') 
                { 
                    product = product; 
                } 
                // System.out.println("Product of the two numbers is :"+"\n"+product); 
                return product;
}

}

© www.soinside.com 2019 - 2024. All rights reserved.