Remove Linked List Elements leetcode

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode node = dummy;
        while (node.next != null) {
            if (node.next.val == val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }
        return dummy.next;
    }
}

Single Number III leetcode

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

与single number1 类似 每个重复的数都出现两次, 假设不重复的数字为a, b. 用^遍历所有数组就会得到一个a^b的结果c. 我们知道在c中, 每一位1说明在这一位上a与b是不同的. 
      3 (0011) xor 
      5 (0101)= 
     6 (0110) 
我们只需要找到这1位, 然后把数组按照这一位是1还是这一位是0分为两个数组 然后分别做^遍历 就会在每个组中找到一个独立的单身狗了.

public class Solution {
    public int[] singleNumber(int[] nums) {
        int[] res = new int[2];
        if (nums == null || nums.length == 0) {
            return res;
        }
        int tem = 0;
        for (int c : nums) {
            tem ^= c;
        }
        int pre = 0;
        while (tem!= 0) {
            pre = tem;
            tem &= tem - 1;
        }
        for (int n : nums) {
            if ((n & pre) == 0) {
                res[0] ^= n;
            } else {
                res[1] ^= n;
            }
        }
        return res;
    }
}

Sliding Window Maximum leetcode

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

用deque来解决, deque里入他们的下角标, 每当入新数的时候把新数与deque的num[末尾]比较 如果num[末尾]小就把末尾扔掉, 直到num[末尾]大于等于num[新数], 这样一来deque里就是按照num的大小顺序排列的 前边的最大 后边的最小. 每次不用出列不在窗口里德数字, 我们只需要确定deque开头的数是在窗口就可以了. 因为每个数只可能被操作最多两次，一次是加入队列的时候，一次是因为有别的更大数在后面，所以被扔掉，或者因为出了窗口而被扔掉。   所以时间复杂度为O(N).

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < n; i++) {
            //如果最左侧的数不在窗口内 出列
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.pollFirst();
            }
            //如果结尾的数小于新数则出列
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            //添加入新数
            deque.offerLast(i);
            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return res;
    }
}