LeetCodeをやってみたのでまずはThe LeetCode Beginner's Guideから取り組んでみる
はじめに
他職種かた未経験でエンジニアに転職して 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...
}
}
- 学び
- prefix sum は累積和のこと、running sum は累計のこと。
- 累積和の計算式：
runningSum[i]=nums[0]+nums[1]+...+nums[i]
- 累積和の計算式：
- 与えられた配列 nums の配列サイズと等しいサイズの空配列を作成する方法
int[] resultList = new int[nums.length] - 与えられた配列が空の場合の条件も含める
- 与えられた配列が空の時の値を結果配列に入れる（
resultList[0] = nums[0]）と、for ループで初期値を 1 にして、ループの中の式を 1 行にできる。
- prefix sum は累積和のこと、running sum は累計のこと。
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;
}
}
- 考え方
- 行が顧客、列が各銀行でのアカウントを意味するため、各顧客の合計資産額を計算するためには、各行で全アカウントの資産額を足し上げれば良い。各行で繰り返し計算して、合計値の算出をして、現在の行の合計値と以前の最大値レコードよりも大きい時に最大値を更新する。
- アプローチ
- 最大資産額を格納するための変数 ans を最小値 0 で初期化する
- 各顧客（二次元配列の各行）において、その行の累積和を格納する変数 sum を最小値 0 で初期化する
- 各行で各銀行口座残高に対して繰り返し処理を行い、合計残高を累計する
- それぞれの顧客に対して合計資産を計算し、それまでに最大値として格納されていた値と比較をして大きければ asn を更新する
- 全行が計算されたら、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>();
- 要素数(n)を指定する場合
- 整数型を文字列型に変換する方法 ①：
Java Integer.toString(i)
https://codegym.cc/ja/groups/posts/ja.149.javadeintwostringni-bian-huansuru-fang-fa - 整数型を文字列型に変換する方法 ②：
Java String.valueOf(i) - 三項演算子を使って条件式を書き並べていく方法もある（別解）
- 配列型 List<String>の変数 output は以下で初期化できる
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;
}
}
- ビット演算についての解説
- 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 が偶数であることを示しています。
- 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 演算の結果は偶数の次の数（奇数）になります。
- シフト演算 (>>)
- 定義: シフト演算は、ビット列を右または左にシフトさせる操作です。右シフト（>>）の場合、ビットを右に移動させ、その結果として数値を半分にします（整数の除算に相当）。
- 使用条件:
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 となる。
- シフト演算（>>）
- シフト演算は、ビット列を右または左にシフトさせる操作。右シフト（>>）の場合、ビットを右に移動させ、その結果として数値を半分にする（整数の除算に相当）。
- AND 演算（&）：&演算子は 2 つのビットが両方とも 1 である場合にのみ 1 を返し、それ以外の場合（0 AND 0, 0 AND 1, 1 AND 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 と等しい文字の数がカウントされる。
- 学び
- Java で HashMap を定義する方法
https://qiita.com/t_t238/items/4cf5b8257f3f9bf66ac5 - Map のメソッド
- getOrDefault(c, 0)
https://qiita.com/pinebookplus/items/8bbd63f89e4c014caefb - containsKey(c)
- getOrDefault(c, 0)
- for-in 文
- toCharArry()メソッドを使い、文字列を文字配列に変換する。
- Java で HashMap を定義する方法
次のステップ
The LeetCode Beginner's Guide を一通り解いたが、もう一度時直して全問正解できないような気がするので、時間をおいて再度復習したい。
また、次に何に取り組むかを検討中。
候補としては、以下を考えている。Easy レベルの問題から慣れたいが 1 番目は 700 問ほどあるので 2 番目から取り組もうか考え中。
- Random Easy Problems
https://leetcode.com/problemset/algorithms/?difficulty=EASY - コーディング面接のために解きたい 60 問
https://1kohei1.com/leetcode/
https://leetcode.com/problem-list/xo2bgr0r/ - 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/ - Sean Prashad さんの LeetCode Patterns
https://seanprashad.com/leetcode-patterns/