スタックと集計アルゴリズム応用【2020年Python実習職場-アルゴリズム問題】
11809 ワード
一、スタック構造問題入力:1つの文字列、要素は小文字からなる 出力:文字列内のすべての「b」と「ac」のアルファベットの組み合わせを除去する必要がある.すなわち、出力の結果に「b」と「ac」 が含まれない.
スタックの採用:O(n)実装構想:listのpop()メソッドを使用して、末尾から各文字をポップアップし、フィルタされていない文字を新しいリストに追加します.ただし、b文字に遭遇した場合は次の文字をポップアップし続け、また‘c’に遭遇した場合は複数回ポップアップし、2回ポップアップした内容が‘ac’であるか否かを判断し、もしそうであればポップアップを継続する. コードの内容は以下の通りである:
結果は次のとおりです.
二、並べ替えと重み付け入力:正の整数からなる配列で、要素が増加し始め、 減少するのが特徴です.出力:要求ソートと重量除去 集計アルゴリズムの使用が必要構想:集計アルゴリズムは分治アルゴリズム思想の一種であり、その核心思想は1つの大きな配列を中間から左右の2つの配列を分割し、この2つの配列をそれぞれ分割し、配列が1つの要素しかないときに戻るまで順番に類推し、戻り配列に対して先が小さくて後が大きい順に1つを合併することである. コードは次のとおりです:
テストコードは次のとおりです.
結果は次のとおりです.
スタックの採用:O(n)実装
s1 = 'goodbye disen! back see you !'
s1_list = list(s1)
new_str = []
while len(s1_list) > 0:
c = s1_list.pop()
if c == 'b':
continue
elif c == 'c':
c2 = s1_list.pop() if len(s1_list) > 0 else ''
if c2 != 'a':
new_str.insert(0, c)
if c2 != '':
new_str.insert(0, c2)
else:
new_str.insert(0, c)
print(''.join(new_str))
結果は次のとおりです.
goodye disen!k see you !
二、並べ替えと重み付け
def merge(arr_left, arr_right):
c = [] #
i = j = 0
#
while i < len(arr_left) and j < len(arr_right):
if arr_left[i] < arr_right[j]:
#
if arr_left[i] not in c:
c.append(arr_left[i])
i += 1
else:
#
if arr_right[j] not in c:
c.append(arr_right[j])
j += 1
#
# ( )，
# ，
if i == len(arr_left):
# c.extend(arr_right[j:])
for k in arr_right[j:]:
if k not in c:
c.append(k)
else:
# c.extend(arr_left[i:])
for k in arr_left[i:]:
if k not in c:
c.append(k)
return c
def merge_sorted(arr):
if len(arr) <= 1:
return arr
middle = len(arr) // 2
arr_left = merge_sorted(arr[:middle])
arr_right = merge_sorted(arr[middle:])
return merge(arr_left, arr_right)
テストコードは次のとおりです.
arr = [8, 2, 1, 4, 2, 8, 6, 1, 4, 5, 7]
print(merge_sorted(arr))
結果は次のとおりです.
[1, 2, 4, 5, 6, 7, 8]