Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняСтатья 30 темы LeetCodeСтатья, давайте рассмотрим задачу группировки строк.
смысл названия
Смысл этого вопроса очень прост, учитывая массив строк, спроситеСгруппировать все строки по составу.
Например, задан массив [есть, ел, чай, загорать, нат, летучая мышь].
Среди них все буквы, используемые в трех словах есть, ели и чай, — это е, т и а. И tan, и nat используют a, n и t, и, наконец, остается bat, поэтому результаты группировки следующие: [есть, ели, чай], [tan, nat] и [bat].
Насилие
Мы по-прежнему исходим из самой простой идеи, а группируемся по признакурегистр букв, используемых в каждой строке. Таким образом, мы можем разобрать все элементы в каждой строке и поместить их в словарь, а затем использовать этот словарь в качестве критерия группировки и поместить строки с одним и тем же словарем в одну группу.
Например, мы превращаем его в {'e': 1, 'a': 1, 't': 1}. Поскольку буква может встречаться более одной, нам также нужно записать количество вхождений. Но есть проблема, dict это динамические данные,В Python мы не можем использовать его как ключ другого словаря.. Более простой способ сделать это - написать методобъединить этот дикт в строку, например "e1a1t1". Мы используем это как ключ. Но у этого есть другая проблема.Ключи в словаре не обязательно упорядочены, поэтому нам нужно отсортировать словарь.Вы можете увидеть процесс на рисунке ниже.
То есть нам нужно реализовать функцию, входом которой является строка, а выходом — элементы этой строки.
def splitStr(s):
d = defaultdict(int)
for c in s:
d[c] += 1
ret = ''
# 将dict中内容排序
for k,v in sorted(d.items()):
ret += (str(k) + str(v))
return ret
Здесь все просто, мы создаем еще один словарь во внешнем слое для использованияХранить сгруппированные результатыТо есть мы можем легко написать код:
from collections import defaultdict
class Solution:
def splitStr(self, s):
d = defaultdict(int)
# 拆分字符串中元素
for c in s:
d[c] += 1
ret = ''
# 将dict中内容排序
for k,v in sorted(d.items()):
ret += (str(k) + str(v))
return ret
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for s in strs:
# 拿到拆分之后的字符串作为key进行分组
key = self.splitStr(s)
groups[key].append(s)
ret = []
for _, v in groups.items():
ret.append(v)
return ret
Некоторым друзьям может быть известно о проблеме, так как мы сначала конвертируем его в словарь, а затем объединяем в строку, мыПочему бы просто не отсортировать строку напрямую, а как насчет использования отсортированного результата в качестве ключа? Строки с одинаковыми элементами будут иметь одинаковый результат после сортировки.
Например, apple и pplae после сортировки становятся aelpp, возможно ли это?
Идея ок, но подача не проходит. Причина тоже очень проста, ее можно выразить тремя словами, то естьсложность. Сложность этого очень велика, потому что длина строк не фиксирована, и нам нужно много накладных расходов, чтобы отсортировать их одну за другой. Кроме того, в качестве ключа мы используем отсортированный результат, который также будет занимать ресурсы хранения. Так что это не лучший способ.
hash
Далее появится наш главный герой.Все должны были видеть его по названию.Этот вопрос ихеш-алгоритмСвязанный.
Справедливости ради следует отметить, что название хеш-алгоритма звучит как гром, и мы часто слышим его, но многие люди не знают, что делает хэш-алгоритм или где мы его используем. Вы можете узнать больше о hashMap.
На самом деле содержание алгоритма хеширования очень простое, вы можетеПростой для понимания как отображение. Наш ввод может быть чем угодно, это может быть число, массив или объект, но наш вывод - этофиксированное количество байтинформация о составе. Например, взятие по модулю 4 на рисунке ниже является хеш-функцией Мы можем классифицировать числа по разным корзинам в соответствии с результатом взятия по модулю 4.
Мы можем разделить некоторые данные в одно и то же ведро по нашему желанию, мыВы также можете сделать результаты каждого хэша данных как можно более разными., это достигаетсясжатие информации. Например, мы хэшируем экземпляр размером 2 МБ и получаем 32-битную строку. Это эквивалентно использованию 32-битной строки для представления исходного содержимого размером 2 МБ, чтобы мы могли выполнять эффективные запросы или другие операции. Например, текущий модуль распознавания лиц можно просто понимать как хеш-функцию. Камера делает снимок, алгоритм хэширует фотографию в идентификатор, а затем обращается к базе данных, чтобы найти личную информацию, соответствующую этому идентификатору, для завершения процесса идентификации.
В этой задаче мы хотим разработать хэш-функцию, которая считывает строку,Хэш в соответствии с содержимым строки, чтобы гарантировать согласованность результатов, полученных при построении одного и того же строкового хэша. Через результат этого хеширования мы делим ведра, по сути вышеописанный метод тоже можно считать хеш-методом. Однако, поскольку задействована сортировка, она немного сложнее, а окончательный результат — строка. С точки зрения временной и пространственной сложности еще есть место для оптимизации. Давайте рассмотрим более часто используемый хеш-алгоритм. .
В этом алгоритме мывыберет простое число в качестве хеш-фактора, так что вероятность коллизии хэшей будет ниже. Чтобы построить результат хеширования по степени простого числа, давайте посмотрим на код:
def hash(dict):
ret = 0
prime = 23
# k代表字符，v表示出现次数
for k, v in dict:
ret += v * pow(23, ord(k) - ord('a'))
# 对2^32取模，控制返回值在32个bit内
ret %= (1 << 32)
return ret
Орд здесь — операция взятия ascii-кода, то есть преобразования английских букв в цифры. мыИспользуйте разные степени простого числа для представления разных букв, умноженный на количество вхождений буквы в качестве коэффициента. Наконец, хеш-значение каждой буквы накапливается, чтобы получить хеш-значение всей строки. Коэффициенты и степени построения одной и той же строки одинаковы, поэтому окончательные результаты суммирования, очевидно, будут одинаковыми. С этим проблем нет. вывод. Но, наоборот, действительно ли строки с одинаковыми хеш-значениями одинаковы?
На самом деле, если мы подумаем об этом, мы можем придумать контрпримеры.Например, если у нас есть один символ a, результат его хеш-значения равен
, хэш-значение одного b также легко вычислить, оно равно 23. Каково хеш-значение 23 a? Если посчитать, то 23. Поскольку, хотя силы, которые мы используем, различны, но их основы одинаковы, мыРазницу в показателях можно компенсировать предыдущими коэффициентами. Эта ситуация, когда результаты хэширования разных объектов одинаковы, называетсяхэш-коллизия, это не то, что мы ожидали. Но несомненно, что в большинстве случаев коллизии хэшей почти неизбежны. Поскольку цель нашего хэша — заменить исходные сложные и огромные данные простым числом или строкой, точно так же, как при съемке фотографии, два разных человека также могут выглядеть одинаково при съемке.
Мы существуем в этом процессеСжатие или потеря информацииНапример, мы используем 10-битные числа для представления исходных 2000-битных данных. Независимо от того, какую стратегию мы используем, данные, которые могут быть выражены 10 битами, ограничены. В соответствии с принципом голубиной клетки, пока у нас достаточно хеш-данных, всегда будут сталкиваться два разных результата хеширования данных.
Однако путем разработки соответствующих факторов и алгоритмов вероятность столкновений можно уменьшить или контролировать. Например, в этом вопросе мыЧем больше простое число, тем меньше вероятность столкновений., потому что чем больше выбранное простое число, тем больше символов нужно повторить, чтобы образовалась коллизия, и тем меньше вероятность ее возникновения.
Наконец, давайте посмотрим на полный код:
from collections import defaultdict
import math
class Solution:
def splitStr(self, s):
hashtable = [0 for _ in range(30)]
ret = 0
for c in s:
hashtable[ord(c) - ord('a')] += 1
# hash算法
for i in range(26):
ret = ret * 23 + hashtable[i]
# 控制返回值在32个bit内
ret %= (1 << 32)
return ret
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for s in strs:
key = self.splitStr(s)
groups[key].append(s)
ret = []
for _, v in groups.items():
ret.append(v)
return ret
В коде есть деталь.То, что мы только что написали, это v * pow(23, k).Почему мы изменили способ записи здесь?
Поскольку pow-функция в Python возвращает число с плавающей запятой, точность будет потеряна, что сильно повысит вероятность коллизии хэшей, поэтому мы изменили метод, который не применяет pow-функцию.
Суммировать
По сложности сегодняшняя задача несложная, даже люди, не знающие алгоритма хеширования, могут придумать решение. Однако наша цель не в том, чтобы быть актуальным, а в том, чтобы вырасти из него, и алгоритм хеширования — очень важный и очень простой алгоритм, который используется во многих приложениях и сценариях. Поэтому мы понимаем принцип алгоритма хеширования, что очень полезно для нашего будущего роста.
На сегодняшней статье все. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.