1. 二次元配列内の要素検索
二次元配列（各一次元配列の長さが同じ）で、各行が左から右に昇順に、各列が上から下に昇順にソートされている場合、与えられた整数が配列内に存在するかを判断する関数を作成します。
public class Solution {
public boolean find(int target, int[][] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
if (target == array[i][j]) {
return true;
}
}
}
return false;
}
}
改良版コード
各行に対して二分探索を使用して効率を上げます。
public class Solution {
public boolean find(int target, int[][] array) {
for (int i = 0; i < array.length; i++) {
int low = 0;
int high = array[i].length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (target > array[i][mid]) {
low = mid + 1;
} else if (target < array[i][mid]) {
high = mid - 1;
} else {
return true;
}
}
}
return false;
}
}
さらに改良版コード
右上隅から開始し、対象の値と比較しながら移動することで効率的に検索します。
public class Solution {
public boolean find(int target, int[][] array) {
int row = 0;
int col = array[0].length - 1;
while (row < array.length && col >= 0) {
if (target > array[row][col]) {
row++;
} else if (target < array[row][col]) {
col--;
} else {
return true;
}
}
return false;
}
}
2. 空白文字の置換
文字列内の全ての空白文字を「%20」に置き換える関数を作成します。
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuffer buffer = new StringBuffer();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == ' ') {
buffer.append("%20");
} else {
buffer.append(c);
}
}
return buffer.toString();
}
}
簡易版コード
Stringクラスのreplaceメソッドを使用して簡潔に実装します。
public class Solution {
public String replaceSpace(StringBuffer str) {
return str.toString().replace(" ", "%20");
}
}
3. リストの逆順表示
リストの要素を逆順に表示する関数を作成します。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
while (listNode != null) {
list.add(0, listNode.val);
listNode = listNode.next;
}
return list;
}
}
スタックを使用したコード
スタックの特性を利用して逆順にリストを表示します。
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
Stack<ListNode> stack = new Stack<>();
while (listNode != null) {
stack.push(listNode);
listNode = listNode.next;
}
while (!stack.empty()) {
list.add(stack.pop().val);
}
return list;
}
}
4. 二分木の再構築
二分木の前序遍歴と中序遍歴の結果から、その二分木を再構築する関数を作成します。
import java.util.Arrays;
public class Solution {
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
if (pre.length == 0 || in.length == 0) {
return null;
}
TreeNode node = new TreeNode(pre[0]);
for (int i = 0; i < in.length; i++) {
if (pre[0] == in[i]) {
node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
}
}
return node;
}
}
5. スタックを用いたキューの実装
2つのスタックを使用してキューのpushとpop操作を実装します。
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
6. 回転配列内の最小値
非減少順に並んだ配列の一部を末尾に移動させた回転配列の最小値を求めます。
public class Solution {
public int minNumberInRotateArray(int[] array) {
if (array.length == 0) return 0;
for (int i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
return array[i + 1];
}
}
return array[0];
}
}
二分探索を使用したコード
二分探索を使用して効率的に最小値を求める方法です。
public class Solution {
public int minNumberInRotateArray(int[] array) {
if (array.length == 0) return 0;
int low = 0;
int high = array.length - 1;
while (low < high) {
if (array[low] < array[high]) return array[low];
int mid = (low + high) / 2;
if (array[low] < array[mid]) {
low = mid + 1;
} else if (array[mid] < array[high]) {
high = mid;
} else {
low++;
}
}
return array[low];
}
}
7. フィボナッチ数列
フィボナッチ数列の第n項を求める関数を作成します。
public class Solution {
public int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
動的計画法を使用したコード
動的計画法を用いて計算時間を短縮します。
public class Solution {
public int fibonacci(int n) {
int[] array = new int[40];
array[0] = 0;
array[1] = 1;
for (int i = 2; i < 40; i++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[n];
}
}
8. 階段の跳躍パターン
1段または2段ずつ跳ぶことができる場合、n段の階段を跳ぶ方法の総数を求める関数を作成します。
public class Solution {
public int jumpFloor(int target) {
if (target <= 0) return 0;
if (target == 1) return 1;
if (target == 2) return 2;
return jumpFloor(target - 1) + jumpFloor(target - 2);
}
}
動的計画法を使用したコード
動的計画法を用いて計算時間を短縮します。
public class Solution {
public int jumpFloor(int target) {
if (target <= 0) return 0;
int i = 1;
int j = 2;
int tmp;
while (--target > 0) {
tmp = j;
j += i;
i = tmp;
}
return i;
}
}
9. 階段の跳躍パターン2
任意の段数まで跳ぶことができる場合、n段の階段を跳ぶ方法の総数を求める関数を作成します。
public class Solution {
public int jumpFloorII(int target) {
if (target <= 0) return 0;
return (int) Math.pow(2, target - 1);
}
}