Преобразовать строку в строку на основе условия

Question

В качестве ввода у меня есть объект String, который содержит только '0'.

Пример ввода String word = "00000".

Вопрос заключается в том, чтобы преобразовать эту строку в другую строку в качестве вывода.

Преобразование заключается в замене некоторых '0' на '1' в некоторых конкретных позициях, в результате чего каждое '0' смежно по крайней мере с одним '1'.

некоторые примеры:

input     |    output
0000          0101
00000         01001
000000        010010
0000000       0100101
00000000      01001010

Как мы видим, выходы удовлетворяют условию, каждый '0' смежен хотя бы с одним '1'.

Вторым условием является то, что мы должны использовать минимальное число «1».

После некоторой работы я понял, что мы можем знать минимальное число '1', которое должно заменить значения 0.

Формула представлена ​​методом getMinNumber (String word).

Вот что я сделал.

  public class TestUtilities {

    public static void main( String[] args ) {

        String [] words ={"0000","00000","000000","0000000"} ;
        for (String str :words) {
            System.out.println(transform(str));
        }
    }
    private static String  transform( String word ) {
        int min =  getMinNumber(word);
        //////
        //Some processing Here  
        /////
        return "";
    }

    public static int getMinNumber(String word) {
        int min;
        if (word.length() % 3 == 0) {
            min = word.length() / 3;
        } else {
            min = (word.length() / 3) + 1;
        }
        return min;
    }
}

Как показано, я оставил часть обработки, потому что не нашел подходящего алгоритма. Обычно я должен заменять один 0 каждые три 0, но это не работает для каждого слова.

Я ищу решение, которое может обработать любое слово.

Answer 1

Чтобы получить минимальные значения 1, нам нужно, чтобы каждый 1 обрабатывал как можно больше 0, что означает, что нам нужно повторить 010 максимальное количество раз.Таким образом, мы можем начать замену нулей на 010 слева

0000000000
↓↓↓↓↓↓↓↓↓
010010010x   <- here you can't place another 010 and we have one extra place to fill

Если 010 не заполнило все число, это означает, что нам нужна одна или две цифры.

Что нам делать, если это одна цифра?Можем ли мы использовать 0 здесь?Давайте посмотрим: 010010010x станет 0100100100?
Это действительный результат?НЕТ, потому что последний ноль не имеет 1 рядом с ним.Поэтому мы не можем использовать 0, что оставляет нас с 1 как 0100100101.

Итак, если нам нужна еще одна цифра, мы заменим ее на 1.

Теперь, что происходит, когда у нас есть две цифры для заполнения, например 010010010xx?Мы не можем использовать 00, потому что у последнего 0 не будет соседних 1.

• Можем ли мы использовать 01?ДА: потому что мы получим 010010010<b><i>01</i></b> все 0 имеют смежные 1
• Можем ли мы использовать 10?ДА: потому что мы получим 010010010<b><i>10</i></b> и здесь также все 0 имеют смежные 1

Должны ли мы проверить 11?Нет, потому что мы уже можем использовать 01 или 10, которые добавляют один 1, в то время как 11 добавляет два 1, чтобы результат не содержал минимальное количество 1.

---

Я оставлю написание кода, используя этот подход для вас.

Answer 2

Я считаю ответ @ Пшемо элегантным и прямым.С его подходом вам даже не нужно рассчитывать минимальное количество 1 для замены.Тем не менее у меня есть альтернативный способ, который может быть полезен:

public static void main( String[] args ) {

    String [] words ={"00","000","0000","00000","000000","0000000","00000000","000000000","0000000000"} ;
    for (String str :words) {
        System.out.println(transform(str));
    }
}
private static String  transform( String word ) {
    int min =  getMinNumber(word);
    StringBuilder sb = new StringBuilder(word);
    //starting from char at index 1 replace each third '0' with '1'
    //and substract 1 for each replaced char from min 
    for(int i = 1; i< word.length(); i = i+3){
        sb.setCharAt(i, '1');
        min--;
    }
    //if minimum replacement count not yet met replace last char
    if(min >0){
        sb.setCharAt(word.length()-1, '1');
    }
    return sb.toString();
}

public static int getMinNumber(String word) { 
    //just replaced your logic to make it shorter; you can keep your own implementation
    return (int) Math.ceil(word.length() / 3.);
}