

leetcode_OJ WC78 解題心得

Contest time: Apr 1, 2018

PA. 811. Subdomain Visit Count substr + map 活用水題

思路：簡單的水題，用substr裁切網域名稱後再hash到統計數字，以stoi函數來將string的數字轉成統計值

#define FORI(n) for(int i = 0; i < n; ++ i)
#define pb push_back
class Solution
{
public:
    vector<string> subdomainVisits(vector<string>& cpdomains)
    {
        map<string ,int> mymap;
        vector<vector <int> > dotpos;
        vector<int> visit; //each domain visit
        dotpos.resize(cpdomains.size());
        //cpdomains[i].size() - 1
        FORI(cpdomains.size())
        {
            for(int j = cpdomains[i].size() - 1; j >= 0; j--)
            {
                if(cpdomains[i][j] == '.')
                {
                    dotpos[i].pb(j);
                }
                else if(cpdomains[i][j] == ' ')
                {
                    dotpos[i].pb(j);
                    break;
                }
            }
        } //subdomain pos
        string tmp;
        FORI(cpdomains.size())
        {
            for(int j = 0; j < cpdomains[i].size(); j++)
            {
                if(cpdomains[i][j] == ' ')
                {
                    tmp = cpdomains[i].substr(0,j + 1);
                    int tmp2 = stoi(tmp);
                    visit.pb(tmp2);
                    break;
                }
            }
        } //times
        int poscnt = 0;
        FORI(cpdomains.size())
        {
            for(int j = 0; j < dotpos[i].size(); j++)
            {
                tmp = cpdomains[i].substr(dotpos[i][j] + 1, cpdomains[i].size() - dotpos[i][j] + 1);
                mymap[tmp] += visit[i];
            }
        }//accumulate

        vector<string> res;
        string timestr;
        for(map<string, int>::iterator it = mymap.begin(); it != mymap.end(); ++it)
        {
            timestr = to_string(it->second);
            res.pb(timestr + " " + it->first);
        }
        return res;
    }
};

PB.809. Expressive Words 字串雙指標推理觀察題

思路：不算難的題目，只是題目有點含糊不好懂，實際上意思為若以word的char來延伸成功（延伸成功的定義為：並列的char達到三個以上）"並且" 經由成功延伸的char 最後能達到目標字串，便是一個expressive word轉換例如：dddiiiinnssssssoooo 若為目標字串則 dinnsoo 可以因為 d+dd(延伸達到3) i+iii(延伸達到4) nn=nn s+sssss(延伸達到6) o+ooo(延伸達到4) 最後能組成目標字串 ddinnso也可(當初以為要dd視為一組來延神，而ddd / dd 只有1.5倍不行，然而題目只要求延伸，因此也能用單一字元湊成，是故以單一字元延伸是一種保險的作法)

又如 ddinsoo便不行，乃是於 n+n只延伸了兩次，無法達陣，因此勢必無法做成原本的目標字串而放棄。

用上述的想法便能寫出以下ac代碼

#define FORI(n) for(int i = 0; i < n; ++ i)
#define pb push_back
class Solution
{
public:
    int expressiveWords(string str, vector<string>& words)
    {
        int res = 0, can = 0, cnt = 0, total_len = 0, extend_len = 0, group_len;
        for(int i = 0;i < words.size();i++)
        {
            can = 1; //can --> 可延伸湊出結果
            int k = 0;
            total_len = words[i].size(); //第i個檢測word的長度
            for(int j = 0;j < words[i].size();)
            {
                extend_len = 0;
                group_len = 1;
                if(words[i][j] != str[k])
                {
                    can = 0; //若有不一樣的，勢必無法湊成，
                    break;
                }
                else
                {
                    while(j != words[i].size() - 1 && words[i][j + 1] == words[i][j]) //找出在word中，相連一樣的組成一群的長度
                    {
                        j++;
                        group_len++;
                    }
                    while(1) //able to extend
                    {
                        if(words[i][j] == str[k])//延伸
                        {
                            k++;
                            extend_len++;
                        }
                        else //發現不一樣後跳出
                        {
                            // can = 0; 這個can = 0不可以加，因為這是再延深後判斷跳出的條件，並不是發現mismatch
                            break;
                        }
                    }

                    //last character extend
                    while(k < str.size() && j == words[i].size()-1) //結尾特例，繼續延伸
                    {
                        if(words[i][j] == str[k]) //延伸
                        {
                            k++;
                            extend_len++;
                        }
                        else //發現不一樣後跳出
                        {
                            can = 0; //在此的can 便要加入 = 0 例如 target = abcd 但是 word = abc 而 此時j會卡在size - 1 之後k繼續走到d發現不一樣便是無法組成
                            break;
                        }
                    }

                    if(extend_len < group_len) //若延伸的長度小於原本長度也不行
                    {
                        can = 0;
                        break;
                    }

                    if(extend_len >= 3) //if extend, should >=3 (as a group per unit)
                    {
                        total_len += extend_len - group_len ; // aa延伸成 aaaa 延伸的長度為 2 而非 4 故要扣除本身群組長度
                    }
                    j++;
                }
            }
            if(total_len != str.size()) //若最後依然長度附等，也不符合要求，故can=0
            {
                can = 0;
            }
            if(can)
            {
                res++;
            }
        }
        return res;
    }
};

PC. 808. Soup Servings 有點難觀察出規律的動態規劃題(施工中)

思路：以每25毫升為單位切割，因此先把a b湯種的份量/25化繁為簡。

接著，以dp表示『已經消費的湯種份量』 a湯種為row b為col，由於每一格均代表消耗的份量，因此可以採用由底層推上來的方式，將每一格由之前的四項點推得，並且逐步構築到serve份。

而猶如題目所說，同時讓ab湯種耗盡時，需要乘上0.5的係數，而耗盡a湯種，因為是目標，故乘上1係數，然而耗盡b湯種並不是我們所要的，故乘上0係數

如下查看每一種消費（實際上是從0 0開始看『已經』消耗的湯種份量，慢慢疊到serve份，需注意要將serve + 1來作為dp方陣的因在於我們要消耗到0份而非1份，因此在dp表格必須 + 1作為初始化的大小邊界，最後迴圈也跑到等於serve才停下，而非小於serve

以下為迭代版本的程式碼

if(i - 4 <= 0 && j <=0)
{
    dir1 = 0.5;
}
else if(i - 4 <= 0)
{
    dir1 = 1;
}
else if(j <= 0)
{
    dir1 = 0;
}
else
{
    dir1 = dp[i - 4][j];
}

(在題目以下的每個回圈判斷式便可以看到，詳細分析請見程式碼註解)

class Solution
{
public:
    double soupServings(int all)
    {
        if(all > 6000) //monotonically increasing since A is always used more than B. (by empirical method)
            return 1.0;

        int serve = ceil(all / 25.0) ; //25 ml as a serving unit,
        //一定要用ceil因為即便是沒有滿25ml也要完整的處理完畢，故得用ceil來將未滿一單位的湯種處理，既有的cpp除法會捨去
        vector<vector <double> > dp(serve + 1, vector<double>(serve + 1, 0)); //each grid represent the rest amount(unit) of a and be which //comes to here
        //A row, B col
        double dir1, dir2, dir3, dir4;
        for(int i = 0; i <= serve; i++)
        {
            for(int j = 0; j <= serve; j++)
            {
                if(i - 4 <= 0 && j <=0)
                {
                    dir1 = 0.5;
                }
                else if(i - 4 <= 0)
                {
                    dir1 = 1;
                }
                else if(j <= 0)
                {
                    dir1 = 0;
                }
                else
                {
                    dir1 = dp[i - 4][j];
                }

                if(i - 3 <= 0 && j - 1 <= 0)
                {
                    dir2 = 0.5;
                }
                else if(i - 3 <= 0)
                {
                    dir2 = 1;
                }
                else if(j - 1 <= 0)
                {
                    dir2 = 0;
                }
                else
                {
                    dir2 = dp[i - 3][j - 1];
                }


                if(i - 2 <= 0 && j - 2 <= 0)
                {
                    dir3 = 0.5;
                }
                else if(i - 2 <= 0)
                {
                    dir3 = 1;
                }
                else if(j - 2 <= 0)
                {
                    dir3 = 0;
                }
                else
                {
                    dir3 = dp[i - 2][j - 2];
                }


                if(i - 1 <= 0 && j - 3 <= 0)
                {
                    dir4 = 0.5;
                }
                else if(i - 1 <= 0)
                {
                    dir4 = 1;
                }
                else if(j - 3 <= 0)
                {
                    dir4 = 0;
                }
                else
                {
                    dir4 = dp[i - 1][j - 3];
                }
                dp[i][j] = 0.25 * (dir1 + dir2 + dir3 + dir4);
            }
        }
        return dp[serve][serve];
    }
};