剑指offer第四天

/*
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;
        //第一步：克隆每个结点的值和next，并且将新节点放置在对应旧结点之后
        RandomListNode node = pHead;
        while(node != null){
            RandomListNode cloneNode = new RandomListNode(node.label);
            //cloneNode.label = node.label;
            cloneNode.next = node.next;
            node.next = cloneNode;
            node = cloneNode.next;
        }
        //第二步：克隆每个随机指针
        node = pHead;
        while(node != null){
            RandomListNode cloneNode = node.next;
            if(node.random != null)
                cloneNode.random = node.random.next;
            node = cloneNode.next;
        }
        //第三步：拆分拼接的链表
        node = pHead;
        RandomListNode cloneHead = pHead.next;
        while(node != null){
            RandomListNode cloneNode = node.next;
            node.next = cloneNode.next;
            node = node.next;
            if(node != null)
                cloneNode.next = node.next;
            else
                cloneNode.next = null;
        }
        return cloneHead;
    } 
}

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        if(pRootOfTree.left == null && pRootOfTree.right == null) return pRootOfTree;
        TreeNode left = Convert(pRootOfTree.left);
        TreeNode node = left;
        
        if(node == null)
            pRootOfTree.left = null;
        else{
            while(node.right != null)
                node = node.right;
            pRootOfTree.left = node;
            node.right = pRootOfTree;
        }
        TreeNode right = Convert(pRootOfTree.right);
        pRootOfTree.right = right;
        if(right != null)
            right.left = pRootOfTree;
        return left != null ? left : pRootOfTree; 
    }
}

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Collections;
public class Solution {
    ArrayList<String> result = new ArrayList<String>();
    public ArrayList<String> Permutation(String str) {
        if(str == null) return null;
        char[] charArray = str.toCharArray();
        permutation(charArray,0);
        Collections.sort(result);
        return result;
    }
    public void permutation(char[] charArray,int beginIdx){
        if(beginIdx >= charArray.length) return;
        if(beginIdx == charArray.length-1){
            result.add(String.valueOf(charArray));
        }
        HashSet<Character> charSet = new HashSet<>();
        for(int i = beginIdx;i<charArray.length;i++){
            if(i == beginIdx){
                charSet.add(charArray[i]);
                permutation(charArray,beginIdx+1);
            }else if(i != beginIdx && !charSet.contains(charArray[i])){
                char temp = charArray[beginIdx];
                charArray[beginIdx] = charArray[i];
                charArray[i] = temp;
                permutation(charArray,beginIdx+1);
                temp = charArray[beginIdx];
                charArray[beginIdx] = charArray[i];
                charArray[i] = temp;
            }
        }
    }
}