java - 艰难的算法 - 不要让相同的字符重复 n 个位置

Question

我无法弄清楚这个问题，因为我不知道如何计算“插入”下划线。我包括了我解决这个问题的尝试。

Given a string, do not let the same character repeat for n positions. If it does repeat, insert an underscore to push it X positions down. The final output needed is just the total number of characters.

• Example 1) Input "QQ",2 becomes "Q__Q", the return value is 4.
• Example 2) Input "ABCA",2 becomes "ABCA" (no spaces needed), total characters is 4.
• Example 3) Input "DEDEE", 1 becomes "DEDE_E", total chars is 6.
• Example 4) Input "JKJK", 2 becomes "JK_JK", total characters is 5 (The toughest example).

import java.lang.Math;
import java.util.HashMap;
import java.util.ArrayList;

public class Spacer {
    public static void main (String args[]) {
        System.out.println("QQ,2 = " + spacey("QQ", 2) + ", expected 4");
        System.out.println("ABCA,2 = " + spacey("ABCA",2) + ", expected 4");
        System.out.println("DEDEE,1 = " + spacey("DEDEE", 1) + ", expected 6");
        System.out.println("JKJK,2 = " + spacey("JKJK", 2) + ", expected 5");
    }

    private static int spacey(String word, int spaces) {
        // int shift = 0;
        HashMap<Character, Integer> hm = new HashMap<>();
        for (int i=0; i<word.length(); i++) {
            char letter = word.charAt(i);
            System.out.println(i + "=" + letter + " last saw " + hm.get(word.charAt(i)));
            if (hm.get(letter) == null) {
                hm.put(letter, i);
            } else {
                System.out.println(i + "-" + hm.get(letter) + "<=" + spaces);
                if (i - hm.get(word.charAt(i)) <= spaces) {
                    // System.out.println("add " + (spaces + 1 - (i - hm.get(letter))));
                    // shift += (spaces + 1) - (i - hm.get(letter));
                    word = word.substring(0, i) + "_" + word.substring(i);
                    System.out.println(i + " word=" + word);
                }
                hm.put(letter, i);      // update the hashmap with the last seen again
            }
        }
        return word.length();
    }
}

Answer 1

您的问题(主要)是关于插入下划线的。可以帮助向前推进的一个关键见解是输入和输出字符串不同，因此使用 StringBuilder 这样对待它们会更清晰。例如。此外，在这个阶段使用临时变量来捕获字符之间的距离等概念也没有坏处。利用这两个想法，你可以有更多的自解释代码，例如:

public static String space(String input, int spaces) {
    HashMap<Character, Integer> map = new HashMap<>();
    StringBuilder result = new StringBuilder();
    for( char symbol : input.toCharArray() ) {
        int position = result.length();
        int lastPosition = map.getOrDefault(symbol, position-spaces-1);
        int distance = position - lastPosition -1;
        for( int j = 0; j < Math.max( spaces - distance, 0) ; j++ ) {
            result.append('_');
        }
        result.append(symbol);
        map.put(symbol, result.length()-1);
    }
    return result.toString();
}

(一旦掌握和消化了这一点，当然可以内联临时工)