转码野生老农刷题打卡

2022-10-23打卡

744        寻找比目标字母大的最小字母
Link：https://leetcode.cn/problems/fin ... reater-than-target/
题解：https://gitee.com/vincentmliu/Al ... aterThanTarget.java
耗时： 20min


笔记：
1.二分查找，终止条件是mid-1 <= target && mid > target

时间复杂度 O(logN)
空间复杂度 O(1) 在原数组搜索，3个指针

2022-10-24打卡

35        搜索插入位置
Link：https://leetcode.cn/problems/search-insert-position/
题解：https://gitee.com/vincentmliu/Al ... InsertPosition.java
耗时： 30min



笔记：
1. 二分查找，查询范围是左闭右闭区间
2. 到最后如果没找到，判断以下mid最后的位置。nums[mid] >= target ? mid : mid + 1;

时间复杂度 O(logN) 二分
空间复杂度 O(1) 只需要指针

2022-10-25打卡

34        在排序数组中查找元素的第一个和最后一个位置
Link：https://leetcode.cn/problems/search-insert-position/
题解：https://gitee.com/vincentmliu/Al ... tInSortedArray.java
耗时： 30min



笔记：
1. 二分查找，查询左右边界

时间复杂度 O(logN) 二分
空间复杂度 O(1) 只需要指针

2022-10-26打卡

Interview 10.05        稀疏数组搜索
Link：https://leetcode.cn/problems/sparse-array-search-lcci/
题解：https://gitee.com/vincentmliu/Al ... rraySearchLcci.java
耗时： 30min，没做出来



笔记：
1. 框架基本是二分的框架，主要是mid碰到“”的时候怎么移动。
2. 左右都可以移动，while(mid<=r&&words[mid].equals("")) mid++;但是单纯的这么写，后面判断会造成数组越界。因为mid会停在r+1或者l-1的位置。
3. 所以在开头加上
            while(l<=r&&words[l].equals("")) l++;
            while(l<=r&&words[r].equals("")) r--;
        就可以避免数组越界
       
时间复杂度 O(N) 二分，但是最坏可能会全部遍历
空间复杂度 O(1) 只需要指针

2022-10-27打卡

33         搜索旋转排序数组
Link：https://leetcode.cn/problems/sparse-array-search-lcci/
题解：https://gitee.com/vincentmliu/Al ... tedSortedArray.java
耗时： 45min



笔记：
1. 策略是，先将数组拆成前后两段（也就是找到k）。然后再分别对两段数组二分查找
2. wether there is a possibility that nums reverse on index len - 1;？？？ YES！！！！！ corner case！！！
3. 找k的逻辑是：k点满足nums[mid] > nums[mid+1], 如果mid滑到了右边界，会造成数组越界。所以最后while循环要停在left滑到了右边界，会造成数组越界。所以最后while循环要停在left==right上面。所以while循环的条件是（left<right)
当nums[mid] >= left的时候，说明mid落在了左半段，因为右半段所有值都小于left。所以这时候left = mid +1;
为什么要有等于号？因为如果mid==left（数组长度为2），且旋转位置为0（nums[mid]永远大于nums[right]）的情况，left坐标就不会动了，right也不会动，就死循环了。所以既要有等号又要 mid + 1(因为mid已经不满足nums[mid] > nums[mid+1]了，可以排除出搜索范围了 );

当nums[mid] < right的时候，right = mid；说明在右半段。有坐标左移。
为什么没有等号？为社么不mid-1？原理和left差不多，因为除了len = 1，mid不会落在right上面（否则就停止搜索了停止区间为[left,left)），
为什么不-1，因为搜索范围本身就不包含right。mid -1 还要参与搜索。
       
时间复杂度 O(logn) 二分，最多三次
空间复杂度 O(1) 只需要指针

2022-10-28打卡

153        寻找旋转排序数组中的最小值
Link：https://leetcode.cn/problems/sparse-array-search-lcci/
题解：https://gitee.com/vincentmliu/Al ... tedSortedArray.java
耗时： 15min



笔记：
1. 和昨天得33题一样，也是先找到k点，k+1就是最小。如果k是len -1， 最小就是0；
       
时间复杂度 O(logn) 二分
空间复杂度 O(1) 只需要指针

2022-10-28打卡

852        山脉数组的峰顶索引
Link：https://leetcode.cn/problems/peak-index-in-a-mountain-array/
题解：https://gitee.com/vincentmliu/Al ... AMountainArray.java
耗时： 5min



笔记：
1. 初始化条件，left = 1； right = len - 1；
2. 循环终止条件while(left <= right) if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])       
时间复杂度 O(logn) 二分
空间复杂度 O(1) 只需要指针

2022-10-29打卡

162        寻找峰值
Link：https://leetcode.cn/problems/find-peak-element/
题解：https://gitee.com/vincentmliu/Al ... indPeakElement.java
耗时： 10min


笔记：
1.0和len-1只需要用1和len-2来判断下就可以输出了
2.如果没有就寻找【1，len-2】之间的山峰，while(left <= right) 左闭右闭。终止条件是nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]
3. 更新mid要判断是在左山坡还是右山坡

时间复杂度 O(logN)
空间复杂度 O(1) 指针

2022-10-31打卡

69         x 的平方根
Link：https://leetcode.cn/problems/sqrtx/
题解：https://gitee.com/vincentmliu/Al ... h/ID00069Sqrtx.java
耗时： 30min



笔记：
1. 终止条件： mid*mid == x || (mid*mid < x && (mid+1)*(mid+1) > x)
前半段是针对正好为整数的平方根，后半段是小数的平方根
2. 因为x范围[0, 2147483647],
   (int)Math.sqrt(Integer.MAX_VALUE) = 46340，
   46340 * 46340 = 2147395600，
   所以，
   x > 2147395600 直接返回46340，--- 防止 46340 + 1 > 2147483647,int越界
3. 左闭右闭区间

时间复杂度 O(logn) 二分
空间复杂度 O(1) 只需要指针

2022-11-01打卡

74        搜索二维矩阵
Link：https://leetcode.cn/problems/search-a-2d-matrix/
题解：https://gitee.com/vincentmliu/Al ... earchA2dMatrix.java
耗时： 30min



笔记：
1. 先找 matrix[mid][0] < target && matrix[mid][n-1] > target
2. 然后找 matrix[row][mid] == target

时间复杂度 O(logm + logn) 二分
空间复杂度 O(1) 只需要指针