11ms Java beats 100% doubleLinkedListed


  • 0
    T
    class Node{
            Node prev;
            Node next;
            int val;
            public Node(int v){
                val = v;
            }
        }
        public int[] maxNumber(int[] nums1, int[] nums2, int k) {
            Node[] node1 = makeNode(nums1);
            Node head1 = node1[0], tail1 = node1[1];
            Node[] node2 = makeNode(nums2);
            Node head2 = node2[0], tail2 = node2[1];
            if(nums1.length > k) remove(head1, tail1, nums1.length - k);
            if(nums2.length > k) remove(head2, tail2, nums2.length - k);
            Stack<Node> stack = new Stack();
            int len1 = Math.min(k, nums1.length);
            int len2 = Math.min(k, nums2.length);
            remove(head1, tail1, stack, len1 + len2 - k);
            int[] ret = new int[k];
            for(int i = 0; i <= len1; i++){
                int[] cur = new int[k];
                makeArray(cur, head1, head2);
                ret = comp(ret, cur);
                remove(head2, tail2, 1);
                if(stack.isEmpty()) break;
                Node curnode = stack.pop();
                curnode.prev.next = curnode;
                curnode.next.prev = curnode;
            }
            return ret;
        }
        public Node[] makeNode(int[] nums){
            Node head = new Node(Integer.MAX_VALUE);
            Node prev = head;
            for(int i = 0; i < nums.length; i++){
                Node cur = new Node(nums[i]);
                prev.next = cur;
                cur.prev = prev;
                prev = cur;
            }
            Node tail = new Node(Integer.MIN_VALUE);
            prev.next = tail;
            tail.prev = prev;
            return new Node[]{head, tail};
        }
        public int[] comp(int[] a, int[] b){
            for(int i = 0; i < a.length; i++){
                if(a[i] < b[i]) return b;
                if(a[i] > b[i]) return a;
            }
            return a;
        }
        public boolean comp(Node head1, Node head2){
            while(head1 != null && head2 != null){
                if(head1.val < head2.val) return false;
                if(head1.val > head2.val) return true;
                head1 = head1.next;
                head2 = head2.next;
            }
            return true;
        }
        public void remove(Node head, Node tail, int n){
            Node st = head;
            while(n > 0 && head.next.next != null){
                if(head.next.val < head.next.next.val){
                    head.next = head.next.next;
                    head.next.prev = head;
                    if(head.prev != null) head = head.prev;
                    --n;
                }else{
                    head = head.next;
                }
            }
            while(n > 0 && tail.prev != st){
                tail.prev = tail.prev.prev;
                tail.prev.next = tail;
                --n;
            }
        }
        public void remove(Node head, Node tail, Stack<Node> stack, int n){
            Node st = head;
            while(n > 0 && head.next.next != null){
                if(head.next.val < head.next.next.val){
                    stack.push(head.next);
                    head.next = head.next.next;
                    head.next.prev = head;
                    if(head.prev != null) head = head.prev;
                    --n;
                }else{
                    head = head.next;
                }
            }
            while(n > 0 && tail.prev != st){
                stack.push(tail.prev);
                tail.prev = tail.prev.prev;
                tail.prev.next = tail;
                --n;
            }
        }  
        public void makeArray(int[] cur, Node head1, Node head2){
            head1 = head1.next;
            head2 = head2.next;
            for(int i = 0; i < cur.length; i++){
                if(head1.val > head2.val){
                    cur[i] = head1.val;
                    head1 = head1.next;
                }else if(head1.val < head2.val){
                    cur[i] = head2.val;
                    head2 = head2.next;
                }else{
                    if(comp(head1, head2)){
                       cur[i] = head1.val;
                        head1 = head1.next; 
                    }else{
                        cur[i] = head2.val;
                        head2 = head2.next;
                    }
                }
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.