3-1 从二分查找法看如何写出正确的程序

排序：在数组中解决一个任务
查找：二分查找
数据结构：栈，队列，堆，都是基于数组来构建的

3-2 改变变量定义，依然可以写出正确的算法

二分查找法

对于有序数列，才能使用二分查找（排序的作用）

思路很简单，但往往在代码的实现上会遇到各种问题

  private int binarySearch(int n, int[]arr, int target){
        /* 对于左右边界的设置，网上有很多版本。
           对l/r的初始化不是想当然的，而要基于我怎样赋予他们实际意义
           我自己定义要在[l...r] 范围里寻找target，我定义的都是闭区间
         */
        int l = 0, r = n - 1;

        /* 我在循环条件里是写l<r 还是 l<= r 呢，又是边界问题
           由于之前我们定义了[l...r] 范围里寻找target
           所以在 l == r 时， 区间[l...r]只有一个元素，依然有效
         */
        while(l<=r){
            int mid = l+(r-l)/2;
            if(arr[mid] == target){
                return mid;
            }else if(target > arr[mid]){
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        return -1;
    }

当边界设置有变化时，代码也有变化

    private int binarySearch(int n, int[]arr, int target){
        /* 对于左右边界的设置，网上有很多版本。
           对l/r的初始化不是想当然的，而要基于我怎样赋予他们实际意义
           我自己定义要在[l...r) 范围里寻找target，我定义的是左闭右开
         */
        int l = 0, r = n ;

        /* 我在循环条件里是写l<r 还是 l<= r 呢，又是边界问题
           由于之前我们定义了[l...r) 范围里寻找target
           所以在 l == r 时， 区间[l...r)没有元素，是无效的
         */
        while(l < r){
            int mid = l+(r-l)/2;
            if(arr[mid] == target){
                return mid;
            }else if(target > arr[mid]){
                l = mid + 1;
                /*在target < arr[mid] 时，此时 target在[l ...mid) 中
                  r = mid;
                 */
            }else {
                r = mid ;
            }
        }
        return -1;
    }

3-3 在LeetCode上解决第一个问题 Move Zeros

import java.util.LinkedList;
import java.util.Queue;

public class MoveZeroes {
    private void moveZeroes(int[] arr){


        Queue<Integer> q = new LinkedList<Integer>();
        // 遍历数组，将所有非零元素都拿出来
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]!=0){
                q.add(arr[i]);
            }
        }

        int nonZeroNum = q.size();
        // 将非零元素填补到原数组中
        for (int i = 0;  q.size()>0 ; i++) {
            arr[i] = q.remove();
        }

        // 之后将未填补的位置全都fill为0
        for(int i = nonZeroNum; i< arr.length; i++){
            arr[i] = 0;
        }
    }


    public static void main(String[] args){
        int [] testArray = {0,1,0,3,12};
        MoveZeroes test = new MoveZeroes();
        test.moveZeroes(testArray);
        for(int i : testArray){
            System.out.print(i+" ");
        }
    }
}

3-5 三路快排partition思路的应用 Sort Color

计数排序（适用于元素个数非常有限的情况）：分别统计0，1，2 个数

错误处理可以（1）容错（2）抛出异常

class Solution {
    public void sortColors(int[] nums) {
        int zero = -1;           // nums[0...zero] = 0;
        int two = nums.length;  // nums[two...nums.length-1] = 2;
        for(int i = 0; i<two;){
            if(nums[i]==1){
                i++;
            }else if(nums[i]==2){
                two--;
                swap(nums,i,two);    
            }else{
                zero++;
                swap(nums,zero,i);
                i++;
            }
        }  
    }

    private void swap(int[] nums, int m , int n){
        int temp = nums[m];
        nums[m] = nums[n];
        nums[n] = temp;
    }
}

3-6 对撞指针 Two Sum II - Input Array is Sorted

学会运用题目给出的条件作为其性质，作为有化解的思路

这个题的题设Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

那么我们再用HashMap来做，就“浪费”了其sorted in ascending order 的性质

本节介绍的是two point: 对撞指针

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        //用two pointer 对撞指针
        int left = 0;
        int right = numbers.length-1;
        while(left < right){
            if(numbers[left] + numbers[right] == target){
                return new int[]{left+1, right+1};
            }else if(numbers[left] + numbers[right] < target){
                left++;
            }else{
                right--;
            }
        }
        return null;
    }
}

3-7 滑动窗口 Minimum Size Subarray Sum

本节介绍的是two point: 滑动窗口

什么是子数组（有可能连续，也有可能不连续，请跟面试官提前沟通）

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int l = 0, r = -1; // nums[l...r] <---->  window
        int sum = 0;
        int result = nums.length + 1;

        while(l < nums.length){
            if(r + 1 < nums.length && sum < s){            
                sum += nums[++r];     
            }else{           
                sum -= nums[l++];
            }
            if(sum>=s){
                result = Math.min(result, r-l+1);
            }
        }        
        if(result == nums.length + 1){
            return 0;
        } 
        return result;      
    }
}

3-8 在滑动窗口中做记录 Longest Substring Without Repeating Characters

维护一个滑动窗口，子串s[i---j] 中若没有重复字母，就要试着向后拓展一位，看下个字符是否和当前的字符串产生了重复字符

如果没有产生，指针 j 就可以放心的++

以此类推，我们一直尝试着增大j 来找到一个更长的子串，使得这个子串没有重复字母。直到某一刻我们要考察的下一个字符和子串中的某个字符产生了重复

此时，该子串无法继续向前拓展，我们需要记录s[i---j] 的长度。之后，i ++ 往前直到把该重复字母刨除

此时， j 可以包含刚才重复的字母，j继续往前拓展，寻找没有重复字母的子串

class Solution {
  public int lengthOfLongestSubstring(String s) {
      int[] freq  = new int[256];
      int l = 0, r = -1;
      int result = 0;

      while(l<s.length()){
          if(r+1 < s.length() && freq[s[r+1]]==0){
              freq[s[++r]]++;
          }else{
              freq[s[l++]]--;
          }
          result = max(result, r+1-l);
      }
      return result;
    }
}

第3章数组中的问题其实最常见