Skip to content

leetcode_OJ WC98 99 解題心得

  • 暑假最後因實習進度交接,有點累,打了weekly contest結果懶得更新,這次一次更新吧
  • Contest time WC98: Aug 19, 2018 (題解完成)
  • Contest time WC99: Aug 26, 2018 (題解完成)

WC98

PA. 888. Fair Candy Swap 水題

  • 題意:兩人各持有數堆糖果,每一堆有n個糖果,問各自交換哪一堆可以讓他們兩個的糖果數量一樣
  • 思路:直接做,兩個人一樣取平均,暴力找即可。
  • 分析:Time complexity: O(N^2), Space complexity O(N)
class Solution
{
public:
    vector<int> fairCandySwap(vector<int>& A, vector<int>& B)
    {
        int suma, sumb, flg;
        suma = sumb = 0;
        flg = 0;
        vector<int> res;
        for(int i = 0; i < A.size(); i++)
        {
            suma += A[i];
        }
        for(int i = 0; i < B.size(); i++)
        {
            sumb += B[i];
        }
        int fair = (suma + sumb) / 2;
        for(int i = 0; i < A.size(); i++)
        {
            for(int j = 0; j < B.size(); j++)
            {
                if(suma - A[i] + B[j] == sumb - B[j] + A[i])
                {
                    res.push_back(A[i]);
                    res.push_back(B[j]);
                    flg = 1;
                    break;    
                }
            }
            if(flg)
            {
                break;
            }
        }
        return res;
    }
    bool check(vector<int>& A, vector<int>& B)
    {
        int suma, sumb;
        suma = sumb = 0;
        for(int i = 0; i < A.size(); i++)
        {
            suma += A[i];
        }
        for(int i = 0; i < B.size(); i++)
        {
            sumb += B[i];
        }
        return (suma == sumb) && (suma) && (sumb);//should be more than zero
    }
};

PB. 890. Find and Replace Pattern string + map

  • 題意:找出趨勢一樣的單字,在此趨勢一樣是指英文字出先的『頻率、方式』一致,例如 aabb = ccbb = jjkk , apple = knnrx 等
  • WA思路:趨勢一樣代表說,我下一個是不一樣的字母,則你也是;我如果是一樣的則你也要一樣,這樣直接做即可(但是接下來會遇到一個問題,稍後下方『缺失分析』會提及)

    class Solution
    {
    public:
        vector<string> findAndReplacePattern(vector<string>& words, string pattern)
        {
            vector<string> res;
            for(auto it: words)
            {
                if(check(it, pattern))
                {
                    res.push_back(it);
                }
            }
            return res;
        }
        bool check(string to_chk, string pat)
        {
            if(to_chk.size() != pat.size())
            {
                return false;
            }
            for(int i = 0; i < to_chk.size() - 1; i++)
            {
                if(to_chk[i] == to_chk[i + 1]) //趨勢要一致
                {
                    if(pat[i] != pat[i + 1])
                    {
                        return false;
                    }
                }
                else
                {
                    if(pat[i] == pat[i + 1]) //趨勢要一致
                    {
                        return false;
                    }
                }
            }
            return true;
        }
    };
    

  • 缺失分析:WA的原因在於,這樣會把aba = xyx = abc 但實際上這題要求連每一個字母出現頻率也要一樣,因此最後a b c各自只有一個並不屬於同一類

  • 改進思路:多一個map來統計,並且對照組的map內容要和pattern一樣,在英文字母一樣的時候不用管,不一樣時要看各自map內容物是否相等,否則返回false
class Solution
{
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern)
    {
        vector<string> res;
        for(auto it: words)
        {
            if(check(it, pattern))
            {
                res.push_back(it);
            }
        }
        return res;
    }
    bool check(string to_chk, string pat)
    {
        if(to_chk.size() != pat.size())
        {
            return false;
        }
        /*check the mapping correspondence*/
        map<char, int> chkmap;
        map<char, int> patmap;
        for(auto it : to_chk)
        {
            chkmap[it]++;
        }
        for(auto it : pat)
        {
            patmap[it]++;
        }
        /*check the changing trend*/
        for(int i = 0; i < to_chk.size() - 1; i++)
        {
            if(to_chk[i] == to_chk[i + 1])
            {
                if(pat[i] != pat[i + 1])
                {
                    return false;
                }
            }
            else
            {
                if(pat[i] == pat[i + 1])
                {
                    return false;
                }
                else if(patmap[pat[i]] != chkmap[to_chk[i]] || patmap[pat[i + 1]] != chkmap[to_chk[i + 1]]) /*such as abc and aba should not be the same, if no this part, will get wrong answer*/
                {
                    return false;
                }
            }
        }


        return true;
    }
};
  • 分析(正解整體):Time complexity: O(N * K), where N is # of words, and K is the length of word, Space complexity O(N * K), each time for each pattern and word, we use a map to assist.

PC. 889. Construct Binary Tree from Preorder and Postorder Traversal 重建樹

  • 題意:由先序和後序建立一顆二元樹
  • 思路: https://imgur.com/a/s9kTWbG (Picture source credit to: https://www.youtube.com/watch?v=53aOi0Drp9I )
    • 首先preorder = {root left right}, post order = {left right root},利用上方的圖片可以看到,舉例來說 pre = [1,2,4,5,3,6,7]. post = [4,5,2,6,7,3,1],pre = 1 245 367, post = 452 673 1,pre[1]必為左子樹根,正好對應到post[2] (但不盡然每次都是post[2]),因此可以用code中找出ileft subtree的root位置,最後便能用以下四個(左右子數各自對應之pre post traversal)
      while(pre[1] != post[left_subtree_root_pos]) //find the equal for the right subtree
      {
          left_subtree_root_pos++;
      }
      
      • post traversal of left subtree = post[0:left_subtree_root_pos] (雙端皆為封閉區間 []而非())
      • post traversal of right subtree = post[left_subtree_root_pos + 1:-2] (雙端皆為封閉區間)
      • pre traversal of left subtree = pre[1:left_subtree_root_pos + 1] (雙端皆為封閉區間)
      • pre traversal of right subtree = pre[left_subtree_root_pos + 2:-1] (雙端皆為封閉區間)
      • 接著利用root->left = recursively_construct(left_subtree_pre_traverse, left_subtree_post_traverse)
    • 再利用root->right = recursively_construct(right_subtree_pre_traverse, right_subtree_post_traverse)
  • 分析:Time complexity O(N^2), Space complexity O(N^2) where N is the # of nodes, since each time for every node(N), we have to go through the array of traversed node again(N), which in total is O(N^2)
  • 備註:可以用程式碼附的print_subtree_dbg 來看看子樹到底包了哪些東西喔,比較好瞭解,以及一些stdio
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post)
    {
        return construct(pre, post);
    }
    TreeNode* construct(vector<int>& pre, vector<int>& post)
    {
        if(pre.size() == 1 && post.size() == 1) // the base case with leaf
        {
            //printf("base case presize %d postsize %d\n", pre.size(), post.size());
            TreeNode* newnode = new TreeNode(pre[0]);    
            return newnode;
        }
        else if(pre.size() == 0 && post.size() == 0) //the null
        {
            return NULL;
        }

       vector<int> left_subtree_pre;
        vector<int> left_subtree_pos;
        vector<int> right_subtree_pre;
        vector<int> right_subtree_pos;

        int left_subtree_root_pos = 0;

        while(pre[1] != post[left_subtree_root_pos]) //find the equal for the right subtree
        {
            left_subtree_root_pos++;
        }
        // printf("\nleft pos %d with root %d\n", left_subtree_root_pos, pre[0]);

        for(int i = 0; i <= left_subtree_root_pos; i++)//construct the post traverse of left subtree
        {
            left_subtree_pos.push_back(post[i]);
        }
        for(int i = left_subtree_root_pos + 1; i < post.size() - 1; i++)//construct the post traverse of right subtree
        {
            right_subtree_pos.push_back(post[i]);
        }

        for(int i = 1; i <= left_subtree_root_pos + 1; i++)//construct the pre traverse of left subtree
        {
            left_subtree_pre.push_back(pre[i]);
        }
        for(int i = left_subtree_root_pos + 2; i <= post.size() - 1; i++)//construct the pre traverse of right subtree
        {
            right_subtree_pre.push_back(pre[i]);
        }

//         print_subtree_dbg("left pos",left_subtree_pos);
//         print_subtree_dbg("right pos",right_subtree_pos);

//         print_subtree_dbg("left pre",left_subtree_pre);
//         print_subtree_dbg("right pre",right_subtree_pre);

        newnode->left = construct(left_subtree_pre, left_subtree_pos);
        TreeNode* newnode = new TreeNode(pre[0]); //or post[-1]
        newnode->right = construct(right_subtree_pre, right_subtree_pos);
        return newnode;//after construct, return it
    }
    void print_subtree_dbg(string cond, vector<int>& vec)
    {
        cout << cond << " : " ;
        for(int i = 0; i < vec.size(); i++)
        {
            printf("%d ", vec[i]);
        }
        printf("\n");
    }
};

PD. 891. Sum of Subsequence Widths 數學題,較難

  • 題意: 找出所有子序列的寬度,寬度定義為,子序列最大元素扣除子序列最小元素。
  • 思路: 暴力解顯然行不通,但可以看出每一個元素都會被當作該集合的最大與最小值,因此可以得到如圖中的概念 ,舉例來說(因為linux上中英文同時打有點麻煩,故以下舉例以英文表示)
    • From the given example as [1, 2, 4] (Note that the correct answer should be 9), we have the following subseq with non zero width(i.e. element more than 1):[1, 2] [1, 4] [2, 4] [1, 2, 4]
    • 1 as min: [1, 2], [1, 4], [1, 2, 4] / as max: none / total = (a[1] - a[0]) + (a[2] - a[0]) + (a[2] - a[0])
    • 2 as min: [2, 4] / as max: [1, 2] (a[1] - a[0]) / total = (a[2] - a[1])
    • 4 as min: none / as max: [1, 4], [2, 4]. [1, 2, 4] (all duplicated)
    • after clanup we can found that this is equal to (a[2] + a[2] + a[2]) (max 4 for 3 times) + (a[1] - a[1]) (2 max for 1 times and so do min) + (-a[0] - a[0] - a[0]) (1 min for 3 times)
  • 分析: Time complexity: O(N log N) due to sorting, Space complexity O(1))

  • 以下程式碼TLE,原因在於每一次的相加都要呼叫pow_mod,計算量高,相當費時

    #define ll  long long
    const ll MOD = 1e9 + 7;
    class Solution {
    public:
        int sumSubseqWidths(vector<int>& A) 
        {
            ll res = 0, sz = A.size();
            sort(A.begin(), A.end());
            for(int i = 0; i < sz; i++)
            {
                ll delta = A[i] * pow_mod(2, i) - A[i] * pow_mod(2, sz - i - 1);
                res += delta;
                res %= MOD;
            }
            return res;
        }
        ll pow_mod(ll base, int pow)
        {
            ll res = 1;
            for(int i = 0; i < pow; i++)
            {
                res <<= 1;
                res %= MOD;
            }
            return res - 1;//exclude the null set
    

  • 由於陣列元素最多到20000,故利用
    for(int i = 1; i < sz; i++)
    {
        dp[i] = (dp[i - 1] % MOD * 2) % MOD;
    } 
    
    先將結果cache起來再計算
#define ll  long long
const ll MOD = 1e9 + 7;
class Solution {
public:
    int sumSubseqWidths(vector<int>& A) 
    {
        ll res = 0, sz = A.size();
        sort(A.begin(), A.end());
        ll dp[20001] = {0};
        dp[0] = 1;
        for(int i = 1; i < sz; i++)
        {
            dp[i] = (dp[i - 1] % MOD * 2) % MOD;
        }
        for(int i = 0; i < sz; i++)
        {
            res += A[i] * (dp[i] - dp[sz - i - 1]);
            res %= MOD;
        }
        return res;
    }
};

WC99

PA. 892. Surface Area of 3D Shapes 求表面積,水題

  • 題意: 有 2d grid(2dvector 構成), size is grid.size() * grid.size(),在grid[i][j]有高度為v的立方體堆積(可以想像一下以前的小白方塊),求最後整體的表面積,注意,[[1,1]] [[1,2]] 的答案都是6,因為在grid以外的方塊不採計,被這個提議沒說清楚擺了一道...
  • 思路: 直接算,扣掉重合部份即可(也就是每次看i - 1, j - 1之於自己的重合部份)
  • 分析: Time complexity: O(N^2), Space complexity O(1)
class Solution {
public:
    int surfaceArea(vector<vector<int>> grid) 
    {
        int res = 0, border = grid.size();
        for(int i = 0; i < grid.size(); i++)
        {
            for(int j = 0; j < grid[i].size(); j++)
            {
                if(j > border - 1 || i > border - 1)
                {
                    continue;
                }
                else
                {
                    if(grid[i][j])
                    {
                        res += grid[i][j] * 4 + 2;
                    }
                    if(j > 0) //adjacent sticked area
                    {
                        res -= 2 * min(grid[i][j], grid[i][j - 1]);
                    }
                    if(i > 0) //adjacent sticked area
                    {
                        res -= 2 * min(grid[i][j], grid[i - 1][j]);
                    }
                }
            }
        }
        return res;
    }
};

PB. 893. Groups of Special-Equivalent Strings 簡單字串題

  • 題意: 問 str1, str2 各自中,奇數或偶數位置字元對調,可否成為另一個 ex: abc = cba, abcd = cdab = adcb = cbad
  • 思路: 用map先將一方的odd even以char->count代表基數或偶數中char各自對應多少個,在跑第二個word,跑得過程若出現0代表先前沒出現過(例如 abc, dbc 跑第二個d映射過去會是0(當初abc沒有d因此不屬於同一類型)),直接返回false,全部跑畢才返回true())
  • 分析: Time complexity = O(N^2), Space complexity = O(N * K) where N is the size of input vector and K is the length of word since for each word we construct the map
  • 反思: 覺得有點太冗長,歡迎提供更好作法
    class Solution 
    {
    public:
        int len, sz, cnt;
        int numSpecialEquivGroups(vector<string>& A) 
        {
            vector<bool>visit(A.size(), 0);
            vector<vector<string>> res;
            vector<string>tmp;
            len = A[0].size();
            sz = A.size();
            cnt = 0;
            for(int i = 0; i < sz - 1; i++)
            {
                if(visit[i])
                {
                    continue;
                }
                else
                {
                    tmp.clear();
                    tmp.push_back(A[i]);//push itself
                    visit[i] = true;
                    for(int j = i + 1; j < sz; j ++)
                    {
                        if(eqv(A[i], A[j]))
                        {
                            tmp.push_back(A[j]);
                            visit[j] = true;
                        }
                    }
                    cnt++;
                    res.push_back(tmp);
                }
            }
            if(!visit[sz - 1])
            {
                cnt++;
            }
            return cnt;     
        }
        bool eqv(string s1, string s2)
        {
            map<char, int> odd;
            map<char, int> even;
            for(int i = 0; i < len; i++)
            {
                if(i & 1)
                {
                    odd[s1[i]]++;
                }
                else
                {
                    even[s1[i]]++;
                }
            }
    
            for(int i = 0; i < len; i++)
            {
                if(i & 1)
                {
                    if(odd[s2[i]] == 0)
                    {
                        return false;
                    }
                }
                else
                {
                    if(even[s2[i]] == 0)
                    {
                        return false;
                    }
                }
            }
            //reverse
            odd.clear();
            even.clear();
            for(int i = 0; i < len; i++)
            {
                if(i & 1)
                {
                    odd[s2[i]]++;
                }
                else
                {
                    even[s2[i]]++;
                }
            }
    
            for(int i = 0; i < len; i++)
            {
                if(i & 1)
                {
                    if(odd[s1[i]] == 0)
                    {
                        return false;
                    }
                }
                else
                {
                    if(even[s1[i]] == 0)
                    {
                        return false;
                    }
                }
            }
            return true;
        }
    };
    

PC. 894. All Possible Full Binary Trees 所有可能的二元樹

  • 題意: 就是所有的二元樹可能,建出後把root放到vector返回
  • 思路: 遞迴求解,因為完整二元樹必定有奇數個節點,因此若進入的N不是奇數直接返回空vector,接著逐步建立,切割為i個節點的left subtree和n - i - 1(包含根部)的right subtree遞迴下去解,再接起來如下程式碼
    for(int left = 1; left < N; left += 2 /*(since no even number)*/) //left subtree node count
        {
            vector<TreeNode*> left_subtree = allPossibleFBT(left);
            vector<TreeNode*> right_subtree = allPossibleFBT(N - left - 1);
    
    左右都會是FBT,因此 += 2的迴圈能避開偶數情形,最後奇數+奇數+1正好也是奇數,沒有問題
  • 分析: Time Conplexity O(2^N), Space complexity O(2^N) (卡塔蘭數)
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution 
{
public:
    vector<TreeNode*> allPossibleFBT(int N) 
    {
        printf("N =  %d \n", N);
        TreeNode* root = new TreeNode(0);
        root->left = root->right = NULL;
        vector<TreeNode*> res;
        if(!(N & 1))
        {
            return {};
        }
        else if(N == 1)
        {
            res.push_back(root);
            return res;
        }
        for(int left = 1; left < N; left += 2 /*(since no even number)*/) //left subtree node count
        {
            vector<TreeNode*> left_subtree = allPossibleFBT(left);
            vector<TreeNode*> right_subtree = allPossibleFBT(N - left - 1); //minus left subtree and the root
            for(auto it : left_subtree)
            {
                for(auto it2 : right_subtree) //all conbinations of left X right subtree (cartesian product)
                {
                    TreeNode* new_node = new TreeNode(0); //connect two subtree with the root
                    new_node->left = it;
                    new_node->right = it2;
                    res.push_back(new_node);
                }
            }
        }

        return res;
    }
};

PD. 895. Maximum Frequency Stack 最大頻率棧,雙map應用

  • 題意: 設計一個棧,使得彈出時能返回最大頻率的元素,若有複數個元素頻率相等,則返回最接近棧頂的
  • 思路: 用一個map存放數字與自己對應的頻率 ,再用map> 存放頻率與各頻率出現過得數字,例如push 8次 1 則頻率1 ~ 8 的棧(stack)頂端均會是1,以此類推。 再者,由於後進先出,剛好可以在同一頻率的數字群裡面,選擇最晚進入的數字彈出,如圖
  • 分析: Time complexity O(1), since using unordered_map for inserting data, which is actually the hash, takes O(N) time, and we use stack.top(), pop() to implement "frequency pop" which is also O(1). Space complexity O(N) if N > 10001.
  • 另見: 精簡前的code,多使用了一個 map stack來存放元素對應的位置(實際上直接存元素即可,另外開一個stack紀錄最大值變化略顯多此一舉)
#define MAXN 10001
class FreqStack
{
  public:
    unordered_map<int, int>num_freq; //hash of num to its occurances

    // stack<int> freq_stk[MAXN]; --> this cause MLE since static memory size is too big(use the upper limit from problem)

    unordered_map<int, stack<int>> freq_stk; //data structure of freq stack, record the occurance of number to certain freq, ex push 2 push 3 push 2 push 4, we have freq[1] = [3, 4](top), freq[2] = [2]
    int maxfreq;
    FreqStack()
    {
        maxfreq = 0;
    }

    void push(int x)
    {
        if (++num_freq[x] > maxfreq)
        {
            maxfreq = num_freq[x];
        }
        freq_stk[num_freq[x]].push(x);
        // printf("push %d, maxfreq now %d \n", x, maxfreq);
    }

    int pop()
    {
        if(freq_stk[maxfreq].size() == 0)
        {
            maxfreq--;//means all the numbers corresponding to that freq has been used out
        }
        int res = freq_stk[maxfreq].top();
        freq_stk[maxfreq].pop();
        // printf("pop val %d maxfreq %d\n", res, maxfreq);
        num_freq[res]--;
        return res;
    }
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack obj = new FreqStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 */`