Проверка всех возможных комбинаций из любых двух элементов массива в массиве содержит 0-9 раз хотяб


Я кодирования для онлайн-платформы. Код работает на некоторых тестовых случаев, но получает лимит времени превышен. Какие есть способы, чтобы сделать мой код более эффективным?

Вход

5 
129300455
5559948277 
012334556
56789 
123456879

Выход

5

Объяснение

Выигрышные Пары:

129300455 56789 -->содержит сразу все от 0-9 хотяб

129300455 123456879-->содержит все от 0-9 хотя бы раз и т. д.

   import java.io.*;
   import java.util.*;
   import java.text.*;
   import java.math.*;
   import java.util.regex.*;

   public class Main {

static int winningLotteryTicket(String[] tickets,int n)
 // tickets = array of all strings

 {
    int count=0;
    boolean b=false;
    // the i and j loop are to create all possible combinations
    for(int i=0;i<n;i++)
{

    for(int j=i+1;j<n;j++)
    {

     if(i!=j)
     { String check=tickets[i]+tickets[j];

     // running loop to check from 0-9 atleast once
     for(int u=0;u<=9;u++)
     {
         String r=u+"";
         b=check.contains(r);
         if(!b)
         {
         break;
         }

     }
     if(b){count++;}       
     }
    }
}
    return count;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    String[] tickets = new String[n];
    for(int tickets_i = 0; tickets_i < n; tickets_i++){
        tickets[tickets_i] = in.next();
    }
    int result = winningLotteryTicket(tickets,n);
    System.out.println(result);
    in.close();
}
}


565
0
задан 28 января 2018 в 02:01 Источник Поделиться
Комментарии
2 ответа


static int winningLotteryTicket(String[] tickets,int n)
// tickets = array of all strings

{


Пожалуйста, не ставьте комментарии в объявлении функции и функции организма (которая начинается с {).

Стандартный способ, чтобы написать это в Java

// tickets = array of all strings
static int winningLotteryTicket(String[] tickets, int n) {

Это короче и проще для чтения.

Некоторые люди предпочитают поставить { на отдельной строке. Это не стандарт в Java. Но если вы сделаете это, пожалуйста, поставьте { на линии сразу же после объявления функции. Поставить комментарии либо перед объявлением функции или внутри тела функции.

В Java, в отличие от c, вы не должны пройти длину массива отдельно. Вместо nвы можете просто использовать tickets.length. Так

    for (int i = 0; i < tickets.length; i++) {
for (int j = i + 1; j < tickets.length; j++) {

Это также имеет преимущество быть яснее, чем n. Я могу сразу увидеть, что это длина массива, что является ограничением. И это позволяет избежать ошибок, где n передается как нечто иное, чем длина массива.


     if(i!=j)

Эта линия является ненужным. Так, что внутренний for петля заявил, j всегда больше, чем i.


         b=check.contains(r);

Это неэффективно. Это делает линейный поиск времени для каждой цифры. Мы можем сделать один линейный поиск времени, которая охватывает все цифры. Рассмотрим

public static final int RADIX = 10;

static boolean hasAllDigits(String ticketPair) {
boolean[] found = new boolean[RADIX];
for (char digit : ticketPair.toCharArray()) {
found[digit - '0'] = true;
}

for (boolean digitFound : found) {
if (!digitFound) {
return false;
}
}

return true;
}

Поэтому исходный способ может быть просто

static int winningLotteryTicket(String[] tickets) {
int count = 0;

// the i and j loop are to create all possible combinations
for (int i = 0; i < tickets.length; i++) {
for (int j = i + 1; j < tickets.length; j++) {
if (hasAllDigits(tickets[i] + tickets[j])) {
count++;
}
}
}

return count;
}

Если это все еще не достаточно быстро, рекомендуется хранить цифры в каждой строке. Е. Г. вместо "129300455" магазин "0123459". Затем вы можете просто использовать логику слияния, чтобы проверить, если две строки содержат все цифры.

1
ответ дан 28 января 2018 в 05:01 Источник Поделиться

Вот несколько пунктов для размышления:

Для этих онлайн проблемы, я обнаружил, что во многих случаях обработки данных при считывании из потока, является более эффективным. С этой целью я предлагаю передает сканер, чтобы ваша функция, а не массив строк. Это дает дополнительное преимущество настройки сканера, чтобы прочитать текстовый файл при отладке, а затем установить его обратно в стандарт для отправки.

Путем снижения каждой линии своей уникальной цифр вы получаете ряд преимуществ.


  • Любой набор, который имеет 10 элементов(всего 10 цифр) совпадет с любой другой набор.

  • Любая пара, которая не имеет в общей сложности 10 или больше пунктов не будет соответствовать.

  • При проверке пары каждого будет не более 9 пунктов.

Все это в сочетании может выглядеть примерно так:

public static int FindPairs(Scanner in) {
int retVal = 0;
int n = in.nextInt();
int goodSets = 0;
List<List<Character>> data = new ArrayList<>();
for (int i = 0; i < n; i++) {
//reduce each string to its unique digits.
List<Character> temp = in.next()
.chars()
.distinct()
.mapToObj(x -> (char) x)
.collect(Collectors.toList());
//process complete sets. add the rest.
if (temp.size() == 10) {
goodSets++;
retVal += n - goodSets;
} else {
data.add(temp);
}
}
for (int i = 0; i < data.size(); i++) {
for (int j = i + 1; j < data.size(); j++) {
//check that the total count and the count of the merged unique digits is valid.
if ((data.get(i).size() + data.get(j).size() >= 10) &&
Stream.of(data.get(i), data.get(j))
.flatMap(x -> x.stream())
.distinct()
.count() == 10) {
retVal++;
}
}
}
return retVal;
}

0
ответ дан 6 февраля 2018 в 06:02 Источник Поделиться