最大有效时间，从4位开始

Question

我正在尝试从给定的4位数中找出最大有效时间。我使用了数字(2,4,0,0)。代码returnS 20:42，而它应该返回20:40。对于如何处理这个问题，有什么建议吗？

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

public class MaxTimeCombination {
public static void main(String[] args) {

    System.out.println(solution(2, 4, 0, 0));
    System.out.println(solution(3, 0, 7, 0));
}

public static String solution(int A, int B, int C, int D) {
    // brute force permutation
    int[] temp = new int[] {A, B, C, D};

    List<List<Integer>> permutation = permute(temp);
    int h = Integer.MIN_VALUE;
    int m = Integer.MIN_VALUE;
    boolean exists = false;

    /*      System.out.println("Permutations:" + permutation);
    for (int i = 0; i < permutation.size(); i++) {
    if (permutation.get(i).get(0) > 0  && permutation.get(i).get(0) < 3 ){
        List <Integer> output = permutation.get(i);
        System.out.println(output);     
    }

    }*/


    for (int i = 0; i < permutation.size(); i++) {
        //if (permutation.get(i).get(0) > 0  && permutation.get(i).get(0) < 3 ){
        List<Integer> k = permutation.get(i);
        //System.out.println("Sorted :" + k);
        int hh = k.get(0)*10 + k.get(1);
        if (hh < 24) {
            exists = true;
            if (hh > h) {
                h = hh;
            } 
        } 
        int mm = k.get(2)*10 + k.get(3);

        if ( mm < 60) {
            exists = true;
            if (mm > m) {
                m = mm;
            } 
        } 
    }

    return (exists ? String.format("%02d:%02d", h, m) : "NOT POSSIBLE");
}

public static List<List<Integer>> permute(int[] num) {
    List<List<Integer>> result = new ArrayList<>();

    //start from an empty list
    result.add(new ArrayList<>());

    for (int i = 0; i < num.length; i++) {
        //list of list in current iteration of the array num
        List<List<Integer>> current = new ArrayList<>();

        for (List<Integer> l : result) {
            // # of locations to insert is largest index + 1
            for (int j = 0; j < l.size()+1; j++) {
                // + add num[i] to different locations
                l.add(j, num[i]);

                List<Integer> temp = new ArrayList<>(l);
                current.add(temp);

                //System.out.print(temp + " ");

                //l.remove(num[i]); 
                l.remove(j);
            }

        }

        result = new ArrayList<>(current);
    }

    return result;
}
}

Answer 1

您需要重新构造h和max的测试。您当前的代码独立地查找每个函数的最大值。您得到的是最大小时和最大分钟，即使它们不是在一个排列中一起出现的，比如20:42。

以下是测试的工作版本。

int hh = k.get(0) * 10 + k.get(1);          
if (hh < 24)
{
    if (hh >= h)
    {
        int mm = k.get(2) * 10 + k.get(3);
        if (mm < 60)
        {
            exists = true;
            if (hh > h || mm > m)
            {
                m = mm;
            }
            h = hh;
        }
    }
}

请注意，hh>h已经变成了hh>=h。即使这个小时等于我们之前看到的一个小时，我们也需要寻找最大的分钟。检查最大分钟的代码已在小时测试的if子句中移动。我们需要确保我们正在考虑的分钟与最大小时相关联。最后，当mm>m或具有新的最大小时hh>h时，我们需要更新最大分钟

通过此更改，您的代码将提供期望值：20:40

Answer 2

我认为你对这个问题想得太多了。请按如下方式找到可行的解决方案：

import java.util.ArrayList;
import java.util.Collections;

public class TestClass{

    public static void main(String[] args)
    {
        int maxLimits[] = {2, 3, 5, 9};

        ArrayList<Integer> list = new ArrayList<>();    
        list.add(3);
        list.add(2);
        list.add(9);
        list.add(2);

        Collections.sort(list);
        int time[] = new int[4];

        for(int i = 0; i<4; i++)
        {
            int index = 0;
            for(int j=0; j<list.size(); j++)
            {

                if (list.get(j) <= maxLimits[i]) 
                {
                    time[i] = list.get(j);
                    index = j;
                }
            }

            list.remove(index);
        }
    }
}

希望这能对你有所帮助。:-)