Top.Mail.Ru

Перечень алгоритмов

Python. Простые алгоритмы

Рассматриваются алгоритмы линейной обработки списков, строк - это последовательный поиск и  нахождение заданного значения, когда нужно просмотреть все элементы с первого до последнего. Как только будет найден элемент, равный заданному значению, необходимо вывести найденное значение и завершить поиск. Такой  алгоритм является простейшим алгоритмом поиска. Сложность поиска O(n).

В программировании «О» большое описывает наихудший сценарий. Допустим, у нас есть массив чисел, где мы должны найти какое-то определенное число при помощи цикла for. Оно может быть найдено при любой итерации, и чем раньше, тем быстрее функция завершит работу. О-нотация всегда указывает на верхнюю границу, т. е., описывает случай, когда алгоритму придется осуществить максимальное количество итераций, чтобы найти искомое число. Как, например, в том случае, если это число окажется последним в перебираемом массиве

Строка содержит только заглавные буквы латинского алфавита (ABC…Z).Определите сколько раз встречается каждый символ. Выведите словарь, упорядоченный:

    • по убыванию значений
    • по возрастанию ключей

Выведите максимальное значение и ключ для этого значения.

st ='TFOBMOISUZUTULGEBPSZJKFQWZ'  # строка
s ="QWERTYUIOPASDFGHJKLZXCVBNM"   # алфавит

 

Способ № 1 Использование цикла for и словаря

d = {}
for x in s :
    
if st.count(x)!=0:
       d[x] = st.count(x)
d1 = { x:v
for x, v in sorted(d.items(), key = lambda x: x[1], reverse=1) }
print(d1)          # по убыванию значений
d1 = { x:v for x, v in sorted(d.items(), key = lambda x: x[0], reverse=0) }
print(d1)          # по возрастанию ключей
mx = max(d.values())
for x, v in d.items():
  
if v == mx:
      
print(v,":", x) # максимальное значение и ключ для этого значения

{'U': 3, 'Z': 3, 'T': 2, 'O': 2, 'S': 2, 'F': 2, 'B': 2, 'Q': 1, 'W': 1, 'E': 1, 'I': 1, 'P': 1, 'G': 1, 'J': 1, 'K': 1, 'L': 1, 'M': 1}
{'B': 2, 'E': 1, 'F': 2, 'G': 1, 'I': 1, 'J': 1, 'K': 1, 'L': 1, 'M': 1, 'O': 2, 'P': 1, 'Q': 1, 'S': 2, 'T': 2, 'U': 3, 'W': 1, 'Z': 3}

3 : U
3 : Z

 

 

Способ № 2 Использование множества и словаря

d = {x:st.count(x) for x in set(st) }
print(sorted(d.items(), key = lambda x: x[1], reverse=1))
print(sorted(d.items()))
mx =
max(d.values())
for x, v in d.items():
    
if v == mx:
      
print(v,":", x)

[('Z', 3), ('U', 3), ('F', 2), ('O', 2), ('B', 2), ('T', 2), ('S', 2), ('K', 1), ('E', 1), ('G', 1), ('W', 1), ('P', 1), ('J', 1), ('I', 1), ('M', 1), ('L', 1), ('Q', 1)]
[('B', 2), ('E', 1), ('F', 2), ('G', 1), ('I', 1), ('J', 1), ('K', 1), ('L', 1), ('M', 1), ('O', 2), ('P', 1), ('Q', 1), ('S', 2), ('T', 2), ('U', 3), ('W', 1), ('Z', 3)]

3 : Z
3 : U

st ='TFOBMOISUZUTULGEBPSZJKFQWZ' # строка

Способ № 1 Использование словаря


d = {}
for x in st:
  
if x in d:
         d[x] +=
1
  
else:
         d[x] =
1
maxkey = max(d, key = d.get)
print(maxkey)

# U
Временная сложность: O (n)

 

 

Способ № 2 Использование генератора

mxkey = max(st, key=lambda x: st.count(x))
print(mxkey)

# U
Временная сложность: O (n)

 


Способ № 3 Использование множества и словаря


d = {x:st.count(x) for x in set(st)}

sorted(d)

maxkey = max(d, key = d.get)
print(maxkey)

# U
Временная сложность: O (n)

s = '012A345A67A89'

В примере удаляем символ  'A'


Способ № 1. Использование метода replace()


s = s.replace('A','')
print(s)


# 0123456789
Временная сложность: O (n)

 

 

Способ № 1A. Удаляем только первое вхождение replace()


s = s.replace('A','',1)
print(s)


# 012345A67A89
Временная сложность: O (n)

Способ № 2. Использование цикла for


st =''
for x in s:
  
if x!='A':
       st+=x
print(st)

# 0123456789
Временная сложность: O (n) 

 

Способ № 3. Использование метода split()

m = s.split('A')
st =
''.join(m)
print(st)

# 0123456789
Временная сложность: O (n)

Проверьте, правильно ли в заданном тексте расставлены круглые скобки.

 

В заданном тесте убираем все символы кроме скобок

s = "".join(x for x in s if x in "()")

Способ 1. Использование метода replace()


s= '()()()'
# s= ')(()()()'
s = s.replace('()', "")
if len(s)==0:
  
print('Правильно')
else:
  
print('Не правильно')

#Правильно

 

 

Способ 2. Использование стека

stack = []
for ch in s:
      
if ch == '(':
           stack.append(ch)
      
elif ch == ')':
          
if stack:
               stack.pop()

if len(stack)==0:
  
print('Правильно')
else:
  
print('Не правильно')

#Правильно

 

Вариант для различных скобок

В заданном тесте убираем все символы кроме скобок


s = "".join(x for x in s if x in "({[]})")
# пока в строке есть пары скобок
while '()' in s or '[]'in s or '{}' in s:
   s = s.replace(
'()','').replace('[]','').replace('{}','')
if len(s) ==0:
  
print('Правильно')
else:
  
print('Не правильно')

#Правильно

s= 'Лучше промолчать, чем сказать и потом жалеть о том, что сказал; лучше промолчать, чем сказать необдуманно.'

Способ 1. Использование метода replace() и метода split()

s= s.replace('.','')
s= s.replace(
',','')

s= s.replace(';','')
s= s.replace(
' ','')
s = s.lower()
m = s.split(
' ')
print(m)
a =[]
for x in m:
  
if x not in a and len(x) > 1:
       a.append(x)
print(a)

#['лучше', 'промолчать', 'чем', 'сказать', 'и', 'потом', 'жалеть', 'о', 'том', 'что', 'сказал', 'лучше', 'промолчать', 'чем', 'сказать', 'необдуманно']

# ['лучше', 'промолчать', 'чем', 'сказать', 'потом', 'жалеть', 'том', 'что', 'сказал', 'необдуманно']


Способ № 2 Использование словаря

d = {x:m.count(x) for x in set(m) if len(x) > 1}
a=
list(d)
print(a)

# ['том', 'потом', 'что', 'чем', 'промолчать', 'сказать', 'лучше', 'жалеть', 'сказал', 'необдуманно']

Способ 3 Использование множества


s= s.lower()
d = [x
for x in set(s.split()) if len(x) > 1 ]
print(d)
# ['что', 'лучше', 'сказать', 'чем', 'жалеть', 'потом', 'промолчать,', 'том,', 'сказал;', 'необдуманно.']