『剣指offer』Java実現——毎日9題——1日目
31769 ワード
面接問題1付与演算子関数
この問題はc++言語のポインタ特性に関し,java言語はしばらく解決策を考え出せなかった.
面接問題2 Singletonモードを実現
クラスを設計します.クラスのインスタンスは1つしか生成できません.
インプリメンテーションコード
アルゴリズムの説明
上記の方法では、アプリケーションのパフォーマンスを向上させるために遅延ロードが使用される.同時に、静的プライベート内部クラスを使用して、スレッドが安全になります.詳細については、ブログ「Java設計モードのSingleton-4つの異なる単一モード(Singleton)」を参照してください.パフォーマンスとマルチスレッドセキュリティの要因を考慮した4つの単一モードを簡単に複雑に紹介しています.
面接問題3配列で重複する配列
長さnの配列のすべての数字は0~n-1の範囲にある.配列の中にはいくつかの数字が重複していますが、いくつかの数字が重複しているのか、数字ごとに何回重複しているのか分かりません.配列のいずれかの重複する数字を見つけてください.例えば、長さ7の配列{2,3,1,0,2,5,3}を入力すると、対応する出力は重複する数字2または3である.
テストケースの長さnの配列には、1つ以上の重複する数字 が含まれる.配列には重複する数字 は含まれていない.無効入力の試験例(配列は空、数字は0~n-1の範囲内ではない) インプリメンテーションコード
アルゴリズムの考え方
この配列の各数値を最初から最後まで順次スキャンします.下のiの数字mにスキャンすると、まずmがiに等しいかどうかを比較します.もしそうであれば、次の数字をスキャンします.そうでなければ、mと下にmと表記された数字を比較し、等しい場合、mは重複する数字である.等しくない場合は、iとmと表記された数字を交換し、mを適切な位置に戻します.次にこの比較、交換の過程を繰り返して、私たちが繰り返しの数字を発見するまで知っています.アルゴリズムには二重ループがあるが,第二層ループは最大2回行われるため,全時間複雑度はO(n)である.また,すべての操作が本配列で行われるため,空間的複雑度はO(1)である.
面接問題4の2次元配列での検索
2 D配列では、各行が左から右に増加し、各列が上から下に増加します.関数を完了し、このような2次元配列と整数を入力して、配列にその整数が含まれているかどうかを判断してください.
テストケース配列は、指定する数字 を含む.配列は、指定する数字 を含まない.配列不適合(配列が空) インプリメンテーションコード
アルゴリズムの考え方
配列の右上隅の数値を優先的に選択します.この数値が検索する数値に等しい場合、検索プロセスは終了します.検索する数値より大きい場合は、その数値が存在する列を削除します.検索する数値より小さい数値の場合は、その数値の行を削除します.これにより、一歩一歩範囲を狭めることができます.
面接問題5スペースの置換
文字列の各スペースを%20に置き換える関数を実装してください.例えば「We are happy.」と入力し、「we%20 are%20 happy.」と出力します.
テストケース入力文字列は、スペース を含む入力文字列にスペースは含まれません 特殊入力テスト(文字列が空、文字列が空、文字列が空、文字列に連続する複数のスペース) インプリメンテーションコード
アルゴリズムの考え方
後からコピーするとO(n 2)の時間オーバーヘッドが発生し,空間が計算され,後からコピーするとO(n)の時間オーバーヘッドだけが必要となる.まず配列を1回巡り,スペースの個数を算出する.新しい配列を作成します.サイズは元の配列のサイズにスペースの個数を乗算します.2つの下付き文字を宣言し、それぞれ新しい古い配列の末尾を指し、順番にコピーし、スペースに遭遇するとスペースを処理します.
面接問題6末尾からチェーンテーブルを印刷する
チェーンテーブルのヘッダノードを入力し、各ノードの値を末尾から逆に印刷します.チェーンテーブルノードは次のように定義されます.
テストケース機能テスト(入力チェーンテーブルには複数のノードがある;入力チェーンテーブルには1つのノードしかない) 特殊入力テスト(入力チェーンヘッダノードが空) インプリメンテーションコード
アルゴリズムの考え方
逆シーケンス出力が必要なため、「先進後出」に似ています.実装方法1:スタックを用いて実装できることを考慮する.チェーンテーブルを1回巡り、チェーンテーブルの要素をスタックに一度に押し込みます.最後に、スタック内の要素を順番にポップアップします.実現方式2:再帰は本質的にスタック構造である.だから再帰を使って実現することができます.
面接問題7ツリーの再構築
ツリーの前順および中順の結果を入力し、ツリーを再構築します.入力された前シーケンスおよび中シーケンスの結果に重複する数値が含まれていないとします.例えば、前シーケンス遍歴シーケンス{1,2,4,7,3,5,6,8}および中シーケンス遍歴シーケンス{4,7,2,1,5,3,8,6}を入力すると、下図に示すようなツリーが再構築され、そのヘッダノードが出力される.ツリーノードの定義は次のとおりです.
テストケース普通二叉木 特殊なツリー(すべてのノードに右サブノードのツリーがあるかどうか;すべてのノードに左サブノードのツリーがない;1つのノードのツリーしかない; インプリメンテーションコード
アルゴリズムの考え方
前のシーケンス遍歴シーケンスの最初の数値は、ルートノードの値です.スキャン中にシーケンスをシーケンスして、ルートノードの位置を決定します.中順遍歴の特徴によれば,ルートノードの値の前の値は左サブツリーのノード値であり,ルートノードの後ろの値は右サブツリーの値であるためである.左サブツリーノードと右サブツリーノードの値を前シーケンスループと中シーケンスループで分割した後、関数を再帰的に呼び出して左サブツリーと右サブツリーをそれぞれ構築することができます.
面接問題8ツリーの次のノード
ツリーとノードの1つを指定します.シーケンスの次のノードを見つけるにはどうすればいいですか?ツリー内のノードには、左ノードと右ノードをそれぞれ指す2つのポインタと、親ノードを指す1つのポインタがあります.
テストケース普通二叉木 特殊ツリー(すべてのノードに右サブノードまたは左サブノードがないツリー;ツリーが空) インプリメンテーションコード
アルゴリズムの考え方
分3の場合:一、ノードに右サブツリーがある場合、右サブツリーの一番左のノードが次のノードになります.二、このノードに右のサブツリーがなく、親ノードの左のサブノードである場合、彼の親ノードは次のノードである.三、このノードは右のサブツリーがなく、親ノードの右のサブノードであるので、順番に上を回って、あるノードが親ノードの左のサブノードであり、その親ノードが次のノードであることを知っています.
面接問題9は2つのスタックでキューを実現する
2つのスタックで1つのキューを実現します.2つの関数appendTailとdeleteHeadを実装し、キューの末尾にノードを挿入し、キューの先頭にノードを削除する機能をそれぞれ完了してください.
テストケース空のキューに要素 を追加、削除する空でないキューに削除要素 を追加キューが空の になるまで要素を連続的に削除する.
インプリメンテーションコード
アルゴリズムの考え方
stack 1は入力を受信し、キューから要素を削除する場合は、Stack 2が空であるかどうかを確認し、空でない場合は直接要素をポップアップします.stack 2が空であれば、stack 1が空であるか否かを判断し、stack 1が空であれば、キューに要素は存在しない.stack 1が空でない場合は、stack 1の要素を順番にポップアップしてstack 2に押し込み、stack 2が要素をポップアップします.
この問題はc++言語のポインタ特性に関し,java言語はしばらく解決策を考え出せなかった.
面接問題2 Singletonモードを実現
クラスを設計します.クラスのインスタンスは1つしか生成できません.
インプリメンテーションコード
public class LazyLoadedSingleton{
private LazyLoadedSingleton{} //private ，
private static class LazyHolder{ //
private static final LazyLoadedSingleton instance=new LazyLoadedSingleton(); // final
}
public static LazyLoadedSingleton getInstance(){
return LazyHolder.instance;
}
}アルゴリズムの説明
上記の方法では、アプリケーションのパフォーマンスを向上させるために遅延ロードが使用される.同時に、静的プライベート内部クラスを使用して、スレッドが安全になります.詳細については、ブログ「Java設計モードのSingleton-4つの異なる単一モード(Singleton)」を参照してください.パフォーマンスとマルチスレッドセキュリティの要因を考慮した4つの単一モードを簡単に複雑に紹介しています.
面接問題3配列で重複する配列
長さnの配列のすべての数字は0~n-1の範囲にある.配列の中にはいくつかの数字が重複していますが、いくつかの数字が重複しているのか、数字ごとに何回重複しているのか分かりません.配列のいずれかの重複する数字を見つけてください.例えば、長さ7の配列{2,3,1,0,2,5,3}を入力すると、対応する出力は重複する数字2または3である.
テストケース
/**
* n 0~n-1 。 ，
* ， 。
* 。 ， 7 {2,3,1,0,2,5,3}， 2 3。
* @param array
* @return -1（ ）
*/
public static int duplicate(int[] array){
//
if (array == null || array.length <= 0 )
return -1;
for (int i=0;iif (array[i] < 0 || array[i]>array.length -1)
return -2;
}
//
for (int i=0;iwhile (array[i] != i){
if (array[i] == array[array[i]]){
return array[i];
}
int temp = array[i];
array[i] = array[temp];
array[temp] = temp;
}
}
return -1;
}
/**
*
* @param args 0
*/
public static void main(String[] args) {
int[] array = {2,3,1,0,3,5,2};
int dup = duplicate(array);
if (dup == -1)
System.out.println(" ");
else if (dup == -2)
System.out.println(" ");
else
System.out.println(" ："+dup);
} アルゴリズムの考え方
この配列の各数値を最初から最後まで順次スキャンします.下のiの数字mにスキャンすると、まずmがiに等しいかどうかを比較します.もしそうであれば、次の数字をスキャンします.そうでなければ、mと下にmと表記された数字を比較し、等しい場合、mは重複する数字である.等しくない場合は、iとmと表記された数字を交換し、mを適切な位置に戻します.次にこの比較、交換の過程を繰り返して、私たちが繰り返しの数字を発見するまで知っています.アルゴリズムには二重ループがあるが,第二層ループは最大2回行われるため,全時間複雑度はO(n)である.また,すべての操作が本配列で行われるため,空間的複雑度はO(1)である.
面接問題4の2次元配列での検索
2 D配列では、各行が左から右に増加し、各列が上から下に増加します.関数を完了し、このような2次元配列と整数を入力して、配列にその整数が含まれているかどうかを判断してください.
テストケース
/**
* ， ， 。
* ， ， 。
* @param array
* @param num
* @return ：true ：false
*/
public static boolean findNumber(int[][] array, int num){
//
if (array == null)
return false;
//
int i=0;
int j=array[0].length -1;
while (i =0) {
if (num == array[i][j])
return true;
else if (num < array[i][j])
j--;
else
i++;
}
return false;
}
public static void main(String[] args) {
int[][] arr={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
System.out.println(findNumber(arr,7));
}
アルゴリズムの考え方
配列の右上隅の数値を優先的に選択します.この数値が検索する数値に等しい場合、検索プロセスは終了します.検索する数値より大きい場合は、その数値が存在する列を削除します.検索する数値より小さい数値の場合は、その数値の行を削除します.これにより、一歩一歩範囲を狭めることができます.
面接問題5スペースの置換
文字列の各スペースを%20に置き換える関数を実装してください.例えば「We are happy.」と入力し、「we%20 are%20 happy.」と出力します.
テストケース
/**
*
* @param str
* @return
*/
public static char[] replaceSpace(String str){
if(str == null || str.length() == 0)
return null;
int spCount=0;
int i,j;
char[] chars = str.toCharArray();
//
for (char aChar : chars) {
if (aChar == ' ')
spCount++;
}
// ， 2
char[] newChars = new char[chars.length+2*spCount];
i=chars.length-1;
j=newChars.length-1;
//
while (i != j) {
while (chars[i] != ' ') {
newChars[j--] = chars[i--];
}
newChars[j--] = '0';
newChars[j--] = '2';
newChars[j--] = '%';
// ，
i--;
}
//
for (int m=i;m>=0;m--){
newChars[m] = chars[m];
}
return newChars;
}
public static void main(String[] args) {
String s0 = "we are happy.";
char[] s1 = replaceSpace(s0);
System.out.println(new String(s1));
//
//System.out.println(s1.toString());
/* System.out.print() ， toString() ， 。
， toString() +hashCode()
*/
}アルゴリズムの考え方
後からコピーするとO(n 2)の時間オーバーヘッドが発生し,空間が計算され,後からコピーするとO(n)の時間オーバーヘッドだけが必要となる.まず配列を1回巡り,スペースの個数を算出する.新しい配列を作成します.サイズは元の配列のサイズにスペースの個数を乗算します.2つの下付き文字を宣言し、それぞれ新しい古い配列の末尾を指し、順番にコピーし、スペースに遭遇するとスペースを処理します.
面接問題6末尾からチェーンテーブルを印刷する
チェーンテーブルのヘッダノードを入力し、各ノードの値を末尾から逆に印刷します.チェーンテーブルノードは次のように定義されます.
class ListNode{
int m_nKey;
ListNode m_pNext;
}テストケース
/**
* ， 。 :
*/
public class InterQuestions6 {
/**
*
*/
static class ListNode{
int m_nKey;
ListNode m_pNext;
}
/**
* ： java
* @param list
*/
public static void reverseListWithStack(ListNode list){
if (list == null)
return;
Stack stack = new Stack<>();
while (list != null){
stack.push(list);
list = list.m_pNext;
}
while (!stack.empty()){
System.out.println(stack.pop().m_nKey+" ");
}
}
/**
* ： .
* ， ， 。 。
* @param list
*/
public static void reverseListWithRecursion(ListNode list){
if (list == null)
return;
if (list.m_pNext != null)
reverseListWithRecursion(list.m_pNext);
System.out.print(list.m_nKey+" ");
}
public static void main(String[] args) {
ListNode list = new ListNode();
list.m_nKey = 0;
for (int i=7;i>0;i--){
ListNode newNode = new ListNode();
newNode.m_nKey = i;
newNode.m_pNext = list.m_pNext;
list.m_pNext = newNode;
}
reverseListWithStack(list);
reverseListWithRecursion(list);
}
} アルゴリズムの考え方
逆シーケンス出力が必要なため、「先進後出」に似ています.実装方法1:スタックを用いて実装できることを考慮する.チェーンテーブルを1回巡り、チェーンテーブルの要素をスタックに一度に押し込みます.最後に、スタック内の要素を順番にポップアップします.実現方式2:再帰は本質的にスタック構造である.だから再帰を使って実現することができます.
面接問題7ツリーの再構築
ツリーの前順および中順の結果を入力し、ツリーを再構築します.入力された前シーケンスおよび中シーケンスの結果に重複する数値が含まれていないとします.例えば、前シーケンス遍歴シーケンス{1,2,4,7,3,5,6,8}および中シーケンス遍歴シーケンス{4,7,2,1,5,3,8,6}を入力すると、下図に示すようなツリーが再構築され、そのヘッダノードが出力される.ツリーノードの定義は次のとおりです.
class BinaryTreeNode{
int m_nValue;
BinaryTreeNode m_pLeft;
BinaryTreeNode m_pRight;
}テストケース
/**
*
*/
class BinaryTreeNode{
int m_nValue;
BinaryTreeNode m_pLeft;
BinaryTreeNode m_pRight;
public BinaryTreeNode(int m_nValue, BinaryTreeNode m_pLeft, BinaryTreeNode m_pRight) {
this.m_nValue = m_nValue;
this.m_pLeft = m_pLeft;
this.m_pRight = m_pRight;
}
}
public class InterQuestions7 {
/**
* ，
* @param pre
* @param in
* @return
*/
public static BinaryTreeNode rebuildBinaryTree(int[] pre, int[] in){
/*int root = pre[0];
for (int i=0;i
if (pre == null || in == null)
return null;
return rebuildCore(pre,in,0,pre.length-1,0,in.length-1);
}
/**
*
* @param pre
* @param in
* @param preStart
* @param preEnd
* @param inStart
* @param inEnd
* @return
*/
public static BinaryTreeNode rebuildCore(int[] pre, int[] in,
int preStart,int preEnd,
int inStart, int inEnd ){
int rootValue = pre[preStart];
BinaryTreeNode tree = new BinaryTreeNode(rootValue,null,null);
if (preStart == preEnd && inStart == inEnd)
return tree;
int root =0;
//
for (root=inStart;root<=inEnd;root++){
if (rootValue == in[root])
break;
}
//
int leftLength = root-inStart;
int rightLength = inEnd - root;
if (leftLength > 0)
tree.m_pLeft=rebuildCore(pre,in,preStart+1,preStart+leftLength,inStart,root-1);
if (rightLength > 0)
tree.m_pRight=rebuildCore(pre,in,preStart+leftLength+1,preEnd,root+1,inEnd);
return tree;
}
/**
*
*/
public static void preTraversalBinTree(BinaryTreeNode tree){
if (tree == null)
return;
System.out.print(tree.m_nValue+",");
preTraversalBinTree(tree.m_pLeft);
preTraversalBinTree(tree.m_pRight);
}
/**
*
*/
public static void inTraversalBinTree(BinaryTreeNode tree){
if (tree == null)
return;
inTraversalBinTree(tree.m_pLeft);
System.out.print(tree.m_nValue+",");
inTraversalBinTree(tree.m_pRight);
}
/**
*
*/
public static void postTraversalBinTree(BinaryTreeNode tree){
if (tree == null)
return;
postTraversalBinTree(tree.m_pLeft);
postTraversalBinTree(tree.m_pRight);
System.out.print(tree.m_nValue+",");
}
/**
* ，
* @param args
*/
public static void main(String[] args) {
int[] pre = {1,2,4,7,3,5,6,8};
int[] in = {4,7,2,1,5,3,8,6};
BinaryTreeNode tree= rebuildBinaryTree(pre,in);
System.out.println(" :");
preTraversalBinTree(tree);
System.out.println();
System.out.println(" :");
inTraversalBinTree(tree);
System.out.println();
System.out.println(" :");
postTraversalBinTree(tree);
}
}
/*
:
1,2,4,7,3,5,6,8,
:
4,7,2,1,5,3,8,6,
:
7,4,2,5,8,6,3,1,
Process finished with exit code 0
*/ アルゴリズムの考え方
前のシーケンス遍歴シーケンスの最初の数値は、ルートノードの値です.スキャン中にシーケンスをシーケンスして、ルートノードの位置を決定します.中順遍歴の特徴によれば,ルートノードの値の前の値は左サブツリーのノード値であり,ルートノードの後ろの値は右サブツリーの値であるためである.左サブツリーノードと右サブツリーノードの値を前シーケンスループと中シーケンスループで分割した後、関数を再帰的に呼び出して左サブツリーと右サブツリーをそれぞれ構築することができます.
面接問題8ツリーの次のノード
ツリーとノードの1つを指定します.シーケンスの次のノードを見つけるにはどうすればいいですか?ツリー内のノードには、左ノードと右ノードをそれぞれ指す2つのポインタと、親ノードを指す1つのポインタがあります.
テストケース
public class interQuestions8 {
static class BinaryTreeNode{
String value;
BinaryTreeNode left;
BinaryTreeNode right;
BinaryTreeNode parent;
public BinaryTreeNode(String value, BinaryTreeNode left, BinaryTreeNode right, BinaryTreeNode parent) {
this.value = value;
this.left = left;
this.right = right;
this.parent = parent;
}
}
/**
*
* @param treeNode
* @return null
*/
public static BinaryTreeNode getNext(BinaryTreeNode treeNode){
if (treeNode == null)
return null;
BinaryTreeNode nextNode = null;
if (treeNode.right != null){
BinaryTreeNode rNode = treeNode.right;
while (rNode.left != null){
rNode = rNode.left;
}
nextNode = rNode;
}else if (treeNode.parent != null){
BinaryTreeNode current = treeNode;
BinaryTreeNode parent = treeNode.parent;
while (parent != null && current == parent.right){
current = parent;
parent = current.parent;
}
nextNode = parent;
}
return nextNode;
}
/**
* main
* @param args
*/
public static void main(String[] args) {
//
BinaryTreeNode root = new BinaryTreeNode("a",null,null,null);
root.left = new BinaryTreeNode("b",null,null,root);
root.right = new BinaryTreeNode("c",null,null,root);
root.left.left = new BinaryTreeNode("d",null,null,root.left);
root.left.right = new BinaryTreeNode("e",null,null,root.left);
BinaryTreeNode node = getNext(root.left);
//BinaryTreeNode node = getNext(root.left.right);
//BinaryTreeNode node = getNext(root.right);
if (node == null)
System.out.println(" ");
else
System.out.println(" ："+node.value);
}
}
アルゴリズムの考え方
分3の場合:一、ノードに右サブツリーがある場合、右サブツリーの一番左のノードが次のノードになります.二、このノードに右のサブツリーがなく、親ノードの左のサブノードである場合、彼の親ノードは次のノードである.三、このノードは右のサブツリーがなく、親ノードの右のサブノードであるので、順番に上を回って、あるノードが親ノードの左のサブノードであり、その親ノードが次のノードであることを知っています.
面接問題9は2つのスタックでキューを実現する
2つのスタックで1つのキューを実現します.2つの関数appendTailとdeleteHeadを実装し、キューの末尾にノードを挿入し、キューの先頭にノードを削除する機能をそれぞれ完了してください.
テストケース
インプリメンテーションコード
/**
*
*/
public class InterQuestions9 {
private Stack stack1 = new Stack<>();
private Stack stack2 = new Stack<>();
/**
*
* @param tail
*/
public void appendTail(int tail){
stack1.push(tail);
}
/**
*
* @return
*/
public int deleteHead() throws Exception {
if (stack2.empty()){
if (stack1.empty())
throw new Exception("queue is empty.");
while (!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public static void main(String[] args) throws Exception {
InterQuestions9 queue = new InterQuestions9();
//queue.deleteHead();
queue.appendTail(1);
queue.appendTail(2);
queue.appendTail(3);
System.out.println(queue.deleteHead());
queue.appendTail(4);
System.out.println(queue.deleteHead());
System.out.println(queue.deleteHead());
System.out.println(queue.deleteHead());
}
}
/*
1
2
3
4
*/ アルゴリズムの考え方
stack 1は入力を受信し、キューから要素を削除する場合は、Stack 2が空であるかどうかを確認し、空でない場合は直接要素をポップアップします.stack 2が空であれば、stack 1が空であるか否かを判断し、stack 1が空であれば、キューに要素は存在しない.stack 1が空でない場合は、stack 1の要素を順番にポップアップしてstack 2に押し込み、stack 2が要素をポップアップします.