Zenn
🤖

LeetCodeをやってみたのでまずはThe LeetCode Beginner's Guideから取り組んでみる

2024/12/29に公開
データ構造
駆け出しエンジニア
LeetCode
アルゴリズムとデータ構造
アリゴリズム
tech

はじめに

他職種かた未経験でエンジニアに転職して1年半が経過したが、普段のプロジェクトでWebアプリ開発する中で様々なことを学んできたが、アルゴリズムに関しては全く学習を進めてきていなかった。
パズル感覚で日々やれたらいいなと思い軽い気持ちでLeetCodeを始めた。
はじめての人はまず着手した方が良さげな初心者ガイドのようなページがあったので、まずはそこから取り組んでみる。

Solving Your First Problem

Additional Tools and Resources

2236. Root Equals Sum of Children

https://leetcode.com/problems/root-equals-sum-of-children/description/

  • 問題文
    root、左子ノード、右子ノードの３つのノードから成るバイナリツリーが与えられている。
    2つの子ノードの和がrootノードの値と等しい場合はtrueを返し、そうではない時にfalseを返すようなコードを記述せよ。

  • 自分の解答

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean checkTree(TreeNode root) {
        int sum = root.left.val + root.right.val;
        if ( root.val != sum ) {
            return false;
        }
        return true;
    }
}
  • 別解
    ==で比較することで、正の場合はtrueを返し、負の場合はfalseを返す。
class Solution {
    public boolean checkTree(TreeNode root) {
       return root.val == root.right.val + root.left.val; 
    }
}

Challenge Problems

Begginer Challenge Problems

1480. Running Sum of 1D Array（一次元配列の累積和）

https://leetcode.com/problems/running-sum-of-1d-array/description/

  • 学習内容
    How to build a prefix sum array.

  • 問題文
    nums配列が与えられている時、runningSum[i] = sum(nums[0]...nums[i])として配列の累計を定義する。numsの累計を計算してください。

  • 自分の解答

class Solution {
    public int[] runningSum(int[] nums) {
        int l = nums.length;
        int sum = 0;
        int[] resultList = new int[l];
        for( int i=0; i<l; i++ ){
            sum += nums[i];
            resultList[i] = sum;
        }
        return resultList;
    }
}
  • 別解
// Runtime: 0 ms, faster than 100.00% of Java online submissions for Running Sum of 1d Array.
// Time Complexity : O(n)
// Space Complexity : O(n)
class Solution {
    public int[] runningSum(int[] nums) {
        // Create an output array of size equal to given nums size...
        int[] output = new int[nums.length];
        // Base case: if the array is empty...
        if(nums.length == 0)
            return output;
        // Set output[0] = nums[0]...
        output[0] = nums[0];
        // Traverse all elements through the for loop...
        for(int idx = 1; idx < nums.length; idx++) {
            // Storing the running sum...
            output[idx] = output[idx-1]+ nums[idx];
        }
        return output;      // Return the running sum of nums...
    }
}
  • 学び
    1. prefix sumは累積和のこと、running sumは累計のこと。
      • 累積和の計算式：runningSum[i]=nums[0]+nums[1]+...+nums[i]
    2. 与えられた配列numsの配列サイズと等しいサイズの空配列を作成する方法
      int[] resultList = new int[nums.length]
    3. 与えられた配列が空の場合の条件も含める
    4. 与えられた配列が空の時の値を結果配列に入れる（resultList[0] = nums[0]）と、forループで初期値を1にして、ループの中の式を1行にできる。

1672. Richest Customer Wealth（最も裕福な顧客の資産）

https://leetcode.com/problems/richest-customer-wealth/description/

  • 学習内容
    二次元配列による繰り返し計算。

  • 問題文
    m行n列の整数による二次元配列accountsが与えられている。accounts[i][j]はi番目の顧客がj番目の銀行に顧客アカウントを所有していることを意味する。
    全ての顧客の中で最も資産を有する顧客の資産額を計算せよ。
    ここで、顧客の資産とは、ある顧客が全銀行において保有する資産の合計金額を意味する。

  • 自分の解答

class Solution {
    public int maximumWealth(int[][] accounts) {
        int richestAmount = 0;
        for(int i=0; i<accounts.length; i++){
            int sum = 0;
            for(int j=0; j<accounts[i].length; j++){
                sum += accounts[i][j];
            }
            if(sum > richestAmount){
                richestAmount = sum;
            }
        }
        return richestAmount;
    }
}
  • 別解
class Solution {
    public int maximumWealth(int[][] accounts) {
        int res = 0;
        for(int i =0;i<accounts.length;i++){
            int temp = 0;
            for(int j = 0;j<accounts[i].length;j++){
                temp+=accounts[i][j];
            }
            res = Math.max(res,temp);
        }
        return res;
    }
}
  • 考え方
    • 行が顧客、列が各銀行でのアカウントを意味するため、各顧客の合計資産額を計算するためには、各行で全アカウントの資産額を足し上げれば良い。各行で繰り返し計算して、合計値の算出をして、現在の行の合計値と以前の最大値レコードよりも大きい時に最大値を更新する。
    • アプローチ
      1. 最大資産額を格納するための変数 ans を最小値0で初期化する
      2. 各顧客（二次元配列の各行）において、その行の累積和を格納する変数 sum を最小値0で初期化する
      3. 各行で各銀行口座残高に対して繰り返し処理を行い、合計残高を累計する
      4. それぞれの顧客に対して合計資産を計算し、それまでに最大値として格納されていた値と比較をして大きければ asnを更新する
      5. 全行が計算されたら、ansは最大資産額を保持している。
    • 複雑度
      • Time: O(m×n)
      • Space: O(1)
  • 学び
    • 計算結果を格納する変数は計算を行うスコープの前に初期化する
    • 二次元配列(accounts[m][n])の各次元の配列の長さの出し方
      • m == accounts.length
      • n == accounts[i].length
    • Math.max(A, B)を使うことでAとBを比較して大きい方の値を返す

412. Fizz Buzz

https://leetcode.com/problems/fizz-buzz/description/

  • 学習内容
    繰り返しにおけるモジュロ（剰余演算）や文字列連結について。

  • 問題文
    整数nが与えられている時、以下の条件を満たす文字列配列answer(1次元配列)を返しなさい。
    i番目のiが3と5で割り切れる時は、answer[i] == "FizzBuzz"を返す。
    i番目のiが3で割り切れる時は、answer[i] == "Fizz"を返す。
    i番目のiが5で割り切れる時は、answer[i] == "Buzz"を返す。
    上記以外の時は、answer[i] == iを返す。

  • 自分の解答

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> output = new ArrayList<String>(n);
        for(int i = 1; i < n+1; i++){
            if(i % 3 == 0 && i % 5 == 0) {
                output.add("FizzBuzz");
            } else if (i % 3 == 0) {
                output.add("Fizz");
            } else if (i % 5 == 0) {
                output.add("Buzz");
            } else {
                output.add(Integer.toString(i));
            }
        }
        return output;
    }
}
  • 別解
class Solution {
    public List fizzBuzz(int n) {
        List ans = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            ans.add(
                i % 15 == 0 ? "FizzBuzz" :
                i % 5 == 0  ? "Buzz" :
                i % 3 == 0  ? "Fizz" :
                String.valueOf(i)
            );
        }

        return ans;
    }
}
  • 考え方
    • 条件が厳しいものから緩い条件への順番に条件式を並べる
  • 学び
    • 配列型List<String>の変数outputは以下で初期化できる
      • 要素数(n)を指定する場合
        JavaList<String> output = new ArrayList<String>(n);
        https://www.sejuku.net/blog/15073
      • 要素数を指定しない場合
        JavaList<String> output = new ArrayList<String>();
    • 整数型を文字列型に変換する方法①：Java Integer.toString(i)
      https://codegym.cc/ja/groups/posts/ja.149.javadeintwostringni-bian-huansuru-fang-fa
    • 整数型を文字列型に変換する方法②：Java String.valueOf(i)
    • 三項演算子を使って条件式を書き並べていく方法もある（別解）

1342. Number of Steps to Reduce a Number to Zero

ここにLeetCodeの問題URL貼り付け

  • 学習内容
    ある値が偶数か奇数かを特定する方法。
    ビット演算の方法（別解）。

  • 問題文
    整数型numが与えられている時、それをゼロまで減らすステップ数を返しなさい。
    一つのステップにおいて、現在の値が偶数なら2で割り、奇数なら1を引く処理を行う。

  • 自分の解答（Iterative）

class Solution {
    public int numberOfSteps(int num) {
        int step = 0;
        while(num>0) {
            if (num % 2 == 0){
                num = num / 2;
            } else {
                num = num - 1;
            }
            step += 1;
        }
        return step;
    }
}
  • 別解1（Bit Manipulation）
class Solution {

    // Notes:
    // & is AND Operation (1 AND 1 is 1, 1 AND 0 is 0, 0 AND 0 is 0)
    // num & 1 == 1 meaning odd, == 0 meaning even.
    // Example:
    // n = 15 or 1111. n & 0001 = 0001
    // n = 8 or 1000. n & 0001 = 0000.
    //
    // ^ is XOR Operation (1 OR 1 is 0, 1 OR 0 is 1, 0 OR 0 is 0)
    // num ^ 1 is num - 1 if num is odd, or num + 1 if num is even.
    // We only use num ^ 1 when num is odd.
    // Example:
    // n = 15 or 1111. n ^ 0001 = 1110 (14)
    // n = 8 or 1000. n ^ 0001 = 1001 (9)
    //
    // >> is SHIFT RIGHT Operation, the number is the number of bits moved (moving the whole binary one bit right).
    // num >> 1 is num / 2 if num is even. If num is odd, then is (num - 1) / 2.
    // Example:
    // n = 15 or 1111. n >> 1 = 0111 (7)
    // n = 8 or 1000. n >> 1 = 0100 (4)

    public int numberOfSteps(int num) {
        int count = 0;

        while (num > 0) {
            num = (num & 1) == 1 ? num ^ 1 : num >> 1;
            count++;
        }
        return count;
    }
}
  • ビット演算についての解説
    1. AND 演算 (&)
    • 定義: AND 演算は、2つのビットが両方とも1である場合にのみ1を返します。それ以外の場合（0 AND 0, 0 AND 1, 1 AND 0）は0を返します。
    • 例:
      n = 15（2進数では1111）の場合、n & 0001は、最下位ビット（右端）とAND演算を行うため、結果は0001（1）になります。この場合、nは奇数です。
      n = 8（2進数では1000）の場合、n & 0001は、最下位ビットが0なので、結果は0000（0）になります。これは、nが偶数であることを示しています。
    1. XOR 演算 (^)
    • 定義: XOR（排他的論理和）演算は、2つのビットが異なる場合に1を返し、同じ場合には0を返します。つまり、1 XOR 1は0、1 XOR 0は1、0 XOR 0は0です。
    • 使用条件: num ^ 1は、numが奇数のときに使用します。この場合、奇数から1を引いた結果が得られます。偶数の場合は（理論上は）偶数に1を足すことになりますが、実際にはこの操作は奇数に対してのみ意味があります。
    • 例:
      n = 15（1111）の場合、n ^ 0001は1110（14）になります。これは、15が奇数であるため、1を引いて14になっています。
      n = 8（1000）の場合、n ^ 0001は1001（9）になります。この場合、8は偶数ですが、XOR演算の結果は偶数の次の数（奇数）になります。
    1. シフト演算 (>>)
    • 定義: シフト演算は、ビット列を右または左にシフトさせる操作です。右シフト（>>）の場合、ビットを右に移動させ、その結果として数値を半分にします（整数の除算に相当）。
    • 使用条件:
      num >> 1は、numが偶数の場合は単純にnum / 2と同じ結果を返し、奇数の場合は(num - 1) / 2となります。
    • 例:
      n = 15（1111）の場合、n >> 1は0111（7）になります。これは、15を2で割った結果です。
      n = 8（1000）の場合、n >> 1は0100（4）になります。こちらも8を2で割った結果です。
  • 別解2（Recursive）
class Solution {
    public int numberOfSteps(int num) {
        return count(num, 0);
    }
    private int count(int num, int steps) {
        if (num == 0) {
            return steps;
        }
        if (num % 2 == 0) {
            return count(num / 2, steps + 1);
        }
        return count(num - 1, steps + 1);
    }
}
  • 学び
    • while文の条件式でnum>0とし、0の場合を含まない。（0になるまでの計算ステップ数のため）
    • ビット演算の計算方法
      • AND演算（&）：&演算子は2つのビットが両方とも1である場合にのみ1を返し、それ以外の場合（0 AND 0, 0 AND 1, 1 AND 0）は0を返す。
        • 最下位ビットで比較を行う。奇数の場合は最下位ビットが1で、偶数の場合は最下位ビットが0。
      • XOR演算（^）
        • XOR（排他的論理和）演算は、2つのビットが異なる場合に1を返し、同じ場合には0を返す。つまり、1 XOR 1は0、1 XOR 0は1、0 XOR 0は0となる。
      • シフト演算（>>）
        • シフト演算は、ビット列を右または左にシフトさせる操作。右シフト（>>）の場合、ビットを右に移動させ、その結果として数値を半分にする（整数の除算に相当）。
    • 再帰関数を用いる解法もある

876. Middle of The Linked List（連結リストの中央要素）

https://leetcode.com/problems/middle-of-the-linked-list/description/

  • 学習内容

    • 連結リストの中央要素を求めるアルゴリズム

  • 問題文
    単一連結リストのheadが与えられた時、連結リストの中央ノードを返しなさい。
    中央ノードが2つある場合、2番目の中央ノードを返すようにしてください。

  • 自分の解答
    ListNodeがよくわからなかったので調べてみた。
    https://qiita.com/RNT8888/items/e9ef4f8eb04479a56dd3

// 例題1の渡される引数
Input: head = [1,2,3,4,5]

// 渡されるListNodeのイメージ
ListNode{
    int val = 1;
    ListNode next = ListNode{
        int val = 2;
        ListNode next = ListNode{
            int val = 3;
            ListNode next = ListNode{
                int val = 4;
                ListNode next = ListNode{
                    int val = 5;
                    ListNode next = null;
                }
            }
        }
    }
}

ListNodeの理解が少しできたところで問題を解く。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode[] linkedList = new ListNode[100];
        int i = 0;
        while(head != null){
            linkedList[i] = head;
            i += 1;
            head = head.next;
        }
        return linkedList[i / 2];
    }
}
  • 別解
class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null) {
            return head;
        }   

        ListNode fast = head;
        ListNode slow = head;

        while(fast!=null && fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

  • 考え方

    • slowが1ステップ進むのに対して、fastは2ステップ進む。ステップを進める量が1/2のため、fastが連結リストの全要素を走査した時点ではslowは半分まで進んでいる。

  • 学び

    • ListNodeは、Linked List（連結リスト）と呼ばれるもので、「コンピュータサイエンスで使用される最も一般的なデータ構造の一つ」
    • インクリメント(t++)は、tを使った処理を行った後にt=t+1をして増加する。
    • ListNodeクラスのインスタンス化をする際、1 <= Node.val <= 100の最大値から100を使って要素数が100の配列オブジェクトを生成する。
    • 計算を全て行い、連結リストの要素数も同時にカウントする。最後に連結リストの要素数を2で割って中央ノードの存在する位置の要素番号を最後に求める。
    • i/2で計算される値に小数点部分が存在する場合は、小数点部分は切り捨てられる。
    • (別解)進む量が2種類のポインタを2つ用意して、多く進む方のポインタを遅く進むポインタの2倍の進み方にして計算を進める。

383. Ransom Note

https://leetcode.com/problems/ransom-note/description/

  • 学習内容
    Hashマップ（辞書型）のデータ構造。
    ソートによるアプローチ。

  • 問題文
    2つの文字列ransomeNoteとmagazineが与えられている時、ransomeNoteがmagazineの文字を使って構成されている場合はtrueを返しなさい。それ以外はfalseを返しなさい。
    magazineの各文字はransomeNoteで一度のみ使われる。

  • 自分の解答
    HashMapのアプローチを試みたが、自力で解けなかったのでSolutionsを参考にしながら作成。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {

        HashMap<Character, Integer> map = new HashMap<>();
        
        for (char c : magazine.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        for (char d : ransomNote.toCharArray()) {
            if (!map.containsKey(d) || map.get(d)==0) {
                return false;
            }
            map.put(d, map.get(d)-1);
        }
        return true;
    }
}
  • 別解①（Arrayを活用したアプローチ）
public boolean canConstruct(String ransomNote, String magazine) {
        int a[] = new int[26]; // find occurence of each character in string magazine
        for (char i : magazine.toCharArray()) {
            a[i - 'a']++;
        }
        for (char i : ransomNote.toCharArray()) {
            if (a[i - 'a'] == 0) { // character is not found in magazine or a particular character doesn't have same or greater count than count in magazine
                return false;
            } else {
                a[i - 'a']--; // decrement if character exists
            }
        }
        return true;
    }

i - 'a'は、ASCIIコードの値を用いて引き算を行っている。
プログラムコードの序盤に要素数が26の整数型配列を作成しているが、この26という数字は英語アルファベットの数で、a=0, b=1, c=2, ..., z=25に対応している。
それ以外はHashMapでの考え方とほとんど同じで、magazine文字列での走査時にはアルファベットが存在した場合は配列の該当の要素番号に1を加算し、ransomNote文字列の走査時にはアルファベットが存在している場合は配列の該当の要素番号から1を減算する。

  • 別解②（ユニーク文字に注目したアプローチ）
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }

        Set<Character> ransomSet = new HashSet<>();
        for (char c : ransomNote.toCharArray()) {
            ransomSet.add(c);
        }

        for (char c : ransomSet) {
            if (countOccurrences(magazine, c) < countOccurrences(ransomNote, c)) {
                return false;
            }
        }
        return true;
    }

    private int countOccurrences(String str, char c) {
        return (int) str.chars().filter(ch -> ch == c).count();
    }
}

ransomNoteの文字数がmagazineの文字数よりも大きい時点で成立しないためfalse。
chars() メソッドは文字列を整数のストリームに変換する。
ch はストリーム内の各整数（文字のUnicodeコードポイント）を表し、cはchar型の変数で特定の文字を指している。
.filter(ch -> ch == c)は、ストリームに対して条件を適用し、その条件を満たす要素のみを残す。ここでは、ch が与えられた文字 c と等しい場合にその文字を残す。
count() メソッドは、ストリーム内の要素の数をカウントして、その数を返す。ここでは、filter メソッドによって残された c と等しい文字の数がカウントされる。

次のステップ

The LeetCode Beginner's Guideを一通り解いたが、もう一度時直して全問正解できないような気がするので、時間をおいて再度復習したい。
また、次に何に取り組むかを検討中。
候補としては、以下を考えている。Easyレベルの問題から慣れたいが1番目は700問ほどあるので2番目から取り組もうか考え中。

  1. Random Easy Problems
    https://leetcode.com/problemset/algorithms/?difficulty=EASY
  2. コーディング面接のために解きたい60問
    https://1kohei1.com/leetcode/
    https://leetcode.com/problem-list/xo2bgr0r/
  3. Blind75
    https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU
    https://leetcode.com/problem-list/xi4ci4ig/
  4. Sean PrashadさんのLeetCode Patterns
    https://seanprashad.com/leetcode-patterns/

Discussion