LeetCode 704:二分查找
題目鏈接：二分查找
二分法很常見巷屿，但是在while循環(huán)里的條件與后續(xù)left/right指針的變化邏輯有很大關(guān)聯(lián)羽资，很容易出現(xiàn)思路正確软免，代碼怎么也無法通過的情況熄浓，浪費(fèi)時(shí)間。
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
int left = 0;
int right = len-1;
while(right>=left){
int index = (left+right)/2;
if(nums[index]==target){
return index;
}else if(nums[index]>target){
right = index-1;
}else{
left = index+1;
}
}
return -1;
}
}
這里采用的是左閉右閉的思路區(qū)來寫的
左閉右閉指的是拭卿，在新劃分出來的區(qū)間中醋奠，left和right都是需要下一步比較的[left,right]，因此：
-
left==right時(shí)耳峦，還不能跳出循環(huán)恩静，閉區(qū)間內(nèi)仍然有一個(gè)元素等待比較，while里面的條件為right>=left蹲坷； -
left和right的每一次更新都是index+1驶乾，index-1, 因?yàn)?code>index已經(jīng)被比較過，不可以再進(jìn)入下一次比較的區(qū)間內(nèi)
LeetCode 27： 移除元素
題目鏈接：移除元素
這道題采用的是雙指針+swap的思路來做的冠句，踩了很多坑轻掩，針對這一種寫法幸乒，有以下幾點(diǎn)注意：
-
while里面的條件盡量不要寫!=懦底，容錯(cuò)率大大降低，很容易死循環(huán)罕扎！ - 處理順序的問題聚唐，先做主要邏輯，即判斷可以交換后交換值腔召，再往下尋找
- 對于這種前后雙指針向中間靠的問題仍然需要進(jìn)一步總結(jié)杆查，在這里真的踩了很多坑，每次都稀里糊涂的過了
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
int right = nums.length-1;
while(left<=right){
if(nums[left]==val&&nums[right]!=val){
nums[left] = nums[right];
nums[right] = val;
}
else{
if(nums[left]!=val){
left++;
}
if(nums[right]==val){
right--;
}
}
}
return left;
}
}
這道題還有一種更加清晰的思路：快慢指針方法
用快指針尋找非val值臀蛛，用慢指針一步一步覆蓋原數(shù)組里面的值
class Solution {
public int removeElement(int[] nums, int val) {
int slow = 0;
int fast = 0;
while(fast<nums.length){
if(nums[fast]!=val){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
注意return的是slow亲桦，而不是slow+1崖蜜，因?yàn)閟low是下一個(gè)元素待填入位置
