day29

The finger of the sword Offer 06. Print linked list from end to end

Force button topic link

subject

Enter the head node of a linked list , Return the value of each node from the end to the end （ Return with array ）.

Example 1：

 Input ：head = [1,3,2]
 Output ：[2,3,1]

Limit ：

0 <=  Chain length  <= 10000

The recursive method

Ideas

• Recurrence stage ： Every time I pass in head.next , With head == null（ That is, walk through the tail node of the linked list ） Is a recursive termination condition , Go straight back to .
• Backtracking phase ： When you go back layer by layer , Add the current node value to the list , namely list.add(head.val).
• Final , Will list list Convert to array res , And return .

Code implementation

/** * https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/ * * @author xiexu * @create 2022-04-22 09:25 */
public class _ The finger of the sword Offer06_ Print linked list from end to end  {
    

    ArrayList<Integer> list = new ArrayList<>();

    public int[] reversePrint(ListNode head) {
    
        recur(head);
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
    
            res[i] = list.get(i);
        }
        return res;
    }

    void recur(ListNode head) {
    
        if (head == null) {
    
            return;
        }
        recur(head.next);
        list.add(head.val);
    }

}

no need ArrayList Methods

/** * https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/ * * @author xiexu * @create 2022-04-22 09:25 */
public class _ The finger of the sword Offer06_ Print linked list from end to end _ no need ArrayList {
    

    int[] res;
    int i = 0;
    int j = 0;

    public int[] reversePrint(ListNode head) {
    
        solve(head);
        return res;
    }

    void solve(ListNode head) {
    
        if (head == null) {
    
            res = new int[i];
            return;
        }
        i++;
        solve(head.next);
        res[j] = head.val;
        j++;
    }

}

Auxiliary stack method

Ideas

• Push ： Traversing the linked list , Set the value of each node push Push .（Java With the help of LinkedList Of addLast() Method ）.
• Out of the stack ： Set the value of each node pop Out of the stack , Store in array and return .（Java Create a new array , adopt popLast() Store the elements in the array , Realize reverse order output ）.

Code implementation

/** * https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/ * * @author xiexu * @create 2022-04-22 09:25 */
public class _ The finger of the sword Offer06_ Print linked list from end to end _ Auxiliary stack  {
    

    public int[] reversePrint(ListNode head) {
    
        LinkedList<Integer> stack = new LinkedList<>();
        while (head != null) {
    
            stack.addLast(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for (int i = 0; i < res.length; i++) {
    
            res[i] = stack.removeLast();
        }
        return res;
    }

}

The finger of the sword Offer 18. Delete the node of the linked list

Force button topic link

subject

Given the head pointer of one-way linked list and the value of a node to be deleted , Define a function to delete the node .

Return the head node of the deleted linked list .

** Be careful ：** This question is different from the original one

Example 1:

 Input : head = [4,5,1,9], val = 5
 Output : [4,1,9]
 explain :  Given that the value of your list is  5  Second node of , So after calling your function , The list should be  4 -> 1 -> 9.

Example 2:

 Input : head = [4,5,1,9], val = 1
 Output : [4,5,9]
 explain :  Given that the value of your list is  1  The third node of , So after calling your function , The list should be  4 -> 5 -> 9.

explain ：

 Ensure that the values of nodes in the list are different from each other 

Code implementation

/** * https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/ * * @author xiexu * @create 2022-04-22 10:12 */
public class _ The finger of the sword Offer18_ Delete the node of the linked list  {
    

    public ListNode deleteNode(ListNode head, int val) {
    
        if (head == null) {
    
            return null;
        }
        if (head.val == val) {
     //  The head node is the node to be deleted 
            return head.next;
        }
        ListNode cur = head;
        while (cur.next != null && cur.next.val != val) {
    
            cur = cur.next;
        }
        //  Come here  cur.next == val  了 
        if (cur.next != null) {
    
            cur.next = cur.next.next;
        }
        return head;
    }

}

The finger of the sword Offer 35. Replication of complex linked list

Force button topic link

subject

Please implement copyRandomList function , Copy a complex list . In complex linked list , Each node has one next The pointer points to the next node , One more random The pointer points to any node in the list or null.

Example 1：

 Input ：he
ad = [[7,null],[13,0],[11,4],[10,2],[1,0]]
 Output ：[[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2：

 Input ：head = [[1,1],[2,1]]
 Output ：[[1,1],[2,1]]

Example 3：

 Input ：head = [[3,null],[3,0],[3,null]]
 Output ：[[3,null],[3,0],[3,null]]

Example 4：

 Input ：head = []
 Output ：[]
 explain ： The given list is empty （ Null pointer ）, Therefore return  null.

Tips ：

-10000 <= Node.val <= 10000
Node.random  It's empty （null） Or point to a node in the list .
 The number of nodes does not exceed  1000 .

Code implementation

/** * https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/ * * @author xiexu * @create 2022-04-22 10:21 */
public class _ The finger of the sword Offer35_ Replication of complex linked list  {
    

    public Node copyRandomList(Node head) {
    
        if (head == null) {
    
            return null;
        }
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        //  Copy each node , And establish  “ Original node  ->  New node ”  Of  Map  mapping 
        while (cur != null) {
    
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        //  To build a new linked list  next  and  random  Point to 
        while (cur != null) {
    
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        //  Return the head node of the new linked list 
        return map.get(head);
    }

}

The finger of the sword Offer 53 - I. Look up numbers in the sort array I

Force button topic link

subject

Count the number of times a number appears in the sort array .

Example 1:

 Input : nums = [5,7,7,8,8,10], target = 8
 Output : 2

Example  2:

 Input : nums = [5,7,7,8,8,10], target = 6
 Output : 0

Tips ：

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums  It is a group of non decreasing numbers 
-10^9 <= target <= 10^9

Code implementation

/** * https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/ * * @author xiexu * @create 2022-04-22 11:11 */
public class _ The finger of the sword Offer53_I_ Look up numbers in the sort array _I {
    

    public int search(int[] nums, int target) {
    
        if (nums.length == 0) {
    
            return 0;
        }
        int left = 0; //  Left border index 
        int right = 0; //  Right border index 
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
    
            int mid = l + r >> 1;
            if (nums[mid] >= target) {
    
                r = mid;
            } else {
    
                l = mid + 1;
            }
        }
        if (nums[l] != target) {
    
            return 0;
        } else {
    
            left = l;
            l = 0;
            r = nums.length - 1;
            while (l < r) {
    
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= target) {
    
                    l = mid;
                } else {
    
                    r = mid - 1;
                }
            }
            right = l;
        }
        return right - left + 1;
    }

}

The finger of the sword Offer 53 - II. 0～n-1 Missing numbers in

Force button topic link

subject

A length of n-1 All numbers in the incremental sort array of are unique , And every number is in the range 0～n-1 within . In scope 0～n-1 Internal n There are and only one number is not in the array , Please find out the number .

Example 1:

 Input : [0,1,3]
 Output : 2

Example  2:

 Input : [0,1,2,3,4,5,6,7,9]
 Output : 8

Limit ：

1 <=  The length of the array  <= 10000

Ideas

Sort the search problem in the array , think first of Dichotomy solve .
According to the meaning , The array can be divided into two parts according to the following rules .
Left subarray ： nums[mid] = mid;
Right subarray ： nums[mid] ≠ mid;

Missing number equals  “ The first element of the right subarray ”  The corresponding index ; So consider using dichotomy to find “ The first element of the right subarray ” .

• initialization ： Left boundary left = 0 , Right border right = len(nums)−1 ; Represents a closed interval [left, right] .
• Cycle two ： When left ≤ right Time cycle （ When closed interval [left, j] Jump out when empty ） ;
• Calculate the midpoint mid = (left + right) >> 1
• if nums[mid] = mid , explain mid The previous elements must be complete, so you just need to continue to split the array on the right , be “ The first element of the right subarray ” It must be in the closed interval [mid+1, right] in , So execute left = mid+1;
• if nums[mid] != mid , explain mid There are fewer elements in the front, so just continue to split the array on the left , be “ The last element of the left subarray ” It must be in the closed interval [left, mid−1] in , So execute right = mid−1;
• Return value ： When jumping out , Variable i and j Point to respectively “ The first element of the right subarray ” and “ Last element of left subarray ” . Therefore return i that will do .

Code implementation

/** * https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/ * * @author xiexu * @create 2022-04-22 11:40 */
public class _ The finger of the sword Offer53_II_0 To 1 Missing numbers in  {
    

    public int missingNumber(int[] nums) {
    
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
    
            int mid = left + right >> 1;
            if (nums[mid] == mid) {
    
                left = mid + 1;
            } else {
    
                left = mid - 1;
            }
        }
        return left;
    }

}