[python]ハッシュテーブル(2)

に質問重複文字のない最長部分文字列

重複文字がない最長部分の文字列の長さを返します.

ex入力:「abcabcbb」->出力:3(len(abc)->3)

ex)入力:「bbb」->出力:1

プール(スライドウィンドウとダブルポインタで寸法を調整)

def lengthOfLongestSubstring(self,s):
    used={}
    max_length , start = 0,0
    for index, char in enumerate(s):
        # 이미 등장했던 문자라면 'start' 위치 갱신
        if char in used and start <= used[char]:
            start = used[char] + 1
        else:
            max_length = max(max_length, index - start + 1)
        
        #현재 문자의 위치 삽입
        used[char] = index
        
    return max_length 
        

両ポインタとも左側から.

charが使用中であれば、既に出現している単語であるため、startはdickshernryのkeyを用いてcharの値を1加算して記憶する.

ただし、最初に出現した単語であれば、index-start+1と現在のmax length値を比較し、より大きな値をmax lengthに格納することができる.

used[CHAR]は、現在文字をキーとしたスケジュールである.

従って、startが既に出現している文字であれば左ポインタstartを現在位置に移動し、そうでなければ現在位置+1の位置に移動する.

に質問親K周波数要素

k回以上出現した元素を抽出する.

ex)入力:nums=[1,1,1,2,2,3]、k=2->出力[1,2]

草。カウンタを使用して負の値の順に抽出

import heapq
import collections
def topKFrequent( nums,k):
    freqs = collections.Counter(nums)
    freqs_heap = []
    # 힙에 음수로 삽입
    for f in freqs:
        heapq.heappush(freqs_heap , (-freqs[f],f))
    
    topk = list()
    #k번 만큼 추출, 최소 힙이므로 가장 작은 음수 순으로 추출
    
    for _ in range(k):
        topk.append(heapq.heappop(freqs_heap)[1])
        
    return topk

Counterでリストの要素の個数を数えます.

heapqでは、キー/値を変えて要素を負数に入れます.負数を使用すると、最も頻度の高い値が最大の負数になります.もしそうであれば、最小臀部で最も頻度の高い値を抽出することができます.

Python Down方式

def topKFrequent(nums,k):
    return list(zip(*collections.Counter(nums).most_common(k)))[0]

zipは、複数のリストを1つのtupleに組み合わせた関数である.

で梱包をキャンセルできます.

ex )

fruits = ['lemon' , 'pear' ,'watermelon']
for f in fruits:
    print(f, end=' ')

lemon pear watermelon

print(*fruits)

lemon pear watermelon

同様の結果が得られた.

［(1,3),(2,2)］が［(1,2),(3,2)］になることがわかる.