データ構造とアルゴリズムPython版第8週OJジョブ

1文字列のすべての再配置(10分)
タイトル内容:
1つの文字列sと検索対象文字列pを指定し、s[i:i+len(p)]がpの1文字列であるようにするすべての下付きiを与えてください.
タイトル保証文字列p非空
入力形式:
2行の文字列、第1の動作s、第2の動作p
出力フォーマット:
条件を満たすすべての下付き文字を小から大に並べ、出力をスペースで区切る
対応する下付き文字がない場合は「none」を出力します
サンプルを入力:
cbaebabacd
abc
出力サンプル:
0 6
問題解決の考え方:
検索対象文字列pとs[i:i+len(p)]を並べ替えて順番に比較する
プログラムコード:

def findAnagrams(s, p):
    p_rank = sorted(p)
    sub = []
    for i in range(len(s)-len(p)+1):
        s_rank = sorted(s[i:i+len(p)])
        if p_rank == s_rank:
            sub.append(i)
    if sub == []:
        print('none')
    else:
        print(' '.join([str(i) for i in sub]))


s = [i for i in input()]
p = [i for i in input()]
findAnagrams(s, p)

2リストで最も頻繁に表示される要素(10点)
タイトル内容:
1つのリストとデジタルKが与えられ、リストの前のK個が最も頻繁に現れる要素が出現回数の逆順に出力される.K個未満の要素はすべての要素を返します
入力形式:
2行として入力
第1の行為が与えられたリストは、合法的なPython式で与えられる.
第2の動作数K
出力フォーマット:
K個以下の数字をスペースで区切る
サンプルを入力:
[1,1,1,2,2,3]
2
出力サンプル:
1 2
問題解決の考え方:
同じ周波数の場合、同じ周波数の場合は要素サイズで昇順に並べ替えます
プログラムコード:

def topKFrequent(nums, k):
    dict = {}
    for i in set(nums):
        dict[i] = nums.count(i)
    tuple = sorted(dict.items(), key=lambda x: (x[1],-x[0]), reverse=True) #       ，               
    result = []
    if len(tuple) < k:
        for i in range(len(tuple)):
            result.append(tuple[i][0])
        print(' '.join([str(i) for i in result]))
    else:
        for i in range(k):
            result.append(tuple[i][0])
        print(*result)


lst = eval(input())
k = int(input())
topKFrequent(lst, k)

3ハッシュ(10点)
タイトル内容:
指定されたサイズNのハッシュ・リストを指定し、一連の数値を入力します.空のスロットが見つかったら、その数値を挿入し、スロットの位置に戻ります.この数値がハッシュ・リストに存在する場合、その位置が直接出力されます.
注意:ハッシュ競合を解決するには、下付きスケールで増加した二次プローブを使用します.
注意2:ハッシュ・リストの実際のサイズは、ユーザーがNを入力した最小質量数より小さくないように決定する必要があります.
入力形式:
2行
第1動作ユーザ指定ハッシュサイズN
2番目の動作は、スペースで区切られた一連の数値です.
出力フォーマット:
各出力に対応する数値は、ハッシュ・リスト内の位置でスペースで区切られます.
数値を挿入できない場合は、"-"を出力します.
サンプルを入力:
4
10 6 4 10 15
出力サンプル:
0 1 4 0 -
問題解決の考え方:
二次プローブ法とは、現在のkeyが以前のkeyとハッシュ競合した場合、現在のkeyには、そのアドレスの後オフセット量(1,2,3...)の二次方アドレスが存在することを意味する.
プログラムコード:

def createHashTable(n):
    if n <= 2:
        return [None] * 2
    for i in range(2, n):
        if n % i == 0:
            n += 1
    else:
        return [None] * n


def insertNumbers(table, nums):
    lenth = len(table)
    result = []
    for i in nums:
        hashValue = i % lenth
        if i in table:
            result.append(table.index(i))
        elif table[hashValue] == None:
            table[hashValue] = i
            result.append(hashValue)
        else:
            for j in range(1, lenth):
                hashValue = (i + j * j) % lenth
                if table[hashValue] == None:
                    table[hashValue] = i
                    result.append(hashValue)
                    break
            else:
                result.append('-')

    print(*result)


n = int(input())
nums = list(map(int, input().split()))
table = createHashTable(n)
insertNumbers(table, nums)