⭐️个人主页：摸鱼の文酱博客主页🙋‍♂️
🍑博客领域：java编程基础,mysql
🍅写作风格：干货,干货,还是tmd的干货
🌸精选专栏：【Java】【mysql】 【算法刷题笔记】
🎯博主的码云gitee，平常博主写的程序代码都在里面。
🚀支持博主：点赞👍、收藏⭐、留言💬
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

💓 写在前面

其实刚开始就该说这些话的,但是我真的没有对自己抱有太大的信心,以前也想过无数次每天要坚持刷几道算法题,也跟着各种网课,书籍去刷过,但是都没有坚持几天,这次有幸参加了英雄哥的算法《九日集训》,在这里和许多志同道合的兄弟们一起刷题,互相鼓励,互相监督,我相信我这次一定能坚持下来,先把这九天坚持下来,在制定新的计划.
如果你们也想要刷算法题又苦于无法坚持和没有系统的计划,欢迎大家也来 《九日集训》试一试.
关注我,我们一起刷爆LeetCode!!!

🎪 今日刷题内容

今天的题目是有关一维数组的

🎯 33. 搜索旋转排序数组

题目描述:整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例:
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

可以看得出来,这又是一道典型的用二分查找来解决的问题.
但是问题来了,基础的二分查找是对于一个整体有序的序列进行的,而这个数组并非整体有序,我们又该如何处理?

🍭思路一:HashMap

相信很多人就会说:先把数组排序,然后进行简单的二分查找,可是那样查找到的下标还是原来的下标吗?
于是,我就想用什么办法可以储存原来的下标,我想到了它–HashMap<key,value>;
我们只要将排序前的数组的下标和对应值存入HashMap中,然后再将数组排序后二分,找到值的情况下,再HashMap中查找其对应的原来的下标

代码如下(在IDEA测试用例是没问题的,但是在LeetCode中时长超出,应该是想HashMap中存数据消耗了时间,如果有大佬知道怎么优化解决或者发现我的问题的,恳请大佬告知):

public  int search(int[] nums, int target) {
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            hashMap.put(i,nums[i]);
        }
        Arrays.sort(nums);
        int left=0;
        int right=nums.length-1;
        while(left<right){
            int mid = left+(right-left)/2;
            if(nums[mid] > target){
                //下一轮搜索范围[left,mid-1]
                right=mid-1;
            }else{
                //下一轮搜索范围[mid,right]
                left=mid;
            }
        }
        if(nums[left] == target){
            return hashMap.get(nums[left]);
        }
        return -1;
    }

既然上面的行不通,那就只能在数组本身上下手,将数组本身划分为有序和无序两种

🍭思路二:分段进行二分查找

思路：如果中间的数小于最右边的数，则右半段是有序的，
     如果中间的数大于最右边的数，则左半段是有序的，
     我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定保留哪半边了

 public int search(int[] nums, int target) {
        int len = nums.length;
        int left = 0, right = len-1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] < nums[right]){
            //[mid,right]有序
                if(nums[mid] < target && target <= nums[right])
                //判断target是否在[mid,right]这个范围内
                //在的话就搜索右半段,否则就搜索左半段
                    left = mid+1;
                else
                    right = mid-1;
            }
            else{
            //[left,mid]有序
                if(nums[left] <= target && target < nums[mid])
                //判断target是否在[left,mid]这个范围内
                //在的话就搜索左半段,否则就搜索右半段
                    right = mid-1;
                else
                    left = mid+1;
            }
        }
        return -1;
    }

我这种菜鸟,除了上面那种解法上面的解法应该是没别的办法了,

🍭思路三:用^代替多次条件判断,然后二分

不过大佬的派头依然狠:这是作者的正版题解
我尝试理解一下:
在这个数组中,基本会出现一下的情况,分别要采取向前或者向后的操作

于是要判断以下三种情况,有两项为真还是只有一项为真。

nums[0] <= target <= nums[i]
               target <= nums[i] < nums[0]
                         nums[i] < nums[0] <= target

使用 “异或” 操作可以轻松的得到上述结果,两项为真时异或结果为假，一项为真时异或结果为真

public int search(int[] nums, int target) {
 
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo == hi && nums[lo] == target ? lo : -1;
    }

做完这题如果还有想要加强二分查找的同学可以参考这个:
https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/xsq0b7/

🎯 81. 搜索旋转排序数组 II

题目描述:已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

思路:
看题目不难发现,这道题和上一道题是类似的,无非是这题的数组中多出来了重复元素.那比起上面的判断方法来说,这道题不可忽视的一点就是你选到的left,right,mid三个下标所对应的数存在相等情况时的影响
对于这种情况，我们只能将当前二分区间的左边界加一，右边界减一，然后在新区间上继续二分查找。

🍭思路一:二分(去除相等元素影响 缩小范围)

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return false;
        }
        if (n == 1) {
            return nums[0] == target;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
                ++l;
                --r;
            } else if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return false;
    }
}

🍭思路二:二分(参照上一题的思路二)

public static boolean search3(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[start] == nums[mid]) {
                start++;
                continue;
            }
            //前半部分有序
            if (nums[start] < nums[mid]) {
                //target在前半部分
                if (nums[mid] > target && nums[start] <= target) {
                    end = mid - 1;
                } else {  //否则，去后半部分找
                    start = mid + 1;
                }
            } else {
                //后半部分有序
                //target在后半部分
                if (nums[mid] < target && nums[end] >= target) {
                    start = mid + 1;
                } else {  //否则，去后半部分找
                    end = mid - 1;

                }
            }
        }
        //一直没找到，返回false
        return false;

    }

🎯153. 寻找旋转排序数组中的最小值

🍭思路一:Arrays.sort

笑死,投机谁不会呢?

public int findMin(int[] nums) {
        Arrays.sort(nums);
        return nums[0];
    }

🍭思路二:二分法

public static int findMin(int[] nums) {

//        Arrays.sort(nums);
//        return nums[0];
        //二分
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            //            取中间值
            int mid = left + (right - left) / 2;
            //            如果中间值小于最大值，则最大值减小
//            疑问：为什么 high = mid;而不是 high = mid-1;
//            解答：{4,5,1,2,3}，如果high=mid-1，则丢失了最小值1
            if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                //如果中间值大于最大值，则最小值变大
//                疑问：为什么 low = mid+1;而不是 low = mid;
//                解答：{4,5,6,1,2,3}，nums[mid]=6，low=mid+1,刚好nums[low]=1
//                继续疑问：上边的解释太牵强了，难道没有可能low=mid+1,正好错过了最小值
//                继续解答：不会错过!!! 如果nums[mid]是最小值的话，则其一定小于nums[high],走if，就不会走else了
                left = mid + 1;
            }
        }
        //        疑问：为什么while的条件是low<high,而不是low<=high呢
//        解答：low<high，假如最后循环到{*,10,1,*}的这种情况时，nums[low]=10,nums[high]=1,nums[mid]=10,low=mid+1,
//             直接可以跳出循环了,所以low<high,此时low指向的就是最小值的下标;
//             如果low<=high的话，low=high，还会再不必要的循环一次，此时最后一次循环的时候会发生low==high==mid，
//             则nums[mid]==nums[high]，则会走一次else语句，则low=mid+1,此时low指向的是最小值的下一个下标，
//             则需要return[low-1]
        return nums[left];
    }

🎯154. 寻找旋转排序数组中的最小值 II

题目描述: 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须尽可能减少整个过程的操作步骤。

当 nums[mid] == nums[right] 时，是此题对比 153题 的难点（原因是此题中数组的元素可重复，难以判断分界点 i 指针区间）

🍭思路一:二分(通过不断向前压缩范围来确定最小数)

我们采用 right = right - 1 解决此问题

    public int findMin(int[] nums) {
        int left=0;
        int right=nums.length-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]<nums[right]){
                //第一种情况是 nums[mid] < nums[right]这说明 nums[mid] 是最小值右侧的元素，
                // 因此我们可以忽略二分查找区间的右半部分。
                right=mid;
            }else if(nums[mid]>nums[right]){
                //第二种情况是 :nums[mid]>nums[right]。这说明nums[mid] 是最小值左侧的元素，
                // 因此我们可以忽略二分查找区间的左半部分和中间位置mid。
                left=mid+1;
            }else{
                //第三种情况是: nums[mid]==nums[righ]。由于重复元素的存在，我们并不能确定
                // nums[mid] 究竟在最小值的左侧还是右侧，因此我们不能莽撞地忽略某一部分的元素。
                // 我们唯一可以知道的是，由于它们的值相同，所以无论 nums[right] 是不是最小值，
                // 都有一个它的「替代品」nums[mid]，因此我们可以忽略二分查找区间的右端点。
                right-=1;
            }
        }
        return nums[left];
    }

🍭思路一:二分(确定数组的旋转点)

public int findMin(int[] nums) {
        /**
         * 思路：有序数组一般用二分查找
         */
        int left = 0;
        int right = nums.length-1;
        while(left < right) {
            int mid = left + (right - left)/2;

            if (nums[mid] > nums[right]) {
                // 中间值 > 右边界值，则旋转点在中间值右侧
                //下一轮[mid+1,right]  (nums[mid]大于某个数,所以肯定不是最小的,不用再考虑)
                left = mid+1;
            } else if (nums[mid] < nums[right]) {
                // 中间值 < 右边界值，则旋转点在中间值左侧，包含自身
                //下一轮[left,mid]
                right = mid;
            } else {
                // 不确定旋转点方向，分情况进行left++或者right--
                if(nums[right-1] <= nums[right]) {
                    // right前一位 <= right当前位置值，说明旋转点一定在right前面
                    right--;
                }else {
                    // 前面的数要比自身大  right位置就是旋转点
                    left = right;
                }
            }
        }
        return nums[left];
    }

🎯70. 爬楼梯

题目描述:假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

典型的斐波那契类型题,相信大家都很熟悉.废话不多说 直接动态干起

🍭思路一:动态规划

 public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

🍭思路一:通顶公式

public int climbStairs(int n) {
        double sqrt_5 = Math.sqrt(5);
        double fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
        return (int)(fib_n / sqrt_5);
    }

🎯509. 斐波那契数

题目描述:斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

🍭思路一:动态规划

定义三个数储存值,一个一个计算

public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }

🍭思路二:递归

public int fib(int n) {
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }

🎯 1137. 第 N 个泰波那契数

题目描述:泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值

🍭思路一:递归

  int[] cache = new int[40];
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        if (cache[n] != 0) return cache[n];
        cache[n] = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3); 
        return cache[n];
    }

🍭思路二:迭代

public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; i++) {
            int d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return c;
    }

🎯 LCP 01. 猜数字

题目描述:小A 和 小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回 小A 猜对了几次？

输入的guess数组为 小A 每次的猜测，answer数组为 小B 每次的选择。guess和answer的长度都等于3

额,说实话,我以为今天的题都是二分了,结果这怎么还越往后越简单了…
可能是怕我们刷题太累放松一下??

🍭思路:直接遍历

public int game(int[] guess, int[] answer) {
        int count=0;
        for(int i=0;i<3;i++){
            if(guess[i] == answer[i]){
                count++;
            }
        }
        return count;
    }

🎯LCP 06. 拿硬币

题目描述:桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。

🍭思路:直接遍历

public int minCount(int[] coins) {
        int count = 0;
        for(int i=0;i<coins.length;i++){
            count+=(coins[i]+1) >> 1;
        }
        return count;
    }

🎯2006. 差的绝对值为 K 的数对数目

题目描述:给你一个整数数组 nums 和一个整数 k ，请你返回数对 (i, j) 的数目，满足 i < j 且 |nums[i] - nums[j]| == k 。

🍭思路一:用双循环遍历

public int countKDifference(int[] nums, int k) {
        int res = 0, n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (Math.abs(nums[i] - nums[j]) == k) {
                    ++res;
                }
            }
        }
        return res;
    }

🍭思路二:用HashMap+一次遍历

public int countKDifference(int[] nums, int k) {
        int res = 0, n = nums.length;
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (int j = 0; j < n; ++j) {
            res += cnt.getOrDefault(nums[j] - k, 0) + cnt.getOrDefault(nums[j] + k, 0);
            cnt.put(nums[j], cnt.getOrDefault(nums[j], 0) + 1);
        }
        return res;
    }

🎯剑指 Offer II 069. 山峰数组的顶部

题目描述:符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：

arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i ，即山峰顶部。
简单来说就是一个数组先升序再降序,有一个最大数
那直接找比它后一位要大的那一个不就得了

🍭思路一:暴力求解

public int peakIndexInMountainArray(int[] arr) {
    
        for(int i=0;i<arr.length-1;i++){
            if(arr[i]>arr[i+1]){
                return i;
            }
        }
        return -1;
    }

🍭思路二:二分法求解

public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 1, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (arr[mid - 1] < arr[mid]) l = mid;
            else r = mid - 1;
        }
        return r;
    }

✅ 总结

经过今天的练习,我发现自己对二分查找的理解还是太浅了,没有想过二分查找可以变幻多种形式来解决多种问题,对于二分查找,我还得再多多练习.