[1日3後を知る](ハッシュ)完走しなかった選手、電話番号リスト、スパイ

3475 ワード

ソース:プログラマ

完走していない選手


参加者と完走者のリストがあります.
参加者数と完走者数は1差しかない.
フルコースを走る人のリストをもとに、参加者の中で誰がフルコースを走っていないのかを見つけます.(急げ!)
1.フルコースランナーリストを巡り、ディックシャーナを作る.このとき,全行程を走る者の名前ごとに時間を計る.(同名)
2.その後参加者名簿を巡回制作する.このとき,各参加者の名前をカウントする.(同名)
3.だから参加者/完走者の数が違うと、こいつは完走していない.参加者はいるが、完走した人は完走していない.
# def solution(participant, completion):
    
#     for complete_id in completion:
#         participant.remove(complete_id)
#     answer = participant[0]
#     return answer

def completion_dic(completion):
    hash_dic = {}
    
    for completion_id in completion:
        if completion_id in hash_dic:
            hash_dic[completion_id] = hash_dic[completion_id] +1
        else:
            hash_dic[completion_id] = 1
    return hash_dic

def participant_dic(participant):
    hash_dic = {}
    
    for participant_id in participant:
        if participant_id in hash_dic:
            hash_dic[participant_id] = hash_dic[participant_id] +1
        else:
            hash_dic[participant_id] = 1
    return hash_dic

def solution(participant, completion):
    
    comp_dic = completion_dic(completion)
    part_dic = participant_dic(participant)
    
    for participant_id in participant:
        # no same name
        if participant_id not in comp_dic:
            answer = participant_id
        
        # yes same name
        else:
            if part_dic[participant_id] != comp_dic[participant_id]:
                answer = participant_id
        
    return answer
最初は間違いだと思っていたけど、リストでアプローチ.
タイムアウトで淘汰されたので
直接近似値のdict特性により計算複雑度はO(1)~O(n)であった.
逆にlistはO(n)である.

電話番号リストで接頭辞を検索

  • 携帯電話番号の個数またはここでは存在するか否かのみを考慮したハッシュ図を作成する.
  • は、すべての携帯電話番号リストを巡回し、接頭辞が1番生成のハッシュテーブルに存在するかどうかを計算する.
  • # 접두어 dictionary
    # 중요 아이디어 : 폰넘버가 해쉬맵에 존재하는지 여부를 1로 표현
    def str_to_dic(dic, phone_num):
    
        dic[phone_num] = 1
        return 1
    
    # given strings, comparing algo
    def solution(phone_book):
        answer = True
        dic = {}
        for phone_num in phone_book:
            str_to_dic(dic, phone_num)
        
        # 폰넘버별로 가능한 모든 접두어 경우의 수를 해쉬 맵에서 찾는다
        for phone_num in phone_book:
            startswith = ''
            for char in phone_num[:-1]:
                startswith = startswith+char
                
                # 접두어 경우의 수 가운데 해쉬 맵에 존재한다면
                if startswith in dic:
                    answer = False
        
        return answer
    最初はハッシュ表の使い方がよく分からなかったようです.
    常にリスト式に近い.
    最初のアクセス方法も、すべての接頭辞の数を求めることによってハッシュマップを作成します.
    すべての接頭辞に対して、数->2つの砲口->を作成できます.計算に失敗しました
    ハッシュは、値を迅速に生成する方法です.
    第1砲で素早く値を見つけたハッシュの長所をよく考えてみましょう.

    スパイ


    スパイ服の数の問題
    1.アパレルカテゴリが1つでない場合、不均一を含むすべての均一な場合の数を数字で近似して求め、すべてのカテゴリから1つの不均一な場合を削除する.
    2.例外の場合、1つのカテゴリしか存在しない場合は、対応するカテゴリの服装個数を返します.
    def get_cats(clothes, dic):
        for item, category in clothes:
            if category in dic:
                dic[category] += 1
            else:
                dic[category] = 1
        return 1
        
    
    
    def solution(clothes):
        dic = {}
        get_cats(clothes,dic)
        answer = 0
        
        
        _ = 0
        if len(dic.keys()) >= 2: # 카테고리가 2개 이상인 경우
            _ = 1
            for value in dic.values():
                _ = _ * (value+1)
            answer = _ - 1
        
        else: # 카테고리가 1개인 경우
            answer = dic[clothes[0][1]]
        
        return answer
    これは簡単です.
    Pythonバイナリのみの利用であれば、数量問題