はじめに
新井康平さん(@koheiarai94)の"コーディング面接対策のために解きたいLeetCode 60問"に触発されて、Leet Codeをはじめました。問題を解いた感想や、関連する情報について記録を残していきたいと思います。
Two sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
単純に、Brute Forceすればできる問題ですが、Time complexity（時間計算量）を下げるために、HashMapを用います。
class Solution {
public int[] twoSum(int[] nums, int target) {
// Create HashMap
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
// Check if current element's complement already exists in the table.
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
このようにすることで、HashMap探索に$O(1)$、n個の配列を一巡すれば問題が解けるため、Time complexityは$O(n)$となります。
また、空間計算量はHashMapに何個の要素が含まれるかで決まるため、$O(n)$で表すことができます。
Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
これはLinked Listの問題です。2つの数字を足し合わせた際、10以上になる場合、次のnodeに1が足されることを忘れないようにしましょう。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode ans = new ListNode(0);
// Create references
ListNode p = l1;
ListNode q = l2;
ListNode curr = ans;
int carry = 0;
// Check if l1 or l2 has a next node.
while ( p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
System.out.println(x);
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
// We don't need to advance "curr" because carry will be added to
// the next sum.
curr.next = new ListNode(carry);
}
return ans.next;
}
}
時間計算量は$O(max(m, n))$（m/nはl1/l2の長さ）で表されます。
空間計算量は新しく作成されるリンクドリストの長さに依存するので、時間計算量と同様に、$O(max(m, n))$（m/nはl1/l2の長さ）で表されます。
Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
スタートポジションをi, エンドポジションをjとし、一意かつ最長な文字列を探します。HashMapを使い、出現した文字とその文字をエンドポジションとしたときのインデックスjを格納します。もし、HashMap内に存在する文字が新たに出現した場合、スタートポジションiをその位置まで、変化させます。
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>();
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}
文字列を一巡するので、時間計算量は$O(n)$となり、空間計算量はHashMapに格納される文字の個数$O(m)$となります。
ZigZag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
文字をジグザグになるように並べ変える問題です。
StringBuilderを使うことで、文字列をappendすることができます。
あとは、一番上ないし最後の列に到達した際に、折り返すような仕組みを作れば終了です。
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) return s;
List<StringBuilder> rows = new ArrayList<>();
for (int i = 0; i < Math.min(numRows, s.length()); i++) {
rows.add(new StringBuilder());
}
int curRow = 0;
boolean goingDown = false;
for (char c: s.toCharArray()) {
rows.get(curRow).append(c);
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}
StringBuilder ret = new StringBuilder();
for (StringBuilder row : rows) ret.append(row);
return ret.toString();
}
}
時間計算量はストリングの長さに依存するので、$O(n)$になり、空間計算量も文字の長さ分のリストを作成するので、$O(n)$になります。
おわりに
Leet Codeは必要とされるData StructureやAlgorithmが明確なので、とても解きやすいと感じました。