LeetCode136+128+152+148

Ideas

         Because it's using O(n) Algorithm of complexity , So we can't solve this problem with our own sorting algorithm . So try to trade space for time to solve the problem . Just use the hash table method .

         First, store all the elements in the hashed table , Then traverse each element , To find whether there are elements adjacent to this element in the hash table , Then find the upper and lower limits , Take the difference between the two and subtract one , Because every time, you subtract or add first, and then find the elements of the hash table .

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        HashSet<Integer> set = new HashSet<>();
        int res = 0;
        for(int num:nums){
            set.add(num);
        }
        for(int i = 0;i<nums.length;i++){
            int down = nums[i]-1;
            while(set.contains(down)){
                set.remove(down);
                down--;
            }
            int up = nums[i] + 1;
            while(set.contains(up)){
                set.remove(up);
                up++;
            }
            res = Math.max(res,up-down-1);
        }
        return res;
    }
}

​​​​​​136. A number that appears only once

Ideas

Because it is a number that only appears twice and once , So we used hashSet To solve .

You can also use bit operations to solve . Just use XOR to calculate directly .

Code

HashSet：

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length == 1) return nums[0];
        HashSet<Integer> hashset = new HashSet<>();
        for(int i = 0;i<nums.length;i++){
            if(hashset.contains(nums[i])){
                hashset.remove(nums[i]);
            }else{
                hashset.add(nums[i]);
            }
        }
        return hashset.iterator().next();
    }
}

An operation ：

        int res = 0;
        for(int i =0;i<nums.length;i++){
            res^=nums[i];
        }
        return res;

148. Sort list

Ideas

It's just to apply merge sorting to the linked list .

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode midNode = mid(head);
        ListNode node2 = midNode.next;
        midNode.next = null;
        return merge(sortList(head),sortList(node2));

        
    }
    public ListNode mid(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode merge(ListNode a,ListNode b){
        ListNode dumy = new ListNode(0);
        ListNode temp  =dumy;
        while(a != null && b != null){
            if(a.val <= b.val){
                temp.next = a;
                a = a.next;
            }else{
                temp.next = b;
                b = b.next;
            }
            temp = temp.next;
        }
        if(a == null)
            temp.next = b;
        if(b == null)
            temp.next = a;
        return dumy.next;

    }
}

152. Product maximum subarray

Ideas

Remember every time you traverse an array element , If it is a negative number, then multiplying by the previous minimum may be the maximum , Or multiply by the largest to get the largest , Or the current element is the largest , No use dp Array to solve this problem .

Code

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        int res = nums[0];
        for(int i = 1;i<nums.length;i++){
            int temp = max;
            max = Math.max(Math.max(max*nums[i],min*nums[i]),nums[i]);
            min = Math.min(Math.min(temp*nums[i],min*nums[i]),nums[i]);
            res = Math.max(res,max);
        }
        return res;
    }
}