java - 计算山谷

Question

我正在解决 Hackkerrank 的一个问题，我有点被这个问题困住了。自表格结束以来，我已经尝试了足够多的方法并以某种方式找到了该算法，但不幸的是它不适用于大多数输入。它适用于一些测试用例。链接是:Counting Valleys

问题陈述

这里我们必须计算 XYZ 人访问的山谷数量。

• 山谷是海平面以下一系列连续的台阶，从海平面下降开始，到海平面上升结束。

向上一级是U，向下一级是D。我们将以字符串的形式给出 XYZ 人走过的步数加上上下，即 UUDDUDUDDUU 这样。

示例输入

8
UDDDUDUU

示例输出

1

说明

如果我们将_表示为海平面，将上升表示为/，将下降表示为\，则可以绘制加里的徒步旅行如:

_/\      _
   \    /
    \/\/

他进出一个山谷。

算法

根据我的理论:

山谷从下降开始:

• 遍历并检查字符串中的两对
• 检查获取到的字符串是否等于DD
• 再次从DD开始的pos开始循环，找出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

这个问题的关键是理解什么是山谷。根据我的阅读，只有当你走出山谷时，你才算有一个山谷。该规则规定山谷以“......上升到海平面”结束。

因此，我们跟踪我们的海拔高度，只有当我们从海平面以下移动到海平面时，我们才算一个山谷。这是我的快速尝试:

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"));
}

请尝试您拥有的所有测试用例，如果失败请告诉我。