めも

メモ.

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

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

コード:GitHub - Y-kyoto/leetcode

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

Problem595

概要:DBから面積と人口が指定以上の国を抽出する.

SQL問題、内容は簡単なのでインデントの仕方を覚えつつ提出.

# Write your MySQL query statement below
SELECT
    name,
    population,
    area 
FROM
    World 
WHERE 
    (
        area > 3000000
        OR population > 25000000
    )

Problem709

概要:英語の大文字を小文字に変換して返す、英語以外はそのままにする.

Python

str.lower(), str.upper() の小文字・大文字変換が用意されているので、一行で終わる.

class Solution:
    def toLowerCase(self, str: str) -> str:
        return str.lower()
  • ord: 文字からアスキーコードを取得して
  • chr: アスキーコードから文字へ戻す

アスキーコード上で32こ足した箇所に小文字が存在するので、大文字のアスキーコード(65:A 〜 90:Z)の範囲の文字がきたら +32して小文字にする. 上記と速度もメモリも変わらず.

class Solution:
    def toLowerCase(self, str: str) -> str:
        res = ""
        for c in str:
            oc = ord(c)
            if 64<oc<91:
                res += chr(oc+32)
            else:
                res += c
                
        return res

Problem771

概要:文字列の中に指定した文字が何回出現するかをカウントする。

python3

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        res = 0
        for s in S:
            if s in J:
                res += 1
        
        return res

submission detail

C++

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int res = 0;
        set<char> cJ(J.begin(), J.end());
        for (char s : S) {
            if (cJ.count(s)) res++;
        }
        return res; 
    }
};

Problem804

概要:コードをモールス信号に変換した時、何個ユニークな信号が出てくるか.

Python3

愚直に全て一度モールス信号に書き換えて、ユニークな数 (setで作成した集合の大きさ)を返す.

問題文に

words[i] will only consist of lowercase letters.

とあるので、入力は必ず小文字の英語だと信じて od-97で英語のアスキーコードord(a)=97を元にインデックスを指定した. Python3

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        mmap = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
        res = []
        oda, odz = ord("a"), ord("z")

        for word in words:
            mc_word = ""
            for c in word:
                od = ord(c)
                mc_word += mmap[od-97]
            res.append(mc_word)

        return len(set(res))

C++

class Solution {
public:
    
    int uniqueMorseRepresentations(vector<string>& words) {
        // ユニーク数だけ知りたいので集合に追加していく
        set<string> res;
        string mc[] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        
        // wordsに含まれる単語それぞれをモールス信号に変換
        for (const auto& word : words) {
            string mc_word = "";
            for(int j = 0; j<word.length(); j++) mc_word += mc[word[j] - 'a'];
            res.insert(mc_word);
        }
        return res.size();
    }
};

Problem832

概要:intリストのリストが渡されるので、それぞれを逆順にして、0/1を反転させる。

Python3

class Solution:
    def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
        res = []
        for r in A:
            r.reverse()
            res.append([1-ri for ri in r])
        return res

javascript

map()を使って一列ごとに反転+ビットの反転を行う.

Array.prototype.map() - JavaScript | MDN

mapでリストをそれぞれ反転し、さらにmapでリストの要素それぞれのビットを反転(evrow.map(x=>1-x))させる.

/**
 * @param {number[][]} A
 * @return {number[][]}
 */
var flipAndInvertImage = function(A) {
    var res = A.map(function(row) {
        var revrow = row.reverse();
        return revrow.map(x=>1-x);
    });
    return res;
};

Problem938

概要:二分木の探索を行い、指定された範囲内の数値の和を結果とする. 範囲内(L<=val<=R)の数値を見つけた場合、self.resに足していく.

Python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rangeSumBST(self, root, L, R):
        self.res = 0

        def search(node):
            if node is not None:
                nv = node.val
                if L <= nv <= R:self.res += node.val
                if L < nv:search(node.left)
                if nv < R:search(node.right)

        search(root)
        return self.res

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        search(root, L, R);
        return res;
    }
    
    int res = 0;
    
    void search(TreeNode* root, int L, int R){
        if (root==nullptr){
            return;
        } else {
            if (L<=root->val && root->val<=R){
                res += root->val;
            }
            if (L<root->val) search(root->left, L, R);
            if (root->val<R) search(root->right, L, R);
        }
    }
};

Problem1021

問題文

概要:入力は必ず()で構成された文字列、()の一番外側だけを取り除いた文字列を返したい.

cnt()を見るたびに増減するスタックとして使う、一番外側の場合(cntが1の場合)以外は結果として返すresに繋げる.

Python3

class Solution(object):
    def removeOuterParentheses(self, S):
        """
        :type S: str
        :rtype: str
        """
        res = ""
        cnt = 0

        for s in S:
            if s=="(":
                cnt+=1
                if cnt>1:res+=s
            else:
                if cnt>1:res+=s
                cnt-=1
        return res

Problem1108

概要:IPv4のアドレスのドットを置き換えるのみ. vscodeの環境を整えながら、色々な言語で試す.

python3

class Solution(object):
    def defangIPaddr(self, address):
        """
        :type address: str
        :rtype: str
        """
        return address.replace(".", "[.]")

Rust

impl Solution {
    pub fn defang_i_paddr(address: String) -> String {
        return address.replace(".", "[.]")
    }
}

C++

class Solution {
public:
    string defangIPaddr(string address) {
    string res;
    for (const char c : address) {
      if (c == '.') res += "[.]";
      else res += c;
    }
    return res;
    }
};

C#

public class Solution {
    public string DefangIPaddr(string address) {
        return address.Replace(".", "[.]");
    }
}

Go

stringsの操作を見ながら確認. strings - The Go Programming Language

func defangIPaddr(address string) string {
    return strings.Replace(address, ".", "[.]", -1)
}

submission Detail