1. 搜寻插入地位

https://leetcode-cn.com/problems/search-insert-position/

class Solution {public int searchInsert(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while(left<=right){int mid=(left+right)/2;
            if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid-1;}else{return mid;}
        }
        return left;
    }
}

2. 搜寻二维矩阵

https://leetcode-cn.com/problems/search-a-2d-matrix/

public boolean searchMatrix(int[][] matrix, int target) {if(matrix.length == 0)
        return false;
    int row = 0, col = matrix[0].length-1;
    while(row < matrix.length && col >= 0){if(matrix[row][col] < target)
            row++;
        else if(matrix[row][col] > target)
            col--;
        else
            return true;
    }
    return false;
}

3. 删除排序数组反复项

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

public int removeDuplicates(int[] nums) {
        // 应用双指针
        if(nums==null || nums.length == 1){return nums.length;}
        int i = 0,j =1;
        while(j<nums.length){if(nums[i]==nums[j]){j++;}else{
                i++;
                nums[i]=nums[j];
                j++;
            }
        }
        return i+1;
    }

4. 链表的两头节点

https://leetcode-cn.com/problems/middle-of-the-linked-list/

public ListNode middleNode(ListNode head) {
        ListNode p = head, q = head;
        while (q != null && q.next != null) {
            q = q.next.next;
            p = p.next;
        }
        return p;
}

5. 爱生气的书店老板

https://leetcode-cn.com/problems/grumpy-bookstore-owner/

/*
首先 找到不扭转的时候客人就称心的数量和 同时更新数组
这样问题就转变为 求数组指定长度最大和的问题
工夫复杂度 O(n) 空间复杂度为 O（1）*/
class Solution {public int maxSatisfied(int[] customers, int[] grumpy, int x) {
        int sum = 0, len = customers.length;
        for (int i = 0; i < len; i++) {if (grumpy[i] == 0){sum += customers[i];
                customers[i] = 0;
            } 
        }
        int num = customers[0];
        int maxval = customers[0];
        for (int i = 1; i < len; i++){if (i < x) num = num + customers[i];
            else num = num + customers[i] - customers[i - x];
            maxval = Math.max(maxval, num);
        }
        
        return (sum + maxval);
    }
}

6. 滑动窗口最大值

https://leetcode-cn.com/problems/sliding-window-maximum/

/*
  思路：遍历数组 L R 为滑窗左右边界 只增不减
        双向队列保留以后窗口中最大的值的数组下标 双向队列中的数从大到小排序，新进来的数如果大于等于队列中的数 则将这些数弹出 再增加
        当 R -L+1=k 时 滑窗大小确定 每次 R 前进一步 L 也前进一步 保障此时滑窗中最大值的
        数组下标在 [L，R] 中，并将以后最大值记录
  举例：nums[1，3，-1，-3，5，3，6，7] k=3
     1：L=0，R=0，队列【0】R-L+1 < k
            队列代表值【1】2: L=0,R=1, 队列【1】R-L+1 < k
            队列代表值【3】解释：以后数为 3 队列中的数为【1】要保障队列中的数从大到小 弹出 1 退出 3
          但队列中保留的是值对应的数组下标 所以队列为【1】窗口长度为 2 不增加记录
     3: L=0,R=2, 队列【1，2】R-L+1 = k ,result={3}
            队列代表值【3，-1】解释：以后数为 -1 队列中的数为【3】比队列尾值小 间接退出 队列为【3，-1】窗口长度为 3 增加记录记录为队首元素对应的值 result[0]=3
     4: L=1,R=3, 队列【1，2，3】R-L+1 = k ,result={3，3}
            队列代表值【3，-1,-3】解释：以后数为 -3 队列中的数为【3，-1】比队列尾值小 间接退出 队列为【3，-1，-3】窗口长度为 4 要保障窗口大小为 3 L+1=1 此时队首元素下标为 1 没有生效
          增加记录记录为队首元素对应的值 result[1]=3
     5: L=2,R=4, 队列【4】R-L+1 = k ,result={3，3，5}
            队列代表值【5】解释：以后数为 5 队列中的数为【3，-1，-3】保障从大到小 顺次弹出增加 队列为【5】窗口长度为 4 要保障窗口大小为 3 L+1=2 此时队首元素下标为 4 没有生效
          增加记录记录为队首元素对应的值 result[2]=5
    顺次类推 如果队首元素小于 L 阐明此时值生效 须要弹出
*/
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums==null||nums.length<2) return nums;
        // 双向队列 保留以后窗口最大值的数组地位 保障队列中数组地位的数按从大到小排序
        LinkedList<Integer> list = new LinkedList();
        // 后果数组
        int[] result = new int[nums.length-k+1];
        for(int i=0;i<nums.length;i++){
            // 保障从大到小 如果后面数小 弹出
            while(!list.isEmpty()&&nums[list.peekLast()]<=nums[i]){list.pollLast();
            }
            // 增加以后值对应的数组下标
            list.addLast(i);
            // 初始化窗口 等到窗口长度为 k 时 下次挪动在删除过期数值
            if(list.peek()<=i-k){list.poll();   
            } 
            // 窗口长度为 k 时 再保留以后窗口中最大值
            if(i-k+1>=0){result[i-k+1] = nums[list.peek()];
            }
        }
        return result;
    }
}

吴邪，小三爷，混迹于后盾，大数据，人工智能畛域的小菜鸟。
更多请关注