テストコード-ワード変換の準備

8357 ワード
Java DFS coding test programmers テキストリンク
符号化テストを行う場合、実際の作業でよく使われるハッシュや文字列に関する問題は比較的解決しやすいが、実際の作業でよく使われないプローブやグラフの問題に遭遇すると、いつも苦戦する.
だから私の弱いタイプを中心に、問題を解くことでまとめたいと思います.
今日整理するコードテスト問題はプログラマーの「単語変換」問題で、dfsで解く3級問題を利用できます.
個人的には再帰関数を有効に使えば、これは難しくない問題だと思います.

質問する



プールコード

class Solution {
    static boolean[] check;
    static int answer = 0; 
    public int solution(String begin, String target, String[] words) {
        check = new boolean[words.length];
        dfs(begin, target, words, 0);
        return answer;
    }
    public void dfs(String begin, String target, String[] words, int count){
        if(begin.equals(target)){
            answer=count;
            return;
        }
        for(int i=0; i<words.length; i++){
            if(check[i] == true){
                continue;
            }
            int same = 0;
            for(int j=0; j<begin.length(); j++){
                if(begin.charAt(j) == words[i].charAt(j)){
                    same++;
                }
            }
            if(same == begin.length()-1){
                check[i] = true;
                dfs(words[i], target, words, count+1);
                check[i]  = false;
            }
        }
    }
}

問題を解く


void関数dfsを生成し、int countを受信してbegin、target、words、および現在どの単語変換が行われているかを確認します.再帰関数として
  • が用いられるため、脱出条件としてbeginをtargetと同じ値で逃がし、response値を変数を受け入れるcount値に設定する.このため、クラスで答えを静的値として指定できます.
  • クラスでは、ブール配列checkを静的値として指定し、ソリューションメソッドで単語の長さを指定します.
  • dfsメソッドでは、インデックスのcheck値がtrueの場合、アクセス済みであることを示します.そうでない場合は、charatを使用してbeginとword[i]値の文字数がどれだけ一致するかを検証します.
  • が一致する文字数が問題で要求される「1つを除くすべての一致」である場合、checkはその配列のインデックス値をtrueに設定します.
  • 単語[i]の値をbegin値に設定し、countが1増加した値を再帰的に呼び出す.
    • すべての場合の合計数を表示するには、check[i]値をfalseに設定します.

    に感銘を与える


    最後の7回の値を設定するのを忘れ、なぜ正常な値がないのか悩んだ.
    これまで、dfs問題は文字列タイプの問題のように頭の中で自由に描かれていなかったが、このタイプの問題を持続的に解決し、自然にしなければならない.
    DOM
    [JS] 6. データ型