-2

我有一个问题陈述，需要将 3 个不同的数字传递给一个方法并检查哪些 3 个数字满足某个约束。

这是我的代码，但我想知道不是创建嵌套循环，而是有更优化的方法来检查哪一组三元组满足某个约束。?

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solution
{

    static List l = new ArrayList();

    static int geometricTrick(String s)
    {
        int count = 0;

        for (int i = 0; i < s.length(); i++)
        {
            for (int j = 0; j < s.length(); j++)
            {
                for (int k = 0; k < s.length(); k++)
                {
                    if (is1stConstraintTrue(s, i, j, k) && is2ndConstraintTrue(i, j, k))
                    {
                        l.add(new Triplet(i, j, k));
                    }
                }
            }
        }

        count = l.size();

        return count;

    }

    static boolean is2ndConstraintTrue(int i, int j, int k)
    {
        boolean retVal = false;

        double LHS = Math.pow((j + 1), 2);

        double RHS = (i + 1) * (k + 1);

        if (LHS == RHS)
            retVal = true;
        else
            retVal = false;

        return retVal;
    }

    static boolean is1stConstraintTrue(String s, int i, int j, int k)
    {
        boolean retVal = false;

        char[] localChar = s.toCharArray();

        if (localChar[i] == 'a' && localChar[j] == 'b' && localChar[k] == 'c')
        {
            retVal = true;
        }

        return retVal;
    }

    static class Triplet
    {
        public int i, j, k;

        public Triplet(int i, int j, int k)
        {
            this.i= i;
            this.j= j;
            this.k= k;
        }
    }
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String s = in.next();
        int result = geometricTrick(s);
        System.out.println(result);

    }
}
4

3 回答 3

0

您提出的幼稚方法具有立方时间复杂度（三个嵌套for循环）。如果您有很多次出现'a'，'b'并且'c'在您的输入中，可能值得首先确定所有'a'' 'b's 和'c''s 的索引，然后仅在该集合上检查您的第二个条件。

import java.util.ArrayList;
import java.util.List;

public class Main {

    public static List<Integer> getAllOccurrences(String input, char of) {
        List<Integer> occurrences = new ArrayList<Integer>();
        char[] chars = input.toCharArray();

        for (int idx = 0; idx < chars.length; ++idx) {
            if (of == chars[idx]) {
                occurrences.add(idx);
            }
        }

        return (occurrences);
    }

    static List<Triplet> geometricTrick(String input){
        List<Integer> allAs = getAllOccurrences(input, 'a');
        List<Integer> allBs = getAllOccurrences(input, 'b');
        List<Integer> allCs = getAllOccurrences(input, 'c');
        List<Triplet> solutions = new ArrayList<Triplet>();

        // reorder the loops, so that the c-loop is the innermost loop (see
        // below why this is useful and how it is exploited).
        for (int a : allAs) {
            for (int c : allCs) {
                // calculate lhs as soon as possible, no need to recalculate the
                // same value multiple times
                final int lhs = ((a + 1) * (c + 1));

                for (int b : allBs) {
                    final int rhs = ((b + 1) * (b + 1));
                    if (lhs > rhs) {
                       continue;
                    }

                    /* else */ if (lhs == rhs) {
                        solutions.add(new Triplet(a, b, c));
                    }

                    // by construction, the b-values are in ascending or der.
                    // Thus if the rhs-value is larger or equal to the
                    // lhs-value, we can skip all other rhs-values. for this
                    // lhs-value.

                    // if (lhs <= rhs) {
                        break;
                    // }
                }
            }
        }
        return (solutions);
    }

    static class Triplet {

        public final int i;
        public final int j;
        public final int k;

        public Triplet(int i, int j, int k) {
            this.i = i;
            this.j = j;
            this.k = k;
        }
    }
}

char在给定中搜索所有出现的 1String需要 O(n)（方法getAllOccurrences(...)），调用它 3 次不会改变复杂度（3 * n \in O(n)）。遍历 , 的所有可能组合a并花费b# c* a# b* #c时间，其中 # a、 #b和 #c停留在您a的. 这给出了 O(n + # * # * # ) 的总时间复杂度。bcinputabc

请注意，最坏​​情况下的时间复杂度，即如果字符串a的 1/3 由b's组成，1/3 由 's 组成，1/3 由 's 组成c，仍然是三次方。

于 2017-10-30T09:55:57.243 回答
0

这里有一些提示：

  1. 通过乘法计算平方将比使用更快pow

  2. String::toCharray()太贵了。它将所有字符复制到一个新数组中。每次调用它。不要多次调用它。

  3. 如果结果是三元组的数量，则无需构建列表。您甚至不需要创建Triple实例。数一数。

  4. 如果您需要迭代所有组合，嵌套循环并不是低效的。

于 2017-10-30T09:42:07.307 回答
0

为您提供一个简单且“愚蠢”的解决方案，以不使用那些内部循环。

让我们使用像Iterator. 这将通过使用条件语句“隐藏”循环。

public class TripletFactory{

    final int maxI, maxJ, maxK;
    int i, j ,k;

    public TripletFactory(int i, int j, int k){
        this.maxI = i;
        this.maxJ = j;
        this.maxK = k;
    }

    public Triplet next(){
        if(++k > maxK){
            k = 0;
            if(++j > maxJ){
                j = 0;
                if(++i > maxI){
                    return null;
                }
            }
        }
        return new Triplet(i,j,k);
    }
}

这样，您只需要在 ONE 循环中获取一个新实例Triple即可null

TripletFactory fact = new TripletFactory(2, 3 ,5);

Triplet t = null;
while((t = fact.next()) != null){
    System.out.println(t);
}
//no more Triplet

并随心所欲地使用它。

然后，您必须更新约束方法以采用 aTriplet并使用 getter 来检查实例。

顺便说一句，这可能是一种Triplet让它验证自己的方法。

笔记 ：

我使用了与 相同的符号，Iterator因为我们可以实现Iterator并Iterable使用如下符号：

for(Triplet t : factory){
    ...
}
于 2017-10-30T09:42:31.380 回答