LeetCode の人気問題 100 指針：https://leetcode.cn/studyplan/top-100-liked/
実際には二回目の挑戦ですが、練習しないと手が鈍りますね =)
ハッシュ#
配列、HashSet、HashMap。
1. 二数の和#
配列のインデックスを返すためには、数字とそのインデックスを同時に記録する必要があり、HashMap を使用します。
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return new int[0];
}
}
49. アナグラムのグループ化#
HashMap を使用し、キーは文字を順番に並べ替えた単語、値はその単語のアナグラムをすべて格納したリストです。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> map = new HashMap<>();
for(String str:strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
List<String> list = map.getOrDefault(key, new ArrayList<>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
128. 最長連続数列#
重要なのは連続した数列の起点を見つけることです。
class Solution {
public int longestConsecutive(int[] nums) {
int max = 0;
int count = 0;
HashSet<Integer> set = new HashSet<>();
for(int num : nums) {
set.add(num);
}
for(int num : set) {
if(!set.contains(num-1)) { // 開始点
count = 0;
while(set.contains(num)) {
num++;
count++;
}
max = max < count ? count : max;
}
}
return max;
}
}
二指標#
二指標には主に向かい合う指標と速い遅い指標の二種類があります。
283. ゼロを移動#
class Solution {
public void moveZeroes(int[] nums) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
for(;slow<nums.length;slow++) { // 0で埋める
nums[slow] = 0;
}
}
}
11. 最も多くの水を保持する容器#
参考：拡張と延長
向かい合う指標で、左右から中央に近づき、低い側を中央に寄せ、過程で最大値を記録します。
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int max = 0;
while (left < right) {
int v = Math.min(height[left], height[right]) * (right - left);
if (v > max) {
max = v;
}
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max;
}
}
15. 三数の和#
全探索で、最初の数字を決定すると、二数の和の問題に変わります。
配列は双方向指標を使用する必要があり、必ずソートする必要があります。
この問題の重要な点は重複を避けることです。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // まずソートする必要があり、正確な遍歴を保証する
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0)
break;
if (i >= 1 && nums[i - 1] == nums[i])
continue; // 最初の数nums[i]の重複を避ける
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
List<Integer> ans = new ArrayList<>();
ans.add(nums[i]);
ans.add(nums[left]);
ans.add(nums[right]);
result.add(ans);
while (right > left && nums[right] == nums[right - 1])
right--; // nums[right]の重複を避ける
while (right > left && nums[left] == nums[left + 1])
left++; // nums[left]の重複を避ける
left++;
right--; // すべての可能な組み合わせを求めるため、breakしない
} else if (sum > 0)
right--;
else if (sum < 0)
left++;
}
}
return result;
}
}
42. 雨水を受ける#
局所的な考え方として、ある位置がどれだけの水を保持できるかは、左側の最高の柱の高さと右側の最高の柱の高さの最小値によって決まります。暴力的なアルゴリズムは、すべての位置の左側と右側の柱を遍歴することですが、最適化ポイントは、最初に一度計算して記録することです。これにより、各位置を再計算する必要がなくなります。
class Solution {
public int trap(int[] height) {
int[] lmax = new int[height.length]; // 各位置の左側の最高柱の高さ
int[] rmax = new int[height.length]; // 各位置の右側の最高柱の高さ
lmax[0] = height[0];
rmax[height.length-1] = height[height.length-1];
for(int i=1;i<height.length;i++) {
lmax[i] = Math.max(lmax[i-1], height[i]);
}
for(int i=height.length-2;i>=0;i--) {
rmax[i] = Math.max(rmax[i+1], height[i]);
}
int result = 0;
for(int i=0;i<height.length;i++) {
result = result + Math.min(lmax[i], rmax[i]) - height[i];
}
return result;
}
}
双指標解法、メモリを節約するために、歩きながら計算します。lmaxは 0 から left までの最大の高さ、rmaxは right から最右側の最大の高さです。lmaxが小さい場合は left の位置を計算し、逆も然りです。
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int lmax = 0, rmax = 0;
int result = 0;
while (left < right) {
lmax = Math.max(height[left], lmax);
rmax = Math.max(height[right], rmax);
if(lmax < rmax) {
result = result + lmax - height[left];
left++;
} else {
result = result + rmax - height[right];
right--;
}
}
return result;
}
}
スライディングウィンドウ#
参考：私が詩を書いたので、スライディングウィンドウアルゴリズムを暗記問題に変えました
スライディングウィンドウは実質的に速い遅い指標の使用技術です。不変量に注意し、ウィンドウ区間は左閉右開を推奨します。
3. 重複しない文字の最長部分列#
参考：4. 最長重複なし部分列
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> window = new HashSet<>();
char[] chars = s.toCharArray();
int left = 0, right = 0; // 左閉右開
int max = 0;
while(right < chars.length) {
char c = chars[right];
while(window.contains(c)) { // ウィンドウを収縮
window.remove(chars[left]);
left++;
}
window.add(c); // ウィンドウを拡大
right++;
max = max >= (right - left) ? max : (right - left);
}
return max;
}
}
438. 文字列中のすべてのアナグラムを見つける#
この問題には二つの重要なポイントがあります。一つは収縮の条件、もう一つはアナグラムであるかどうかを判断する方法です。
収縮条件は、固定長のウィンドウを維持することです。つまり、長さが p の長さに等しいときに収縮し、毛虫のように這うことです。
アナグラムを判断するには、上記の固定長ウィンドウと、同じ要素の数を記録する二つの要素が必要です。要素の数が同じであれば、validが 1 増加します。ウィンドウ内のその文字の数が必要以上に増加することを心配する必要はありません。なぜなら、固定長ウィンドウが制限されているため、その文字が増えすぎると、他の文字がvalid + 1 の条件を満たさなくなり、アナグラムにはならないからです。validの減少は、ウィンドウが収縮する際に実現されます。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character, Integer> need = new HashMap<>(); // <文字, 出現回数>
HashMap<Character, Integer> window = new HashMap<>();
for (char c : p.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
List<Integer> res = new ArrayList<>();
int left = 0, right = 0; // 左閉右開の区間
int valid = 0;
char[] chars = s.toCharArray();
while (right < chars.length) {
char c = chars[right];
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
right++;
while ((right - left) >= p.length()) {
if (valid == need.size()) { // 収縮前にアナグラムであるか判断
res.add(left);
}
char d = chars[left];
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) { // 削除前に判断
valid--;
}
window.put(d, window.get(d) - 1);
}
left++;
}
}
return res;
}
}
注意：Java では、二つのIntegerオブジェクトの大きさを比較する際に、==演算子を使用すると予期しない結果を引き起こす可能性があります。なぜなら、==演算子はオブジェクトの参照を比較するからです。二つのIntegerオブジェクトの値を比較するには、.equals()メソッドを使用するか、それらを原始型intにボックス解除して比較する必要があります。
サブストリング#
560. K の合計の部分配列#
累積和のテクニック。
参考：小さくて美しいアルゴリズムテクニック：累積和配列 day4_prefixSum2
class Solution {
public int subarraySum(int[] nums, int k) {
/**
* 累積和を計算することで、問題を二つの累積和の差がkに等しい場合に変換します。
* 配列の累積和配列をprefixSumとし、prefixSum[i]は[0,i]位置の要素の合計を表します。
* したがって、任意の二つのインデックスiとj（i<j）について、prefixSum[j] - prefixSum[i] = k
* つまり、[i+1,j]位置の要素の合計がkに等しいことを意味します。
* 配列を遍歴し、各位置の累積和を計算し、ハッシュテーブルを使用して各累積和の出現回数を記録します。
* 遍歴の過程で、prefixSum[j]-kの累積和が存在するかどうかを確認します（現在のカーソルはjです）。
* 存在する場合、ある位置から現在の位置までの連続部分配列の合計がkであることを示し、対応する回数を結果に加算します。
* こうして、配列を一度遍歴することで、合計がkの連続部分配列の個数を統計でき、時間計算量はO(n)で、nは配列の長さです。
*/
int count = 0;
int sum = 0;
HashMap<Integer, Integer> map = new HashMap<>(); // <累積和, 出現回数>
map.put(0, 1); // インデックス0からインデックスiまでの合計がkに等しい場合を解決するため、便利に統一処理
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k)) {
count += map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
239. スライディングウィンドウの最大値#
単調キュー。
単調減少のキューを維持し、キューの先頭要素がウィンドウ内の最大値です。実際の実装過程では、キューの中にインデックスを格納する必要があります。ウィンドウが右に移動するときに、正しく左側の要素を削除します。
双端キューを使用して単調キューを模倣することができ、スタックに似ています。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
Deque<Integer> queue = new ArrayDeque<>(); // 双端キューで単調キューを模倣
for (int i = 0; i < k; i++) {
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.pollLast();
}
queue.offerLast(i);
}
res[0] = nums[queue.peekFirst()];
for (int i = k; i < nums.length; i++) {
if (i - k == queue.peekFirst()) {
queue.pollFirst();
}
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.pollLast();
}
queue.offerLast(i);
res[i - k + 1] = nums[queue.peekFirst()];
}
return res;
}
}
76. 最小覆う部分列#
典型的なスライディングウィンドウ問題で、解法の考え方は438. 文字列中のすべてのアナグラムを見つけると基本的に一致しています。
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>();
for(char c:t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0)+1);
}
HashMap<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int valid = 0;
int start = 0, len = s.length()+1; // 結果を切り取るため
while (right<s.length()) {
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0)+1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
while (valid >= need.size()) {
char d = s.charAt(left);
if(right-left < len) { // 一度保存
start = left;
len = right - left;
}
if(need.containsKey(d)) {
if(window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d)-1);
}
left++;
}
}
if(len == s.length()+1) {
return "";
}
return s.substring(start, start+len);
}
}
普通の配列#
53. 最大部分配列の和#
参考：4. 最大部分配列の和
貪欲法で、直接シミュレーションを行い、sum が局所的な和が 0 未満の場合は破棄し、res が最大値を記録します。
class Solution {
public int maxSubArray(int[] nums) {
int res = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
res = sum > res ? sum : res; // 区間の累積最大値を取る（最大部分配列の終端位置を決定）
if (sum < 0) { // 最大部分配列の起点位置をリセット
sum = 0;
}
}
return res;
}
}
別の貪欲な実装で、本質は同じです。
class Solution {
public int maxSubArray(int[] nums) {
int preSum = 0;
int maxSum = Integer.MIN_VALUE;
for(int i=0;i<nums.length;i++) {
if(preSum<=0) {
maxSum = Math.max(nums[i], maxSum);
preSum = nums[i];
} else {
maxSum = Math.max(nums[i] + preSum, maxSum);
preSum = nums[i]+preSum;
}
}
return maxSum;
}
}
動的計画法の実装：
class Solution {
public int maxSubArray(int[] nums) {
// dp[j] は nums[j] を末尾とする連続部分配列の最大和
// dp[i] = Math.max(dp[i], dp[i-1]+nums[i])
int[] dp = new int[nums.length];
// 初期値 dp[i] = nums[i]
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); // 続けるか、最初から計算するか
res = Math.max(res, dp[i]);
}
return res;
}
}
前缀和の考え方も非常に巧妙です：
class Solution {
public int maxSubArray(int[] nums) {
int ans = Integer.MIN_VALUE;
int minPreSum = 0;
int preSum = 0;
for (int x : nums) {
preSum += x; // 現在の前缀和
ans = Math.max(ans, preSum - minPreSum); // 前缀和の最小値を引く
minPreSum = Math.min(minPreSum, preSum); // 前缀和の最小値を維持
}
return ans;
}
}
56. 区間の結合#
参考：20. 区間の結合
区間の重複を判断し、最初にソートしてから処理します。貪欲法の一種です。
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (x, y) -> x[0] - y[0]); // 左端でソート
List<int[]> res = new ArrayList<>();
int start = intervals[0][0]; // 左端
int rightBound = intervals[0][1]; // 右端
for(int i = 1;i<intervals.length;i++) {
if(intervals[i][0]<=rightBound) { // 区間が重複
rightBound = Math.max(intervals[i][1], rightBound);
} else {
res.add(new int[]{start, rightBound}); // 区間が重複しない
start = intervals[i][0];
rightBound = intervals[i][1];
}
}
res.add(new int[]{start, rightBound});
return res.toArray(new int[res.size()][]);
}
}
189. 配列の回転#
純粋なテクニックの問題で、最も簡単なのは追加の配列を使用し、元の配列のインデックス i の要素を新しい配列のインデックス (i+k)modn の位置に置くことです。
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] newArr = new int[n];
for (int i = 0; i < n; ++i) {
newArr[(i + k) % n] = nums[i];
}
System.arraycopy(newArr, 0, nums, 0, n);
}
}
規則を見つければ、3 回の配列反転を使用して実現できます：
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start += 1;
end -= 1;
}
}
}
238. 自身以外の配列の積#
前缀積配列と後缀積配列を計算し、もう一度遍歴して結果を計算します。前缀積 x 後缀積です。
実際には、前缀と後缀の配列を計算する過程も最も簡単な動的計画法と見なすことができます。
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] answer = new int[nums.length];
int[] prefix = new int[nums.length];
int[] suffix = new int[nums.length];
prefix[0] = 1;
suffix[nums.length - 1] = 1;
for (int i = 1; i < nums.length; i++) {
prefix[i] = prefix[i - 1] * nums[i - 1];
}
for (int i = nums.length - 2; i >= 0; i--) {
suffix[i] = suffix[i + 1] * nums[i + 1];
}
for (int i = 0; i < nums.length; i++) {
answer[i] = prefix[i] * suffix[i];
}
return answer;
}
}
41. 最初の正の数の欠如#
参考：最初の正の数の欠如
まず注意すべきは、抽斗原理です。長さが N の配列において、最小の正の整数が出現しない場合は、必ず [1, N+1] の範囲内に存在します。
追加の時間空間の複雑さがない場合は、すべての数をハッシュテーブルに入れ、1 から順に正の整数を列挙し、ハッシュテーブルに存在するかどうかを確認することを考えます。時間計算量は O(N)、空間計算量は O(N) です。
空間の複雑さを減らすためには、与えられた配列を利用していくつかの状態を保存し、与えられた配列をハッシュテーブルに変換する必要があります。
配列を遍歴し、訪問した数 x が [1,N] の範囲内にある場合、配列の x−1 の位置（注意：配列のインデックスは 0 から始まる）に「マーク」を付けます。遍歴が終了した後、すべての位置にマークが付けられている場合、答えは N+1 であり、そうでない場合は、最小のマークが付けられていない位置に 1 を加えたものです。
class Solution {
public int firstMissingPositive(int[] nums) {
// まず非正整数を排除
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= 0) {
nums[i] = Integer.MAX_VALUE;
}
}
// 配列を遍歴し、[1, n]の範囲内の数xにマークを付ける
// nums[x-1]を負の数にする
for (int i = 0; i < nums.length; i++) {
int num = Math.abs(nums[i]); // 絶対値を取って、未遍歴だがマークが付けられた負の数をスキップ
if (num >= 1 && num <= nums.length) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
// 最後の遍歴でマークを確認
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) { // マークが付いていない
return i + 1;
}
}
return nums.length + 1;
}
}
マークを付ける以外にも、置換の方法を使用して、配列の第 x−1 の要素を x にし、各不一致の位置が欠落している正の数を表します。
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { // 無限ループを避ける
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
行列#
73. 行列をゼロに設定#
空間計算量 O (m+n) の実装の一つで、二つのハッシュテーブルに値が 0 の位置の行番号と列番号を保存し、最後に遍歴して 0 に設定します。
class Solution {
public void setZeroes(int[][] matrix) {
HashSet<Integer> rows = new HashSet<>();
HashSet<Integer> columns = new HashSet<>();
for(int i=0;i<matrix.length;i++) {
for(int j=0;j<matrix[0].length;j++) {
if(matrix[i][j]==0) {
rows.add(i);
columns.add(j);
}
}
}
for(int i : rows) {
for(int j=0;j<matrix[0].length;j++) {
matrix[i][j] = 0;
}
}
for(int j:columns) {
for(int i=0;i<matrix.length;i++) {
matrix[i][j] = 0;
}
}
}
}
54. 螺旋行列#
解法の核心は、右、下、左、上の順に配列を遍歴し、四つの変数を使用して未遍歴要素の境界を定義することです。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int upper_bound = 0, lower_bound = m - 1;
int left_bound = 0, right_bound = n - 1;
List<Integer> res = new ArrayList<>();
while (res.size() < m * n) { // 相等時遍歴完了
// 上部から左から右へ遍歴
if (upper_bound <= lower_bound) { // この条件を満たす場合のみこの行を遍歴する必要がある
for (int i = left_bound; i <= right_bound; i++) {
res.add(matrix[upper_bound][i]);
}
upper_bound++;
}
// 右側から上から下へ遍歴
if (left_bound <= right_bound) {
for (int i = upper_bound; i <= lower_bound; i++) {
res.add(matrix[i][right_bound]);
}
right_bound--;
}
// 下部から右から左へ遍歴
if (upper_bound <= lower_bound) {
for (int i = right_bound; i >= left_bound; i--) {
res.add(matrix[lower_bound][i]);
}
lower_bound--;
}
// 左側から下から上へ遍歴
if (left_bound <= right_bound) {
for (int i = lower_bound; i >= upper_bound; i--) {
res.add(matrix[i][left_bound]);
}
left_bound++;
}
}
return res;
}
}
48. 画像を回転#
純粋なテクニックで、反転を回転の代わりに使用し、まず対角線に沿って行列を反転し、次に各行を反転するだけです。
class Solution {
public void rotate(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < i; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length / 2; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length - j - 1];
matrix[i][matrix.length - j - 1] = tmp;
}
}
}
}
240. 二次元行列の検索 II#
例の行列を観察すると、左上から検索を開始する場合、目標値が左上の数より大きい場合、後続の検索方向は左側または下側の二つになります。右下から検索を開始する場合も同様です。しかし、他の二つの角から検索を開始すると、全く異なります。
線形検索、公式解は Z 字形検索と呼ばれます：
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int i = m - 1, j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
i--;
} else {
j++;
}
}
return false;
}
}
または各行に二分探索を使用することもできます。
リスト#
/**
* 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; }
* }
*/
160. 交差するリスト#
この問題を解決する鍵は、p1 と p2 が交差ノードに同時に到達できるようにすることです。
事前に二つのリンクリストの長さを計算することで実現できます。尾部を揃えます。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 先に二つのリストの長さを求める
int lenA = 0, lenB = 0;
ListNode node = headA;
while(node!=null) {
lenA++;
node=node.next;
}
node = headB;
while(node!=null) {
lenB++;
node = node.next;
}
// ListAを短い方のリストにする
if(lenA>lenB) {
node = headA;
headA = headB;
headB = node;
int tmp = lenA;
lenA = lenB;
lenB = tmp;
}
// 速い遅い指標を起動し、速い指標を先にいくつか進める
for(int i=0;i<lenB-lenA;i++) {
headB = headB.next;
}
while(headA!=null && headB!=null) {
if(headA==headB) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
}
より巧妙な方法は、リストを結合させ、p1 がリスト A の末尾に到達したらリスト B を遍歴し、p2 がリスト B の末尾に到達したらリスト A を遍歴します。これにより、論理的に二つのリストが繋がることになります。
(バージョン2) リストを結合して同期移動を実現
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// p1はAリストの頭、p2はBリストの頭を指す
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
// p1は一歩進む。Aリストの末尾に到達したらBリストに移動
if (p1 == null) p1 = headB;
else p1 = p1.next;
// p2は一歩進む。Bリストの末尾に到達したらAリストに移動
if (p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1;
}
}
206. リストを反転する#
双指標法：
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode tmp = null;
while (cur!=null) {
tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
頭挿入法、空間計算量が高い：
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null)
return null;
ListNode resultList = new ListNode(head.val, null);
ListNode currentNode = head;
while(currentNode.next != null) {
currentNode = currentNode.next;
ListNode toAdd = new ListNode(currentNode.val, resultList);
resultList = toAdd;
}
return resultList;
}
}
再帰法、参考：再帰の魔法：単一リンクリストを反転する
class Solution {
// 定義：単一リンクリストの頭を入力として、そのリンクリストを反転し、新しい頭を返す
public ListNode reverse(ListNode head) {
if (head == null || head.next == null) { // 再帰のベースケース
return head;
}
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
}
234. 回文リスト#
方法 1：値を配列にコピーしてから双指標法を使用します。技術的な内容はありません。
方法 2：速い遅い指標。リンクリストの後半部分を反転させ（リンクリストの構造を変更）、前半部分と後半部分を比較します。比較が完了したら、リンクリストを元に戻す必要があります。
方法 3：再帰を使用してリンクリストの後序遍歴を実現し、双指標を模倣して回文を判断します。
class Solution {
ListNode left; // 左から右に移動するポインタ
public boolean isPalindrome(ListNode head) {
left = head;
return traverse(head);
}
boolean traverse(ListNode right) {
if (right == null) {
return true;
}
if (traverse(right.next)) {
if (left.val == right.val) {
left = left.next;
return true;
}
}
return false;
}
}
141. 循環リンクリスト#
速い遅い指標のテクニック、遅いポインタは一歩進み、速いポインタは二歩進む。速い遅いポインタが出会った場合、環があることを示します。
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
実際には、二つの条件の判断があまり明確ではない。いつ(fast != null && fast.next != null)を使用し、いつ(fast.next != null && fast.next.next != null)を使用するのか、理解できていません。
142. 循環リンクリスト II#
参考：リンクリストに環があるかどうかを判断する 8. 循環リンクリスト II
同様に速い遅いポインタですが、今回は入環の位置を返す必要があります。速いポインタと遅いポインタが出会ったとき、遅いポインタを頭に戻し、遅いポインタと速いポインタを同じ速度で出発させ、再び出会った位置が環の入口位置です。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
21. 二つのソートされたリストをマージする#
この問題は非常に簡単で、反復的に尾部を挿入するだけです。仮想の頭ノードを使用することに注意し、便利に使用することが重要です。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode p = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
p.next = list1;
list1 = list1.next;
} else {
p.next = list2;
list2 = list2.next;
}
p = p.next; // pは常に前進
}
if (list1 == null) {
p.next = list2;
}
if (list2 == null) {
p.next = list1;
}
return dummy.next;
}
}
2. 二数を加算する#
この問題は二つのソートされたリストをマージするのと似た感じがします。特に注意すべきは、最後に繰り上がりがある場合、ノードを追加する必要があることです。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode p = dummy;
int carry = 0;
while (l1 != null || l2 != null) {
int val1 = l1 == null ? 0 : l1.val;
int val2 = l2 == null ? 0 : l2.val;
int sum = val1 + val2 + carry;
ListNode node = new ListNode(sum % 10);
carry = sum / 10;
p.next = node;
p = p.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry != 0) {
p.next = new ListNode(carry);
}
return dummy.next;
}
}
19. リストの最後から N 番目のノードを削除する#
一目で速い遅いポインタが思い浮かびます。交差するリストや回文リストの速い遅いポインタの解法の考え方は一致しています。
基本的なやり方は、速いポインタをいくつか進めた後、速い遅いポインタを一緒に進めることです。こうすることで、二つのポインタの間の距離が固定され、特定の位置を見つけるのが非常に便利です。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1, head);
ListNode slow = dummy, fast = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
注意、仮想の頭ノードのテクニックを使用して、空ポインタの状況を防ぐためです。
24. リスト内のノードを二つずつ交換する#
この問題の考え方はリストを反転するのと非常に似ており、双指標を使用します。また、仮想の頭ノードを使用することに慣れる必要があります。
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(-1, head);
ListNode cur = dummyHead;
// 二つのノードがあれば交換
while (cur.next != null && cur.next.next != null) {
ListNode tmp = cur.next;
cur.next = cur.next.next;
ListNode tmp1 = cur.next.next;
cur.next.next = tmp;
tmp.next = tmp1;
cur = cur.next.next;
}
return dummyHead.next;
}
}
再帰を使用して実装することもでき、非常に理解しやすいです：
class Solution {
public ListNode swapPairs(ListNode head) {
// ベースケース：ノードが不足している
if (head == null || head.next == null) {
return head;
}
ListNode next1 = head.next;
ListNode next2 = swapPairs(head.next.next); // 再帰
head.next = next2;
next1.next = head;
return next1;
}
}
25. K 個のグループでノードを反転する#
この問題は206. リストを反転すると関連しており、部分リストを反転する機能を実装し、最後にリストを結合します。再帰的な考え方で解くと、非常に優雅になります。反復的な方法は、結局は while ループで終わります（さらに仮想の頭ノードがあります）。
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null) {
return null;
}
ListNode a = head, b = head;
for (int i = 0; i < k; i++) {
if (b == null) {
return head; // ベースケース：ノードの総数<k
}
b = b.next;
}
ListNode newHead = reverse(a, b);
a.next = reverseKGroup(b, k); // aは区間[a, b)を反転した後の尾ノード
return newHead;
}
// 区間[a, b)の要素を反転する。左閉右開に注意
ListNode reverse(ListNode a, ListNode b) {
ListNode pre = null, cur = a, nxt = a;
while (cur != b) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
}
138. ランダムポインタを持つリストのコピー#
最初の解法はバックトラッキング + ハッシュテーブルで、ハッシュテーブルを使用して各ノードに対応する新しいノードの作成状況を記録します。リンクリストを遍歴する過程で、「現在のノードの後継ノード」と「現在のノードのランダムポインタが指すノード」の作成状況を確認します。これらの二つのノードのいずれかの新しいノードが作成されていない場合、すぐに再帰的に作成を行います。コピーが完了したら、現在のレイヤーに戻り、現在のノードのポインタを割り当てることができます。注意、あるノードは複数の他のノードから指される可能性があるため、同じノードを再度コピーすることを防ぐために、現在のノードがすでにコピーされているかどうかを確認する必要があります。すでにコピーされている場合は、ハッシュテーブルからコピー後のノードのポインタを取得して返すことができます。
class Solution {
HashMap<Node, Node> map = new HashMap<>();
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
if (map.containsKey(head)) {
return map.get(head);
}
Node newHead = new Node(head.val);
map.put(head, newHead);
newHead.next = copyRandomList(head.next);
newHead.random = copyRandomList(head.random);
return newHead;
}
}
実際には、上記の長い説明は複雑すぎます。最初にリンクリストを一度遍歴し、ノードと対応する新しいノードをハッシュテーブルに入れ、その後、リンクリストをもう一度遍歴して、各新しいノードの next と random をハッシュテーブルから取得して割り当てます。
class Solution {
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
Node cur = head;
HashMap<Node,Node> map = new HashMap<>();
while(cur!=null){
map.put(cur,new Node(cur.val));
cur = cur.next;
}
cur=head;
while(cur!=null){
map.get(cur).next=map.get(cur.next);
map.get(cur).random=map.get(cur.random);
cur=cur.next;
}
return map.get(head);
}
}
もう一つの解法は、反転の挿入法を使用して、私はそれを交互挿入法と呼びます。合計で三回遍歴します：最初の遍歴で新しいノードを作成し、元のノードの後に挿入します。二回目の遍歴でランダムポインタをコピーします。三回目の遍歴で新しいリンクリストを元のリンクリストから分離します。
148. リストをソートする#
挿入ソート（147. リストに挿入ソートを行う）：
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(-1, head); // 頭ノードに挿入するため便利
ListNode last = head; // ソートされた部分の最後のノードを維持
ListNode cur = head.next; // 挿入待ちの要素
while (cur != null) {
if (cur.val >= last.val) {
last = cur;
} else {
ListNode ptr = dummy;
while (ptr != last) {
if (cur.val <= ptr.next.val) {
last.next = cur.next;
cur.next = ptr.next;
ptr.next = cur;
break;
} else {
ptr = ptr.next;
}
}
}
cur = last.next;
}
return dummy.next;
}
}
トップダウンのマージソート：
最初のステップは、中点を見つけてリンクリストを分割し、速い遅いポインタのテクニックを使用します。次のステップは、二つのサブリストをそれぞれソートし、再帰的に呼び出します。最後のステップは、ソートされたリンクリストをマージすることです。これは21. 二つのソートされたリストをマージするのやり方を使用します。
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) { // ベースケース
return head;
}
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode rightHead = slow.next;
slow.next = null; // 中点を見つけて、リンクリストを分割
ListNode left = sortList(head);
ListNode right = sortList(rightHead); // 再帰的にソート
return merge(left, right);
}
ListNode merge(ListNode a, ListNode b) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (a != null && b != null) {
if (a.val <= b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
if (a == null) {
cur.next = b;
} else {
cur.next = a;
}
return dummy.next;
}
}
トップダウンのマージソートの空間計算量はO(logn) ですが、ボトムアップのマージソートを使用すると、O(1) の空間計算量を達成できます。しかし、実際にはそれほど必要ではありません。
23. K 個のソートされたリストをマージする#
21. 二つのソートされたリストをマージするに似ています。鍵は K 個のノードの中から最小のノードを迅速に見つける方法です。優先度キューを使用して最適化できます。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode head : lists) { // K個のリストの頭ノードを最小ヒープに追加
if (head != null) {
pq.add(head);
}
}
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
p.next = node;
p = node;
if (node.next != null) {
pq.add(node.next);
}
}
return dummy.next;
}
}
146. LRU キャッシュ#
参考：アルゴリズムはレゴを組み立てるようなもの：LRU アルゴリズムを手動で実装する
ハッシュテーブルマッピング + 双方向リスト = ハッシュリスト LinkedHashMap
class LRUCache {
HashMap<Integer, Node> map = new HashMap<>();
DoubleLinkedList linkedlist = new DoubleLinkedList();
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node node = map.get(key);
linkedlist.remove(node); // アクセスしたノードをリストの末尾に移動
linkedlist.addLast(node);
return node.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
linkedlist.remove(node); // 更新するノードをリストの末尾に移動
node.value = value; // 値を更新
linkedlist.addLast(node);
} else {
Node node = new Node(key, value);
map.put(key, node);
linkedlist.addLast(node);
if (linkedlist.size() > capacity) {
Node removed = linkedlist.removeFirst();
map.remove(removed.key);
}
}
}
}
class Node {
int key, value;
Node next, prev;
public Node() {}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
class DoubleLinkedList {
Node head, tail; // 仮想の頭と尾のノード
int size;
public DoubleLinkedList() {
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
this.size = 0;
}
public Node addLast(Node node) {
node.prev = tail.prev;
node.next = tail;
tail.prev.next = node;
tail.prev = node;
size++;
return node;
}
public Node removeFirst() {
if (size == 0) {
return null;
}
Node node = head.next;
remove(node);
return node;
}
public void remove(Node node) {
node.next.prev = node.prev;
node.prev.next = node.next;
size--;
}
public int size() {
return this.size;
}
}
Java の組み込み型 LinkedHashMap を使用して LRU アルゴリズムを実装することもできます。
二分探索#
参考：詩を書いたので、二分探索アルゴリズムを暗記問題に変えました
35. 挿入位置を検索#
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length; // 左閉右開
while (left < right) {
int mid = (right - left) / 2 + left;
if (nums[mid] == target) {
left = mid;
break;
} else if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
74. 二次元行列の検索#
二次元行列を平坦な有序一維配列として見なし、この仮想の配列上で二分探索を行います。行列は実際には二次元ですが、行列の要素にアクセスするために行列のインデックスを計算することができます。
m x n の行列に対して、この行列を長さ m * n の一維配列として見なし、各要素のインデックス k は以下の式で二次元行列の行と列にマッピングできます：
- 行インデックス：
row = k / n - 列インデックス：
col = k % n
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length; // 行数
int n = matrix[0].length; // 列数
int left = 0;
int right = m * n - 1; // 仮想一維配列の長さ
while (left <= right) {
int mid = left + (right - left) / 2; // 中間インデックス
int midValue = matrix[mid / n][mid % n]; // 一維インデックスを二次元インデックスに変換
if (midValue == target) {
return true; // 目標値を見つけた
} else if (midValue < target) {
left = mid + 1; // 右半分を検索
} else {
right = mid - 1; // 左半分を検索
}
}
return false; // 目標値が見つからなかった
}
}
34. ソートされた配列の中で要素の最初と最後の位置を見つける#
class Solution {
public int[] searchRange(int[] nums, int target) {
int left_bound = binarySearchLeft(nums, target);
int right_bound = binarySearchRight(nums, target);
if (left_bound >= right_bound) {
return new int[] { -1, -1 };
}
return new int[] { left_bound, right_bound - 1 };
}
// 左端を探す
int binarySearchLeft(int[] nums, int target) {
int left = 0, right = nums.length; // 左閉右開
while (left < right) {
int mid = (right - left) / 2 + left;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return right;
}
// 右端を探す
int binarySearchRight(int[] nums, int target) {
int left = 0, right = nums.length; // 左閉右開
while (left < right) {
int mid = (right - left) / 2 + left;
if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
33. 回転ソートされた配列を検索#
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length; // 左閉右開
while (left < right) {
int mid = (right - left) / 2 + left;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] >= nums[left]) {
// 左側がソートされている
if (nums[left] <= target && target < nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
} else {
// 右側がソートされている
if (nums[mid] < target && target <= nums[right - 1]) {
left = mid + 1;
} else {
right = mid;
}
}
}
return -1;
}
}
普通の二分探索との違いは、target がどの区間にあるかを判断する方法です。普通の二分探索では、単純に nums [mid] と target の大小を比較するだけで、target が mid の左側か右側かを判断しますが、この問題では、どちらの側がソートされているかを確認し、target の値がソートされている側の範囲内にあるかどうかを確認する必要があります。要約すると、左側か右側を判断する方法が異なります。
153. 回転ソートされた配列の最小値を探す#
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length; // 左閉右開
int min = nums[left];
while (left < right) {
int mid = (right - left) / 2 + left;
if (nums[mid] >= nums[left]) {
// 左側がソートされている
min = Math.min(min, nums[left]);
left = mid + 1;
} else {
// 右側がソートされている
min = Math.min(min, nums[mid]);
right = mid;
}
}
return min;
}
}
4. 二つのソートされた配列の中位数を探す#
参考：二つのソートされた配列の中位数を探す 詳細で通俗的な思考分析、多解法
配列を分割する：
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
if (m > n) {
return findMedianSortedArrays(nums2, nums1); // ensure m<=n
}
int left = 0, right = m; // 左閉右閉、二分[0, m]
while (left <= right) {
int i = (left + right) / 2;
int j = (m + n + 1) / 2 - i;
int maxLeft1 = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
int minRight1 = i == m ? Integer.MAX_VALUE : nums1[i];
int maxLeft2 = j == 0 ? Integer.MIN_VALUE :