Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняТемы LeetCodeВ 39-й статье давайте рассмотрим 68-й вопрос LeetCode, Обоснование текста.
Официальная сложность этого вопросаHard, проходной балл меньше 1/3. И 624 одобряют, и 1505 не одобряют. Только взглянув на эти данные, вы можете подумать, что этот вопрос сложный, или что есть какие-то подводные камни, но на самом деле, проделав это, вы обнаружите, что это не так. Тема только немного сложная, не сложная, единственная возможность, что все больше боятся обработки строк.
смысл названия
Вопрос даст ряд слов и максимальную длину каждой строки, maxWidth, и попросит нас переставить эти слова в соответствии с этой длиной и организовать их как можно аккуратнее.
Тут столько метких определений, в первую очередь перестановка текстаДлина каждой строки фиксирована., это максимальная ширина. Для этого заголовок гарантирует, что в словах не будет слов длиннее этого предела.
Кроме того, требуется использовать как можно меньше строк для хранения этих слов. то естьКаждая строка должна содержать как можно больше слов, а порядок между словами менять нельзя, то есть слова следует располагать в порядке, заданном заглавием. Количество слов в строке не ограничено, их может быть одно или несколько. Если количество слов в строке превышает 1, между словами следует ставить пробелы. ТребоватьРасстояние между словами как можно равномернее, если невозможно гарантировать, что количество пробелов в каждом промежутке точно равно, то убедитесь, что количество пробелов спереди больше, чем количество пробелов сзади.
Последняя строка текста должна быть выровнена по левому краю, что означает, что все слова располагаются слева, а между словами есть только один пробел. Все остальные пробелы размещаются в конце строки.
Звучит как громоздко для меня, чтобы сказать это, но на самом деле это очень просто.Давайте посмотрим пример, чтобы понять.
输入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
输出:
[
"What must be",
"acknowledgment ",
"shall be "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be",
因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。
В приведенном выше примере мы видим, что входное слово разделено на три строки, каждая строка имеет длину 16 единиц. Слова дополняются пробелами, а единственная строка и последняя строка выравниваются по левому краю, то есть все пробелы находятся справа.
решение
Решение этого вопроса очевидно, в этом и смысл самого вопроса. То есть это тожешуточные вопросы, то, как и в случае с другими задачами моделирования, упомянутыми ранее, его характеристикиНазвание простое, но сделать это с кодом хлопотно. Это легко найти, если подумать.Во-первых, нам нужно сегментировать слова, чтобы узнать, какие слова находятся в строке. Затем размещение этих слов также очень специфично, размещение отдельных слов и нескольких слов различно, и необходимо судить, является ли это последней строкой, потому что размещение последней строки также различно.
После того, как эти проблемы решены, мы сталкиваемся с проблемой пробелов: нам нужно разумно расположить пробелы, чтобы слова располагались как можно более равномерно. Чтобы сделать пробелы как можно более однородными, необходимо сначала рассчитать, сколько пробелов и сколько пробелов. Затем выясните, сколько мест расположено в каждом промежутке, но, поскольку количество мест не может быть разделено поровну, также необходимо убедиться, что переднее пространство на одно больше, чем последнее. Итак, нам нужно снова вычислить остаток, чтобы выяснить, сколько пробелов и еще один пробел...
Очевидно, что это решение очень хлопотно, но, кажется, какое-то время не было особенно хорошего способа. Если вы новичок, вы можете чувствовать себя большой головой и бардаком, или вы можете написать много кода за один раз, а затем после запуска обнаружите, что ситуация совершенно неправильная, и ваш менталитет рухнет.
Итак, прежде чем мы начнем формально писать код, давайте поговорим о нашем опыте.
Я уже читал такую небольшую историю, в которой говорилось, что был выдающийся монах, который достиг Дао и, наконец, достиг Дао после многолетней практики. После этого не забудьте взять у него интервью и спросить: «Учитель, изменилась ли ваша жизнь после того, как вы достигли Дао?»
Именитый монах сказал: нет, они по-прежнему носят воду, рубят дрова и готовят еду каждый день.
Репортер снова спросил, разве ваша жизнь до просветления не была такой же?
Выдающийся монах покачал головой. Все было по-другому. До того, как он стал просветленным, он думал о рубке дров, когда носил воду, думал о приготовлении пищи, когда рубил дрова, и думал о переноске воды, когда готовил. После просветления носить воду — значит носить воду, а готовить — значит готовить.
История лживая, но правда верна. У нас так много дел каждый день, и я часто ловлю себя на том, что иногда только начинаю или на полпути к одному делу, и что-то другое приходит мне в голову. Иногда сила воли слаба, и внимание отвлекается на другие дела. Затем на полпути к другим вещам и вернитесь к текущей вещи. Не только при выполнении дел, но и при решении проблем, иногдаТекущая проблема явно не решена, а голова занята будущими проблемами. Очевидно, что это неэффективно.
Хотя мы не можем стать мастерами-монахами, мы также можем черпать вдохновение из этой истории. Составляя планы, согласовывайте общую ситуацию и смотрите далеко вперед. При выполнении смотрите себе под ноги, а о проблемах думайте потом.
Мы применяем эту идею к решению проблем.Хотя эта проблема имеет много деталей, мы обычно делим ее на два основных процесса.Первый процесс — сегментация, то есть сегментация слов, какие слова становятся строкой.Второй процесс – заполнение, то есть заполните соответствующее количество пробелов между словами, чтобы оно соответствовало смыслу вопроса.
Как узнать, сколько слов должно содержаться в этой строке? Конечно, это оценивается по длине слова, поэтому нам нужно поддерживать общую длину слова, а также нужен список для хранения текущего кандидата, чтобы стать кандидатом слова для строки.
Когда можно добавлять новые слова? Очевидно, это возможно только в том случае, если длина новых слов не будет превышать предела. В противном случае поместите слово на следующую строку.
Итак, согласно этой идее, мы можем написать код сегментации:
curLen, curWords = 0, []
for w in words:
# 由于要保证单词之间至少有一个空格，所以还需要加上候选词的数量
if curLen + len(w) + len(curWords) <= maxWidth:
curLen += len(w)
curWords.append(w)
else:
# TODO: 在curWords当中填充空格
# 把单词w放入下一行中
curLen, curWords = len(w), [w]
# 最后一行单独处理
if len(curWords) > 0:
# TODO 填充最后一行
Таким образом написана наша логика сегментации, и очевидно, что она не имеет ничего общего с заполнением. Как независимый компонент алгоритма, мы можем самостоятельно протестировать эту часть, чтобы убедиться в ее правильности. Так же нам удобно отлаживать в целом после написания всего кода.
Логика заполнения кажется немного более сложной, но ее можно внимательно перечислить.Все переменные являются определяемыми. Определяется количество пробелов, которые необходимо заполнить в первую очередь, равное maxWidth минус общая длина выбранного в данный момент слова. Также определяется количество заполненных пропусков, то есть количество слов -1. Итак, мы делим количество мест на количество мест, чтобы получить количество мест, выделенных для каждого места. Мы берем количество пробелов по модулю количества пробелов, и мы получаем количество пробелов, которым выделяется еще одно пространство.
def process(self, curLen, curWords, maxWidth):
# 空格数量
num_space = maxWidth - curLen
# 如果只有一个单词就没必要考虑分配，直接填充空格即可
if len(curWords) == 1:
return curWords[0] + ' ' * (maxWidth - curLen)
# 每个空隙分到的空格数量
num_sep = num_space // (len(curWords) - 1)
# 分到空格数量多一个的空隙
head_sep = num_space % (len(curWords) - 1)
cur = ''
# 分配
for i in range(len(curWords) - 1):
cur = cur + curWords[i] + (' ' * (num_sep + 1) if i < head_sep else ' ' * num_sep)
# 分配结束之后把最后一个单词连上
cur = cur + curWords[-1]
return cur
Мы связываем эти два компонента вместе, чтобы получить окончательный результат:
class Solution:
def process(self, curLen, curWords, maxWidth):
num_space = maxWidth - curLen
if len(curWords) == 1:
return curWords[0] + ' ' * (maxWidth - curLen)
num_sep = num_space // (len(curWords) - 1)
head_sep = num_space % (len(curWords) - 1)
cur = ''
for i in range(len(curWords) - 1):
cur = cur + curWords[i] + (' ' * (num_sep + 1) if i < head_sep else ' ' * num_sep)
cur = cur + curWords[-1]
return cur
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
ret = []
curLen, curWords = 0, []
for w in words:
if curLen + len(w) + len(curWords) <= maxWidth:
curLen += len(w)
curWords.append(w)
else:
ret.append(self.process(curLen, curWords, maxWidth))
curLen, curWords = len(w), [w]
# 单独处理最后一行
if len(curWords) > 0:
cur = ''
for i in range(len(curWords) - 1):
cur = cur + curWords[i] + ' '
cur = cur + curWords[-1]
cur += ' ' * (maxWidth - len(cur))
ret.append(cur)
return ret
Суммировать
На этом наша проблема решена. Выглядит очень сложной задачей, но после ее решения остается всего более 30 строк. Не знаю, проще ли, чем вы думаете?
Обнаружили ли вы, что мы очень верны соглашениям о программировании после того, как урезали вещи? По сути, функция в коде играет роль маленького модуля, и сложная функция тоже состоит из этих маленьких модулей, независимых друг от друга. С этой точки зрения, многие принципы модульного проектирования в процессе выполнения действий от сложного к простому и модульного проектирования в процессе разработки программы схожи.
Надеюсь, вам понравился сегодняшний вопрос, если можно, пожалуйстаобращать внимание, подбодрите меня и облегчите доступ к другим статьям.