Chapter 1: 配列と文字列

1.1 重複のない文字列

set を用いると楽。

def is_unique(s):
    return len(s) == len(set(s))

1.2 順列チェック

ソートしたものが同じかを比較する。sort() だと返り値が None であることに注意。

def is_permutation(s1, s2):
    return sorted(s1) == sorted(s2)

1.3 URLify

右端のスペースを取り除いた後で残りのスペースを %20 に置き換える。

def urlify(s):
    s = s.rstrip()
    s = s.replace(' ', '%20')
    return s

1.4 回文の順列

例を見る限り、大文字・小文字やスペースは関係ないらしいのでまず文字列を調整する。その後、各文字をカウントして記録しておく（今回は辞書を用いた）。調整した文字列の各文字が以下を満たせば回文が生成可能なのでそれをチェックする。

カウントがすべて偶数
カウントが奇数のものが 1 個

def is_palindrome_permutation(s):
    s = s.lower()
    s = s.replace(' ', '')

    d = {}
    while(s != ''):
        d[s[0]] = s.count(s[0])
        s = s.replace(s[0], '')

    odd_count = 0
    for val in d.values():
        if val % 2 != 0:
            odd_count += 1

    if odd_count > 1:
        return False
    else:
        return True

1.5 一発変換

文字列が完全一致の場合は当然 True。一致しない場合は文字列の長さの差を見て場合分けを行う。

def is_edited(s1, s2):
    if s1 == s2:
        return True

    if len(s1) + 1 == len(s2):    # insert
        for i in range(len(s1)):
            if s1[i] == s2[i]:
                continue
            else:
                return s1[i:] == s2[i+1:]
        return True
    elif len(s1) - 1 == len(s2):  # delete
        for i in range(len(s2)):
            if s1[i] == s2[i]:
                continue
            else:
                return s1[i+1:] == s2[i:]
        return True
    elif len(s1) == len(s2):      # replace
        flag = False
        for i in range(len(s1)):
            if s1[i] != s2[i]:
                if flag:
                    return False
                flag = True
        return True

    return False

1.6 文字列圧縮

まず、与えられた文字列に対して、文字の変わり目に , を付けて、split 関数を用いることでリストを作る。

例: aaabcccdd → aaa,b,ccc,dd → ['aaa', 'b', 'ccc', 'dd']

あとはリストの要素を見て適当に圧縮文字列を作成していけばよい。最後に元の文字列との長さ比較をお忘れなく。

def compress(s):
    s_org = s
    s = s + ' '

    i = 0
    while s[i+1] != ' ':
        if s[i] == s[i+1]:
            i += 1
        else:
            s = s[:i+1] + ',' + s[i+1:]
            i += 2

    s = s.strip()
    l = s.split(',')

    compressed = ''
    for i in range(len(l)):
        compressed += l[i][0] + str(len(l[i]))

    if len(s_org) < len(compressed):
        return s_org
    else:
        return compressed

1.7 行列の回転

画像だとアレだから勝手に行列の回転にしました。というか勘違いしていたというか…

入力は AtCoder 風なものとする。

N

a₁₁ ... a_1N

:

a_N1 ... a_NN

これをリストの形で受け取って変換していくことにする。

N = int(input().strip())
A = [list(map(int, input().split())) for _ in range(N)]
A = rotate(A)

rotate 関数の中身であるが、受け取ったリストを NumPy 配列に変換して rot90 関数を用いればよい。回転後は tolist でリストの形に戻す。Python って便利ね～。

import numpy as np

def rotate(l):
    arr_l = np.array(l)
    arr_l_rot = np.rot90(arr_l)
    return arr_l_rot.tolist()

さて、これアルゴリズムの訓練にならないよね？と突っ込まれそうなので一応言っておくと、スマートな解法としては行列を上下逆にしてから転置をとると 90 度右に回転できるらしい。

qiita.com

1.8 0 の行列

行列に対し、走査を 2 回行う。1 回目の走査では要素 0 を持つ行・列の集合を作成する（それぞれ zeros_row、zeros_column とする）。

2 回目の走査で適切な場所に 0 を埋めていく。

def set_zeros(A, M, N):
    zeros_row = set()
    zeros_column = set()

    for m in range(M):
        for n in range(N):
            if A[m][n] == 0:
                zeros_row.add(m)
                zeros_column.add(n)

    for m in range(M):
        for n in range(N):
            if (m in zeros_row) or (n in zeros_column):
                A[m][n] = 0

    return A

1.9 文字列の回転

s2 が s1 の回転文字列ならば、s1 = xy と置いたとき、s2 = yx となるはず。yx は必ず xyxy の部分文字列なので、s1 + s1 に s2 が含まれているかを isSubstring メソッドで調べればよい。ただし、s1 と s2 の長さが同じであることを確かめる必要がある点に注意。

def isSubstring(s1, s2):
    return s2 in s1

def is_rotation(s1, s2):
    if len(s1) != len(s2):
        return False

    s1s1 = s1 + s1
    return isSubstring(s1s1, s2)

感想

序盤であるがかなり難しく感じた。~~世界で闘う気はないが~~世界の広さを早くも痛感する結果となったのは言うまでもない。というか半分以上解けなかったんだがこれからどうなるんだこれ

Koi なるもの

『世界で闘うプログラミング力を鍛える本』を Python で解く: Chapter 1