Как изменить длину клавиш на простой карте?

Question

Нам дается текст предложения (предложение представляет собой строку слов, разделенных пробелами) в следующем формате:

Первая буква в верхнем регистре. Каждое слово в тексте разделяется одним пробелом. Наша задача - переставить слова в тексте так, чтобы все слова располагались в порядке возрастания их длины. Если два слова имеют одинаковую длину, мы располагаем их в исходном порядке.

Example:

Input: text = "Keep calm and code on"
Output: "On and keep calm code"
Explanation: Output is ordered as follows:
"On" 2 letters.
"and" 3 letters.
"keep" 4 letters in case of tie order by position in the original text.
"calm" 4 letters.
"code" 4 letters.

Решение:

class Solution {
    
    public String arrangeWords(String inputText) {
        String text = inputText.toLowerCase();
        String[] allWords = text.split("\\s+");

        Map<Integer, List<String>> lengthToWordsMap = new HashMap<>();

        for (int i = 0; i < allWords.length; i++) {
            lengthToWordsMap.computeIfAbsent(allWords[i].length(), k -> new ArrayList<>());
            lengthToWordsMap.get(allWords[i].length()).add(allWords[i]);
        }

        StringBuilder answerStringBuilder = new StringBuilder();

        for (int length : lengthToWordsMap.keySet()) {
            for (String word : lengthToWordsMap.get(length)) {
                answerStringBuilder.append(answerStringBuilder.length() == 0 ? "" : " ").append(word);
            }
        }

        String firstLetterInUppercase = answerStringBuilder.toString().substring(0, 1).toUpperCase();
        String restOfSentenceInLowercase = answerStringBuilder.toString().substring(1);
        
        String answer = firstLetterInUppercase + restOfSentenceInLowercase;
        
        return answer;
    }
}

Я понимаю, что после разделения текста и сохранения его в Строковый массив, мы используем HashMap для хранения длины слов в качестве ключа и слов этой длины в качестве значений длины. Но ключи не сортируются в HashMaps, поэтому не сортируется и длина. Итак, после добавления слов каждого ключа (длины каждого слова) к «sb», как мы можем гарантировать, что слова переставлены в порядке возрастания их длины?

Edit:

Ладно, это не мой код. Это было одно из решений, размещенных на доске обсуждений. Этот вопрос размещен на Leetcode, и ссылка на него: здесь .

Это решение также проходит все 75 тестовых случаев, поэтому я не думаю, что это сработает случайно.

Answer 1

HashMap сохраняет ключи на карте, сначала преобразуя ключ в целое число, называемое значением ha sh. Это делается путем вызова метода hashCode() объекта. Затем поиск bin в таблице ha sh в зависимости от этого значения ha sh.

Если вы используете Oracle или OpenJDK, скорее всего, hashCode() of integer вернет само int (потому что значение ha sh также является просто int):

/**
 * Returns a hash code for a {@code int} value; compatible with
 * {@code Integer.hashCode()}.
 *
 * @param value the value to hash
 * @since 1.8
 *
 * @return a hash code value for a {@code int} value.
 */
public static int hashCode(int value) {
    return value;
}

Реализация HashMap по умолчанию сильно зависит от java -версии. Принцип (наивная реализация) состоит в том, чтобы взять модуль значения ha sh и длину таблицы, чтобы получить индекс:

index = hash % table.length; // Don't try this, it breaks for negative hash values.

Java 11 реализация, похоже, делает некоторый массив из- обман деревьев, где он ходит по столу, чтобы найти ха sh.

По крайней мере, я мог бы воспроизвести ваш пример с Java 11, и я мог бы сломать ваш пример, изменив эту строку:

    Map<Integer, List<String>> lengthToWordsMap = new HashMap<>(4);

Обратите внимание, что даже метод Integer.hashCode() не указывает , как он вычисляет значение ha sh, поэтому тот факт, что он вычисляет его с помощью функции идентичности, равен недокументированный и поэтому никогда не следует полагаться на него.

Ответ на ваш вопрос таков: это происходит потому, что благоприятные условия сговариваются (и уточняют c детали реализации), а не из-за определенных logi c.

Answer 2

Это просто еще один подход к решению проблемы с O(N Log N) временной сложностью и O(N) пространством.

public class Solution {
    public static final String arrangeWords(String text) {
        String[] s = text.toLowerCase().split(" ");
        Arrays.sort(s, (a, b) -> a.length() - b.length());
        String rearranged = String.join(" ", s);
        return Character.toUpperCase(rearranged.charAt(0)) + rearranged.substring(1);
    }
}

Вы не задаете вопрос, я думаю, ваш метод может быть O(N ^ 2) временем и O(N) пробел, но я могу ошибаться.

Ссылки

• Дополнительные сведения см. На Доске обсуждения . Существует множество принятых решений с множеством языков и объяснений, эффективных алгоритмов, а также асимптот c время / пространство анализ сложности ^{1 , 2} там.

Если вы готовитесь к собеседованию :

• Мы хотели бы написать коды без ошибок и чистые на основе стандартов и соглашений (например, c ^{1 , 2} , c ++ ^{1 , 2} , java ^{1 , 2} , c# ^{1 , 2} , python ¹ , javascript ¹ , go ¹ , ржавчина ¹ ).