java - 黑客排名 : Sherlock and Anagrams

Question

已关闭。此问题需要 debugging details 。目前不接受答案。

---

编辑问题以包含 desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem 。这将有助于其他人回答问题。

已关闭 3 年前。

Improve this question

问题描述:https://www.hackerrank.com/challenges/sherlock-and-anagrams

添加问题陈述的快照:

我只得到了几个正确的测试用例。我的算法是:

1. 查找给定字符串的所有子字符串。
2. 通过使用每个字母表的数组为每个子字符串创建代码。
3. 将该代码转换为字符串并使用 hashmap 映射该字符串。
4. 如果子字符串的映射值包含非零值，则增加结果。

我的代码:

 static int sherlockAndAnagrams(String s) {
 HashMap<String,Integer> map = new HashMap<String,Integer>();
 int d,i,k=0;
 int length = s.length();
 int n = length*(length+1)/2;
 String []sub = new String[n]; 
 for (d = 0; d < length; d++){
     for(i = d+1; i <= length; i++)
      {
        sub[k++] = s.substring(d, i);
      }
  }
int []c = new int[26];

  int result=0;;
for(int l=0;l<n;l++){
    for(int m=0;m<25;m++){
    c[m] = 0;
    }
   char []suba = sub[l].toCharArray();  
  for(char ch : suba){
      c[ch-'a']+=1;
  }
  String temp = Arrays.toString(c);
  Integer x = map.get(temp);
  if(x!=null){
      result = result+x;
    map.put(temp,++x);}
  else{
  map.put(temp,1);
   }
  }
  return result;
}

Answer 1

好的，这里有几件事。

• 您必须计算对的数量，而不是有多少碰撞。

• 所以，结果就是result = result + x;

• 此外，map.put(...,x++) 应该像我们一样 map.put(...,++x);将使用预先递增的值进行更新。

• 此外，您的 c 填充从 0 到 24 但它应该是 0到25。对于这个问题，最好只执行 Arrays.fill(c,0) 。

<小时/>

为了空间效率，我们完全可以避免将每个子数组放入数组中，而只是根据字符对子数组进行排序。这样，每个字谜将映射到映射中的相同键，帮助您避免将每个数组显式存储在 sub 字符串数组中。然而，整体空间复杂度将保持不变。