Я должен использовать целые числа без знака для подсчета участников?
Вы можете перебрать setA от самой короткой строки до самой длинной и добавить данную строку в setC, только если ни одна из возможных подстрок строки уже находится в setC. Вы можете сгенерировать все возможные подстроки из строки, перебирая начальный индекс по длине строки и перебирая размер подстроки от 1 до оставшейся длины строки из текущего начального индекса, а затем используя начальный индекс и длина подстроки для нарезки строки:
setC = set()
for s in sorted(setA, key=len):
if not any(s[i: i + n + 1] in setC for i in range(len(s)) for n in range(len(s) - i)):
setC.add(s)
setC становится:
{'AAB'}
Это улучшает общую сложность времени с O (n ^ 2) вашего решения O (n log n) .
6 ответов
Нет, определенно нет. Delphi идиома здесь использовать целые числа. Не борись с языком. В 32-битной среде у вас не будет больше элементов в списке, за исключением случаев, когда вы попытаетесь создать растровое изображение.
Давайте проясним: каждый программист, которому придется использовать ваш код, будет ненавидеть вас за использование кардинал вместо целого числа.
Беззнаковые целые числа почти всегда доставляют больше хлопот, чем они того стоят, потому что в какой-то момент вы обычно смешиваете целые числа со знаком и без знака в выражениях. Это означает, что тип должен быть расширен (и, возможно, иметь снижение производительности), чтобы получить правильную семантику (в идеале компилятор делает это в соответствии с определением языка), иначе вам нужно быть очень осторожным при проверке диапазона.
Возьмем, например, C / C ++: size_t - это тип целого числа для размеров и распределения памяти, он не имеет знака, но ptrdiff_t - это тип смещения, которое вы получаете, когда вы вычитайте один указатель из другого, и обязательно подписывайте. Хотите знать, сколько элементов вы размещены в массиве? Возможно, вы вычли адрес первого элемента из адреса последнего элемента + 1 и поделили на размер sizeof (тип элемента) ? Что ж, теперь вы просто смешали целые числа со знаком и без знака.
Что касается вашего заявления о том, что «Я думаю, что в целом это хороший принцип - всегда использовать наименее общий (а значит, самый особенный) тип». - на самом деле, я думаю, что это хороший принцип - использовать тип данных, который вызовет у вас наименьшее беспокойство и Проблема.
Обычно для меня это подписанное int, поскольку:
- У меня обычно нет списков с 2 31 или более элементами в них.
- У вас не должно быть таких больших списков. либо: -)
- Мне не нравится, когда в моем коде возникают особые крайние случаи.
Но это действительно проблема стиля. Если «чистота» кода важнее для вас, чем краткость кода, Ваш метод лучше всего (с модификациями, чтобы поймать крайние случаи). Сам я предпочитаю краткость, так как крайние случаи имеют тенденцию загромождать код и уменьшать понимание.
Мораль: используйте итераторы и foreach , когда можете, потому что это полностью исключает этот вопрос.
Не.
Это не просто идет вразрез с идиомой программирования, это явный запрос к компилятору использовать арифметику без знака, которая либо склонна к аномальному поведению (если вы не t защита от переполнений) или от несущественных исключений времени выполнения (если вы защитите от переполнений, временное переполнение будет фатальным, например, если вычесть перед добавлением, даже если конечный результат положительный, и я имею в виду уровень кода операции ЦП упорядочение операций, которые могут не иметь тривиального отношения к тому, что у вас есть в вашем коде).
Имейте в виду, что «unsigned» не не переводит в «положительное», оно переводится как «не есть знак ", который отличается. Термин «без знака» был выбран не зря (и назвал его «Кардинал»). в Delphi было плохим выбором IMO).
Типы без знака предназначены для необработанных спецификаций хранения, побитовых операций, кода ASM, встроенных контроллеров и других специальных применений. Когда вы занимаетесь программированием высокого уровня, вы должны забыть, что когда-либо слышали о неподписанных типах.
Граничные условия часто представляют проблемы. Разрешение на тип, который может стать отрицательным, может просто сдвинуть проблему. Возможно, это смещает его так, что его легче отлаживать, а может и нет. Я начал использовать целые числа для подсчета таких циклов, но позже переключился на кардиналы, чтобы помочь мне отлавливать ошибки.