加权一致串

Question

问题

改编自这个黑客等级问题。

与打印YES或NO不同，我只想返回输入String的所有可能权重的Set。

我发现这个例子是说明性的。

Implementation

我的一些想法正在实施中，作为评论。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class WeightedUniformStrings {
  public static Set<Long> getWeights(String s) {
    // I thought about using streams here, but I'm not using java 8
    Set<Long> weights = new HashSet<>();
    Map<Character, Long> consecutiveCharacterCounts = WeightedUniformStrings.getConsecutiveCharactersCounts(s);
    for (Map.Entry<Character, Long> entry : consecutiveCharacterCounts.entrySet()) {
      if (entry.getValue() != null && entry.getKey() != null) {
        long weight = WeightedUniformStrings.calculateWeight(entry.getKey());
        for (long i = 0; i < entry.getValue() + 1; i++) {
          weights.add(weight * i);
        }
      }
    }
    return weights;
  }

  private static long calculateWeight(char c) {
    // Could add a check to see if character is alphabetical
    return Character.toLowerCase(c) - 'a' + 1;
  }

  private static Map<Character, Long> getConsecutiveCharactersCounts(String s) {
    if (s.isEmpty()) {
      return new HashMap<>();
    }

    Map<Character, Long> consecutiveCharacterCounts = new HashMap<>();
    char[] chars = s.toCharArray();

    // I'm not a big fan of this initialization + for loop - but I haven't thought of a better alternative implementation
    char startingCharacter = chars[0];
    long consecutiveCharacterCount = 1;
    consecutiveCharacterCounts.put(startingCharacter, consecutiveCharacterCount);

    for (int i = 1; i < chars.length; i++) {
      char currentCharacter = chars[i];

      if (currentCharacter == startingCharacter) {
        consecutiveCharacterCount++;
      }

      if (currentCharacter != startingCharacter || i == chars.length - 1) {
        Long characterCount = consecutiveCharacterCounts.get(startingCharacter);
        if (characterCount == null || consecutiveCharacterCount > characterCount) {
          consecutiveCharacterCounts.put(startingCharacter, consecutiveCharacterCount);
        }
      }

      // Doing this logical check twice feels weird
      if (currentCharacter != startingCharacter) {
        startingCharacter = currentCharacter;
        consecutiveCharacterCount = 1;
        Long characterCount = consecutiveCharacterCounts.get(startingCharacter);
        if (characterCount == null || consecutiveCharacterCount > characterCount) {
          consecutiveCharacterCounts.put(startingCharacter, consecutiveCharacterCount);
        }
      }
    }

    return consecutiveCharacterCounts;
  }
}

Answer 1

避免不必要的数学

for (long i = 0; i < entry.getValue() + 1; i++) {

正如您在评论中所指出的，这应该从1开始。

        for (long i = 1; i < entry.getValue() + 1; i++) {

但我们也可以简化结尾。

        for (int i = 1; i <= entry.getValue(); i++) {

我们想要处理entry.getValue()，然后停止，所以这样做。不需要确定下一个我们不想去的地方。另一种方式是可行的，但这更容易读懂。

我们也不需要在这里使用long。因为Java数组的索引不能超过int的范围，所以我们可以确保所有计数都不会超过int的容量。当然，如果我们在这里更改为int，那么我们也应该在其他地方进行更改。

使用助手

consecutiveCharacterCounts.put(startingCharacter, consecutiveCharacterCount); for (int i = 1; i < chars.length; i++) { char currentCharacter = chars[i]; if (currentCharacter == startingCharacter) { consecutiveCharacterCount++; } if (currentCharacter != startingCharacter || i == chars.length - 1) { Long characterCount = consecutiveCharacterCounts.get(startingCharacter); if (characterCount == null || consecutiveCharacterCount > characterCount) { consecutiveCharacterCounts.put(startingCharacter, consecutiveCharacterCount); } } // Doing this logical check twice feels weird if (currentCharacter != startingCharacter) { startingCharacter = currentCharacter; consecutiveCharacterCount = 1; Long characterCount = consecutiveCharacterCounts.get(startingCharacter); if (characterCount == null || consecutiveCharacterCount > characterCount) { consecutiveCharacterCounts.put(startingCharacter, consecutiveCharacterCount); } } }

您可以通过一个助手方法来简化这个过程：

public static void update(Map<Character, Long> counts, char c, int count) {
    Long oldCount = counts.get(c);
    if (oldCount == null || count > oldCount) {
        counts.put(c, count);
    }
}

然后我们可以改变for循环的边界。

    for (int i = 1, n = chars.length - 1; i < n; i++) {
      if (chars[i] == startingCharacter) {
        consecutiveCharacterCount++;
        continue;
      }

      update(consecutiveCharacterCounts, startingCharacter, consecutiveCharacterCount);
      startingCharacter = chars[i];
      consecutiveCharacterCount = 1;
    }

    if (chars[chars.length - 1] == startingCharacter) {
      consecutiveCharacterCount++;
    } else {
      update(consecutiveCharacterCounts, startingCharacter, consecutiveCharacterCount);
      consecutiveCharacterCount = 1;
    }

    update(consecutiveCharacterCounts, chars[chars.length - 1], consecutiveCharacterCount);

现在，我们减少了一次迭代，在退出循环时，我们进行了不同的处理。这使我们不必对循环的每一次迭代进行额外的检查。

现在我们不需要对currentCharacter和startingCharacter进行三次比较。一次就够了。

使用continue比使用else节省了一定程度的缩进。

我们不需要为每个字母的第一个更新Map。逻辑没有这个作用。