色欲无码蜜桃,久操福利免费

快捷導(dǎo)航

詳解C語(yǔ)言中雙指針?biāo)惴ǖ氖褂?/h1>

更新時(shí)間：2022年08月18日 11:48:04 作者：微涼秋意

雙指針，指的是在遍歷對(duì)象的過(guò)程中，不是普通的使用單個(gè)指針進(jìn)行訪問(wèn)，而是使用兩個(gè)相同方向（快慢指針）或者相反方向（對(duì)撞指針）的指針進(jìn)行掃描，從而達(dá)到相應(yīng)的目的。本文將通過(guò)示例帶大家深入了解雙指針?biāo)惴ǖ氖褂?/div>

前言

雙指針?biāo)惴?/p>

算法思想

雙指針，指的是在遍歷對(duì)象的過(guò)程中，不是普通的使用單個(gè)指針進(jìn)行訪問(wèn)，而是使用兩個(gè)相同方向（快慢指針）或者相反方向（對(duì)撞指針）的指針進(jìn)行掃描，從而達(dá)到相應(yīng)的目的。

換言之，雙指針?lè)ǔ浞质褂昧藬?shù)組有序這一特征，從而在某些情況下能夠簡(jiǎn)化一些運(yùn)算。

今天帶大家來(lái)學(xué)習(xí)算法中雙指針的應(yīng)用場(chǎng)景。

一、最長(zhǎng)不含重復(fù)字符的子字符串

1.題目要求

2.個(gè)人題解

2.1 解題思路

利用雙指針，定義一個(gè)指針i和一個(gè)指針j

讓i開始走，固定住j，然后我們利用一個(gè)輔助數(shù)組來(lái)記錄下每個(gè)字符出現(xiàn)的次數(shù)。

比如對(duì)于字符串“abcabcdd”，當(dāng)i走到第二個(gè)a的時(shí)候，a出現(xiàn)了兩次，這時(shí)候讓j開始向前走，走到b。

這時(shí)候i和j之間的字符串是bca。沒(méi)有重復(fù)的，i可以繼續(xù)走，j繼續(xù)固定。

i走到b的時(shí)候b出現(xiàn)兩次。這時(shí)候要移動(dòng)j直至沒(méi)有字符出現(xiàn)次數(shù)超過(guò)兩次。如此反復(fù)直到i走到字符串結(jié)尾。

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

class Solution {
public:
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        int S[128];
        memset(S,0x00, sizeof(S));
        int ans = 0;
        for(int i=0,j=0;i<len;++i)
        {
            S[s.at(i)]++;
            while(S[s.at(i)]>1)
            {
                S[s.at(j)]--;
                j++;
            }
            ans=max(ans,i-j+1); //更新區(qū)間最大長(zhǎng)度
        }
        return ans;
    }
};

2.3 代碼解析

首先定義數(shù)組S[128]，利用memset函數(shù)來(lái)初始化該數(shù)組。

memset：作用是在一段內(nèi)存塊中填充某個(gè)給定的值，它是對(duì)較大的結(jié)構(gòu)體或數(shù)組進(jìn)行清零操作的一種最快方法。

for循環(huán)里聲明i，j 為0，先讓字符串的第一個(gè)字符對(duì)應(yīng)的整數(shù)作為數(shù)組S的下標(biāo)，該位置元素值加一；

如果沒(méi)有重復(fù)字符，ans遞增；如果有重復(fù)字符今后進(jìn)入while循環(huán)，隨著j的遞增，之前數(shù)組里為一的元素值都會(huì)減一，為2的元素值也會(huì)減一并變?yōu)橐唬?/p>

接著j固定，i繼續(xù)增長(zhǎng)，再有重復(fù)字符就會(huì)重復(fù)上述操作，最終通過(guò)max函數(shù)得到最大的無(wú)重復(fù)子字符串長(zhǎng)度。

二、和為S的兩個(gè)數(shù)字

1.題目要求

2.個(gè)人題解

2.1 解題思路

根據(jù)題目可知該數(shù)組是升序排列，那我們可以用兩個(gè)指針：一個(gè)在左邊界，一個(gè)在右邊界。

如果數(shù)組下標(biāo)對(duì)應(yīng)的值相加比num小，那么就讓左邊指針遞增，反之則右邊指針遞減。

如果左右指針相等，說(shuō)明沒(méi)有滿足條件的數(shù)對(duì)，返回空數(shù)組。

如果存在該數(shù)對(duì)，利用push_back方法插入數(shù)組并返回即可

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

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int left,right;
        int i,j,k;
        vector<int> res;
        left=0;
        right=array.size()-1;
        //如果數(shù)組為空,返回空數(shù)組
        if(array.empty()){
            return res;
        }
        while(array[left]+array[right]!=sum && left!=right){
            if(array[left]+array[right]<sum){
                left+=1;
            }else if(array[left]+array[right]>sum){
                right-=1;
            }
        }
        //如果不存在該數(shù)對(duì),返回空數(shù)組
        if(left==right){
            return res;
        }
        //如果存在
        res.push_back(array[left]);
        res.push_back(array[right]);
        return res;
    }
};

本題思路確定后代碼比較好理解，就沒(méi)有分析部分了。

這兩道題都是雙指針的解法：第一題相當(dāng)于是相鄰指針，第二題則是雙端指針，各有特色。

到此這篇關(guān)于詳解C語(yǔ)言中雙指針?biāo)惴ǖ氖褂玫奈恼戮徒榻B到這了,更多相關(guān)C語(yǔ)言雙指針?biāo)惴▋?nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: