java - hashmap.get() == 运算符返回 false

Question

我正在解决以下问题:

加里是一位狂热的徒步旅行者。他一丝不苟地追踪自己的徒步旅行，密切关注地形等小细节。在他最后一次徒步旅行中，他正好走了 n 步。

对于他迈出的每一步，他都会注明是上坡(U)还是下坡(D)。加里的徒步旅行从海平面开始和结束，每上升或下降代表 1 个单位的高度变化。我们定义以下术语:

山是海平面以上一系列连续的台阶，从海平面上升到海平面结束。

山谷是海平面以下一系列连续的台阶，从海平面下降开始，到海平面上升结束。鉴于加里上次徒步旅行时的上下台阶顺序，找出并打印出他走过的山谷数量。

例如，如果加里的路径是 s = [DDUUUUDD]，他首先进入一个 2 单位深的山谷。然后他爬上一座 2 个单位高的山。最后，他回到海平面并结束了徒步旅行。

功能说明

在下面的编辑器中完成countingValleys函数。它必须返回一个整数，表示 Gary 走过的山谷数量。

countingValleys 具有以下参数:

n:Gary 走了的步数

s:描述他的路径的字符串输入格式

第一行包含一个整数，即加里徒步旅行的步数。第二行包含一个字符串，其中的字符描述了他的路径。

输出格式

打印一个整数，表示加里在徒步旅行期间走过的山谷数量。

示例输入

8嘟嘟嘟U

示例输出

1

下面是我在java中的实现。它适用于小型测试用例，但不适用于大型测试用例。

static int countingValleys(int n, String s) {


  //Use a hashmap to keep track of the number of moves.
  HashMap<Character,Integer> map = new HashMap();

  boolean sea = true;//check if we are at sea level

  //if both D and U have the same total no, we are at sea level.
  map.put('D',0);
  map.put('U',0);

  int valleys = 0;//count num of valleys

  for(int i = 0; i < n; i++){
      char key = s.charAt(i);

      //check if we are at sea level
      if(map.get('D') == map.get('U')){//<--PROBLEM
          sea = true;
      }
      else
          sea = false;

      if(sea == true && key == 'D'){//if we are at sea level and our next key is D, we have a valley

          valleys += 1;
      }

      map.put(key,map.get(key) + 1);//add move and update our hashmap   
  }

  return valleys;

}

问题似乎出在“if(map.get('D') == map.get('U'))”，对于大数字似乎返回 false，有人可以告诉我为什么吗？如果我将每个 map.get() 分配给一个变量并比较变量，它就会起作用。

我还在 javascript 中使用“new Object()”类型编写了完全相同的内容，并且它通过了所有测试用例，但它不能在 java 中使用 hashmap 工作，这是为什么？

原始问题的链接 - https://www.hackerrank.com/challenges/counting-valleys/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup

Answer 1

首先，正如其他答案中提到的，在这种情况下使用 .equals() 而不是 == 。更好的方法是，您甚至不需要使用 Map。只需一个整数就足够了。

由于您的问题是...对于大数字返回 false，有人可以告诉我为什么吗？

原因如下。

有几件事你需要了解

1。变量类型

首先，你需要知道Java中有两种类型的变量:Primitive和Reference。

整数通常是基元，因此变量本身就是整数值:int a = 1234;:a 本身的值为 1234。

要比较原始变量，您应该使用==

对于引用类型，变量本身就是一个“指针”。在 Java 中，有原语的包装类。例如，Integer 是 int 的包装器。因此，在 Integer a = new Integer(1234); 中，a 不包含 1234 的值。它是一个指向Integer对象引用的指针。在引用类型变量上使用 == 不会比较内容，而仅检查指针值是否相同(即检查它们是否指向同一个对象实例)

2。自动装箱

从 Java 1.5 (iirc) 开始，有一个称为自动装箱(和拆箱)的功能，可以方便程序员在基本类型及其相应的包装器之间进行转换。

过去，你需要做这样的事情:

int a = 1234;
Integer intWrapper = new Integer(a);

int b = intWrapper.intValue();

使用自动装箱，您只需编写:

int a = 1234;
Integer intWrapper = a;
int b = intWrapper;

编译器会将其转换为:

int a = 1234;
Integer intWrapper = Integer.valueOf(a);
int b = intWrapper.intValue();

到目前为止还好吗？

最终答案

所以您的代码适用于小数字的原因是:Integer.valueOf() 正在缓存常用的值。来自 API 文档:

public static Integer valueOf(int i)

Returns an Integer instance representing the specified int value. If a new Integer instance is not required, this method should generally be used in preference to the constructor Integer(int), as this method is likely to yield significantly better space and time performance by caching frequently requested values. This method will always cache values in the range -128 to 127, inclusive, and may cache other values outside of this range.

因为它正在缓存包装器，因此如果您正在执行 map.put(key,map.get(key) + 1)，则 get(key) + 1< 的结果，它是一个 int，当转换为 Integer 时，如果它是一个小数字，将是 Integer 的相同实例相同的 int 值。这意味着 == 仍然有效(因为变量指向相同的 Integer)。但是，如果它是未缓存的数字，则每次调用都将是不同的实例，并且 == 将不起作用(因为变量指向 Integer 的不同实例，但Integer 实例中的值是相同的)

<小时/>

对你的算法的建议，虽然有点偏离主题:

你的逻辑太复杂了。可以大大简化为(伪代码):

countValley(String s) {
    currentLevel = 0
    valleyCount = 0
    for (step in s) {
        if step == 'U' {
            ++currentLevel;
            if (currentLevel == 0) {  // returning to sea level
                ++valleyCount
            }
        } else if step == 'D' {
            --currentLevel;
        }
    }
    return valleyCount
}