Java基础算法每日5道详解(3)

朱雀 2023-09-23 18:34 78阅读 0赞

# 136. Single Number #

单号

Given a **non-empty** array of integers `nums`, every element appears *twice* except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.  
给定一个非空整数数组 nums，每个元素出现两次，除了一个。 找到那个单一的。

您必须实现一个具有线性运行时复杂性的解决方案，并且只使用恒定的额外空间。

**Example 1:**

Input: nums = [2,2,1]
    Output: 1

**Example 2:**

Input: nums = [4,1,2,1,2]
    Output: 4

**Example 3:**

Input: nums = [1]
    Output: 1

## leetcode代码 ##

class Solution {
        
        public int singleNumber(int[] nums) {
        
            int ans =0;
    
            int len = nums.length;
            for(int i=0;i!=len;i++)
                ans ^= nums[i];
    
            return ans;
    
        }
    }

# 141. Linked List Cycle 链表循环 #

Given `head`, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that tail’s `next` pointer is connected to. **Note that `pos` is not passed as a parameter**.

Return `true` *if there is a cycle in the linked list*. Otherwise, return `false`.

**Example 1:**

![https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png][https_assets.leetcode.com_uploads_2018_12_07_circularlinkedlist.png]

Input: head = [3,2,0,-4], pos = 1
    Output: true
    Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

**Example 2:**

![https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist\_test2.png][https_assets.leetcode.com_uploads_2018_12_07_circularlinkedlist_test2.png]

Input: head = [1,2], pos = 0
    Output: true
    Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

**Example 3:**

![https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist\_test3.png][https_assets.leetcode.com_uploads_2018_12_07_circularlinkedlist_test3.png]

Input: head = [1], pos = -1
    Output: false
    Explanation: There is no cycle in the linked list.

## leetcode代码 ##

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        
        public boolean hasCycle(ListNode head) {
        
        ListNode slow = head, fast = head;
      
        while (fast != null && fast.next != null) {
        
            slow = slow.next;
            fast = fast.next.next;
    
            if (slow == fast) 
                return true;
        }
    
        return false;
            
        }
    }

# 144. Binary Tree Preorder Traversal #

二叉树先序遍历

Given the `root` of a binary tree, return *the preorder traversal of its nodes’ values*.  
给定二叉树的根，返回其节点值的前序遍历。

**Example 1:**

![https://assets.leetcode.com/uploads/2020/09/15/inorder\_1.jpg][https_assets.leetcode.com_uploads_2020_09_15_inorder_1.jpg]

Input: root = [1,null,2,3]
    Output: [1,2,3]

**Example 2:**

Input: root = []
    Output: []

**Example 3:**

Input: root = [1]
    Output: [1]

## leetcode代码 ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
       public List<Integer> preorderTraversal(TreeNode node) {
        
            List<Integer> list = new LinkedList<Integer>();
            Stack<TreeNode> rights = new Stack<TreeNode>();
            while(node != null) {
        
                list.add(node.val);
                if (node.right != null) {
        
                    rights.push(node.right);
                }
                node = node.left;
                if (node == null && !rights.isEmpty()) {
        
                    node = rights.pop();
                }
            }
            return list;
       }
    }

# 145. Binary Tree Postorder Traversal #

二叉树邮政顺序遍历

Given the `root` of a binary tree, return *the postorder traversal of its nodes’ values*. 给定二叉树的根，返回其节点值的后序遍历。

**Example 1:**

![https://assets.leetcode.com/uploads/2020/08/28/pre1.jpg][https_assets.leetcode.com_uploads_2020_08_28_pre1.jpg]

Input: root = [1,null,2,3]
    Output: [3,2,1]

**Example 2:**

Input: root = []
    Output: []

**Example 3:**

Input: root = [1]
    Output: [1]

## leetcode代码 ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            LinkedList<Integer> ans = new LinkedList<>();
            Stack<TreeNode> stack = new Stack<>();
            if (root == null) return ans;
    
            stack.push(root);
            while (!stack.isEmpty()) {
        
                TreeNode cur = stack.pop();
                ans.addFirst(cur.val);
                if (cur.left != null) {
        
                    stack.push(cur.left);
                }
                if (cur.right != null) {
        
                    stack.push(cur.right);
                } 
            }
            return ans;
        }
    }

# 160. Intersection of Two Linked Lists #

两个链表的交集

Given the heads of two singly linked-lists `headA` and `headB`, return *the node at which the two lists intersect*. If the two linked lists have no intersection at all, return `null`.

For example, the following two linked lists begin to intersect at node `c1`:

![https://assets.leetcode.com/uploads/2021/03/05/160\_statement.png][https_assets.leetcode.com_uploads_2021_03_05_160_statement.png]

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

**Note** that the linked lists must **retain their original structure** after the function returns.

**Custom Judge:**

The inputs to the **judge** are given as follows (your program is **not** given these inputs):

*  `intersectVal` \- The value of the node where the intersection occurs. This is `0` if there is no intersected node.
 *  `listA` \- The first linked list.
 *  `listB` \- The second linked list.
 *  `skipA` \- The number of nodes to skip ahead in `listA` (starting from the head) to get to the intersected node.
 *  `skipB` \- The number of nodes to skip ahead in `listB` (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, `headA` and `headB` to your program. If you correctly return the intersected node, then your solution will be **accepted**.  
给定两个单链表 headA 和 headB 的头，返回两个列表相交的节点。如果两个链表完全没有交集，则返回 null。

例如，以下两个链表在节点 c1 处开始相交：

测试用例的生成使得整个链接结构中的任何地方都没有循环。

请注意，函数返回后，链表必须保留其原始结构。

自定义裁判：

给法官的输入如下（你的程序没有给出这些输入）：

intersectVal - 发生交点的节点的值。如果没有相交节点，则为 0。  
listA - 第一个链表。  
listB - 第二个链表。  
skipA - 在 listA 中向前跳过（从头部开始）以到达相交节点的节点数。  
skipB - 在 listB 中向前跳过（从头部开始）以到达相交节点的节点数。  
然后，法官将根据这些输入创建链接结构，并将两个头（headA 和 headB）传递给您的程序。如果您正确返回相交节点，那么您的解决方案将被接受。  
**Example 1:**

![https://assets.leetcode.com/uploads/2021/03/05/160\_example\_1\_1.png][https_assets.leetcode.com_uploads_2021_03_05_160_example_1_1.png]

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
    Output: Intersected at '8'
    Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
    From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
    - Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

**Example 2:**

![https://assets.leetcode.com/uploads/2021/03/05/160\_example\_2.png][https_assets.leetcode.com_uploads_2021_03_05_160_example_2.png]

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
    Output: Intersected at '2'
    Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
    From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

**Example 3:**

![https://assets.leetcode.com/uploads/2021/03/05/160\_example\_3.png][https_assets.leetcode.com_uploads_2021_03_05_160_example_3.png]

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
    Output: No intersection
    Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
    Explanation: The two lists do not intersect, so return null.

## leetcode代码 ##

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
        //boundary check
        if(headA == null || headB == null) return null;
        
        ListNode a = headA;
        ListNode b = headB;
        
        //if a & b have different len, then we will stop the loop after second iteration
        while( a != b){
        
        	//for the end of first iteration, we just reset the pointer to the head of another linkedlist
            a = a == null? headB : a.next;
            b = b == null? headA : b.next;    
        }
        
        return a;
    }

[https_assets.leetcode.com_uploads_2018_12_07_circularlinkedlist.png]: https://img-blog.csdnimg.cn/img_convert/32051730fc73a6afed28ab0c3639b8aa.png
[https_assets.leetcode.com_uploads_2018_12_07_circularlinkedlist_test2.png]: https://img-blog.csdnimg.cn/img_convert/ad5ac4da56fa5b5130f9f83296fd3c7d.png
[https_assets.leetcode.com_uploads_2018_12_07_circularlinkedlist_test3.png]: https://img-blog.csdnimg.cn/img_convert/f695107c711de069e76683a56cb55a90.png
[https_assets.leetcode.com_uploads_2020_09_15_inorder_1.jpg]: https://img-blog.csdnimg.cn/img_convert/efed1686a74b7c78a2ed530ff6a39126.jpeg
[https_assets.leetcode.com_uploads_2020_08_28_pre1.jpg]: https://img-blog.csdnimg.cn/img_convert/8419b266b82d65a7ea47a5765a6c5a6a.jpeg
[https_assets.leetcode.com_uploads_2021_03_05_160_statement.png]: https://img-blog.csdnimg.cn/img_convert/39ed540acdaa33f38576704129e9ef23.png
[https_assets.leetcode.com_uploads_2021_03_05_160_example_1_1.png]: https://img-blog.csdnimg.cn/img_convert/4ff2f504867dce5f39c25ffa6dc4d6f6.png
[https_assets.leetcode.com_uploads_2021_03_05_160_example_2.png]: https://img-blog.csdnimg.cn/img_convert/f28debad279291baa9805873714a4bc1.png
[https_assets.leetcode.com_uploads_2021_03_05_160_example_3.png]: https://img-blog.csdnimg.cn/img_convert/110bc8e56881bb8c6f57b6c2fd67ff23.png