скорость до питон вложенных цикла

Question

Вот мой код .Это занимает больше минуты, чтобы обрабатывать большие строки input.Is там какой-нибудь способ, чтобы закрепить этот

q=int(input()) 
x=input() 
count=0 
for i in range(q): 
    for j in range(q): 
     k= j+i+1 
     if k<=q: 
      u=x[i:k] 
      if u[0]==u[-1] or len(u)==1: 
       count+=1 


print(count) 

Answer 1

Если бы я получил вашу точку зрения, вот код

length = int(input()) 
s = input() 
count = 0 
# i: the head index of substring 
# j: the tail index of substring, and len(substring) <=length 
for i in range(len(s)): 
    for j in range(min(length, len(s) - i)): 
     if s[i] == s[i + j]: 
      count += 1 

print(count) 

Answer 2

По крайней мере, два вопроса:

1) Вы перебирают слишком много значений, где ваше k равно> q. Внутренняя петля должна быть в диапазоне, который зависит от i

2) какова точка всех этих срезов (u = x [i: k]) ?. Зачем проверять u [0] и u [-1] вместо x [i] и x [k-1] непосредственно? Кроме того, вы можете проверить длину вашего u, выполнив арифметику на i и k. Эти кусочки не нужны и, вероятно, являются главным виновником.

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

Answer 3

Ну, вы можете избежать нарезки, что делает ненужную копию:

q = int(input()) 
x = input() 
count = 0 
for i in range(q): 
    for j in range(q): 
     k = j+i+1 
     if k<=q: 
      if x[i]==x[k] or i==k: 
       count+=1 

print(count) 

Даже лучше, вы можете избавиться от внутренний цикл полностью

q = int(input()) 
x = input() 
count = q 
for i in range(q-1): 
    if x[i]==x[-i]: 
     count+=1 

print(count) 

Я не проверял, я с помощью мобильного телефона ...

Answer 4

Оптимизация алгоритма потребовала бы, чтобы вы определили flabs и отрезали его. Флаги выделяются четко, если вы видите условие с переменными цикла в цикле без блока else, и мы ясно видим это. Мы, безусловно, тратить итерации и которые должны быть обрезаны из

Ясно вместо перерасчета K, вам необходимо повторно запустить вторую петлю таким образом, что вы можете отказаться от промежуточной переменной j

Как k = j+i+1 где 0 <=j < q, мы можем переписать диапазон, i + 1 <= k < q + i + 1

, но мы также знаем, K < = д, так что указанное выше условие можно записать в виде i + 1 <= k < q + 1

так наша новая фу nction будет выглядеть так:

def bar(): 
    q=int(raw_input()) 
    x=raw_input() 
    count=0 
    for i in range(q): 
     for k in range(i + 1, q + 1): 
      u=x[i:k] 
      if u[0]==u[-1] or len(u)==1: 
       count+=1 
    return count 

Второе условие u[0]==u[-1] or len(u)==1 интересно. Вы создаете кусочек и проверить префикс и суффикс, а также длины

безусловно len(u) == k - i == 1, так что вам не нужно переоценивать ломтик и вызвать вызов функции, вместо этого мы можем написать, как k == i + 1

def bar(): 
    q=int(raw_input()) 
    x=raw_input() 
    count=0 
    for i in range(q): 
     for k in range(i + 1, q + 1): 
      if x[i]==x[k - 1] or k == i + 1: 
       count+=1 
    return count 

Answer 5

Вы надеваете Для этого вам нужно два цикла, чтобы сделать это, вы можете сделать это, просто подсчитав повторяющиеся символы кумулятивно. так что вы можете найти результат в O (n) времени, но в результате получите дополнительное пространство O (n).

q=int(input()) 
x=input() 
from collections import defaultdict 
d1 = defaultdict(int) 
count = 0 
for i in x: 
    d1[i] += 1 
    count += d1[i] 

print count 

Answer 6

Вот интересное решение, которое чрезвычайно эффективно.Он рассматривает проблему с совершенно другой точки зрения.

q=int(input()) 
x=input() 

y = x[0: q] 

alphabet = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 
     'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 
     'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0, ' ': 0} 

letters = set(list(y)) 
for letter in letters: 
    alphabet[letter] += y.count(letter) 

repeats = [i for i in list(alphabet.values()) if i > 1] 
singles = len(y) 

count = singles 
for repeat in repeats: 
    count += ((repeat*(repeat - 1))/2) 

Что здесь происходит? Посмотрите на искусственный пример, где y = 'abbda efba hia jkla mbnop' и рассмотрим символ 'a'. Как это подсчитывается?

1) Он подсчитывается каждый раз, когда он появляется в строке. Это 5 раз, и это фиксируется в словаре «алфавит». Существует один проход через уникальные символы в строке, чтобы получить счет. Это меньше или равно 27 символам. Я включил пробел. Это тоже нужно учитывать!

2) Символ 'a' также считается другим способом по оригинальному алгоритму. Он подсчитывается, когда он появляется на обоих концах подстроки. В этом случае для первого «а», который появляется, мы получаем вложенные строки:

abba 
    abba efba 
    abba efba hia 
    abba efba hia jkla 

для второго «а», который появляется там еще три таких суб строки:

a efba 
    a efba hia 
    a efba hia jkla 

И так вниз по линии. Поэтому мы подсчитываем «а» 5 раз за каждый раз, когда он появляется в строке, но также подсчитываем 4 + 3 + 2 + 1 подстроки, где они находятся на концах. Это просто r (r-1)/еще 2 числа для буквы «a». Нет необходимости в цикле, когда есть аналитическое выражение для результата. Это является основой эффективности алгоритма.