鄭州網(wǎng)站建設(shè)zzjisu網(wǎng)絡(luò)軟文營(yíng)銷案例3篇
💐個(gè)人主頁(yè)：初晴~
📚相關(guān)專欄：尋找one piece的刷題之路
什么是雙指針?biāo)惴?
雙指針?biāo)惴ㄊ且环N常用的編程技巧，尤其在處理數(shù)組和字符串問(wèn)題時(shí)非常有效。這種方法的核心思想是使用兩個(gè)指針來(lái)遍歷數(shù)據(jù)結(jié)構(gòu)，這兩個(gè)指針通常分別位于數(shù)據(jù)結(jié)構(gòu)的起始位置或某些特定位置，通過(guò)移動(dòng)這兩個(gè)指針來(lái)達(dá)到解決問(wèn)題的目的。雙指針?biāo)惴梢燥@著減少時(shí)間復(fù)雜度，使其從O(n2)O(n2)降低到O(n)O(n)，甚至在某些情況下可以達(dá)到O(log?n)O(logn)。
- 對(duì)撞指針從兩端向中間移動(dòng)。?個(gè)指針從最左端開(kāi)始，另?個(gè)從最右端開(kāi)始，然后逐漸往中間逼近。
- 對(duì)撞指針的終?條件?般是兩個(gè)指針相遇或者錯(cuò)開(kāi)（也可能在循環(huán)內(nèi)部找到結(jié)果直接跳出循 環(huán)），也就是：
- left == right （兩個(gè)指針指向同?個(gè)位置）
- left > right （兩個(gè)指針錯(cuò)開(kāi)）
一、復(fù)寫零
題目鏈接
題目描述：
題目分析：
題目的意思就是遍歷原數(shù)組，每遇到一次0，就將后面所有的數(shù)水平向右移動(dòng)一位，并再插入一個(gè)0，最后仍丟棄溢出的數(shù)據(jù)，仍取原來(lái)的數(shù)組長(zhǎng)度的數(shù)據(jù)。
分析：
我們先初始化兩個(gè)指針 cur = 0 ， dest = -1
判斷 cur 位置的元素:? 如果是 0 的話， dest 往后移動(dòng)兩位；? 否則， dest 往后移動(dòng)?位。
注意：
要判斷 dest 是否越界到 n 的位置：如果越界，執(zhí)?下?三步：
- n - 1 位置的值修改成 0 ；
- cur 向移動(dòng)?步；
- dest 向前移動(dòng)兩步。
? 2.然后從后向前進(jìn)?復(fù)寫操作
從 cur 位置開(kāi)始往前遍歷原數(shù)組，依次還原出復(fù)寫后的結(jié)果數(shù)組：
代碼實(shí)現(xiàn)：
class Solution {public void duplicateZeros(int[] arr) {int len=arr.length,cur=0,dest=-1;while(cur<len){if(arr[cur]==0){dest+=2;}else{dest++;}if(dest==len-1)break;if(dest>len-1){arr[len-1]=0;cur--;dest=len-2;break;}cur++;}if(dest==cur)return;while(cur>=0){if(arr[cur]!=0){arr[dest--]=arr[cur--];}else{arr[dest--]=0;arr[dest--]=0;cur--;}}}
}
二、盛?最多的容器
題目描述：
題目分析：
v = (right - left) * min( height[right], height[left])
- 容器的寬度?定變?。
- 由于左邊界較?，決定了?的?度。如果改變左邊界，新的???度不確定，但是可能會(huì)超過(guò)原來(lái)左邊界的柱??度，因此容器的容積可能會(huì)增?。
- 如果改變右邊界，?論右邊界移動(dòng)到哪?，新的??的?度?定不會(huì)超過(guò)左邊界，也就是不會(huì)超過(guò)現(xiàn)在的???度，但是由于容器的寬度減?，因此容器的容積?定會(huì)變?的。
- 當(dāng)我們不斷重復(fù)上述過(guò)程，每次都可以舍去?量不必要的枚舉過(guò)程，直到 left 與 right 相遇。期間產(chǎn)?的所有的容積??的最?值，就是最終答案。
代碼實(shí)現(xiàn)：
class Solution {public int maxArea(int[] height) {int l=0,r=height.length-1,max=0,t;while(l<r){if(height[l]<height[r]){t=height[l]*(r-l);l++;}else{t=height[r]*(r-l);r--;}if(max<t)max=t;}return max;}
}
三、有效三?形的個(gè)數(shù)
題目鏈接
題目描述：
題目分析：
首先我們得知道，三條邊能構(gòu)成三角形的充要條件是：任意兩邊之和大于第三邊。
不過(guò)事實(shí)上，我們只要保證兩條短邊和大于最長(zhǎng)邊即可。
因此，我們可以先將數(shù)組從小到大進(jìn)行排序，接著用一個(gè)指針 j 固定一個(gè)「最?邊」，然后在?這條邊?的有序數(shù)組中找出?個(gè)?元組，使這個(gè)?元組之和?于這個(gè)最?邊。由于數(shù)組是有序的，我們可以利?「對(duì)撞指針」來(lái)優(yōu)化
設(shè)最?邊枚舉到 j?位置，區(qū)間 [left, right] 是 j?位置左邊的區(qū)間（也就是?它?的區(qū)間）：
- 如果 nums[left] + nums[right] > nums[i] ：
說(shuō)明 [left, right - 1] 區(qū)間上的所有元素均可以與 nums[right] 構(gòu)成? nums[j] ?的?元組
則滿?條件的有 right - left 種
此時(shí) right 位置的元素的所有情況相當(dāng)于全部考慮完畢， right-- ，進(jìn)?下?輪判斷
- ?如果 nums[left] + nums[right] <= nums[i] ：
說(shuō)明 left 位置的元素是不可能與 [left + 1, right] 位置上的元素構(gòu)成滿?條件的?元組
left 位置的元素可以舍去， left++ 進(jìn)?下輪循環(huán)
代碼實(shí)現(xiàn)：
class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int sum=0;for(int j=nums.length-1;j>=2;j--){int l=0,r=j-1;while(l<r){if(nums[l]+nums[r]>nums[j]){sum=sum+r-l;r--;}else{l++;}}}return sum;}
}
?四、三數(shù)之和
題目鏈接
題目描述：
題目分析：
這題其實(shí)與上一題十分相似，都是要找一個(gè)滿足一定條件的三元組，因此同樣，我們可以采用先排序，接著用一個(gè)指針 j 固定一個(gè)數(shù) a，接著在之后的區(qū)間內(nèi)，利用雙指針?biāo)惴?/span>找到兩數(shù)之和等于-a即可
需要注意的是，題目要求進(jìn)行「去重」操作：
- 找到?個(gè)結(jié)果之后， left 和 right 指針要「跳過(guò)重復(fù)」的元素；
- 當(dāng)使?完?次雙指針?biāo)惴ㄖ?#xff0c;固定的 a 也要「跳過(guò)重復(fù)」的元素
代碼實(shí)現(xiàn)：
class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<List<Integer>>();int n=nums.length;for(int j=0;j<n;){if(nums[j]>0)break;int l=j+1,r=n-1;int target=-nums[j];while(l<r){int sum=nums[l]+nums[r];if(sum==target){ans.add(new ArrayList<Integer>(Arrays.asList(nums[l],nums[r], nums[j])));if(nums[r]==nums[l])break;l++;r--;while(l<r&&nums[r+1]==nums[r])r--;while(l<r&&nums[l-1]==nums[l])l++;}else if(sum>target){r--;}else{l++; } }j++;while(j<n&&nums[j]==nums[j-1])j++;}return ans;}
}
五、四數(shù)之和
題目鏈接
題目描述：
題目描述：
這題的思想其實(shí)也與三數(shù)之和類似，我們只需要先排序，再用一個(gè)指針 i 固定一個(gè)數(shù) a，在這個(gè)數(shù) a 的后?區(qū)間上，利?「三數(shù)之和」找到三個(gè)數(shù)，使這三個(gè)數(shù)的和等于 target - a 即可
代碼實(shí)現(xiàn)：
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {int n=nums.length;long t,q;Arrays.sort(nums);List<List<Integer>> ans=new ArrayList<List<Integer>>();for(int i=0;i<n;){t=target;t-=nums[i];//if(t<0)return ans;for(int j=i+1;j<n;){q=t;q-=nums[j];int l=j+1,r=n-1;while(l<r){int sum=nums[l]+nums[r];if(sum==q){List<Integer> list=new ArrayList<Integer>();list.add(nums[i]);list.add(nums[j]);list.add(nums[l]);list.add(nums[r]);ans.add(list);l++;r--;while(l<r&&nums[l]==nums[l-1])l++;while(l<r&&nums[r]==nums[r+1])r--;}else if(sum>q)r--;else l++;}j++;while(j<n&&nums[j]==nums[j-1])j++;}i++;while(i<n&&nums[i]==nums[i-1])i++;}return ans;}
}
?總結(jié)
雙指針技巧的關(guān)鍵點(diǎn)：
- 初始化：通常一個(gè)指針指向序列的開(kāi)始位置，另一個(gè)指針指向序列的結(jié)束位置或某個(gè)特定位置。
- 移動(dòng)規(guī)則：根據(jù)問(wèn)題的具體情況定義指針的移動(dòng)規(guī)則，如當(dāng)條件不滿足時(shí)向前或向后移動(dòng)。
- 更新?tīng)顟B(tài)：在每次移動(dòng)指針之后更新當(dāng)前的狀態(tài)，如累加、記錄最大值等。
- 退出條件：當(dāng)兩個(gè)指針相遇或某個(gè)指針超出界限時(shí)結(jié)束循環(huán)。
雙指針?biāo)惴ㄊ且环N簡(jiǎn)單而有效的算法技巧，通過(guò)維護(hù)兩個(gè)指針的狀態(tài)來(lái)簡(jiǎn)化問(wèn)題的復(fù)雜度。合理地運(yùn)用雙指針?lè)?#xff0c;可以幫助我們?cè)谔幚頂?shù)組和字符串問(wèn)題時(shí)更加高效地達(dá)成目標(biāo)。
那么本篇文章就到此為止了，如果覺(jué)得這篇文章對(duì)你有幫助的話，可以點(diǎn)一下關(guān)注和點(diǎn)贊來(lái)支持作者哦。如果有什么講的不對(duì)的地方歡迎在評(píng)論區(qū)指出，希望能夠和你們一起進(jìn)步?
