プログラミング面接で学ぶべきアルゴリズム概念トップ10のまとめ

コーディング面接でよく聞かれるアルゴリズム関連の概念トップ 10 を紹介します。簡単な例を使ってこれらの概念を説明します。これらの概念を完全に理解するにはより多くの努力が必要なので、このリストはあくまでも入門として意図されています。この記事では、Java の観点から問題を検討し、次の概念について説明します。

1. 文字列

2. リンクリスト

3. 木

4. グラフ

5. ソート

6. 再帰と反復

7. 動的プログラミング

8. ビット操作

9. 確率の問題

10. 順列と組み合わせ

1. 文字列

IDE にコード自動補完機能がない場合は、次の方法を覚えておいてください。

 toCharyArray() // 文字列に対応する文字配列を取得する 
 Arrays.sort() // 配列のソート 
 Arrays.toString( char [] a) // 配列を文字列に変換 
 charAt( int x) // 特定のインデックスの文字を取得します 
 length() // 文字列の長さ 
長さ// 配列のサイズ

2. リンクリスト

Java では、リンクリストの実装は非常に簡単です。各ノード Node には値 val と、次のノードを指すリンク next があります。

クラスノード{
整数値;
    次のノード; 
  
    ノード( int x) {
        val = x;
        次 = null ;
    }
 }

リンクリストの 2 つの有名なアプリケーションは、スタックとキューです。

スタック：

クラスStack{
    ノードトップ; 
  
パブリックノードピーク(){
 （トップ！= null ） {
先頭に戻る;
        } 
  
戻る ヌル;
    } 
  
パブリックノードポップ(){
 （トップ == null ）の場合{
戻る ヌル;
        }それ以外{
            ノード temp = new Node(top.val);
            上 = top.next;
温度を返します。
        }
    } 
  
公共  void push(ノードn){
 (n != null )の場合{
            n.next = トップ;
            上 = n;
        }
    }
 }

列：

クラスQueue{
    ノードが最初、最後。 
  
公共  void enqueue(ノードn){
 if (first == null ){
            最初 = n;
            最後 = 最初;
        }それ以外{
            最後.次 = n;
            最後 = n;
        }
    } 
  
パブリックノードデキュー(){
 if (first == null ){
戻る ヌル;
        }それ以外{
            ノード temp = new Node(first.val);
            最初 = first.next;
温度を返します。
        }
    }
 }

3. 木

ここでのツリーは通常、バイナリツリーを指し、各ノードには次のように左の子ノードと右の子ノードが含まれます。

クラスTreeNode{
 int値;
    TreeNode 左;
    TreeNode 右;
 }

木に関連するいくつかの概念を次に示します。

バランス型と非バランス型: バランス型の二分木では、各ノードの左サブツリーと右サブツリーの深さは最大 1 (1 または 0) 異なります。
完全二分木: リーフノードを除くすべてのノードには 2 つの子があります。
完全二分木: すべてのリーフノードが同じ深さまたは同じレベルにあり、各親ノードには 2 つの子ノードが存在するという特性を持つ完全な二分木。
完全な二分木: 二分木では、最後のレベルを除いて各レベルが完全に埋められ、すべてのノードは可能な限り左に配置されている必要があります。

翻訳者注: 完全二分木は、漠然と完全二分木とも呼ばれます。完全な二分木の例としては、特定の深さにある人の祖先グラフが挙げられます。これは、すべての人が 2 人の生物学的な親を持つ必要があるためです。完全な二分木は、左側にいくつかの追加の葉ノードがある完全な二分木として見ることができます。質問: 完全二分木と完全二分木の違いは何ですか? (参考: http://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html)

#p#

4. グラフ

グラフ関連の問題は、主に深さ優先探索と呼吸優先探索に焦点を当てています。

以下はグラフ上の幅優先探索の簡単な実装です。

1) GraphNodeを定義する

クラスGraphNode{
整数値;
    GraphNode 次;
    GraphNode[] の隣接ノード;
ブール値訪問済み; 
  
    グラフノード( int x) {
        val = x;
    } 
  
    グラフノード( int x, グラフノード[] n){
        val = x;
        近隣 = n;
    } 
  
パブリック文字列toString(){
戻る  "値: " + this .val;
    }
 }

2) キューを定義する

クラスQueue{
    GraphNode 最初、最後; 
  
公共  void enqueue(GraphNode n){
 if (first == null ){
            最初 = n;
            最後 = 最初;
        }それ以外{
            最後.次 = n;
            最後 = n;
        }
    } 
  
パブリックGraphNodeデキュー(){
 if (first == null ){
戻る ヌル;
        }それ以外{
            GraphNode temp = new GraphNode(first.val, first.neighbors);
            最初 = first.next;
温度を返します。
        }
    }
 }

3) キューを使用して幅優先探索を実装する

公共 クラスGraphTest { 
  
公共 静的  void main(String[] args) {
        グラフノード n1 =新しいグラフノード( 1 );
        グラフノード n2 =新しいグラフノード( 2 );
        グラフノード n3 =新しいグラフノード( 3 );
        グラフノード n4 =新しいグラフノード( 4 );
        グラフノード n5 =新しいグラフノード( 5 ); 
  
        n1.neighbors =新しいGraphNode[]{n2,n3,n5};
        n2.neighbors =新しいGraphNode[]{n1,n4};
        n3.neighbors =新しいGraphNode[]{n1,n4,n5};
        n4.neighbors =新しいGraphNode[]{n2,n3,n5};
        n5.neighbors =新しいGraphNode[]{n1,n3,n4}; 
  
        ブレスファーストサーチ(n1, 5 );
    } 
  
公共 静的  void呼吸ファーストサーチ(グラフノードルート、 int x){
 (root.val == x)の場合
            System.out.println( "ルート内で検索" ); 
  
        キュー queue = new Queue();
        ルートが訪問済み = true ;
        キューをエンキューします(ルート); 
  
 (queue.first != null ) {
            GraphNode c = (GraphNode) queue.dequeue();
 (GraphNode n: c.neighbors)の場合{ 
  
訪問した場合
                    System.out.print(n + " " );
                    n.visited = true ;
 (n.val == x)の場合
                        System.out.println( "検索 " +n);
                    キューをエンキューします。(n);
                }
            }
        }
    }
 }

出力：

値: 2値: 3値: 5値を検索: 5  
値: 4

5. ソート

以下は、さまざまなソートアルゴリズムの時間計算量です。これらのアルゴリズムの基本的な考え方については、Wiki を参照してください。

アルゴリズム	平均時間	最悪の時期	空間
バブルソート	2乗	2乗	1
選択ソート	2乗	2乗	1
カウントソート	ん+k	ん+k	ん+k
挿入ソート	2乗	2乗
クイックソート	n 対数(n)	2乗
マージソート	n 対数(n)	n 対数(n)	依存する

また、いくつかの実装/デモがあります: Counting sort、Mergesort、Quicksort、InsertionSort。

《よく使われる7つのソートアルゴリズムを視覚的に直感的に体験》
《ビデオ: 6 分で 15 種類のソートアルゴリズムを解説》

#p#

6. 再帰と反復

プログラマーにとって、再帰は組み込みの考え方であるべきであり、簡単な例で説明できます。

質問: 階段には n 段あり、一度に 1 段または 2 段しか上れません。階段を上る方法は何通りありますか?

ステップ 1: 最初の n ステップと最初の n-1 ステップの関係を見つけます。

n 段を歩くには、n-1 段目から 1 段登るか、n-2 段目から 2 段登るかの 2 つの方法しかありません。 f(n) が n 番目のステップに登る方法の数である場合、f(n) = f(n-1) + f(n-2) となります。

ステップ 2: 開始条件が正しいことを確認します。

0 = 0;

1 = 1;

公共 静的  int f( int n){
 n <= 2の場合はn を返します。
整数x = f(n- 1 ) + f(n- 2 );
 xを返します。
 }

再帰法の時間計算量は、次のように冗長な計算が多いため、n に対して指数関数的に増加します。

5 倍
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)

単純なアイデアは、再帰を反復に変換することです。

公共 静的  int f( int n) { 
  
 (n <= 2 )の場合{
 nを返します。
    } 
  
 int最初 = 1 、 2 番目 = 2 ;
整数3番目 = 0 ; 
  
 ( int i = 3 ; i <= n; i++)の場合{
        3番目 = 1番目 + 2番目;
        最初 = 2番目;
        2番目 = 3番目;
    } 
  
 3番目を返します。
 }

この例では、反復処理にかかる時間が短くなります。再帰と反復処理も確認することをお勧めします。

7. 動的プログラミング

動的プログラミングは、次のような性質の問題を解決するための手法です。

問題は、より小さなサブ問題の解決によって解決できます。

いくつかのサブ問題の解は複数回計算する必要がある場合があります (翻訳者注: これはサブ問題の重複性によるものです)。

サブ問題の解はテーブルに保存されるため、各サブ問題は 1 回だけ計算すれば済みます。

時間を節約するには余分なスペースが必要です。

階段登り問題は上記の 4 つの特性を完全に満たしているため、動的計画法で解決できます。

公共 静的  int [] A =新しい 整数[ 100 ]; 
  
公共 静的 整数f3(整数n){
 (n <= 2 )の場合
        A[n] = n; 
  
もし(A[n] > 0 )
 A[n]を返す。
それ以外 
        A[n] = f3(n- 1 ) + f3(n- 2 ); // 結果を保存して一度だけ計算します。  
 A[n]を返す。
 }

8. ビット操作

ビット演算子:

または (\|)	そして（＆）	排他的論理和 (^)	左シフト (<<)	右シフト (>>)	ない（〜）
1\|0=1	1&0=0	1^0=1	0010<<2=1000	1100>>2=0011	~1=0

指定された数値 n の i 番目の桁を取得します (i は 0 から数えられ、右から始まります)

公共 静的 ブール型getBit( int num, int i){
 int結果 = num & ( 1 << i ); 
  
結果 == 0の場合
戻る 間違い;
    }それ以外{
戻る 真実;
    }

たとえば、数字 10 の 2 番目の数字を取得するには、次のようにします。

i=1, n=10
1<<1= 10
1010&10=10
10 は 0 ではないので、true を返します。

9. 確率の問題

確率の問題を解くには、通常、問題を適切にフォーマットする必要があります。次に、そのような問題の簡単な例を示します。

部屋には 50 人がいます。そのうち少なくとも 2 人が同じ誕生日である確率はどれくらいでしょうか。（うるう年を無視すると、1年は365日です）

何かの確率を計算することは、多くの場合、まずその逆を計算することに変換できます。この例では、すべての人が異なる誕生日である確率を計算できます。これは、365/365 + 364/365 + 363/365 + 365-n/365 + 365-49/365 となり、少なくとも 2 人の誕生日が同じである確率は、1 - この値になります。

公共 静的 ダブル計算確率( int n){
ダブルx = 1 ; 
  
 ( int i = 0 ; i < n; i++) {
        x * = ( 365.0 -i) / 365.0 ;
    } 
  
ダブルプロ = Math.round(( 1 -x) * 100 );
 pro/ 100を返します。