Подсчитывать вхождение символов в строку в понятном виде? - PullRequest
Новая
       8

Подсчитывать вхождение символов в строку в понятном виде?

2 голосов
/ 19 января 2020

Я выполняю следующее упражнение по программированию: Числа строки . Оператор:

Вам дана строка ввода.

Для каждого символа в строке, если это первый символ, замените его на '1', иначе замените его с количеством раз, которое вы уже видели ...

Но будет ли ваш код достаточно быстрым ? Примеры: 

input   =  "Hello, World!"
result  =  "1112111121311"

input   =  "aaaaaaaaaaaa"
result  =  "123456789101112"

В строке могут содержаться символы, не являющиеся символами ascii.

Примечание. Не будет переполнения домена int (число символов будет меньше 2 миллиардов).

Я написал следующий ответ: 

import java.util.*;
import java.util.stream.*;
public class JomoPipi {
  public static String numericals(String s) {
    System.out.println("s: "+s);
    Map<String, Long> ocurrences = Arrays.stream(s.split("")).
                                    collect(Collectors.groupingBy(c -> c,
                                    Collectors.counting()));
    System.out.println("ocurrences: "+ocurrences.toString());                                    
    StringBuilder result = new StringBuilder();                                    
    for(int i = s.length()-1; i >= 0; i--){
      String c = String.valueOf(s.charAt(i));
      result.append(ocurrences.get(c) + " ");
      ocurrences.put(c, ocurrences.get(c)-1);
    }
    System.out.println("result: "+result.toString());
    String[] chars = result.toString().split(" ");
    Collections.reverse(Arrays.asList(chars));
    String sorted = String.join("",chars);
    System.out.println("sorted: "+sorted);
    return sorted;
  }
}

Однако время ожидания (время выполнения превышает 16000 мс), когда входная строка велика.

Кому Посмотрите, как это работает, есть трассировка с очень маленькой входной строкой: 

s: Hello, World!
result: 1 1 3 1 2 1 1 1 1 2 1 1 1 
sorted: 1112111121311

Кроме того, я также написал следующий альтернативный ответ: 

import java.util.*;
import java.util.stream.*;
public class JomoPipi {
  public static String numericals(String s) {
    System.out.println("s: "+s);
    Map<String, Long> ocurrences = Arrays.stream(s.split("")).
                                    collect(Collectors.groupingBy(c -> c,
                                    Collectors.counting()));
    String[] result = new String[s.length()];                                   
    for(int i = s.length()-1; i >= 0; i--){
      String c = String.valueOf(s.charAt(i));
      result[i] = String.valueOf(ocurrences.get(c));
      ocurrences.put(c, ocurrences.get(c)-1);
    }
    System.out.println("result: "+Arrays.toString(result));
    return String.join("",result);
  }
}

Несмотря на это, он все еще синхронизируется out.

Вот трассировка с небольшой входной строкой: 

s: Hello, World!
result: [1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 3, 1, 1]

Как мы могли бы улучшить решение? Какой алгоритм будет работать лучше, чтобы обрабатывать очень большие входные строки? Где узкое место, которое мы должны отлаживать и избегать, чтобы улучшить этот ответ?

Чтобы попытаться решить его самостоятельно, я прочитал:

EDIT: Здесь у нас есть ответ, основанный на предложении @khelwood: 

import java.util.*;
import java.util.stream.*;
public class JomoPipi {
  public static String numericals/*?->?*/(String s) {
    Map<String, Integer> ocurrences = new HashMap<String,Integer>();
    StringBuilder result = new StringBuilder();
    for(int i = 0; i < s.length(); i++){
      String c = String.valueOf(s.charAt(i));
      ocurrences.putIfAbsent(c, 0);
      ocurrences.put(c,ocurrences.get(c)+1);
      result.append(ocurrences.get(c));
    }
    return result.toString();
  }
}

1 Ответ

2 голосов
/ 19 января 2020

Я думаю, что вы на правильном пути с Map, но ваш тип ключа должен быть Character, а тип подсчета Integer. Я думаю, что вы пошли не так, когда вы изменили и отсортировали результаты. Кроме того, ваш код будет легче читать без потока (и ключевой частью написания быстрого кода является запись немого кода ). Например, 

public static String numericals(String s) {
    int len = s.length();
    Map<Character, Integer> occurrences = new HashMap<>(); // ocurrences
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < len; i++) {
        char ch = s.charAt(i);
        int count = occurrences.getOrDefault(ch, 0) + 1;
        occurrences.put(ch, count);
        sb.append(count);
    }
    return sb.toString();
}

А затем проверить его 

public static void main(String[] args) {
    String[] input = { "Hello, World!", "aaaaaaaaaaaa" };
    String[] output = { "1112111121311", "123456789101112" };
    for (int i = 0; i < input.length; i++) {
        String result = numericals(input[i]);
        System.out.printf("%s %b%n", result, result.equals(output[i]));
    }
}

Какие выходы 

1112111121311 true
123456789101112 true
...