一、字符串解碼

點(diǎn)我直達(dá)~

思路：棧

這道題怎么看都好像是用棧來(lái)實(shí)現(xiàn)，因?yàn)橛凶笥依ㄌ?hào)。(可是第一時(shí)間我沒(méi)想到)

• 遍歷字符串，此時(shí)會(huì)有幾種情況：
• 1.如果是數(shù)字字符，給一個(gè)num變量，將該字符轉(zhuǎn)化成數(shù)字存儲(chǔ)起來(lái)。
• 2.如果是字母（題目說(shuō)只可能是小寫(xiě)），給一個(gè)字符串str，將該字母存儲(chǔ)到字符串里。
• 3.如果是" [ ",此時(shí)需要將剛才的數(shù)字和字母分別入棧，將數(shù)字num入到nums棧，str入到strs棧，然后清空num和str
• 4.如果是" ] “,先將nums棧的棧頂元素取出來(lái)給給top變量，然后循環(huán)top次將str追加到strs棧的棧頂元素后面，比如這時(shí)候strs棧棧頂元素是"aaa”，str是"ab"，top = 2，那么就將str追加，結(jié)果為：aaaabab。最后再將strs棧的棧頂元素賦值回給str。
• 注意：遇到" ] “后，下一個(gè)字符不可能是” [ "，不符合題目要求，只可能是數(shù)字字符或字母字符，仍然會(huì)按照正常的流程繼續(xù)走下去。
• 最后返回str即可。

具體代碼如下：

class Solution {
public:
    string decodeString(string s) 
    {
        int num = 0; //存儲(chǔ)數(shù)字
        string str = ""; //存儲(chǔ)字符串
        stack<int> nums; //遇到'['：數(shù)字入數(shù)字棧
        stack<string> strs;//字符串入字符串棧

        for(int i = 0;i<s.size();++i)
        {
            if(s[i] >='0' && s[i] <= '9')
            {
                //如果出現(xiàn)連續(xù)的數(shù)字，個(gè)位就要*10再加起來(lái)
                num = num * 10 + (s[i] - '0') ;
            }
            else if(s[i] >= 'a' && s[i] <='z')
            {
                str = str + s[i];
            }
            else if(s[i] == '[')
            {
                //入數(shù)字棧
                nums.push(num);
                num = 0;
                //入字符串棧
                strs.push(str);
                str = "";
            }
            //遇到']'了
            else
            {
                int top = nums.top();
                nums.pop();
                for(int j = 0;j<top;++j)
                {
                    //注意這里是將str追加到棧頂元素之后
                    strs.top() += str;
                }
                //將棧頂元素給回str
                //']'之后接下來(lái)的字符不可能是'['，這不符合題目要求
                //所以接下來(lái)的字符不管是數(shù)字還是字母，都可以正常進(jìn)行
                str = strs.top();
                strs.pop();
            }
        }
        return str;
    }
};

時(shí)間復(fù)雜度：O(N)，空間復(fù)雜度O(1)

二、數(shù)組中重復(fù)的數(shù)字

點(diǎn)我直達(dá)~

思路1：計(jì)數(shù)法

具體過(guò)程如下：

• 1.開(kāi)一個(gè)n大小的順序表，初始化為0，作為0~n-1區(qū)間的每個(gè)數(shù)字出現(xiàn)的次數(shù)。
• 2.遍歷一遍數(shù)組，將出現(xiàn)的數(shù)字在計(jì)數(shù)順序表的位置++，比如：出現(xiàn)的數(shù)字是5，那么就在順序表的下標(biāo)5的位置+1
• 3.如果計(jì)數(shù)順序表中的任意元素出現(xiàn)次數(shù)大于1，則說(shuō)明對(duì)應(yīng)的元素重復(fù)出現(xiàn)，返回即可。

具體代碼如下：

class Solution {
public:
 
    int findRepeatNumber(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> count(n);
        for(int i =0;i<nums.size();++i)
        {
            count[nums[i]]++;
            if(count[nums[i]] > 1)
                return nums[i];
        }
        return -1;
    }
};

時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(n)

思路2：原地交換法

這個(gè)方法也可以理解為：崗位對(duì)接人才問(wèn)題。

具體如下：

• 1.這個(gè)原地交換法就相當(dāng)于分配工作，每個(gè)索引代表一個(gè)工作崗位，每個(gè)崗位必須專(zhuān)業(yè)對(duì)口，既0索引必須0元素才能上崗。而我們的目的就是找出溢出的人才，既0索引崗位有多個(gè)0元素競(jìng)爭(zhēng)。
• 2.我們先從0索引崗位開(kāi)始遍歷，首先我們看0索引是不是已經(jīng)專(zhuān)業(yè)對(duì)口了，如果已經(jīng)專(zhuān)業(yè)對(duì)口既nums[0]=0，那我們就跳過(guò)0崗位看1崗位。
• 3.如果0索引沒(méi)有專(zhuān)業(yè)對(duì)口，那么我們看現(xiàn)在0索引上的人才調(diào)整到他對(duì)應(yīng)的崗位上，比如num[0]=2，那我們就把2這個(gè)元素挪到他對(duì)應(yīng)的崗位上既num[2]，這個(gè)時(shí)候有兩種情況:
• • 1、num[2]崗位上已經(jīng)有專(zhuān)業(yè)對(duì)口的人才了，既num[2]=2，這就說(shuō)明剛剛那個(gè)在num[0]上的2是溢出的人才，我們直接將其返回即可。
• • 2、num[2]上的不是專(zhuān)業(yè)對(duì)口的人才，那我們將num[0]上的元素和num[2]上的元素交換，這樣num[2]就找到專(zhuān)業(yè)對(duì)口的人才了。
• 4.之后重復(fù)這個(gè)過(guò)程直到幫num[0]找到專(zhuān)業(yè)對(duì)口的人才，然后以此類(lèi)推幫num[1]找人才、幫num[2]找人才，直到找到溢出的人才。

圖解過(guò)程如下：

具體代碼如下：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) 
    {
        int i = 0;
        while(i < nums.size())
        {
            //崗位和人才對(duì)口了，繼續(xù)往下找，直到找到溢出的人才
            if(i == nums[i])
            {
                ++i;
                continue;
            }

            //情況1.該人才是溢出人才
            if(nums[i] == nums[nums[i]])
                return nums[i];

            //情況2.不是溢出人才，那就把該人才調(diào)整到對(duì)應(yīng)崗位
            else
                swap(nums[i],nums[nums[i]]);

        }
        
        return -1;
    }
};

時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

總結(jié)

通過(guò)今天的兩道題：

• 1.我發(fā)現(xiàn)只要有括號(hào)的匹配，或者有涉及到括號(hào)的，都可以考慮使用棧來(lái)解決。

• 2.對(duì)于找重復(fù)的數(shù)字/字符串/字符等，均可使用計(jì)數(shù)法，空間復(fù)雜度O（N）來(lái)統(tǒng)計(jì)出現(xiàn)次數(shù)。
  或者使用“崗位對(duì)接人才”的原地交換法解決此類(lèi)問(wèn)題。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-476606.html

到了這里，關(guān)于【每日撓頭算法題(3)】字符串解碼|數(shù)組中重復(fù)的數(shù)字的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！