Подсчет долин

Question

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

Постановка задачи

Здесь мы должны подсчитать, сколько долин посещает человек XYZ.

• Долина - это последовательность последовательных шагов ниже уровня моря, начиная с шага вниз от уровня моря и заканчивая шагом вверх до уровня моря.

На один шаг вверх это U , а на один шаг вниз это D . Нам будет дано количество шагов, пройденных человеком XYZ, плюс взлеты и падения в виде строки, то есть UUDDUDUDDUU , как это.

Пример ввода

8
UDDDUDUU

Пример вывода

1

Объяснение

Если мы представим _ как уровень моря, шаг вверх как /, и шаг вниз как \, поход Гэри может быть нарисован как:

_/\      _
   \    /
    \/\/

Он входит и покидает одну долину.

Алгоритм

Согласно моей теории:

Долина начинает спускаться:

• Пройдите и проверьте две пары из строки
• Проверьте, равна ли полученная строка DD
• Снова запустите цикл с позиции, начинающейся с DD , и найдите, где UU падает или нет
• Увеличить счетчик, разбить;
• Счетчик возвратов

Но этот алгоритм не работает для большинства тестовых случаев

Код

static int countingValleys(int n, String s) {
    int valleyVisits = 0, i=0;
    String str = "", strOne = "";

    /*Here we make pairs of two, in order to get the valley's visits. Since this visit starts from DD and ends at UU. So first we get the two strings and match with DD */
    while(i<n){
      //Gives the two strings from i to i+2
      str = s.substring(i, i+2);
      i = i+2; //not to start from next, but to the even pair

      //Checking if the pair starts from DD
      if(str.equals("DD")){
        int j = i;
        /* Rerunning the loop to get the end of the valley trip that is UU from this point */
        while(j < n){
          // Getting new strings starting after DD
          strOne = s.substring(j, j+2);
          j = j+2;

          //Similar operation, but the getting the end from DD and then breaks
          if(strOne.equals("UU")){
            valleyVisits++;
            break;
          }
        }
      }
    }

    return valleyVisits;
}

Пройдены тестовые задания 1

8
UDDDUDUU

Expected Output : 1

Пройденный тестовый кейс 2

12
DDUUDDUDUUUD

Expected Output : 2

Неудачный тестовый пример 1

10
DUDDDUUDUU

Expected Output : 2

Неудачный тестовый пример 2

100
DUDUUUUUUUUDUDDUUDUUDDDUUDDDDDUUDUUUUDDDUUUUUUUDDUDUDUUUDDDDUUDDDUDDDDUUDDUDDUUUDUUUDUUDUDUDDDDDDDDD

Expected Output : 2

Я почти там, но я не знаю, почему моя логика не работает здесь. Заранее благодарю за любую помощь. :)

Answer 1

Ключ при движении вверх, вы должны проверить уровень моря и проигнорировать нисходящий тренд для быстрой обработки.

Вот мое простое и точное решение -

static int countingValleys(int n, String s) {

        int valleyCounter = 0, altitude = 0;

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (ch == 'U') {
                altitude++;
                if (altitude == 0) {
                    valleyCounter++;
                }

            } else {

                altitude--;
            }
        }
        return valleyCounter;
    }

Если все еще неясно и вам нужны дополнительные объяснения, вы можете нажать здесь.

Answer 2

Ключом к этой проблеме является понимание того, что составляет долину. Из моего прочтения ты считаешь долину только тогда, когда выходишь из нее. Правило гласит, что долина заканчивается "... шагом до уровня моря".

Таким образом, мы отслеживаем наш уровень, и только если мы переместимся чуть ниже уровня моря к уровню моря, мы посчитаем долину. Вот моя быстрая попытка:

private int countValleys(String s)
{
    int level = 0; // 0 is sea-level
    int valleys = 0;

    for (char c : s.toCharArray())
    {
        if (c == 'U') {
            level++;
            if (level == 0)
            {
                valleys++;
            }
        }
        else {
            level--;
        }
    }
    return valleys;
}

Я выполнил следующие тестовые примеры (из вашего вопроса), и все они прошли:

@Test
public void testValleyCounting()
{
    Assert.assertEquals(1, countValleys("UDDDUDUU"));
    Assert.assertEquals(2, countValleys("DDUUDDUDUUUD"));
    Assert.assertEquals(2, countValleys("DUDDDUUDUU"));
    Assert.assertEquals(2, countValleys("DUDUUUUUUUUDUDDUUDUUDDDUUDDDDDUUDUUUUDDDUUUUUUUDDUDUDUUUDDDDUUDDDUDDDDUUDDUDDUUUDUUUDUUDUDUDDDDDDDDD"));
}

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