秋招算法之——双指针、二分查找

1. 二分查找：针对有序数组、旋转数组查找

  1. 寻找旋转数组的最小值(旋转点)：存在重复元素
class Solution {
    public int findMin(int[] nums) {
        /*
        旋转数组的最小值
        8.24
        */

        //二分查找
        int left = 0;
        int right = nums.length-1;

        while(left <= right){
            int middle = left + (right - left)/2;

            if(nums[middle] < nums[right]){
                //如果比最右小，说明middle在右半数组，旋转点在左边。right = middle
                right = middle;
            }else if(nums[middle] > nums[right]){
                //如果比最右大，说明middle在左半数组，旋转点在右边，left = middle+1;
                left = middle+1;
            }else{
                //否则，right--。
                right--;
            }
        }

        return nums[left];
    }
}
  1. 寻找旋转数组的最小值(旋转点)：不存在重复元素
class Solution {
    public int findMin(int[] nums) {
        /*
        旋转数组的最小值
        7.25
        */
        //二分查找

        //判断空
        if(nums.length == 0){
            return 0;
        }

        int left = 0;
        int right = nums.length-1;

        while(left < right){
            int middle = (left + right)/2;

            if(nums[middle] < nums[right]){
                //右半数组，旋转点在左边
                right = middle;
            }else{
                left = middle + 1;
            }
        }

        return nums[left];
    }
}
  1. 搜索旋转数组：
class Solution {
    public int search(int[] nums, int target) {
        /*
        搜索旋转数组
        8.24
        */
        //二分查找

        int left = 0;
        int right = nums.length-1;

        while(left <= right){
            int middle = left + (right - left)/2;

            if(nums[middle] == target){
                return middle;

            }else if(nums[middle] <= nums[right]){
                //middle小于right，在右半数组，可以分为[middle,target]和[target,right]
                if(nums[middle] < target && target <= nums[right]){
                    //如果target大于middle并且target小于right，说明target依旧在右半数组，left移动到middle+1
                    left = middle + 1;
                }else{
                    //如果target小于middle并且target大于right，说明target可能位于左半数组，right移动到middle-1
                    right = middle - 1;
                }
            }else if(nums[middle] > nums[right]){
                //middle大于right，在左半数组，可以分为[left,target]和[target,middle]
                if(nums[left] <= target && target < nums[middle]){
                    //如果target大于left并且target小于middle，target依旧在左半数组，right逼近到middle-1
                    right = middle - 1;
                }else{
                    //如果target小于left并且target大于middle，说明target在右半数组，left逼近到middle+1
                    left = middle + 1;
                }
            }
        }

        return -1;
    }
}
  1. 0-n-1中缺失的数字：二分查找可以用于查找递增数字中缺失的数
class Solution {
    public int missingNumber(int[] nums) {
        /*
        0到n-1中缺失的数
        7.27
        */
        //有序数组查找，二分

        int left = 0;
        int right = nums.length-1;

        while(left <= right){
            //通过middle来判断缺失的数
            int middle = (left + right)/2;

            //数组中有这个索引对应的值，
            if(nums[middle] == middle){
                left = middle+1;
            }else{
                right = middle-1;
            }
        }

        return left;
    }
}

2. 双指针：二维矩阵查找、合并数组、三数之和、最接近的三数之和、移动数组元素

  1. 寻找两个正序数组的中位数
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        /*
        寻找两个正序数组的中位数
        7.22
        */
        //合并数组 + 取中点

        int index = 0;
        int index1 = 0;
        int index2 = 0;

        int len1 = nums1.length;
        int len2 = nums2.length;

        int[] temp = new int[len1+len2];

        for(int i=0;i<temp.length;i++){
            if(index1 == len1){
                temp[index++] = nums2[index2++];
            }else if(index2 == len2){
                temp[index++] = nums1[index1++];
            }else if(nums1[index1] < nums2[index2]){
                temp[index++] = nums1[index1++];
            }else{
                temp[index++] = nums2[index2++];
            }
        }

        //提取中位数
        int middle = temp.length/2;
        //如果长度为奇数，返回中位数
        if(temp.length%2 == 1){
            return (double)temp[middle];
            //如果长度为偶数。计算中位数+中位数前一位的和的平均数
        }else{
            return (double)(temp[middle] + temp[middle-1])/2;
        }
    }
}
  1. 搜索二维矩阵
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        /*
        搜索二维矩阵
        7.24
        */
        //双指针，从右上角搜索

        //判断空
        if(matrix.length == 0 || matrix[0].length == 0){
            return false;
        }

        int row = 0;
        int col = matrix[0].length-1;

        while(row < matrix.length && col >= 0){
            if(matrix[row][col] == target){
                return true;
            }else if(matrix[row][col] > target){
                //大，因为是从右上角开始搜索，往前一列，col--
                col--;
            }else if(matrix[row][col] < target){
                //小，因为是从右上角开始搜索，往下一行，row++
                row++;
            }
        }

        return false;
    }
}
  1. 排序数组查找元素的第一个和最后一个位置
class Solution {
    public int[] searchRange(int[] nums, int target) {
        /*
        排序数组中查找元素的第一个和最后一个位置
        7.23
        */
        //二分查找，O(logn)，实质是查找target的左右边界

        int[] fail = new int[]{-1,-1};

        int[] result = new int[2];

        //左边界
        int left = 0;
        int right = nums.length-1;
        while(left <= right){
            int middle = (left + right)/2;
            if(left <= right && nums[middle] < target){
                left = middle + 1;
            }else if(left <= right && nums[middle] >= target){
                right = middle - 1;
            }
        }
        //判断左指针是否越界
        if(left > nums.length-1){
            return fail;
        }
        //判断左指针是否指向target
        if(nums[left] == target){
            result[0] = left;
        }else{
            return fail;
        }

        
        //右边界
        left = 0;
        right = nums.length-1;
        while(left <= right){
            int middle = (left + right)/2;
            if(left <= right && nums[middle] <= target){
                left = middle + 1;
            }else if(left <= right && nums[middle] > target){
                right = middle - 1;
            }
        }
        //判断右指针是否越界
        if(right < 0){
            return fail;
        }
        //判断右指针是否指向target
        if(nums[right] == target){
            result[1] = right;
        }else{
            return fail;
        }

        return result;
    }
}
  1. 三数之和
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        /*
        三数之和
        7.22
        */

        //三指针计算前缀和
        ArrayList<List<Integer>> result = new ArrayList<>();

        //排序，实现去重和剪枝
        Arrays.sort(nums);

        for(int i=0;i<nums.length;i++){
            if(nums[i] > 0){
                break;
            }
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }

            //提取双指针
            int left = i+1;
            int right = nums.length-1;

            while(left < right){
                //计算三指针的前缀和
                int sum = nums[i] + nums[left] + nums[right];

                if(sum == 0){
                    
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));

                    //while去重
                    while(left < right && nums[left] == nums[left+1]){
                        left++;
                    }
                    while(left < right && nums[right] == nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;

                }else if(sum > 0){
                    //太大，right--
                    right--;
                }else{
                    left++;
                }
            }
        }

        return result;
    }
}
  1. 最接近的三数之和
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        /*
        最接近的三数之和
        8.3
        */
        //三数之和的变种，同样使用双指针实现，可通过Math.abs()比较开头三个数之和result和遍历过程中的三数之和sum的绝对值，如果target-sum < target-result，将result更新sum


        //排序
        Arrays.sort(nums);
        int result = nums[0]+nums[1]+nums[2];

        for(int i=0;i<nums.length;i++){
            int left = i+1;
            int rihgt = nums.length-1;

            while(left < rihgt){
                int sum = nums[i] + nums[left] + nums[rihgt];

                if(Math.abs(target - sum) < Math.abs(target - result)){
                    result = sum;
                }else if(sum < target){
                    left++;
                }else if(sum > target){
                    rihgt--;
                }else{
                    return result;
                }
            }
        }

        return result;

    }
}
  1. 颜色分类
class Solution {
    public void sortColors(int[] nums) {
        /*
        颜色分类(0，1，2问题)
        7.24
        */
        //三指针交换

        //判断空
        if(nums.length == 0){
            return;
        }

        int left = 0;
        int right = nums.length-1;
        int cur = 0;

        while(cur <= right){
            if(nums[cur] == 2){
                int temp = nums[cur];
                nums[cur] = nums[right];
                nums[right] = temp;
                //right未搜索，cur不能++
                right--;
            }else if(nums[cur] == 0){
                int temp = nums[cur];
                nums[cur] = nums[left];
                nums[left] = temp;
                //left已经搜过，cur可以++
                left++;
                cur++;
            }else{
                cur++;
            }
        }
    }
}
  1. 盛最多水的容器
class Solution {
    public int maxArea(int[] height) {
        /*
        盛最多水的容器
        7.22
        */
        //双指针，如果左比右大，右为高，计算体积。反之

        int left = 0;
        int right = height.length-1;
        int result = 0;

        while(left <= right){

            if(height[left] > height[right]){
                int high = height[right];
                int width = right-left;
                result = Math.max(high*width,result);
                right--;
                
            }else{
                int high = height[left];
                int width = right-left;
                result = Math.max(result,high*width);
                left++;
            }
        }
        return result;
    }
}
  1. 网易笔试：字典序最小的排列：给出一个长度为m的序列T，求一个长度为n且字典序最小的排列S，要求不改变原序列中元素的相对位置。
第一行输入两个正整数n和m
第二行输入m个数，表示序列
5 3
2 1 5
输出
2 1 3 4 5

个人渣解：

import java.util.HashSet;
import java.util.Scanner;
public class Solution{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int len = sc.nextInt();
        int len1 = sc.nextInt();
        int[] nums1 = new int[len1];
 
        HashSet<Integer> set = new HashSet<>();
        for(int i=0;i<nums1.length;i++){
            nums1[i] = sc.nextInt();
            set.add(nums1[i]);
        }
 
        //nums2，长度为len-len1，存放互补的元素
        int[] nums2 = new int[len-len1];
        int index = 0;
        for(int i=1;i<=len;i++){
            if(!set.contains(i)){
                nums2[index++] = i;
            }
        }
 
        /*双指针判断
        i指针用于控制nums1移动
        j指针用于控制nums2移动
        */
 
        int i = 0;
        int j = 0;
 
        int[] result = new int[len];
        int Resultindex = 0;
 
        //谁的第一个小谁就先存
        if(nums1[0] < nums2[0]){
            result[Resultindex++] = nums1[0];
            i=1;
        }else{
            result[Resultindex++] = nums2[0];
            j=1;
        }
 
        while(i < nums1.length && j < nums2.length){
 
            //谁小存谁
            if(nums1[i] < nums2[j]){
                result[Resultindex++] = nums1[i++];
            }else{
                result[Resultindex++] = nums2[j++];
            }
        }
 
        //补充存入最后一个数
        while(i == nums1.length && j < nums2.length){
            //如果nums1完但nums2未完，存入nums2
            result[Resultindex++] = nums2[j++];
        }
        while(i < nums1.length && j == nums2.length){
            //如果nums2完但nums1未完，存入nums1
            result[Resultindex++] = nums1[i++];
        }
 
        for(int k=0;k<result.length-1;k++){
            System.out.print(result[k] + " ");
        }
        System.out.print(result[result.length-1]);
    }
}

3. 哈希表解决各类型问题

  1. 数组中元素出现次数问题(略，基本都是一套模板带走)

  2. 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        /*
        无重复字符的最长子串
        7.22
        */
        //哈希表判断字符，更新左边界为右边界
        Map<Character,Integer> map = new HashMap<>();
        int left = 0;
        char[] str = s.toCharArray();
        int result = 0;

        for(int i=0;i<str.length;i++){
            if(map.containsKey(str[i])){
                left = Math.max(left,map.get(str[i])+1);
            }

            map.put(str[i],i);

            result = Math.max(result,i-left+1);
        }
        return result;
    }
}
  1. 和为K的子数组
class Solution {
    public int subarraySum(int[] nums, int k) {
        /*
        和为k的子数组
        7.26
        */
        //哈希表统计出现次数

        //判断空
        if(nums.length == 0){
            return 0;
        }

        Map<Integer,Integer> map = new HashMap<>();
        int sum = 0;
        int time = 0;

        //预存前缀和
        map.put(sum,1);

        for(int i=0;i<nums.length;i++){
            //前缀和
            sum = sum + nums[i];
            //如果包含
            if(map.containsKey(sum-k)){
                time = time + map.get(sum-k);
            }

            if(map.containsKey(sum)){
                map.put(sum,map.get(sum)+1);
            }else{
                map.put(sum,1);
            }
        }

        return time;
    }
}
  1. 字母异位分组（同一组字母放到同一行）
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        /*
        字母异位分组
        7.24
        */
        //哈希表判断字符串排序后的key，如果map中有，说明是同一组，存到同一行list，否则新开list

        List<List<String>> result = new ArrayList<>();
        Map<String,List<String>> map = new HashMap<>();

        for(int i=0;i<strs.length;i++){
            //字符串转换为字符数组
            char[] str = strs[i].toCharArray();

            //排序
            Arrays.sort(str);

            //转回字符串
            String key = String.valueOf(str);

            //map中含有key，说明key和strs[i]是同一组字母，存到同一行
            if(map.containsKey(key)){
                map.get(key).add(strs[i]);
            }else{
                ArrayList<String> list = new ArrayList<>();
                //list存strs[i]
                list.add(strs[i]);

                //map存key和list，key作为同组的判断
                map.put(key,list);

                //result存入list
                result.add(list);
            }
        }

        return result;
    }
}
  1. 同构字符串(面试高频题)
class Solution {
    public boolean isIsomorphic(String s, String t) {
        /*
        字符串同构
        8.18
        */
        //使用哈希表，s-t映射，如果map中有key为s的字符，但是value却不是对应的t字符，返回false

        HashMap<Character,Character> map = new HashMap<>();

        for(int i=0;i<s.length();i++){
            char s1 = s.charAt(i);
            char t1 = t.charAt(i);

            if(map.containsKey(s1)){
                //再判断s1的value是否是t1，如果不是，说明不是abb和baa的类型，
                if(map.get(s1) != t1){
                    return false;
                }
            }else{
                //如果map中没有s1，但是却有t1
                if(map.containsValue(t1)){
                    return false;
                }
            }

            map.put(s1,t1);
        }

        return true;
    }
}
  1. 设计hashmap（boolean数组和int数组解决最基本的put和get）
class MyHashMap {

    /*
    设计hashmap
    7.26
    */
    //两个数组，keys存放元素，contains判断是否存在

    int[] keys;
    boolean[] contains;

    /** Initialize your data structure here. */
    public MyHashMap() {
        keys = new int[1000001];
        contains = new boolean[1000001];
    }
    
    /** value will always be non-negative. */
    public void put(int key, int value) {
        //直接存
        keys[key] = value;
        contains[key] = true;
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        if(contains[key]){
            return keys[key];
        }else{
            return -1;
        }
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        //直接将contains置为false
        contains[key] = false;
    }
}
  1. 两数之和(面试高频题)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        /*
        两数之和
        7.22
        */
        //思路：哈希表 + 前缀和

        Map<Integer,Integer> map = new HashMap<>();

        for(int i=0;i<nums.length;i++){

            int sum = target - nums[i];

            if(map.containsKey(sum)){
                return new int[]{i,map.get(sum)};
            }

            map.put(nums[i],i);
        }
        
        return new int[0];
    }
}
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

友情链接更多精彩内容