【D35】把数组排成最小的数&复杂链表的复制&二叉搜索树与双向链

剑指 Offer 45. 把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

• 利用Arrays.sort直接进行排序

class Solution {
    public String minNumber(int[] nums) {
        //将整数数组转换为字符串数组
        String[] numStr = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            numStr[i] = String.valueOf(nums[i]);
        }
        // Comparator定制排序
        Arrays.sort(numStr, new Comparator<String>(){
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });

        StringBuilder sb = new StringBuilder();
        for(String s : numStr){
            sb.append(s);
        }
        return sb.toString();
    }   
}

• 快排实现

class Solution {
    public String minNumber(int[] nums) {
        //将整数数组转换为字符串数组
        String[] numStr = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            numStr[i] = String.valueOf(nums[i]);
        }
        quickSort(numStr, 0, nums.length - 1);

        StringBuilder sb = new StringBuilder();
        for(String s : numStr){
            sb.append(s);
        }
        return sb.toString();
    }

    public void quickSort(String[] numStr, int left, int right){
        if(left >= right){
            return;
        }
        //找到基准值
        int index = partition(numStr, left, right);
        //左侧快排
        quickSort(numStr,left, index - 1);
        //右侧快排
        quickSort(numStr, index + 1, right);
    }

    public int partition(String[] numStr, int left, int right){
        String temp = numStr[left];
        while(left < right){
            //找到右侧第一个小于基准值的数
            while(left < right && (numStr[right] + temp).compareTo(temp + numStr[right]) > 0 ){
                right--;
            }
            numStr[left] = numStr[right];

            //找到左侧第一个大于基准值的数
            while(left < right &&  (numStr[left] + temp).compareTo(temp + numStr[left]) <= 0 ){
                left++;
            }
            numStr[right] = numStr[left];
        }
        numStr[left] = temp;
        return left;
    }
}

剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

• 建立原节点与新节点之间的哈希表

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        
        //key为原节点，value为新节点
        HashMap<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null){
            Node newNode = new Node(cur.val);
            map.put(cur, newNode);
            cur = cur.next;
        }

        //建立新节点之间的指针
        cur = head;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
  
    }
}

剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

• 中序遍历得到节点顺序，然后构建链表

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {

    List<Node> nodes = new LinkedList<>();

    public Node treeToDoublyList(Node root) {
        if(root == null){
            return root;
        }

        //中序遍历该树，得到中序节点队列
        inorder(root);
        int len = nodes.size();

        Node head = new Node(0);
        for(int i = 0; i < len; i++){
            Node cur = nodes.get(i);
            if(i == 0){
                //首节点
                head.right = cur;
                cur.left = nodes.get(len - 1);
                cur.right = len == 1 ? cur : nodes.get(i + 1);
            }else if( i != 0 && i == len - 1){
                //尾节点
                cur.left = nodes.get(i - 1);
                cur.right = nodes.get(0);
            }else{
                cur.left = nodes.get(i - 1);
                cur.right = nodes.get(i + 1);
            }
        }
        return head.right;  
    }

    public void inorder(Node root){
        if(root == null){
            return;
        }
        inorder(root.left);
        nodes.add(root);
        inorder(root.right);
    }
}