久久91精品,亚洲精品日本在线观看,天津熟女淫乱视频

快捷導(dǎo)航

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

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

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

前言

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

算法思想

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

換言之，雙指針法充分使用了數(shù)組有序這一特征，從而在某些情況下能夠簡化一些運算。

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

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

1.題目要求

2.個人題解

2.1 解題思路

利用雙指針，定義一個指針i和一個指針j

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

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

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

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

2.2 代碼實現(xiàn)

class Solution {
public:
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jī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ū)間最大長度
        }
        return ans;
    }
};

2.3 代碼解析

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

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

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

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

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

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

1.題目要求

2.個人題解

2.1 解題思路

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

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

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

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

2.2 代碼實現(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ù)對,返回空數(shù)組
        if(left==right){
            return res;
        }
        //如果存在
        res.push_back(array[left]);
        res.push_back(array[right]);
        return res;
    }
};

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

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

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

您可能感興趣的文章: