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

Reverse Bits leetcode

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++, n >>= 1) {
            res = res << 1 | (n & 1);//给res的最后一位置为(n最右一位)
        }
        return res;
    }
}

//方法2
public int reverseBits(int n) {
        int res = 0;
        int[] tem = new int[32];
        for (int i = 0; i < 32; i++) {
            tem[i] = n >> i & 1;
        }
        for (int i = 31; i >= 0; i--) {
            res += tem[i] << (31 - i);
        }
        return res;
    }

Power of Two leetcode

Given an integer, write a function to determine if it is a power of two.

public class Solution {
    public boolean isPowerOfTwo(int n) {
         if (n <= 0) {
             return false;
         }
         return (n & (n - 1)) == 0;
        
    }
}

Number of 1 Bits leetcode

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

解法1: 把每一位都 & 1, 计算所有1的个数
解法2: 因为n & (n - 1)就可以消除掉最右边的一个1, 比如110，减去1得101，相与得100，消去了最右边的1。这样一直消除到没有, 可以计算出1得个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (((n >> i) & 1) == 1) {
                count++;
            }
        }
        return count;
    }
}

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

3Sum Smaller leetcode

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

用3Sum的方法 a=num[i] + num[l] + num[r]
当a < target时候 left++, 但是注意此时对于num[i] + num[l] + num[l + 1 ---> r] 都满足<target
所以这个时候指针右移 count+ right - left;

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        } 
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] < target) {
                    count+= right - left;
                    left++;
                }
                if (nums[i] + nums[left] + nums[right] >= target) {
                    right--;
                }
            }
        }
        return count;
    }
}