数谷

Question

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

问题陈述

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

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

再往上一步U，再往下走一步就是D。我们将给出XYZ人旅行的步骤数，加上上下的字符串形式，即UUDDUDUDDUUDUDUUU那样的。

样本输入

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

请试用你所有的测试用例，如果有任何故障请告诉我。

Answer 2

这个问题即将调查徒步旅行者沿着他的路线爬到海平面上的次数。试试看这个解决方案，它对我有效。

public static int countingValleys(int steps, String path) {
    int s = 0;
    int v = 0;
    for (int i = 0; i < path.length(); i++) {
        if (path.charAt(i) == 'D') {
            s--;
        } else if ((path.charAt(i) == 'U') && (s + 1 == 0)) {
            s++;
            v++;
        } else {
            s++;
        }
    }
    return v;
}

Answer 3

类型记录/JavaScript解决方案：

function countingValleys(steps: number, path: string): number {
  let valleysCount = 0;
  let firstStep = "";
  let stepFromSeaLevel = 0;

  for (let step of path.split("")) {
    firstStep = firstStep || step;
    stepFromSeaLevel += step === "U" ? 1 : -1;

    if (stepFromSeaLevel === 0) {
      valleysCount = valleysCount + (firstStep === "D" ? 1 : 0);
      firstStep = "";
    }
   }

  return valleysCount;
}