В этой серии постов “Leetcode” я опубликую решения проблем с leetcode. Это правда, что вы можете найти большинство/множество решений для leetcode в Интернете, но я постараюсь опубликовать свои решения для проблем, которые интересны, или для проблем, для которых существующие решения недостаточно хорошо объяснены и заслуживают лучшего объяснения.
Цель состоит в том, чтобы поделиться знаниями, и чтобы люди, которые учатся, готовятся к собеседованиям или просто практикуются, могли лучше решать проблемы. Пожалуйста, не стесняйтесь комментировать, если у вас есть предложение или другой подход!
Учитывая слово, вам нужно судить, правильно ли в нем использование заглавных букв или нет.
Мы определяем использование заглавных букв в слове как правильное, когда имеет место один из следующих случаев:
- Все буквы в этом мире – заглавные, как “
- Все буквы в этом слове не являются заглавными, как “leetcode”.
- Только первая буква в этом слове заглавная, как “Google”.
В противном случае мы определяем, что в этом слове неправильно используются заглавные буквы.
Это довольно простая, но интересная проблема. Вы можете проверить доступные решения на сайте leetcode. Здесь я покажу другое решение, использующее другой подход.
Первая попытка
Сначала, после прочтения постановки задачи и просмотра примеров, легко увидеть, что все символы после первого должны быть равны, единственная проблема заключается в проверке того, является ли первый символ прописным или строчным, а затем, основываясь на этой информации, проверьте остальную часть строки.
То есть сказать:
Если строка начинается с верхнего регистра, то либо остальная часть строки также должна быть прописной, либо остальная часть строки должна быть в нижнем регистре.
Если строка начинается со строчной буквы, то остальные также должны быть в нижнем регистре.
Это кажется достаточно простым, и, вероятно, это следует сделать за один проход по всей строке, учитывая линейную временную сложность O(n).
Учитывая эту ситуацию, я думал об общем решении, которое выполняло бы один проход по строке и проверяло некоторые условия на основе первого символа.
Этот подход может немного запутать в случае, если первая буква прописная (пункт 1, упомянутый выше), так как вам также потребуется проверить второй символ, чтобы узнать, нужно ли проверять, чтобы все остальные символы были прописными или строчными.
На этом этапе решение может показаться довольно простым, но для этого потребуется выполнить оператор if-else с циклами for, каждый из которых имеет аналогичный код, но изменяет условие внутри цикла for.
После некоторого времени размышлений о возможных решениях этой проблемы я пришел к не столь очевидному и интересному решению, используя некоторую логику, основанную на наблюдениях за примерами.
Основная идея
Вместо того, чтобы смотреть в начало строки, как насчет того, чтобы посмотреть на ее конец? Возможные решения намного проще:
Если последний символ прописной, то вся строка должна быть прописной.
Если последний символ в нижнем регистре, то вся строка (пропуская первый индекс) должна быть в нижнем регистре.
Мы можем пропустить первого персонажа, теперь это вообще не имеет значения!(ну, по большей части). Потому что последний символ на самом деле говорит нам больше о строке, чем первый символ. Как я уже упоминал ранее, первый символ может быть прописным или строчным, но остальные ДОЛЖНЫ быть одинаковыми. Поэтому мы просто проверяем регистр для последнего символа, а затем проверяем тот же регистр для остальной части строки, начиная с индекса 1.
Однако мы должны рассмотреть один крайний случай, что, если у нас есть эта строка:
“ABCDEF”
Последний символ написан в верхнем регистре, а остальная часть строки, начинающаяся с индекса 1, также написана в верхнем регистре. Это было бы верно в соответствии с предыдущей логикой. Однако результат должен быть ложным, так как первый символ не является прописным. Мы можем просто проверить этот крайний случай, и все.
Объяснение и код
Сначала мы проверяем регистр последнего символа. Допустим, это прописные буквы:
“ABCEDFG” -> Последний символ “G” в верхнем регистре.
Затем мы проверяем, что все остальные символы в строке, начинающиеся с индекса 1, должны быть прописными.
То же самое и со строчными буквами. Например:
“abcdefg” -> Последний символ “g” в нижнем регистре
Логика в обоих случаях одна и та же:
- если в верхнем регистре, то все символы, начинающиеся с индекса 1, должны быть прописными.
- если в нижнем регистре, то все символы, начинающиеся с индекса 1, должны быть в нижнем регистре.
Поскольку у нас здесь двоичное решение, мы можем использовать некоторую пропозициональную логику:)
Обе стороны условного выражения должны быть одинаковыми, в противном случае мы возвращаем false. Это именно то, что обеспечивает таблица Exclusive или истинности.
Таким образом, в основном мы можем использовать оператор xor в Java “^” в качестве оператора условия внутри цикла for.
Наконец, еще до всего этого мы должны проверить наличие крайнего случая. Поэтому, если последний символ в нижнем регистре, а первый – в верхнем, просто верните значение false.
Код выглядит следующим образом:
public boolean detectCapitalUse(String word) {
boolean hasToBeUppercase = Character.isUpperCase(word.charAt(word.length() - 1));
if(hasToBeUppercase && Character.isLowerCase(word.charAt(0))) return false;
for (int i = 1; i < word.length(); i++) {
if(hasToBeUppercase ^ Character.isUpperCase(word.charAt(i))) return false;
}
return true;
}
Всегда давайте своим переменным правильные имена, которые могут оказать большое влияние на читаемость вашего кода.
Код довольно прост, и нам просто нужно один раз перебрать символы в строке. Как только логическое выражение “xor” становится истинным для любой строки в строке, мы возвращаем значение false. В противном случае вся строка соответствует ограничениям, и мы возвращаем true.
Сложность
- Время: O(n), мы выполняем цикл только один раз по строке.
- Пробел: O(1), мы создаем только логическую переменную, которая не зависит от размера входных данных.
Заключительные комментарии:
Иногда решение может быть более простым, если мы посмотрим на проблемы с другой точки зрения. В задачах кодирования часто бывает так, что проще начать с “конца” структуры данных (массивов, строк, списков). Это был один из таких случаев.
Обратите пристальное внимание на примеры и ограничения проблемы. Если возможно, подумайте о своих собственных примерах, а затем, получив информацию, постарайтесь заметить некоторые общие закономерности или свойства, которые могут дать вам больше информации о проблеме.
Всегда старайтесь думать о разных подходах. Попробуйте обобщить свое решение, чтобы не повторять свой код. Например, мне не нравится решение Leetcode (подход 1), так как в нем используется оператор if-else, оба делают практически одно и то же, за исключением условия внутри цикла for, которое можно обобщить, как я продемонстрировал здесь.
Оригинал: “https://dev.to/marcelos/leetcode-520-detect-capital-5a0j”