LeetCode136+128+152+148

思路

        因为是用O(n)复杂度的算法，所以不能用自带的排序算法来解决这个问题。所以就尝试用空间换时间来解决问题。就用了哈希表法。

        首先将所有元素存入带哈希表中，然后遍历每个元素，去寻找哈希表中是否有该元素相邻的元素，然后找到上限和下限，取二者的差并减一，因为每次都是先减或者先加再去找哈希表的元素。

代码

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. 只出现一次的数字

思路

因为是只有出现两次和出现一次的数，所以使用了hashSet来求解。

还可以使用位运算来求解。直接用异或来计算就可以了。

代码

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();
    }
}

位运算：

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

148. 排序链表

思路

就是将归并排序运用到链表上就可以了。

代码

/**
 * 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. 乘积最大子数组

思路

记得每次遍历一个数组元素的时候，如果是负数则乘以之前最小的可能是最大，或者乘以最大的是最大的，或者当前元素就是最大的，不用使用dp数组来求解这道题。

代码

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;
    }
}