Я хочу, чтобы максимальное количество последовательных элементов больше или равно данному элементу

Question

Я решал проблему, в ней я должен возвращать максимальное количество раз подряд элементы были больше (и равны) или меньше, чем данный элемент в списке. Например :- Рассмотрим список элементов [5,10,8,9] and element = 8 Здесь есть 3 последовательных элемента, которые больше (и равны), чем 8, т.е. 10,8,9, поэтому я возвращаю 3.

Другой пример: -

Рассмотрим список элементов [5,10,8,9,1,2,3,4,5,8,9] and element =8 Здесь есть 3 последовательных элемента, которые больше (или равны), чем 8, т.е. 10,8,9, но после него есть 5 последовательных элементов, которые меньше 8, т.е. 1,2,3,4,5, поэтому максимум их 5, поэтому я возвращаю 5.

Я попробовал приведенный ниже код, но не получил правильного ответа.

То, что я сделал, это перебрал список и посмотрел, больше ли элемент, чем заданный элемент, если я его увеличиваю, и я делаю это до тех пор, пока не получу элемент меньше, если получу элемент меньше, добавлю счетчик установить и сделать это ноль. Аналогично для нижних элементов. и наконец я попытался вернуть максимум элементов. Но я не понимаю, как это не работает, все элементы, которые я добавляю, не добавляются в набор.

 public static int findLongest(List<Integer> hours, int limit) {

      int longWork = 0;

      int shortWork = 0;

      Set<Integer> hash_set = new HashSet<Integer>();
      for(int i=0 ; i<hours.size() ; i++) {
          if(hours.get(i) >= limit) {
              longWork++ ;
              hash_set.add(shortWork);
              shortWork = 0;
          }
          else if(hours.get(i) < limit) {
              shortWork++ ;
              hash_set.add(longWork);
              longWork = 0;
          }

      }

      int finalAns = Collections.max(hash_set);
      return finalAns ;

  }
}

Answer 1

Проблема в том, что вы добавили неправильное значение в ваш HashSet. При увеличении longWork вам нужно добавить longWork вместо shortWork следующим образом:

public static void main(String[] args) {
    List<Integer> list1 = Arrays.asList(new Integer[] {5, 10, 8, 9, 1, 2, 3, 4, 5, 8, 9});
    List<Integer> list2 = Arrays.asList(new Integer[] {5, 10, 8, 9});
    List<Integer> list3 = Arrays.asList(new Integer[] {5, 10, 6, 8, 4, 9});
    System.out.println(list1 + " -> " + findLongest(list1, 8));
    System.out.println(list2 + " -> " + findLongest(list2, 8));
    System.out.println(list3 + " -> " + findLongest(list3, 8));
}

public static int findLongest(List<Integer> hours, int limit) {
    int longWork = 0;
    int shortWork = 0;

    Set<Integer> hash_set = new HashSet<Integer>();
    for (int i = 0; i < hours.size(); i++) {
        if (hours.get(i) >= limit) {
            longWork++;
            hash_set.add(longWork);
            shortWork = 0;
        }
        else if (hours.get(i) < limit) {
            shortWork++;
            hash_set.add(shortWork);
            longWork = 0;
        }
    }
    int finalAns = Collections.max(hash_set);
    return finalAns;
}

Тогда вывод:

[5, 10, 8, 9, 1, 2, 3, 4, 5, 8, 9] -> 5
[5, 10, 8, 9] -> 3
[5, 10, 6, 8, 4, 9] -> 1

Редактировать: Или (как упоминалось в комментариях) вы можете просто добавить окончательные значения после цикла, чтобы убедиться, что последние значения добавляются, хотя другого числа больше нет (как в второй список: значение longWork равно 3, но оно никогда не добавляется, поскольку после списка больших значений нет значения, меньшего).

Так что это также будет работать:

public static void main(String[] args) {
    List<Integer> list1 = Arrays.asList(new Integer[] {5, 10, 8, 9, 1, 2, 3, 4, 5, 8, 9});
    List<Integer> list2 = Arrays.asList(new Integer[] {5, 10, 8, 9});
    List<Integer> list3 = Arrays.asList(new Integer[] {5, 10, 6, 8, 4, 9});
    System.out.println(list1 + " -> " + findLongest(list1, 8));
    System.out.println(list2 + " -> " + findLongest(list2, 8));
    System.out.println(list3 + " -> " + findLongest(list3, 8));
}

public static int findLongest(List<Integer> hours, int limit) {
    int longWork = 0;
    int shortWork = 0;

    Set<Integer> hash_set = new HashSet<Integer>();
    for (int i = 0; i < hours.size(); i++) {
        if (hours.get(i) >= limit) {
            longWork++;
            hash_set.add(shortWork);
            shortWork = 0;
        }
        else if (hours.get(i) < limit) {
            shortWork++;
            hash_set.add(longWork);
            longWork = 0;
        }
    }
    //add the last values
    hash_set.add(shortWork);
    hash_set.add(longWork);

    int finalAns = Collections.max(hash_set);
    return finalAns;
}

Вывод снова:

[5, 10, 8, 9, 1, 2, 3, 4, 5, 8, 9] -> 5
[5, 10, 8, 9] -> 3
[5, 10, 6, 8, 4, 9] -> 1

Answer 2

Проблема этой реализации заключается в том, что вы не обрабатываете последний запуск: вы не добавляете окончательные значения longWork и shortWork после цикла. (Это также означает, что вы получите исключение для пустого ввода).

Попробуйте добавить их в набор после цикла, прежде чем вызывать Collections.max.

---

Однако здесь нет необходимости в наборе. Вы просто ищете самый длинный пробег, поэтому все, что вам нужно сделать, это сохранить самый длинный пробег.

int longest = 0;
int a = 0;
while (a < hours.length()) {
  // Start of this run.
  int start = a;
  // Value of discriminator in this run.
  boolean ge = hours.get(a) >= limit;

  // Increment the pointer until you hit the end,
  // or you find the first element of the next run.
  do {
    ++a;
  } while (a < hours.length()
     && (hours.get(a) >= limit) == ge);

  // Maybe update the longest.
  longest = max(longest, a - start);
}
return longest;

Answer 3

Это также проверяет, что числа, которые меньше или больше, являются последовательными.Может быть, не самый эффективный, но он работает.

public static int findLongest(List<Integer> hours, int limit) {
    int longWork = 0;
    int shortWork = 0;
    Set<Integer> hash_set = new HashSet<>();

    Collections.sort(hours);
    int value;

    for(int i = 0; i< hours.size(); i++){
        value = hours.get(i);
        if(hours.size()- 1 == i){
            if((hours.get(hours.size() - 1) == hours.get(i - 1) + 1) && hours.get(i) >= limit){
                longWork++;
                hash_set.add(longWork);
                break;
            }
            break;

        }else{
            if((value + 1) == hours.get(i + 1) && hours.get(i) >= limit){
                longWork++;
            }else {
                longWork++;
                hash_set.add(longWork);
                longWork = 0;
            }
        }

    }

    for(int i = 0; i< hours.size(); i++){

        value = hours.get(i);

        if(hours.size()- 1 == i){
            if((hours.get(hours.size()- 1) == hours.get(i - 1) + 1) && hours.get(i) <= limit){
                shortWork++;
                hash_set.add(shortWork);
                break;
            }
            break;

        }else{
            if((value + 1) == hours.get(i + 1) && hours.get(i) <= limit){
                shortWork++;
            }else {
                shortWork++;
                hash_set.add(shortWork);
                shortWork = 0;
            }
        }
    }

    int finalAns = Collections.max(hash_set);
    return finalAns;

}

Answer 4

Эта проблема может быть сведена к стандартной известной проблеме Максимум последовательных (или нулей) в двоичном массиве . Элементы, которые больше или равны пределу, могут быть представлены как 1, а элементы, которые меньше, чем предел, могут быть представлены как 0. Так что для следующего примера:

[5,10,8,9] и элемент = 8

проблема сводится к

Нахождение максимального числа последовательных (или нулей) в двоичном массиве [0,1,1,1].

Answer 5

Прежде всего, ваше решение имеет недостатки. Этот одиночный хэш-набор не является правильной структурой данных для запоминания информации, которую нужно «запомнить». И это действительно не помогает, что вы продолжаете помещать значения в этот набор во время каждой операции цикла (обратите внимание, что ваш код выполняет if / else ... и оба, if-then и if-else помещают значение в набор: ничего полезного не получается).

Чтобы действительно решить вашу проблему, помните, что вы должны сделать: вам нужно идентифицировать последовательных подсписков вашего списка с номерами = X.

Чтобы решить вашу проблему, вы должны просмотреть свой список, а затем вспомнить, что произошло ранее:

• если вы находитесь в «подпоследовательности», то вам нужно решить, принадлежит ли следующий элемент в списке также к этой последовательности, если да, текущая подпоследовательность получает еще один элемент
• если «подпоследовательность» только что закончилась, вы должны проверить, имеет ли эта подпоследовательность больше элементов, чем предыдущие подпоследовательности