数谷

Question

我正在解决 Hackkerank 的一个问题，但我有点困在这个问题上。自从表单结束以来，我已经尝试了足够多的方法，并以某种方式找到了算法，但不幸的是，它对大多数输入都不起作用。它适用于一些测试用例。链接是：数谷

问题陈述

在这里，我们必须计算 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"));
}

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