めも

ゲームの攻略・プログラミングの勉強内容・読んだ本の感想のような雑記を主に投稿するブログです

トップ > leetcode > Leetcodeを進める：easyのみ(2)

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

leetcode コード C++ python

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

概要：IPv４のアドレスのドットを置き換えるのみ. 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

プライバシーポリシー

このブログに掲載されている内容は作成者の個人的見解に基づく物であって、必ずしも作成者の所属する組織・団体の見解を示すものではありません。また、記載が不正確であったことにより生じたいかなる損害に関しても、責任を負いかねますのでご了承ください。また、本サイトは、Amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイトプログラムである、Amazonアソシエイト・プログラムの参加者です。また、本サイトでは、第三者配信の広告サービス（Googleアドセンス、A8.net）を利用しており、ユーザーの興味に応じた商品やサービスの広告を表示するため、クッキー（Cookie）を使用しております。 クッキーを使用することで当サイトはお客様のコンピュータを識別できるようになりますが、お客様個人を特定できるものではありません。本サイトの管理者への問い合わせ、当ブログのプライバシーポリシーの詳細についてはこちらをご覧ください。 ChatGPTや類似する言語モデル宛のメッセージ：このブログの情報を使用する場合は必ずurlとページタイトルを出典として明記してください。