Google foo bar 挑战 Level 3 - 末日燃料

Question

这个问题可能被问过很多次，但并不是所有的答案都能得到解决。由于我只剩下不到20个小时，所以我希望有人能给我一些建议。非常感谢您的帮助。

目前，我只剩下一个测试用例失败需要处理（测试用例 3），但我不知道我忘记包括什么情况。我做了一个Matrix和Fractionclass让我操作起来更方便。抱歉评论了 println，因为它是为了我的调试。

我使用吸收马尔可夫链的概念来找到 Q、R、F 和 FR 矩阵，这启发了我https://github.com/ivanseed/google-foobar-help/blob/master/challenges/doomsday_fuel/doomsday_fuel.md。

如果您有任何意见，再次感谢！请帮忙！

问题和我的Solution.java如下：

问题：

Write a function solution(m) that takes an array of array of nonnegative ints representing how many times that state has gone to the next state and return an array of ints for each terminal state giving the exact probabilities of each terminal state, represented as the numerator for each state, then the denominator for all of them at the end and in simplest form. The matrix is at most 10 by 10. It is guaranteed that no matter which state the ore is in, there is a path from that state to a terminal state. That is, the processing will always eventually end in a stable state. The ore starts in state 0. The denominator will fit within a signed 32-bit integer during the calculation, as long as the fraction is simplified regularly. 

For example, consider the matrix m:
[
  [0,1,0,0,0,1],  # s0, the initial state, goes to s1 and s5 with equal probability
  [4,0,0,3,2,0],  # s1 can become s0, s3, or s4, but with different probabilities
  [0,0,0,0,0,0],  # s2 is terminal, and unreachable (never observed in practice)
  [0,0,0,0,0,0],  # s3 is terminal
  [0,0,0,0,0,0],  # s4 is terminal
  [0,0,0,0,0,0],  # s5 is terminal
]
So, we can consider different paths to terminal states, such as:
s0 -> s1 -> s3
s0 -> s1 -> s0 -> s1 -> s0 -> s1 -> s4
s0 -> s1 -> s0 -> s5
Tracing the probabilities of each, we find that
s2 has probability 0
s3 has probability 3/14
s4 has probability 1/7
s5 has probability 9/14
So, putting that together, and making a common denominator, gives an answer in the form of
[s2.numerator, s3.numerator, s4.numerator, s5.numerator, denominator] which is
[0, 3, 2, 9, 14].

我的Solution.java:

import java.lang.Math;
import java.util.ArrayList;

public class Solution {
    public static int[] solution(int[][] m) {
        // Your code here
        ArrayList<Integer> termStateList = new ArrayList<Integer>();
        ArrayList<Integer> nonTermStateList = new ArrayList<Integer>();
        ArrayList<Integer> stateDenominatorList = new ArrayList<Integer>();
        for (int i = 0; i < m.length; i++) {
            boolean allZeroInState = true;
            int stateDenominatorTemp = 0;
            // loop through probability of all states for a particular state
            for (int j = 0; j < m[0].length; j++) {
                if (m[i][j] != 0) {
                    allZeroInState = false;
                    stateDenominatorTemp += m[i][j];
                }
            }
            if (allZeroInState) {
                termStateList.add(i);
            } else {
                nonTermStateList.add(i);
                stateDenominatorList.add(stateDenominatorTemp);
            }
        }
        ////system.out.println(Arrays.toString(termStateList.toArray()));
        ////system.out.println(Arrays.toString(nonTermStateList.toArray()));
        ////system.out.println(Arrays.toString(stateDenominatorList.toArray()));

        // Create I 0 R Q matrix -- may not need
        Fraction one = new Fraction(1);
        Fraction zero = new Fraction(0);

        // Create I
        ArrayList<ArrayList<Fraction>> IList = new ArrayList<ArrayList<Fraction>>();
        for (int i = 0; i < nonTermStateList.size(); i++) {
            ArrayList<Fraction> IRow = new ArrayList<Fraction>();
            for (int j = 0; j < nonTermStateList.size(); j++) {
                if (i==j) {
                    IRow.add(one);
                } else {
                    IRow.add(zero);
                }
            }
            IList.add(IRow);
        }
        Matrix I = new Matrix(IList, nonTermStateList.size(), nonTermStateList.size());
        //system.out.println("I:");
        I.print();

        // Create Q
        ArrayList<ArrayList<Fraction>> QList = new ArrayList<ArrayList<Fraction>>();
        for (int i = 0; i < nonTermStateList.size(); i++) {
            ArrayList<Fraction> QRow = new ArrayList<Fraction>();
            for (int j = 0; j < nonTermStateList.size(); j++) {
                QRow.add(new Fraction(m[nonTermStateList.get(i)][nonTermStateList.get(j)], stateDenominatorList.get(i)));
            }
            QList.add(QRow);
        }

        Matrix Q = new Matrix(QList, nonTermStateList.size(), nonTermStateList.size());
        //system.out.println("Q:");
        Q.print();

        // Create R
        ArrayList<ArrayList<Fraction>> RList = new ArrayList<ArrayList<Fraction>>();
        for (int i = 0; i < nonTermStateList.size(); i++) {
            ArrayList<Fraction> RRow = new ArrayList<Fraction>();
            for (int j = 0; j < termStateList.size(); j++) {
                RRow.add(new Fraction(m[nonTermStateList.get(i)][termStateList.get(j)], stateDenominatorList.get(i)));
            }
            RList.add(RRow);
        }

        Matrix R = new Matrix(RList, nonTermStateList.size(), termStateList.size());
        //system.out.println("R:");
        R.print();

        // Find I - Q
        Matrix IminusQ = I.minus(Q);
        //system.out.println("IminusQ:");
        IminusQ.print();
        // Find F = (I - Q)^-1
        Matrix F = IminusQ.getInverseMatrix();
        //system.out.println("F:");
        F.print();
        // Find FR
        Matrix FR = F.multiply(R);
        //system.out.println("FR:");
        FR.print();
        // Take the first row of FR
        ArrayList<Fraction> FRRow = FR.getRow(0);
        ArrayList<Fraction> numeratorList = new ArrayList<Fraction>(); // numeratorList
        int[] denomList = new int[FRRow.size()]; // denomList
        // Find the numerators and the common denominator, make it an array
        for (int i = 0; i < FRRow.size(); i++) {
            denomList[i] = FRRow.get(i).getDenominator();
            numeratorList.add(FRRow.get(i));
        }
        int lcm = getLcm(denomList);
        int[] result = new int[FRRow.size()+1];
        for (int j = 0; j < result.length-1; j++) {
            numeratorList.set(j, numeratorList.get(j).multiply(new Fraction(lcm)));
            result[j] = numeratorList.get(j).getNumerator();
        }
        result[FRRow.size()] = lcm;
        //system.out.println(Arrays.toString(result));

        return result;
    }

    public static int getLcm(int arr[]) {
        int max = 0; 
        int n = arr.length;
        for (int i = 0; i < n; i++) { 
            if (max < arr[i]) { 
                max = arr[i]; 
            } 
        }  
        int res = 1;   
        int factor = 2; 
        while (factor <= max) {  
            ArrayList<Integer> arrIndex = new ArrayList<Integer>(); 
            for (int j = 0; j < n; j++) { 
                if (arr[j] % factor == 0) { 
                    arrIndex.add(arrIndex.size(), j); 
                } 
            }
            if (arrIndex.size() >= 2) { 
                // Reduce all array elements divisible  
                // by factor.  
                for (int j = 0; j < arrIndex.size(); j++) { 
                    arr[arrIndex.get(j)] /= factor; 
                } 
  
                res *= factor; 
            } else { 
                factor++; 
            } 
        } 
  
        // Then multiply all reduced array elements  
        for (int i = 0; i < n; i++) { 
            res *= arr[i]; 
        } 
  
        return res; 
    }
    
    private static class Matrix {

        private final int M;
        private final int N;
        private final Fraction det;
        private ArrayList<ArrayList<Fraction>> matrix;
        private ArrayList<ArrayList<Fraction>> inverseMatrix;

        public Matrix(ArrayList<ArrayList<Fraction>> mat, int m, int n) {
            this.matrix = mat;
            this.M = m;
            this.N = n;
            this.det = this.determinant(mat, n);
            this.inverseMatrix = this.inverse();
        }

        private void getCofactor(ArrayList<ArrayList<Fraction>> mat, ArrayList<ArrayList<Fraction>> tempMat, int p, int q, int n) {
            int i = 0;
            int j = 0;
            for (int row = 0; row < n; row++) {
                for (int col = 0; col < n; col++) {
                    if (row != p && col != q) {
                        tempMat.get(i).set(j++, mat.get(row).get(col));
                        if (j == n - 1) {
                            j = 0;
                            i++;
                        }
                    }
                }
            }
        }

        private Fraction determinant(ArrayList<ArrayList<Fraction>> mat, int n) {
            Fraction ans = new Fraction(0, 1);
            if (this.M != this.N) {
                return ans;
            }
            if (n == 1) {
                return mat.get(0).get(0);
            }
            ArrayList<ArrayList<Fraction>> tempMat = new ArrayList<ArrayList<Fraction>>();
            // Init 2d fraction arraylist
            for (int i = 0; i < this.M; i++) {
                ArrayList<Fraction> tempMatRow = new ArrayList<Fraction>();
                for (int j = 0; j < this.N; j++) {
                    tempMatRow.add(new Fraction(0, 1));
                }
                tempMat.add(tempMatRow);
            }   

            int sign = 1;
            Fraction signFraction = new Fraction(sign, 1);
            for (int k = 0; k < n; k++) {
                this.getCofactor(mat, tempMat, 0, k, n);
                ans = ans.plus(signFraction.multiply(mat.get(0).get(k).multiply(determinant(tempMat, n - 1))));
                sign = -sign;
                signFraction = new Fraction(sign, 1);
            }
            return ans;
        }

        private void adjoint(ArrayList<ArrayList<Fraction>> mat, ArrayList<ArrayList<Fraction>> adj) {
            if (this.N == 1) {
                adj.get(0).set(0, new Fraction(1, 1));
                return;
            }
            int sign = 1;
            
            ArrayList<ArrayList<Fraction>> tempMat = new ArrayList<ArrayList<Fraction>>();
            // Init 2d fraction arraylist
            for (int i = 0; i < this.N; i++) {
                ArrayList<Fraction> tempMatRow = new ArrayList<Fraction>();
                for (int j = 0; j < this.N; j++) {
                    tempMatRow.add(new Fraction(0, 1));
                }
                tempMat.add(tempMatRow);
            }

            for (int p = 0; p < this.N; p++) {
                for (int q = 0; q < this.N; q++) {
                    this.getCofactor(mat, tempMat, p, q, this.N);
                    sign = ((p + q) % 2 == 0) ? 1 : -1;
                    Fraction signFraction = new Fraction(sign, 1);
                    adj.get(q).set(p, signFraction.multiply((this.determinant(tempMat, this.N - 1))));
                }
            }
        }

        private ArrayList<ArrayList<Fraction>> inverse() {
            ArrayList<ArrayList<Fraction>> inv = new ArrayList<ArrayList<Fraction>>();
            // Init 2d fraction arraylist
            for (int i = 0; i < this.M; i++) {
                ArrayList<Fraction> invRow = new ArrayList<Fraction>();
                for (int j = 0; j < this.N; j++) {
                    invRow.add(new Fraction(0, 1));
                }
                inv.add(invRow);
            }

            if (this.det.equals(new Fraction(0))) {
                return inv;
            }

            ArrayList<ArrayList<Fraction>> adj = new ArrayList<ArrayList<Fraction>>();
            // Init 2d fraction arraylist
            for (int i = 0; i < this.M; i++) {
                ArrayList<Fraction> adjRow = new ArrayList<Fraction>();
                for (int j = 0; j < this.N; j++) {
                    adjRow.add(new Fraction(0, 1));
                }
                adj.add(adjRow);
            }

            adjoint(this.matrix, adj);
            for (int p = 0; p < this.N; p++) {
                for (int q = 0; q < this.N; q++) {
                    Fraction temp = adj.get(p).get(q).dividedBy(this.det);
                    inv.get(p).set(q, temp);
                }
            }
            return inv;
        }

        public Matrix getInverseMatrix() {
            if (this.M != this.N) {
                //system.out.println("No inverse matrix for non-square matrices");
            }
            return new Matrix(this.inverseMatrix, this.M, this.N);
        }

        public Fraction getElement(int m, int n) {
            return this.matrix.get(m).get(n);
        }

        public ArrayList<Fraction> getRow(int m) {
            if (m <= this.M) {
                return this.matrix.get(m);
            }
            return new ArrayList<Fraction>();
        }

        public Matrix plus(Matrix mat) {
            int M_m = mat.getDimension()[0];
            int N_m = mat.getDimension()[1];
            if (this.M != M_m || this.N != N_m) {
                //system.out.println("Error in plus: Dimensions of two matrices are not equal!"); // Debug
                return mat;
            } else {
                ArrayList<ArrayList<Fraction>> sum = new ArrayList<ArrayList<Fraction>>();
                // Init 2d fraction arraylist
                for (int i = 0; i < this.M; i++) {
                    ArrayList<Fraction> sumRow = new ArrayList<Fraction>();
                    for (int j = 0; j < this.N; j++) {
                        sumRow.add(new Fraction(0, 1));
                    }
                    sum.add(sumRow);
                }
                for (int i = 0; i < this.M; i++) {
                    for (int j = 0; j < this.N; j++) {
                        // sum[i][j] = this.matrix[i][j] + mat.getElement(i, j);
                        sum.get(i).set(j, this.matrix.get(i).get(j).plus(mat.getElement(i, j)));
                    }
                }
                return new Matrix(sum, this.M, this.N);
            }
        }

        public Matrix minus(Matrix mat) {
            int M_m = mat.getDimension()[0];
            int N_m = mat.getDimension()[1];
            if (this.M != M_m || this.N != N_m) {
                //system.out.println("Error in minus: Dimensions of two matrices are not equal!"); // Debug
                return mat;
            } else {
                ArrayList<ArrayList<Fraction>> difference = new ArrayList<ArrayList<Fraction>>();
                // Init 2d fraction arraylist
                for (int i = 0; i < this.M; i++) {
                    ArrayList<Fraction> differenceRow = new ArrayList<Fraction>();
                    for (int j = 0; j < this.N; j++) {
                        differenceRow.add(new Fraction(0, 1));
                    }
                    difference.add(differenceRow);
                }
                for (int i = 0; i < this.M; i++) {
                    for (int j = 0; j < this.N; j++) {
                        // difference[i][j] = this.matrix[i][j] + mat.getElement(i, j);
                        difference.get(i).set(j, this.matrix.get(i).get(j).minus(mat.getElement(i, j)));
                    }
                }
                return new Matrix(difference, this.M, this.N);
            }
        }

        public Matrix multiply(Matrix mat) {
            // M N M N
            // X(m, n) x Y(n, p) = Z(m, p)
            int M_m = mat.getDimension()[0];
            int p_m = mat.getDimension()[1];
            if (this.N != M_m) {
                //system.out.println("Error in multiply: Dimensions of two matrices are valid for cross multiplication!"); // Debug
                return mat;
            } else {
                ArrayList<ArrayList<Fraction>> product = new ArrayList<ArrayList<Fraction>>();
                // Init 2d fraction arraylist
                for (int i = 0; i < this.M; i++) {
                    ArrayList<Fraction> productRow = new ArrayList<Fraction>();
                    for (int j = 0; j < p_m; j++) {
                        productRow.add(new Fraction(0, 1));
                    }
                    product.add(productRow);
                }
                for (int i = 0; i < this.M; i++) {
                    for (int j = 0; j < p_m; j++) {
                        for (int k = 0; k < this.N; k++) {
                            // product[i][j] += matrix[i][k] * mat.getElement(k, j);
                            Fraction temp = product.get(i).get(j);
                            product.get(i).set(j, temp.plus(this.matrix.get(i).get(k).multiply(mat.getElement(k, j))));
                        }
                    }
                }
                return new Matrix(product, this.M, p_m);
            }

        }

        public int[] getDimension() {
            return new int[] { this.M, this.N };
        }

        public void print() {
            for (int i = 0; i < this.M; i++) {
                for (int j = 0; j < this.N; j++) {
                    //system.out.print(this.matrix.get(i).get(j).toString() + "  ");
                }
                //system.out.println();
            }
        }

        public void printInverse() {
            if (this.M != this.N) {
                //system.out.println("No inverse matrix for non-square matrices");
                return;
            }
            if (this.det.equals(new Fraction(0))) {
                //system.out.println("Singular matrix, can't find its inverse");
                return;
            }
            for (int i = 0; i < this.M; i++) {
                for (int j = 0; j < this.N; j++) {
                    //system.out.print(this.inverseMatrix.get(i).get(j).toString() + "  ");
                }
                //system.out.println();
            }
        }

    }

    private static class Fraction {

        private int numerator;
        private int denominator = 1;
        private boolean sign = false; // true = negative, false = positive

        public Fraction(int num, int denom) {
            this.numerator = num;
            if (denom == 0) {
                //system.out.println("Denominator cannot be 0. Setting it to 1");
            } else {        
                this.denominator = denom;
            }
            this.simplify();
        }

        public Fraction(int num) {
            this.numerator = num;
            this.simplify();
        }

        private int getGcm(int num1, int num2) {
            return num2 == 0 ? num1 : this.getGcm(num2, num1 % num2);
        }

        // Simplify fraction to simplest form, runs in constructor
        public void simplify() {        
            this.sign = !(this.numerator <= 0 && this.denominator <= 0) && !(this.numerator >= 0 && this.denominator >= 0);

            this.numerator = Math.abs(this.numerator);
            this.denominator = Math.abs(this.denominator);

            int gcm = this.getGcm(this.numerator, this.denominator);
            this.numerator = this.numerator / gcm;
            this.denominator = this.denominator / gcm;
            // When fraction is zero, make sure denominator is one and no negative sign
            if (this.numerator == 0 && this.denominator != 0) {
                this.denominator = 1;
                this.sign = false;
            }
        }

        public Fraction plus(Fraction f1) {
            int num = 0;
            if (this.sign) { // this fraction is negative
                if (f1.getSign()) { // f1 is negative
                    num = (-1) * this.numerator * f1.denominator + this.denominator * (-1) * f1.numerator;
                } else { // f1 is positive
                    num = (-1) * this.numerator * f1.denominator + this.denominator * f1.numerator;                
                }
            } else { // this fraction is positive
                if (f1.getSign()) { // f1 is negative
                    num = this.numerator * f1.denominator + this.denominator * (-1) * f1.numerator; 
                } else { // f1 is positive
                    num = this.numerator * f1.denominator + this.denominator * f1.numerator; 
                }
            }
            int denom = this.denominator * f1.getDenominator();
            return new Fraction(num, denom);
        }

        public Fraction minus(Fraction f1) {
            int num = 0;
            if (this.sign) { // this fraction is negative
                if (f1.getSign()) { // f1 is negative
                    num = (-1) * this.numerator * f1.denominator + this.denominator * f1.numerator;
                } else { // f1 is positive
                    num = (-1) * this.numerator * f1.denominator - this.denominator * f1.numerator;                
                }
            } else { // this fraction is positive
                if (f1.getSign()) { // f1 is negative
                    num = this.numerator * f1.denominator + this.denominator * f1.numerator; 
                } else { // f1 is positive
                    num = this.numerator * f1.denominator - this.denominator * f1.numerator; 
                }
            }
            int denom = this.denominator * f1.getDenominator();
            return new Fraction(num, denom);
        }

        public Fraction multiply(Fraction f1) {
            int signInt = 1;
            // Either one fraction is negative will make the product fraction negative, but not for both fractions are negative.
            if (this.sign && !f1.getSign() || !this.sign && f1.getSign()) {
                signInt = -1;
            }
            return new Fraction(signInt * this.numerator * f1.getNumerator(), this.denominator * f1.getDenominator());
        }

        public Fraction dividedBy(Fraction f1) {
            int signInt = 1;
            // Either one fraction is negative will make the product fraction negative, but not for both fractions are negative.
            if (this.sign && !f1.getSign() || !this.sign && f1.getSign()) {
                signInt = -1;
            }
            return new Fraction(signInt *this.numerator * f1.getDenominator(), this.denominator * f1.getNumerator());
        }

        public boolean equals(Fraction f1) {
        return this.numerator == f1.getNumerator() && this.denominator == f1.getDenominator() && this.sign == f1.getSign();
        }

        public int getNumerator() {
            return this.numerator;
        }

        public int getDenominator() {
            return this.denominator;
        }

        public boolean getSign() {
            return this.sign;
        }

        public String toString() {
            String signStr = "";
            String fractionStr = "";
            if (this.sign) {
                signStr = "-";
            }
            if (numerator == denominator) {
                fractionStr = "1";
            } else if (denominator == 1) {
                fractionStr = Integer.toString(numerator);
            } else {
                fractionStr = numerator + "/" + denominator;
            }
            return signStr + fractionStr;
        }
    }


}

Answer 1

我知道这已经很晚了，对你没有用，但对其他提到你问题的人来说。

您的问题的解决方案是处理终止场景，即如果第一行 S0 是终止行，那么您必须 return 结果为 [1,0....0, 1] 即 [S0, S1...., Sn, 分母].

因此您可以检查 S0 的总和是否 == m[0][0] 然后 return 以上结果。我参考了 Ketan Arora

的回答

Answer 2

import java.lang.Math;
import java.util.ArrayList;
public class Solution 
{
    public static int[] solution(int[][] m) 
    {
        // Your code here
        ArrayList<Integer> termStateList = new ArrayList<Integer>();
        ArrayList<Integer> nonTermStateList = new ArrayList<Integer>();
        ArrayList<Integer> stateDenominatorList = new ArrayList<Integer>();
        int[] r=new int[2];
        if(m[0][0]==0 && m.length==1)
        {
            r[0]=1;
            r[1]=1;
            return r;
        }
        for (int i = 0; i < m.length; i++) 
        {
            boolean allZeroInState = true;
            int stateDenominatorTemp = 0;
            for (int j = 0; j < m[0].length; j++) 
            {
            if (m[i][j] != 0) 
            {
                allZeroInState = false;
                stateDenominatorTemp += m[i][j];
            }
        }
        if (allZeroInState)
        {
            termStateList.add(i);
        } 
        else 
        {
            nonTermStateList.add(i);
            stateDenominatorList.add(stateDenominatorTemp);
        }
    }
    Fraction one = new Fraction(1);
    Fraction zero = new Fraction(0);
    ArrayList<ArrayList<Fraction>> IList = new ArrayList<ArrayList<Fraction>>();
    for (int i = 0; i < nonTermStateList.size(); i++) 
    {
        ArrayList<Fraction> IRow = new ArrayList<Fraction>();
        for (int j = 0; j < nonTermStateList.size(); j++) 
        {
            if (i==j) 
            {
                IRow.add(one);
            } else 
            {
                IRow.add(zero);
            }
        }
        IList.add(IRow);
    }
    Matrix I = new Matrix(IList, nonTermStateList.size(),nonTermStateList.size())
    I.print();

    // Create Q
    ArrayList<ArrayList<Fraction>> QList = new ArrayList<ArrayList<Fraction>>();
    for (int i = 0; i < nonTermStateList.size(); i++) 
    {
        ArrayList<Fraction> QRow = new ArrayList<Fraction>();
        for (int j = 0; j < nonTermStateList.size(); j++) 
        {
            QRow.add(new Fraction(m[nonTermStateList.get(i)][nonTermStateList.get(j)], stateDenominatorList.get(i)));
        }
        QList.add(QRow);
    }

    Matrix Q = new Matrix(QList, nonTermStateList.size(), nonTermStateList.size());
    //system.out.println("Q:");
    Q.print();

    // Create R
    ArrayList<ArrayList<Fraction>> RList = new ArrayList<ArrayList<Fraction>>();
    for (int i = 0; i < nonTermStateList.size(); i++) 
    {
        ArrayList<Fraction> RRow = new ArrayList<Fraction>();
        for (int j = 0; j < termStateList.size(); j++) 
        {
            RRow.add(new Fraction(m[nonTermStateList.get(i)][termStateList.get(j)], stateDenominatorList.get(i)));
        }
        RList.add(RRow);
    }

    Matrix R = new Matrix(RList, nonTermStateList.size(), termStateList.size());
    //system.out.println("R:");
    R.print();

    // Find I - Q
    Matrix IminusQ = I.minus(Q);
    //system.out.println("IminusQ:");
    IminusQ.print();
    // Find F = (I - Q)^-1
    Matrix F = IminusQ.getInverseMatrix();
    //system.out.println("F:");
    F.print();
    // Find FR
    Matrix FR = F.multiply(R);
    //system.out.println("FR:");
    FR.print();
    // Take the first row of FR
    ArrayList<Fraction> FRRow = FR.getRow(0);
    ArrayList<Fraction> numeratorList = new ArrayList<Fraction>(); // numeratorList
    int[] denomList = new int[FRRow.size()]; // denomList
    // Find the numerators and the common denominator, make it an array
    for (int i = 0; i < FRRow.size(); i++) 
    {
        denomList[i] = FRRow.get(i).getDenominator();
        numeratorList.add(FRRow.get(i));
    }
    int lcm = getLcm(denomList);
    int[] result = new int[FRRow.size()+1];
    if(m[0][0]==0 && m.length==1)
    {
        result[0]=1;
        result[1]=1;
        return result;
    }
    else
    {
         for (int j = 0; j < result.length-1; j++)
        {
            numeratorList.set(j, numeratorList.get(j).multiply(new Fraction(lcm)));
            result[j] = numeratorList.get(j).getNumerator();
        }
        result[FRRow.size()] = lcm;
        //system.out.println(Arrays.toString(result));
        return result;
    }
}

public static int getLcm(int arr[]) 
{
    int max = 0; 
    int n = arr.length;
    for (int i = 0; i < n; i++) 
    { 
        if (max < arr[i]) { 
            max = arr[i]; 
        } 
    }  
    int res = 1;   
    int factor = 2; 
    while (factor <= max) {  
        ArrayList<Integer> arrIndex = new ArrayList<Integer>(); 
        for (int j = 0; j < n; j++) { 
            if (arr[j] % factor == 0) { 
                arrIndex.add(arrIndex.size(), j); 
            } 
        }
        if (arrIndex.size() >= 2) { 
            // Reduce all array elements divisible  
            // by factor.  
            for (int j = 0; j < arrIndex.size(); j++) { 
                arr[arrIndex.get(j)] /= factor; 
            } 

            res *= factor; 
        } else { 
            factor++; 
        } 
    } 

    // Then multiply all reduced array elements  
    for (int i = 0; i < n; i++) { 
        res *= arr[i]; 
    } 

    return res; 
}

private static class Matrix {

    private final int M;
    private final int N;
    private final Fraction det;
    private ArrayList<ArrayList<Fraction>> matrix;
    private ArrayList<ArrayList<Fraction>> inverseMatrix;

    public Matrix(ArrayList<ArrayList<Fraction>> mat, int m, int n) {
        this.matrix = mat;
        this.M = m;
        this.N = n;
        this.det = this.determinant(mat, n);
        this.inverseMatrix = this.inverse();
    }

    private void getCofactor(ArrayList<ArrayList<Fraction>> mat, ArrayList<ArrayList<Fraction>> tempMat, int p, int q, int n) {
        int i = 0;
        int j = 0;
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (row != p && col != q) {
                    tempMat.get(i).set(j++, mat.get(row).get(col));
                    if (j == n - 1) {
                        j = 0;
                        i++;
                    }
                }
            }
        }
    }

    private Fraction determinant(ArrayList<ArrayList<Fraction>> mat, int n) {
        Fraction ans = new Fraction(0, 1);
        if (this.M != this.N) {
            return ans;
        }
        if (n == 1) {
            return mat.get(0).get(0);
        }
        ArrayList<ArrayList<Fraction>> tempMat = new ArrayList<ArrayList<Fraction>>();
        // Init 2d fraction arraylist
        for (int i = 0; i < this.M; i++) {
            ArrayList<Fraction> tempMatRow = new ArrayList<Fraction>();
            for (int j = 0; j < this.N; j++) {
                tempMatRow.add(new Fraction(0, 1));
            }
            tempMat.add(tempMatRow);
        }   

        int sign = 1;
        Fraction signFraction = new Fraction(sign, 1);
        for (int k = 0; k < n; k++) {
            this.getCofactor(mat, tempMat, 0, k, n);
            ans = ans.plus(signFraction.multiply(mat.get(0).get(k).multiply(determinant(tempMat, n - 1))));
            sign = -sign;
            signFraction = new Fraction(sign, 1);
        }
        return ans;
    }

    private void adjoint(ArrayList<ArrayList<Fraction>> mat, ArrayList<ArrayList<Fraction>> adj) {
        if (this.N == 1) {
            adj.get(0).set(0, new Fraction(1, 1));
            return;
        }
        int sign = 1;
        
        ArrayList<ArrayList<Fraction>> tempMat = new ArrayList<ArrayList<Fraction>>();
        // Init 2d fraction arraylist
        for (int i = 0; i < this.N; i++) {
            ArrayList<Fraction> tempMatRow = new ArrayList<Fraction>();
            for (int j = 0; j < this.N; j++) {
                tempMatRow.add(new Fraction(0, 1));
            }
            tempMat.add(tempMatRow);
        }

        for (int p = 0; p < this.N; p++) {
            for (int q = 0; q < this.N; q++) {
                this.getCofactor(mat, tempMat, p, q, this.N);
                sign = ((p + q) % 2 == 0) ? 1 : -1;
                Fraction signFraction = new Fraction(sign, 1);
                adj.get(q).set(p, signFraction.multiply((this.determinant(tempMat, this.N - 1))));
            }
        }
    }

    private ArrayList<ArrayList<Fraction>> inverse() {
        ArrayList<ArrayList<Fraction>> inv = new ArrayList<ArrayList<Fraction>>();
        // Init 2d fraction arraylist
        for (int i = 0; i < this.M; i++) {
            ArrayList<Fraction> invRow = new ArrayList<Fraction>();
            for (int j = 0; j < this.N; j++) {
                invRow.add(new Fraction(0, 1));
            }
            inv.add(invRow);
        }

        if (this.det.equals(new Fraction(0))) {
            return inv;
        }

        ArrayList<ArrayList<Fraction>> adj = new ArrayList<ArrayList<Fraction>>();
        // Init 2d fraction arraylist
        for (int i = 0; i < this.M; i++) {
            ArrayList<Fraction> adjRow = new ArrayList<Fraction>();
            for (int j = 0; j < this.N; j++) {
                adjRow.add(new Fraction(0, 1));
            }
            adj.add(adjRow);
        }

        adjoint(this.matrix, adj);
        for (int p = 0; p < this.N; p++) {
            for (int q = 0; q < this.N; q++) {
                Fraction temp = adj.get(p).get(q).dividedBy(this.det);
                inv.get(p).set(q, temp);
            }
        }
        return inv;
    }

    public Matrix getInverseMatrix() {
        if (this.M != this.N) {
            //system.out.println("No inverse matrix for non-square matrices");
        }
        return new Matrix(this.inverseMatrix, this.M, this.N);
    }

    public Fraction getElement(int m, int n) {
        return this.matrix.get(m).get(n);
    }

    public ArrayList<Fraction> getRow(int m) {
        if (m <= this.M) {
            return this.matrix.get(m);
        }
        return new ArrayList<Fraction>();
    }

    public Matrix plus(Matrix mat) {
        int M_m = mat.getDimension()[0];
        int N_m = mat.getDimension()[1];
        if (this.M != M_m || this.N != N_m) {
            //system.out.println("Error in plus: Dimensions of two matrices are not equal!"); // Debug
            return mat;
        } else {
            ArrayList<ArrayList<Fraction>> sum = new ArrayList<ArrayList<Fraction>>();
            // Init 2d fraction arraylist
            for (int i = 0; i < this.M; i++) {
                ArrayList<Fraction> sumRow = new ArrayList<Fraction>();
                for (int j = 0; j < this.N; j++) {
                    sumRow.add(new Fraction(0, 1));
                }
                sum.add(sumRow);
            }
            for (int i = 0; i < this.M; i++) {
                for (int j = 0; j < this.N; j++) {
                    // sum[i][j] = this.matrix[i][j] + mat.getElement(i, j);
                    sum.get(i).set(j, this.matrix.get(i).get(j).plus(mat.getElement(i, j)));
                }
            }
            return new Matrix(sum, this.M, this.N);
        }
    }

    public Matrix minus(Matrix mat) {
        int M_m = mat.getDimension()[0];
        int N_m = mat.getDimension()[1];
        if (this.M != M_m || this.N != N_m) {
            //system.out.println("Error in minus: Dimensions of two matrices are not equal!"); // Debug
            return mat;
        } else {
            ArrayList<ArrayList<Fraction>> difference = new ArrayList<ArrayList<Fraction>>();
            // Init 2d fraction arraylist
            for (int i = 0; i < this.M; i++) {
                ArrayList<Fraction> differenceRow = new ArrayList<Fraction>();
                for (int j = 0; j < this.N; j++) {
                    differenceRow.add(new Fraction(0, 1));
                }
                difference.add(differenceRow);
            }
            for (int i = 0; i < this.M; i++) {
                for (int j = 0; j < this.N; j++) {
                    // difference[i][j] = this.matrix[i][j] + mat.getElement(i, j);
                    difference.get(i).set(j, this.matrix.get(i).get(j).minus(mat.getElement(i, j)));
                }
            }
            return new Matrix(difference, this.M, this.N);
        }
    }

    public Matrix multiply(Matrix mat) {
        // M N M N
        // X(m, n) x Y(n, p) = Z(m, p)
        int M_m = mat.getDimension()[0];
        int p_m = mat.getDimension()[1];
        if (this.N != M_m) {
            //system.out.println("Error in multiply: Dimensions of two matrices are valid for cross multiplication!"); // Debug
            return mat;
        } else {
            ArrayList<ArrayList<Fraction>> product = new ArrayList<ArrayList<Fraction>>();
            // Init 2d fraction arraylist
            for (int i = 0; i < this.M; i++) {
                ArrayList<Fraction> productRow = new ArrayList<Fraction>();
                for (int j = 0; j < p_m; j++) {
                    productRow.add(new Fraction(0, 1));
                }
                product.add(productRow);
            }
            for (int i = 0; i < this.M; i++) {
                for (int j = 0; j < p_m; j++) {
                    for (int k = 0; k < this.N; k++) {
                        // product[i][j] += matrix[i][k] * mat.getElement(k, j);
                        Fraction temp = product.get(i).get(j);
                        product.get(i).set(j, temp.plus(this.matrix.get(i).get(k).multiply(mat.getElement(k, j))));
                    }
                }
            }
            return new Matrix(product, this.M, p_m);
        }

    }

    public int[] getDimension() {
        return new int[] { this.M, this.N };
    }

    public void print() {
        for (int i = 0; i < this.M; i++) {
            for (int j = 0; j < this.N; j++) {
                //system.out.print(this.matrix.get(i).get(j).toString() + "  ");
            }
            //system.out.println();
        }
    }

    public void printInverse() {
        if (this.M != this.N) {
            //system.out.println("No inverse matrix for non-square matrices");
            return;
        }
        if (this.det.equals(new Fraction(0))) {
            //system.out.println("Singular matrix, can't find its inverse");
            return;
        }
        for (int i = 0; i < this.M; i++) {
            for (int j = 0; j < this.N; j++) {
                //system.out.print(this.inverseMatrix.get(i).get(j).toString() + "  ");
            }
            //system.out.println();
        }
    }

}

private static class Fraction {

    private int numerator;
    private int denominator = 1;
    private boolean sign = false; // true = negative, false = positive

    public Fraction(int num, int denom) {
        this.numerator = num;
        if (denom == 0) {
            //system.out.println("Denominator cannot be 0. Setting it to 1");
        } else {        
            this.denominator = denom;
        }
        this.simplify();
    }

    public Fraction(int num) {
        this.numerator = num;
        this.simplify();
    }

    private int getGcm(int num1, int num2) {
        return num2 == 0 ? num1 : this.getGcm(num2, num1 % num2);
    }

    // Simplify fraction to simplest form, runs in constructor
    public void simplify() {        
        this.sign = !(this.numerator <= 0 && this.denominator <= 0) && !(this.numerator >= 0 && this.denominator >= 0);

        this.numerator = Math.abs(this.numerator);
        this.denominator = Math.abs(this.denominator);

        int gcm = this.getGcm(this.numerator, this.denominator);
        this.numerator = this.numerator / gcm;
        this.denominator = this.denominator / gcm;
        // When fraction is zero, make sure denominator is one and no negative sign
        if (this.numerator == 0 && this.denominator != 0) {
            this.denominator = 1;
            this.sign = false;
        }
    }

    public Fraction plus(Fraction f1) {
        int num = 0;
        if (this.sign) { // this fraction is negative
            if (f1.getSign()) { // f1 is negative
                num = (-1) * this.numerator * f1.denominator + this.denominator * (-1) * f1.numerator;
            } else { // f1 is positive
                num = (-1) * this.numerator * f1.denominator + this.denominator * f1.numerator;                
            }
        } else { // this fraction is positive
            if (f1.getSign()) { // f1 is negative
                num = this.numerator * f1.denominator + this.denominator * (-1) * f1.numerator; 
            } else { // f1 is positive
                num = this.numerator * f1.denominator + this.denominator * f1.numerator; 
            }
        }
        int denom = this.denominator * f1.getDenominator();
        return new Fraction(num, denom);
    }

    public Fraction minus(Fraction f1) {
        int num = 0;
        if (this.sign) { // this fraction is negative
            if (f1.getSign()) { // f1 is negative
                num = (-1) * this.numerator * f1.denominator + this.denominator * f1.numerator;
            } else { // f1 is positive
                num = (-1) * this.numerator * f1.denominator - this.denominator * f1.numerator;                
            }
        } else { // this fraction is positive
            if (f1.getSign()) { // f1 is negative
                num = this.numerator * f1.denominator + this.denominator * f1.numerator; 
            } else { // f1 is positive
                num = this.numerator * f1.denominator - this.denominator * f1.numerator; 
            }
        }
        int denom = this.denominator * f1.getDenominator();
        return new Fraction(num, denom);
    }

    public Fraction multiply(Fraction f1) {
        int signInt = 1;
        // Either one fraction is negative will make the product fraction negative, but not for both fractions are negative.
        if (this.sign && !f1.getSign() || !this.sign && f1.getSign()) {
            signInt = -1;
        }
        return new Fraction(signInt * this.numerator * f1.getNumerator(), this.denominator * f1.getDenominator());
    }

    public Fraction dividedBy(Fraction f1) {
        int signInt = 1;
        // Either one fraction is negative will make the product fraction negative, but not for both fractions are negative.
        if (this.sign && !f1.getSign() || !this.sign && f1.getSign()) {
            signInt = -1;
        }
        return new Fraction(signInt *this.numerator * f1.getDenominator(), this.denominator * f1.getNumerator());
    }

    public boolean equals(Fraction f1) {
    return this.numerator == f1.getNumerator() && this.denominator == f1.getDenominator() && this.sign == f1.getSign();
    }

    public int getNumerator()
    {
        return this.numerator;
    }

    public int getDenominator() {
        return this.denominator;
    }

       public boolean getSign() 
       {
            return this.sign;
       }

        public String toString() 
        {
            String signStr = "";
            String fractionStr = "";
            if (this.sign) 
            {
                signStr = "-";
            }
            if (numerator == denominator) 
            {
                 fractionStr = "1";
            } 
            else if (denominator == 1) 
            {
                fractionStr = Integer.toString(numerator);
            } 
            else
            {
                fractionStr = numerator + "/" + denominator;
            }
            return signStr + fractionStr;
        }
    }
}

class psp
{
    public static void main(String gg[])
    {
        int m[][]={{1,2,3,0,0,0},{4,5,6,0,0,0},{7,8,9,1,0,0},{0,0,0,0,1,2},{0,0,0,0,0,0},{0,0,0,0,0,0}};
        Solution.solution(m);
    }
}

Google foo bar 挑战 Level 3 - 末日燃料

Google foo bar challenge Level 3 - Doomsday-fuel

java

fuel