LeetCode 137 Single Number II

Link: leetcode.com/problems/si…

Method: bit operation

Idea: One of the common practices in bitwise operations is to count by each digit. Because the title says the figure is only a appeared at a time, there were other just 3 times, then I enumerated the 32-bit, each an array of all count how many 1, assuming that one on a total of 1 is not a multiple of 3, then the only appeared a few, in this one is 1, otherwise 0. So that’s how you construct this number. Code:

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int num : nums) {
                sum += (num >> i) & 1;
            }
            if (sum % 3! =0) {
                res |= (1<< i); }}returnres; }}Copy the code

LeetCode 260 Single Number III

Link: leetcode.com/problems/si…

Method: bit operation

Single Number I = O(n) Single Number I is not written because it is so simple in this age, but it means that only one Number in an array appears once, and all the others appear exactly twice. I’m using xor, because a to the a is equal to 0, so I’m just going to xor everything in the array. So for this problem, there are two numbers that happen exactly once, and if they all or you get the xor of both of them, that’s not going to be very useful. But let’s say I can split the array into two groups, with the two lone elements in one group. Then for the other elements, they all come together in pairs in the same group, and the separation of the two groups is complete. The problem is how to divide into two groups. The lowbit is x & (-x), and the lowbit is used to extract the lowest 1 bit of a number. So, if we say that the value of the two lonelers is xor, and we do lowbit on xOR, that means that the value of the two lonelers is 1, that means that the value of the two lonelers is different in this bit, then we can group the original array according to the value of this bit is 0 or 1, and ensure that the two lonelers are divided into two groups. Code:

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int num : nums) xor ^= num;
        
        int low = xor & (-xor);
        int group0 = 0, group1 = 0;
        for (int num : nums) {
            if ((low & num) == 0) {
                group0 ^= num;
            }
            else{ group1 ^= num; }}return new int[] {group0, group1}; }}Copy the code

LeetCode 142 Linked List Cycle II

Link: leetcode.com/problems/li…

Method: codirectional double pointer

Time complexity: O(n) Space complexity: O(1) Idea: Everybody can do the problem these days, mainly to write the derivation. Reference from yxc bosses www.acwing.com/solution/co… , but I need to continue to prove that slow only takes the first turn when C meets, otherwise it will affect the time complexity. Assume that each point is shown in the figure below:

Both Pointers start at point A, slow one step at A time, fast two at A time, and collide at point C. The collision at C assumes that slow has made n turns on the ring, fast has made M turns on the ring, So x + y + z) * m + y = 2 * [x + n + y) (y + z) * x = (m, 2 n) * (y + z) – y = (m – 2 n – 1) * (y + z + z) So x is the integer times the circumference of the ring plus z. At this point, if we take slow back to the head and fast goes from C, then when slow goes to B, fast also goes to B, and that’s where we want to go. Summary: First, slow and fast move at different speeds until they point to the same address, then move one of them to X, and the two Pointers move one step at a time to find point B. So why is it that when we meet at point C for the first time, Slow must not have completed its first lap? If slow goes to B and fast is at D, it’s l away from slow. So we know that slow takes one step at a time and fast takes two steps at a time. Slow and fast will meet after l units of time, when slow has taken l steps and L is less than the circumference of the circle. So slow is making the first turn when they meet, so the time is O(n). Code:

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        
        ListNode slow = head, fast = head;
        while(fast ! =null&& fast.next ! =null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break; }}if(slow ! = fast)return null;
        slow = head;
        
        while(slow ! = fast) { slow = slow.next; fast = fast.next; }returnslow; }}Copy the code

LeetCode 287 Find the Duplicate Number

Link: leetcode.com/problems/fi…

Method 1: bit operation

Idea: Use a similar approach with Single Number II, where each digit passes. They say n + 1 values, range [1, n], so there’s just one number that happens to be repeated. Enumerates each digit, counting the number of 1’s in the range [1,n], and counting the number of 1’s in the original array (cnt2). If cnT2 > cnT1, the extra digit is 1 in this digit. Code:

class Solution {
    public int findDuplicate(int[] nums) {
        int res = 0, n = nums.length;
        for (int i = 0; i < 32; i++) {
            int bit = 1 << i;
            int cnt1 = 0, cnt2 = 0;
            for (int k = 0; k < n; k++) {
                if ((k & bit) > 0) cnt1++;
                if ((nums[k] & bit) > 0) cnt2++;
            }
            if (cnt2 > cnt1) res += bit;
        }
        
        returnres; }}Copy the code

Method 2: co-direction double pointer

Time complexity: O(n) Space complexity: O(1) Idea: Use the Linked List Cycle II method, which I feel is super insightful to link these two problems together… Anyway, I didn’t expect it at that time, but after reading the solution, I felt it was very reasonable.

  1. Nums [num] does not violate the index because all numbers must be between [1,n] and n + 1, for example, 4 integers in the range [1,3].
  2. If we construct a list node with num as the number in the array and its next pointing to nums[num], we can construct a hypothetical list. Because there’s a duplicate value in the middle, there’s a node that has two nodes pointing to it.
  3. The Linked List Cycle II, 2 is formed as described above. The node described in is the entrance to the ring.
  4. So using Linked List Cycle II, change node.next to node = nums[node].

Code:

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        int n = nums.length;
        
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                break;
            }
        }
        
        fast = 0;
        while(slow ! = fast) { slow = nums[slow]; fast = nums[fast]; }returnslow; }}Copy the code