アルゴリズム復習9

複雑なチェーンテーブルのレプリケーション複雑なチェーンテーブル(各ノードにノード値と2つのポインタがあり、1つは次のノードを指し、もう1つの特殊なポインタは任意のノードを指す)を入力し、レプリケーション後の複雑なチェーンテーブルのheadを返します.(出力結果ではパラメータのノード参照を返さないでください.そうしないと、問題判定プログラムは直接空に戻ります)

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead==null)
            return null;

        //       
        RandomListNode pClonedHead=new RandomListNode(pHead.label);
        pClonedHead.next = pHead.next;
        pClonedHead.random = pHead.random;

        //      
        pClonedHead.next=Clone(pHead.next);

        return pClonedHead;
    }
}

二叉検索ツリーと双方向チェーンテーブルは、二叉検索ツリーを入力し、この二叉検索ツリーをソートされた双方向チェーンテーブルに変換します.新しいノードを作成できない必要があります.ツリー内のノードポインタの方向を調整するしかありません.

   ：    
    ：
1.             。
2.                    。
    import java.util.Stack;
    public TreeNode ConvertBSTToBiList(TreeNode root) {
        if(root==null)
            return null;
        Stack stack = new Stack();
        TreeNode p = root;
        TreeNode pre = null;//                
        boolean isFirst = true;
        while(p!=null||!stack.isEmpty()){
            while(p!=null){
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            if(isFirst){
                root = p;//                 root
                pre = root;
                isFirst = false;
            }else{
                pre.right = p;
                p.left = pre;
                pre = p;
            }      
            p = p.right;
        }
        return root;
    }
   ：   
    ：
1.          ，        。
2.               。
3.            ，   root        。
4.          ，        。
5.            ，       root    。
6.                  。
    public TreeNode Convert(TreeNode root) {
        if(root==null)
            return null;
        if(root.left==null&&root.right==null)
            return root;
        // 1.          ，        
        TreeNode left = Convert(root.left);
        TreeNode p = left;
        // 2.               
        while(p!=null&&p.right!=null){
            p = p.right;
        }
        // 3.            ，   root        
        if(left!=null){
            p.right = root;
            root.left = p;
        }
        // 4.          ，        
        TreeNode right = Convert(root.right);
        // 5.            ，       root    
        if(right!=null){
            right.left = root;
            root.right = right;
        }
        return left!=null?left:root;       
    }
   ：     
    ：
             ，   2         ，                    。
    //              ，                     
    protected TreeNode leftLast = null;
    public TreeNode Convert(TreeNode root) {
        if(root==null)
            return null;
        if(root.left==null&&root.right==null){
            leftLast = root;//                  
            return root;
        }
        // 1.          ，        
        TreeNode left = Convert(root.left);
        // 3.            ，   root        
        if(left!=null){
            leftLast.right = root;
            root.left = leftLast;
        }
        leftLast = root;//           ，            
        // 4.          ，        
        TreeNode right = Convert(root.right);
        // 5.            ，       root    
        if(right!=null){
            right.left = root;
            root.right = right;
        }
        return left!=null?left:root;       
    }

文字列の配列文字列を入力し、その文字列のすべての配列を辞書順に印刷します.例えば文字列abcを入力すると、文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.

import java.util.ArrayList;
import java.util.Stack;
import java.util.TreeSet;
public class Solution {
    public ArrayList<String> Permutation(String str) {
       TreeSet<String> tree = new TreeSet<String>();
       Stack<String[]> stack = new Stack<String[]>();
            ArrayList<String> results = new ArrayList<String>();
            stack.push(new String[]{str,""});
            do{
                String[] popStrs = stack.pop();
                String oldStr = popStrs[1];
                String statckStr = popStrs[0];
                for(int i =statckStr.length()-1;i>=0;i--){
                    String[] strs = new String[]{statckStr.substring(0,i)+statckStr.substring(i+1),oldStr+statckStr.substring(i,i+1)};
                    if(strs[0].length()==0){
                        tree.add(strs[1]);
                    }else{
                        stack.push(strs);
                    }
                }
            }while(!stack.isEmpty());
        for(String s : tree)
            results.add(s);
        return results;
    }
}

ソース:https://github.com/ahongl/algorithm.git