https://leetcode-cn.com/problems/trapping-rain-water/submissions/
经过分析每一个柱子的上面的积水量等于左边最高和右边最高的最低值
所以我们先预处理一遍左边的最高值数组和右边最高值数组
然后一次循环取出来就行

class Solution {
    public int trap(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }
        int n = height.length;
        int[] leftHeight = new int[n];
        int[] rightHeight = new int[n];
        leftHeight[0] = height[0];
        rightHeight[n - 1] = height[n - 1];
        for(int i = 1; i < n; i++){
            leftHeight[i] = Math.max(leftHeight[i-1], height[i]);
        }
        for(int i = n - 2; i>= 0; i--){
            rightHeight[i] = Math.max(rightHeight[i+1], height[i]);
        }
        int res = 0;
        for(int i = 0; i<n; i++){
            res += Math.min(leftHeight[i], rightHeight[i]) - height[i];
        }
        return res;
    }
}

再经过分析我们发现不论是对于每个值如果当前左边比右边低那么只会取左边的值 那么我们可以用左右指针法 对于每个循环到的指针 比如循环到left指针我们可以确保right指针的值比我们left值都高意味着如果出现rightMax的话肯定比leftMax高 所以我们只需要取leftMax比对就可以。

class Solution {
    public int trap(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }
        int n = height.length;
        int left = 0;
        int right = n - 1;
        int leftMax = height[0];
        int rightMax = height[n-1];
        int res = 0;
        while(left < right){
            if(height[left] < height[right]){
                //如果左边比右边矮的话更新则以左边的更新
                if(height[left] > leftMax){
                    leftMax = height[left];
                }else{
                    res += leftMax - height[left];
                }
                left++;
            }else{
                if(height[right] > rightMax){
                    rightMax = height[right];
                }else{
                    res += rightMax - height[right];
                }
                right--;
            }
        }
        return res;
    }
}

我们用一个HashSet来保存所有的数字
然后遍历这个数组 当这个数不存在这个数-1（说明是连续递增的开头）则开始一直循环找这个连续递增的数列直到结束，每次外层循环只会循环连续递增的开头所以复杂度为O(n) 空间复杂度O(n)

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        Set<Integer> set = new HashSet();
        for(int num: nums){
           set.add(num);
        }
        int res = 0;
        for(int num: nums){
            //只有遇到开头才会开始循环
            if(!set.contains(num - 1)){
                int now = num;
                int nowCnt = 1;
                while(set.contains(now + 1)){
                    now++;
                    nowCnt++;
                }
                res = Math.max(res, nowCnt);
            }
        }
        return res;
    }
}

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/
需要两种二分 一种二分之一是找到相同的值要尽量往左边找 一种是找到相同的值要尽量往右边找 循环结束条件是l == r 因为r最终肯定是正确结果 那么我们返回l 或者r都一样

class Solution {
    private int solve(int[] nums, int target, boolean left){
        int l = 0;
        int r = nums.length;
        //结束条件是l == r
        while(l < r){
            int mid = l + ((r - l) >> 1);
            //如果是往左边找的话则要加上=号 继续往左边找 否则往右边找
            if(nums[mid] > target || (left && nums[mid] == target)){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return l;
    }
    public int[] searchRange(int[] nums, int target) {
        int[] res = {-1, -1};
        int leftIdx  = solve(nums, target, true);
        if(leftIdx == nums.length || nums[leftIdx] != target){
            //找不到值就直接返回
            return res;
        }
        //否则就继续找
        res[0] = leftIdx;
        res[1] = solve(nums, target, false) - 1;
        return res;
    }
}

https://leetcode-cn.com/problems/divide-two-integers/submissions/
不能用 乘法、除法、mod 直观的感觉就是暴力循环剪去被除数，但是常数太大，想想为什么会超时，是因为每次减得被除数太少了我们可以剪去他的倍数这样子就可以加速这个过程了，这里可以用位运算直接找出这个数的2^n次倍来试效率高。
最终得出
2^az+2^bz+2^cz=(2^a+2^b+2^c)z 则内容之和则是最终结果。

class Solution {
    public int divide(int dividend, int divisor) {
         if (dividend == 0) { //除0情况直接返回
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {//溢出情况 特判
            return Integer.MAX_VALUE;
        }
        boolean negative;
        negative = (dividend ^ divisor) <0;//用异或来计算是否符号相异 符号是否相同
        long t = Math.abs((long) dividend); //取绝对值
        long d= Math.abs((long) divisor); //取绝对值
        int result = 0;
        for (int i=31; i>=0;i--) {
            if ((t>>i)>=d) {//找出足够大的数2^n*divisor
                result+=1<<i;//将结果加上2^n
                t-=d<<i;//将被除数减去2^n*divisor
            }
        }
        return negative ? -result : result;//符号相异取反
    }
}

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/submissions/
双指针 我们利用删除倒数第N个指针的特性 我们可以用 双指针 第一个指针比第二个指针先走n+1 则如果第一个指针到底则第二个指针的位置就在倒数第n+1上只需要把倒数第n+1.next = n+1.next.next 即可，此外为了方便处理类似：链表长度为1取倒数第一这种情况我们新建一个中间链表 dummy 让整个链表长度+1位则可以很方便的解决这种情况。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy, second = dummy;
        for(int i = 0; i < n + 1; i++){
            first = first.next;
        }
        while(first != null){
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}