overview

LeetCode Hot: longest continuous sequence, numbers that appear only once, word splitting, circular linked list, circular linked list II

LeetCode Hot

2.46 longest continuous sequence

Given an unordered integer array nums, find the length of the longest sequence of consecutive numbers (sequence elements are not required to be continuous in the original array).

Please design and implement an algorithm with time complexity of O(n) to solve this problem.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
 Explanation: the longest consecutive sequence of numbers is [1, 2, 3, 4]. Its length is 4.

//Using Hash sets
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int x:nums){
            set.add(x);
        }
        int longest = 0,curNum,curLen = 0;
        for(int x:nums){
            if(!set.contains(x-1)){		//crux
                curNum = x;
                curLen = 1;
                while(set.contains(curNum+1)){
                    curNum++;
                    curLen++;
                }
            }
            longest = Math.max(longest,curLen);
        }
        return longest;
    }
}

2.47 numbers that appear only once

Given a non empty array of integers, each element appears twice except that one element appears only once. Find the element that appears only once.

explain:

Your algorithm should have linear time complexity. Can you do it without using extra space?

Example 1:

input: [2,2,1]
output: 1

//XOR
//The XOR operation satisfies the commutative law, a^b^a=a^a^b=b, so res is equivalent to nums[0]^nums[1]^nums[2]^nums[3]^nums[4] Then, according to the exchange law, merge the equal elements together for XOR (the result is 0), and then XOR with the elements that have only appeared once, so that the final result is the elements that have only appeared once (0 ^ arbitrary value = arbitrary value)
class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int x:nums){
            res ^= x;
        }
        return res;
    }
}

2.48 word splitting

Give you a string s and a string list wordDict as a dictionary. Please judge whether you can use the words in the dictionary to splice s.

Note: it is not required to use all the words in the dictionary, and the words in the dictionary can be reused.

Example 1:

input: s = "leetcode", wordDict = ["leet", "code"]
output: true
 explain: return true because "leetcode" Can be "leet" and "code" Spliced into.

//DP
//Define whether dp[i] indicates whether the string s[0..i − 1] composed of the first I characters of the string s can be split into several words in the dictionary by spaces
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length(), maxw = 0;
        boolean[] dp = new boolean[len + 1]; 
        dp[0] = true;
        Set<String> set = new HashSet();
        for(String str : wordDict){
            set.add(str);
            maxw = Math.max(maxw, str.length());
        }
        for(int i = 1; i < len + 1; i++){
            for(int j = i; j >= 0 && j >= i - maxw; j--){
                if(dp[j] && set.contains(s.substring(j, i))){	//dp[i] just go ahead and explore the longest word in the dictionary
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}

2.49 circular linked list

Give you a head node of the linked list to judge whether there are links in the linked list.

If there is a node in the linked list that can be reached again by continuously tracking the next pointer, there is a ring in the linked list. In order to represent the links in a given linked list, the evaluation system uses the integer pos to represent the position where the tail of the linked list is connected to the linked list (the index starts from 0). Note: pos is not passed as a parameter. Just to identify the actual situation of the linked list.

Returns true if there are links in the linked list. Otherwise, false is returned.

Input: head = [3,2,0,-4], pos = 1
 Output: true
 Explanation: there is a ring in the linked list, and its tail is connected to the second node.

//Speed pointer
public boolean hasCycle(ListNode head) {
    ListNode fast = head, slow = head;
    while(fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow) { // Compare after the pointer is moved to exclude the initial pointing to the head node
            return true;
        }
    }
    return false;
}

2.50 circular linked list II

Given the head node of a linked list, it returns the first node from the linked list into the ring. If the linked list is acyclic, null is returned.

If there is a node in the linked list that can be reached again by continuously tracking the next pointer, there is a ring in the linked list. In order to represent the links in a given linked list, the evaluation system uses the integer pos to represent the position where the tail of the linked list is connected to the linked list (the index starts from 0). If pos is - 1, there is no ring in the linked list. Note: pos is not passed as a parameter, but only to identify the actual situation of the linked list.

Modification of linked list is not allowed.

Input: head = [3,2,0,-4], pos = 1
 Output: returns the linked list node with index 1
 Explanation: there is a ring in the linked list, and its tail is connected to the second node.

//Speed pointer
/*
1.First encounter, slow = nb
2.a+nb = entry point
3.slow Go a = entrance = head to the entrance = a
4.From 3, the starting distance entrance = first encounter position + a
*/
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;		//After the first meeting, slow takes step nb, and only needs to take step a, that is, the entrance. At this time, let fast move to head, and meet again, that is, take step A
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

summary

1. Review the previous knowledge points and summarize the algorithm template framework.