前言
國慶前最后一次打卡，國慶后繼續開啟，公眾號bigsai回復進群歡迎加入打卡，如有幫助記得點贊收藏，
近期打卡記錄：
LeetCode 32最長有效括號(困難) （本周）
LeetCode 30串聯所有單詞的子串&31下一個排列（上周）
LeetCode 27移除元素&28實作strStr()&29兩數相除(上周)
二分查找我想大家都很熟悉，二分查找每次判斷并比較元素所在區間進行壓縮，每次都可以壓縮一半的區間，所以壓到1個大小把它你想來看就是(最壞)擴散了n次到達原始長度，
很多題就是原始的二分，但很多題就是二分變種，
33搜索旋轉排序陣列
這題其實就是一個二分變種，加了一些其他的條件，每次的mid要根據判斷如何移動.一個正常序列分成左右兩個序列，并且都是遞增的，沒有相同的，
就拿中間mid的值大于target就有以下幾種情況：
按照這樣思路同理分析另一半一直求解即可，
ac代碼為：
public int search(int[] nums, int target) {
if(nums[0]==target)return 0;
if(nums[nums.length-1]==target)return nums.length-1;
int l=0;int r=nums.length-1;
while (l<r) {
int mid=(l+r)/2;
//System.out.println(mid+" "+l+" "+r);
if(nums[mid]==target)return mid;
// 8 9 2 3 4 5 6 7
if(nums[mid]>target)//中間大于目標值
{
if(nums[0]>target) {//最左側都大于 只可能在右側最小區域
if(nums[mid]<nums[0])//當前在右區域
{
r=mid;
}
else {
l=mid+1;
}
}
else {最左側小于目標值 向左
r=mid;
}
}
// 8 9 2 3 4 5 6 7
else {//中間小于目標值
//如果在右側區域往左
if(nums[nums.length-1]<target)//最右側小于target 需要向左側去
{
if(nums[mid]<nums[nums.length-1])//當前
{
r=mid;
}
else {
l=mid+1;
}
}
else //最右側大于target 在小的區域內
{
l=mid+1;
}
//System.out.println(1);
}
}
return -1;
}
34在排序陣列中查找元素的第一個和最后一個位置
入門二分，注意找到一個值后進行左右方向尋找邊界問題，ac代碼為：
public int[] searchRange(int[] nums, int target) {
int a[]= {-1,-1};
if(nums.length==1&&nums[0]==target) {a[0]=0;a[1]=0;return a;}
if(nums.length==0)return a;
int leftindex,rightindex;
int left=0,right=nums.length-1;
while (left<right) {
//System.out.println(left+" "+right);
int mid=(left+right)/2;
if(nums[mid]==target)
{
leftindex=mid;
rightindex=mid;
while (leftindex>=0&&nums[leftindex]==target) {leftindex--;}
while (rightindex<nums.length&&nums[rightindex]==target) {rightindex++;}
a[0]=leftindex+1;a[1]=rightindex-1;
return a;
}
else if (nums[mid]<target) {
left=mid+1;
}
else {
right=mid;
}
}
if(nums[left]==target)
{
a[0]=left;a[1]=left;
}
return a;
}
35搜索插入位置
這題需要注意的就是插入位置或者查找到的編號，經典二分不多說你懂的/
public int searchInsert(int[] nums, int target) {
if(nums[0]>=target)return 0;//剪枝
if(nums[nums.length-1]==target)return nums.length-1;//剪枝
if(nums[nums.length-1]<target)return nums.length;
int left=0,right=nums.length-1;
while (left<right) {
int mid=(left+right)/2;
if(nums[mid]==target)
return mid;
else if (nums[mid]>target) {
right=mid;
}
else {
left=mid+1;
}
}
return left;
}
本次打卡結束拉，下周國慶暫停一次(就一次)，歡迎其他小哥哥小姐姐加入打卡，微信搜索bigsai，回復進群加入打卡力扣！
Big sai
CSDN認證博客專家
scikit-learn
CSDN認證博客專家
scikit-learn
關注微信公眾號:bigsai，回復進群即可加入leetcode打卡群，回復bigsai獲取珍藏pdf一份，江科大本，南理研一，平凡的日子里努力充實自己，努力學習，努力分享，期待你的關注！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/135718.html
標籤：其他