めも

メモ.

Leetcodeを進める:easyのみ(3)

easyの問題を中心に、pythonに限らず複数の言語で解いていく方針に。

コード:GitHub - Y-kyoto/leetcode

他の問題:leetcode カテゴリーの記事一覧 - めも

Problem657

概要:ロボットが上下左右に動き、その動き順が与えられる. 元の場所に戻ってこれるかを判定したい.

奇数回の動きでは元に戻ってこれないので false, 上下と左右の動き回数が同じならば戻ってこれるので true.

python3

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        # 奇数回では戻れないので返す
        if len(moves)%2==1:return False
        # 各動作の出現回数
        ms = {"R":0, "L":0, "U":0, "D":0}
        # 各動作の出現回数をカウント
        for mv in moves:ms[mv]+=1
        return ms["R"]==ms["L"] and ms["U"]==ms["D"]

真面目に最後の点の座標を求める場合は↓.

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        # 各動作の動きの定義
        ms = {"R":[1,0], "L":[-1,0], "U":[0,1], "D":[0,-1]}
        x, y = 0, 0

        # x/yを移動させる
        for mv in moves:
            m = ms[mv]
            x += m[0]
            y += m[1]

        return x==y==0

go

goではstring型に対してループを回す時、

  • stringのインデックスで取得した場合はbyteが取得できる
  • rangeでループした場合はruneが取得できる

ことに注意する. mには一文字単位のrune型のデータが入るので、stringに変換している. 使用しない変数は存在してはいけないので、 _(アンダーバー)で使用しないことを明記.

文字列の長さの取得についても,

  • len([]rune(str)): rune単位での文字列の長さ
  • len(str): byte単位での文字列の長さ

になる.

参考:Goのruneを理解するためのUnicode知識 - Qiita

func judgeCircle(moves string) bool {
    var mc = map[string]int{"R":0, "L":0, "U":0, "D":0}
    for _, m := range moves {
        mc[string(m)] = mc[string(m)] + 1
    }
    
    return mc["R"]==mc["L"] && mc["U"]==mc["D"]
}

Problem728

概要:left~right の範囲の数字について、数字の各桁の値で自分自身を割り算し、全ての桁で割り切れた数のリストを返す.

例:124 -> 124%1=0, 124%2=0, 124%4=0 => Trueなので答えに含める.

Python3

割り算なので, 0で割るケースのみ注意する. 文字列に変換して、各桁で割り算しながら試し、割り切れなかったら以降を確かめずに次の数へ行く.

class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        res = []

        for i in range(right-left+1):
            # left~rightの範囲をチェック
            i += left
            flag = True
            stri = str(i)

            # 0が含まれていたらスキップ
            if "0" in stri:
                continue

            # 割り切れない場合は答えに含めない
            for i_n in str(i):
                if not i%int(i_n)==0:
                    flag = False
                    break

            # 全て割れた場合は追加
            if flag:
                res.append(int(i))

        return res

all() を用いことで for ... で試した真偽値が全て真の時のみTrueになる条件が書ける. ゼロ割算が all以下で出てこないように、先に 0 が数字に含まれているかを評価する.

class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        res = []
        for i in range(right-left+1):
            stri = str(i+left)
            if not "0" in stri and all(((i+left)%int(i_n)==0 for i_n in stri)):res.append(i+left)

        return res

Problem905

概要:偶数をリストの前半、奇数をリストの後半に並べ直す.

python3

リストを2で割った時の値でソートし直す.

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        A.sort(key = lambda x: x % 2)
        return A

Problem961

概要:長さ2Nのリストが渡され、そのうち N 個は同じ値が入っている. N 回出現する値を返す.

リストの長さから、2回以上出現した値=N回出現する値とわかるので二回目が見つかったタイミングでそれを答えにして返す.

Python3

class Solution:
    def repeatedNTimes(self, A: List[int]) -> int:
        for i, ai in enumerate(A):
            if ai in A[:i]:
                return ai

submission detail

C#

C#ではリストに特定の要素が含まれるかを調べる方法として

  • Find: Find(x=>...)の条件を満たす初めの要素を返す
  • IndexOf: インデックスを返し、存在しないならば-1
  • Contains: 含まれているならば true

の3つの方法が考えられる. ここではintしか使用しないとわかっているので List にすでに見た要素を追加していき、過去に一度でも見たことがある要素が存在するならそれを答えにする.

public class Solution {
    public int RepeatedNTimes(int[] A) {
        var intList = new List<int>();
        int res = 0;
        
        foreach (int a in A){
            if (intList.IndexOf(a)>=0){
                res = a;
                break;
            } else {
                intList.Add(a);
            }
        }
        
        return res;
    }
}

submission detail

Problem977

概要:二乗した数字の大きさでソートして返す. 入力としてソート済みの数値の列がくる.

Python3

先頭が0以上なら、ソートせずに全て二乗して返せばいい.

末尾が0以下なら、二乗して逆順にしてから返せばいい.

どちらでもないならば、ソートしてから返す.

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        head, tail = A[0], A[-1]
        A = [x**2 for x in A]

        if head>=0:
            return A
        elif tail<=0:
            return reversed(A)
        else:
            A.sort()
            return A

最小限の構成、絶対値でソートしてから二乗して返す.

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        A.sort(key=lambda x: abs(x))
        return [x**2 for x in A]