目錄

前言?

一：普通雙指針

1.經(jīng)典題目一? 283移動(dòng)0問題

分析

代碼實(shí)現(xiàn)

2.經(jīng)典題目二 1089復(fù)寫0?

分析

代碼實(shí)現(xiàn)

二：解決成環(huán)類問題-快慢指針?

經(jīng)典例題一 202快樂數(shù)

分析?

代碼實(shí)現(xiàn)?

?三：左右相遇指針

經(jīng)典例題一 11 盛最多水的容器

分析?

代碼實(shí)現(xiàn)?

?

接下來(lái)的日子會(huì)順順利利，萬(wàn)事勝意，生活明朗-----------林辭憂

前言?

在解決關(guān)于數(shù)組的問題時(shí)，常常用到雙指針的解決方法來(lái)優(yōu)化算法，幫助解決問題，常見的雙指針分為普通雙指針，快慢指針，左右相遇指針等

一：普通雙指針

普通雙指針就是解決普通問題，一般是在原數(shù)組上改動(dòng)數(shù)據(jù)時(shí)，有從前向后，從后向前，都從前向后，都從后向前，對(duì)數(shù)組分塊來(lái)解決問題等

1.經(jīng)典題目一? 283移動(dòng)0問題

分析

?

代碼實(shí)現(xiàn)

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //雙指針方法
        int cur=0,dest=-1;
        int n=nums.size();
        while(cur<n)
        {
            if(nums[cur]==0)
            {
                ++cur;
            }
            else
            {
                swap(nums[++dest],nums[cur++]);
            }
        }
    }
};

2.經(jīng)典題目二 1089復(fù)寫0?

分析

?

代碼實(shí)現(xiàn)

?

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur=0,dest=-1;
        int n=arr.size();
        //求最后一個(gè)要復(fù)寫的數(shù)據(jù)
        while(cur<n)
        {
            if(arr[cur])//不為0走一步
            {
                ++dest;
            }
            else//為0走兩步
            {
                dest+=2;
            }
            if(dest>=n-1) break;//邊界問題防止越界訪問
            ++cur;
        }

        //處理邊界問題
        if(dest==n)
        {
            arr[n-1]=0;
            dest-=2;
            cur-=1;
        }

        //再?gòu)暮笸皬?fù)寫數(shù)據(jù)
        while(cur>=0)
        {
            if(arr[cur])
            {
                arr[dest--]=arr[cur--];
            }
            else
            {
                arr[dest--]=0;
                arr[dest--]=0;
                --cur;
            }
        }
    }
};

二：解決成環(huán)類問題-快慢指針?

在解決一些關(guān)于數(shù)組或者鏈表成環(huán)類問題時(shí)常常用到的是快慢指針，就是slow指針走一步，fast指針一次走兩步，常常用相遇來(lái)解決問題

經(jīng)典例題一 202快樂數(shù)

分析?

代碼實(shí)現(xiàn)?

class Solution {
public:
    int bitSum(int n)//計(jì)算n的平方和
    {
        int sum=0;
        while(n)
        {
            int tmp=n%10;
            sum+=tmp*tmp;
            n/=10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow=n,fast=bitSum(n);//slow為第一個(gè)位置，fast為第二個(gè)位置
        while(slow!=fast)//走到直至相遇
        {
            slow=bitSum(slow);
            fast=bitSum(bitSum(fast));
        }
        if(slow==1)//是1的話則是快樂數(shù)
        {
            return true;
        }
        return false;
    }
};

?三：左右相遇指針

說(shuō)明一下，左右相遇指針是自己理解取的名字，意思就是這類題定義的雙指針得從兩端向中間走，直至相遇

經(jīng)典例題一 11 盛最多水的容器

分析?

對(duì)于這道題大多人首先想到的是暴力求解，求出每?jī)蓚€(gè)數(shù)據(jù)之間的容量，在求出最大的一個(gè)

但這樣的話對(duì)于這道題，這樣做的話會(huì)超出時(shí)間限制的，因此得采取其他方法

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-850214.html

代碼實(shí)現(xiàn)?

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left=0,right=height.size()-1;//左右雙指針
        int ret=0;
        while(left<right)
        {
            int v=min(height[left],height[right])*(right-left);//算出數(shù)據(jù)
            ret=max(ret,v);//求出最大的一個(gè)數(shù)據(jù)，存放在ret中

            //移動(dòng)指針
            if(height[left]<height[right])
            {
                ++left;
            }
            else
            {
                --right;
            }
        }
        return ret;
    }
};

?

到了這里，關(guān)于算法修煉之路之雙指針含多道leetcode 經(jīng)典題目的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！