【Python】paizaラーニング レベルアップ問題集「特殊な探索」【線形探索】前編

2023/07/24に公開

「定番アルゴリズムの学習」線形探索メニュー「特殊な探索」の問題を解いてみました。

https://paiza.jp/works/mondai/sequence_search_problems/problem_index?language_uid=python3

問題を解くために組んだ関数をご紹介します。

※この問題集では、線形探索アルゴリズム学習のため原則として組み込み関数を禁じ手とし、愚直な探索を行っています。

偶数の探索

def searchFirstEven(l: list):
    """
    リストの中で最初に現れる偶数のインデックスを返す。
    ない場合は-1を返す。
    """
    p = 0
    while p < len(l):
        if l[p] % 2 == 0:
            return p
        p += 1
    return -1

奇数の探索

最後に見つかった数を戻り値とするため、一時変数latestを用意します。また、見つからない場合に備えてフラグ変数flagFalseで初期化し、奇数が見つかった時点でTrueに変更します。

def searchLastOdd(l: list):
    """
    リストの中の最後の奇数を返す。
    ない場合は-1を返す。
    """
    p = 0
    latest = 0
    flag = False
    while p < len(l):
        if l[p] % 2 == 1:
            flag = True
            latest = p
        p += 1
    if flag:
        return latest
    else:
        return -1

条件付き最小値

最小値の初期値として非常に大きな整数を入れておきます。

def minimumOver(l: list, k: int):
    """
    リストの中でk以上の最小値を返す。
    """
    p = 0
    mn = 2**31
    while p < len(l):
        if l[p] < mn and l[p] >= k:
            mn = l[p]
        p += 1
    return mn

条件付き最大値

やることは先程と反対です。最大値の初期値に非常に小さな整数を入れておきます。

def maximumUnder(l: list, k: int):
    """
    リストの中でk以下の最大値を返す。
    """
    p = 0
    mx = -(2**31)
    while p < len(l):
        if l[p] > mx and l[p] <= k:
            mx = l[p]
        p += 1
    return mx

残りは後編に書きます。

Discussion