https://leetcode.com/contest/leetcode-weekly-contest-53/problems/stickers-to-spell-word/

Test pattern generator:
modify:
1. testStringLength
2. maxStickerLength
3. numStickers

 
#include <iostream>
#include <fstream>
#include <vector>

#include <stdlib.h>     /* srand, rand */
#include <time.h> 

using namespace std;

int main () {
    int testStringLength = 25;
    int maxStickerLength = 8;
    int numStickers      = 15;
    srand (time(NULL));

    string input(testStringLength, 0);
    std::vector<std::string> stickersVector(numStickers);

    for (int i = 0; i < testStringLength; i++)
    {
        input.at(i) = rand() % 26 + 'a';
    };

    cout << input << "\n";

    for (int i = 0; i < numStickers; i++)
    {
        int wordLength = (rand() % 10);
        wordLength = ((wordLength < 3) ? 3 : wordLength);
        for (int j = 0; j < wordLength; j++) {
            stickersVector[i].push_back(rand() % 26 + 'a');
        }
        cout << i << ": " <<stickersVector[i] << "\n";
    };
#if 1
    ofstream out;
    out.open("test.txt");

    out << input << "\n\n";
    for (int i = 0; i < numStickers; i++) {
        out << stickersVector[i] << "\n";
    }
#endif
    system("pause");
    return 1;
}


Test pattern:
hxnivvviyumjfesxrgyizwjyd

hdvfq
jox
eygal
jun
ohfpb
ddrnultw
qfgfatt
zsex
jum
uiqaepr
vumwdcuw
frzxaq
vagbaeyyq
qdgxnug
weq




[演算法]:

  1. Native algorithm (BFS with prune and search).
  2. Apply DP.
  3. Compare size firstly when checking ∈.  
  4. Remove from queue also.
Comparison of 1st & 2nd method




1st implementation

 
#include <iostream>
#include <limits.h>
#include <vector>
#include <string>
#include <iterator>
#include <map>
#include <queue>
#include <list>
#include <algorithm>
#include <stdio.h>
#include <set>

#include <stdlib.h>     /* srand, rand */
#include <time.h> 

#include <fstream>      // std::ifstream

using namespace std;


class Solution {
public:

    ~Solution() {
        printf("[comp %d, push %d, sub %d, maxQsize %d]\n", compCount, pushCount, subCount, maxQsize);
    }

    void dump(map<char, int> &input) {
        std::map<char, int>::iterator it;
        for (it = input.begin(); it != input.end(); it++) {
            printf("[%c %d], ", it->first, it->second);
        }
    }

    void dumpQ(list<pair<int/*score*/, map<char, int> > > &q) {
        list<pair<int/*score*/, map<char, int> > >::iterator it;
        for (it = q.begin(); it != q.end(); it++) {
            printf("%d, ", it->first);
            dump(it->second);
            printf("\n");
        }
        printf("\n");
    }

    void stringToMapWithFilter(string &input, map<char, int> &result, map<char, int> &filter) {
        if (input.length() < 1)
            return;

        char now = input.at(0);
        int length = 1;
        for (unsigned i = 1; i < input.length(); ++i)
        {
            if (input.at(i) != now) {
                if (filter.find(now) != filter.end()) {
                    result.insert(std::pair<char,int>(now, length));
                }
                now = input.at(i);
                length = 1;
            } else {
                length++;
            }
        }
        if (filter.find(now) != filter.end()) {
            result.insert(std::pair<char,int>(now, length));
        }
    }

    void stringToMap(string &input, map<char, int> &result) {
        if (input.length() < 1)
            return;

        char now = input.at(0);
        int length = 1;
        for (unsigned i = 1; i < input.length(); ++i)
        {
            if (input.at(i) != now) {
                result.insert(std::pair<char,int>(now, length));
                now = input.at(i);
                length = 1;
            } else {
                length++;
            }
        }
        result.insert(std::pair<char,int>(now, length));
    }

    bool vectorSub(std::map<char, int> &a, std::map<char, int> &b) { 
        subCount++;
        bool result = false;
        std::map<char, int>::iterator it;
        for (it = b.begin(); it != b.end(); it++) {
            if (a.find(it->first) != a.end()) {
                int aCount = a[it->first];
                if (aCount == 0) {
                    continue;
                }
                int bCount = it->second;
                result = true;                
                aCount = (aCount >= bCount) ? (aCount - bCount) : 0;
                a[it->first] = aCount;
            }
        }
        return result;
    }

    bool allZero(std::map<char, int> &a) {
        bool result = false;
        std::map<char, int>::iterator it;
        for (it = a.begin(); it != a.end(); it++) {
            if(it->second != 0) {
                break;
            }
        }
        if (it == a.end()) {
            result = true;
        }
        return result;
    }

    /*a >= b*/
    bool greaterThan(std::map<char, int> &a, std::map<char, int> &b) {
        compCount++;
        std::map<char, int>::iterator it;
        for (it = b.begin(); it != b.end(); it++) {
            if (a.find(it->first) == a.end()) {
                return false;
            } else if (a[it->first] < (it->second)) {
                return false;
            }
        }
        return true;
    }

    int minStickers(vector<string>& stickers, string target) {
        compCount = pushCount = subCount =0;

        vector<std::map<char, int> > stickersList(stickers.size());
        std::map<char, int> targetMap;

        std:sort(target.begin(), target.end());
        stringToMap(target, targetMap);
        std::set<char> targetSet;
        std::set<char> stickerSet;
        for (int i = 0; i < target.length(); i++) {
            targetSet.insert(target.at(i));
        }
        for (int i = 0; i < stickers.size(); i++) {
            for (int j = 0; j < stickers[i].size(); j++) {
                stickerSet.insert(stickers[i].at(j));
            }
            std::sort(stickers[i].begin(), stickers[i].end());
            stringToMapWithFilter(stickers[i], stickersList[i], targetMap);
        }

        std::set<char>::iterator setIt;
        //for (setIt = targetSet.begin(); setIt != targetSet.end(); setIt++) std::cout << *setIt << ' ';
        //cout << "targetSet \n";
        //for (setIt = stickerSet.begin(); setIt != stickerSet.end(); setIt++) std::cout << *setIt << ' ';
        //cout << "stickerSet \n";

        std::set<char> diff;
        std::set_difference(targetSet.begin(), targetSet.end(), stickerSet.begin(), stickerSet.end(), 
            std::inserter(diff, diff.begin()));

        //for (setIt = diff.begin(); setIt != diff.end(); setIt++) std::cout << *setIt << ' ';
        if (diff.size() != 0) {
            return -1;
        }

        list<pair<int/*score*/, map<char, int> > > q;
        q.push_front(make_pair(0, targetMap));
        pushCount++;
        int dbg = 0;
        bool done = false;
        maxQsize = 0;
        while (q.size() && !done) {
            pair<int/*score*/, map<char, int> > item = q.front();
            q.pop_front();
            if (q.size() > maxQsize) {
                maxQsize = q.size();
            }
            for (int i = 0; i < stickers.size(); i++) {
                map<char, int> tmp = item.second;
                int score = item.first + 1;
                bool check = vectorSub(tmp, stickersList[i]);
                if (check) {
                    if (allZero(tmp)) {
                        done = true;
                        printf("score %d\n", score);
                        return score;
                    }
                    list<pair<int/*score*/, map<char, int> > >::iterator it;
                    bool needInsert = true;
                    for (it = q.begin(); it != q.end(); it++) {
                        bool great = greaterThan(tmp, it->second);
                        if (great) {
                            needInsert = false;
                            break;
                        }
                    }
                    if (needInsert) {
                        q.push_back(make_pair(score, tmp));
                        pushCount++;
                    }
                }
            }
        }
        return -1;
    }

    int compCount;
    int pushCount;
    int subCount;
    int maxQsize;
};

int main()
{
    string input;
    ifstream ifs("test.txt", ios::in);
    ifs >> input;
    cout << input << "\n";
    {
        Solution solution;
        std::vector<std::string> v;
        string tmp;
        while (std::getline(ifs, tmp)) {
            v.push_back(tmp);
        }

        for (int i = 0; i < v.size(); i++) {
            cout << v[i] << "\n";
        }

        clock_t begin = clock();
        int ans = solution.minStickers(v, input);
        clock_t end = clock();
        double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
        printf("res %d, time = %f, \n", ans, time_spent);
    }
    system("pause");
    return 1;
}

2nd implementation

 
#include <iostream>
#include <limits.h>
#include <vector>
#include <string>
#include <iterator>
#include <map>
#include <queue>
#include <list>
#include <algorithm>
#include <stdio.h>
#include <set>

#include <stdlib.h>     /* srand, rand */
#include <time.h> 

#include <fstream>      // std::ifstream

using namespace std;

class Solution {
public:

    ~Solution() {
        printf("[comp %d, push %d, sub %d, maxQsize %d]\n", compCount, pushCount, subCount, maxQsize);
    }

    void dump(map<char, int> &input) {
        std::map<char, int>::iterator it;
        for (it = input.begin(); it != input.end(); it++) {
            printf("[%c %d], ", it->first, it->second);
        }
    }

    void dumpQ(list<pair<int/*score*/, map<char, int> > > &q) {
        list<pair<int/*score*/, map<char, int> > >::iterator it;
        for (it = q.begin(); it != q.end(); it++) {
            printf("%d, ", it->first);
            dump(it->second);
            printf("\n");
        }
        printf("\n");
    }

    void stringToMapWithFilter(string &input, map<char, int> &result, map<char, int> &filter) {
        if (input.length() < 1)
            return;

        char now = input.at(0);
        int length = 1;
        for (unsigned i = 1; i < input.length(); ++i)
        {
            if (input.at(i) != now) {
                if (filter.find(now) != filter.end()) {
                    result.insert(std::pair<char,int>(now, length));
                }
                now = input.at(i);
                length = 1;
            } else {
                length++;
            }
        }
        if (filter.find(now) != filter.end()) {
            result.insert(std::pair<char,int>(now, length));
        }
    }

    void stringToMap(string &input, map<char, int> &result) {
        if (input.length() < 1)
            return;

        char now = input.at(0);
        int length = 1;
        for (unsigned i = 1; i < input.length(); ++i)
        {
            if (input.at(i) != now) {
                result.insert(std::pair<char,int>(now, length));
                now = input.at(i);
                length = 1;
            } else {
                length++;
            }
        }
        result.insert(std::pair<char,int>(now, length));
    }

    bool vectorSub(std::map<char, int> &a, std::map<char, int> &b) { 
        subCount++;
        bool result = false;
        std::map<char, int>::iterator it;
        for (it = b.begin(); it != b.end(); it++) {
            if (a.find(it->first) != a.end()) {
                int aCount = a[it->first];
                if (aCount == 0) {
                    continue;
                }
                int bCount = it->second;
                result = true;                
                aCount = (aCount >= bCount) ? (aCount - bCount) : 0;
                a[it->first] = aCount;
            }
        }
        return result;
    }

    bool allZero(std::map<char, int> &a) {
        bool result = false;
        std::map<char, int>::iterator it;
        for (it = a.begin(); it != a.end(); it++) {
            if(it->second != 0) {
                break;
            }
        }
        if (it == a.end()) {
            result = true;
        }
        return result;
    }

    /*a >= b*/
    bool greaterThan(std::map<char, int> &a, std::map<char, int> &b) {
        compCount++;
        std::map<char, int>::iterator it;
        for (it = b.begin(); it != b.end(); it++) {
            if (a.find(it->first) == a.end()) {
                return false;
            } else if (a[it->first] < (it->second)) {
                return false;
            }
        }
        return true;
    }

    int minStickers(vector<string>& stickers, string target) {
        compCount = pushCount = subCount =0;

        vector<std::map<char, int> > stickersList(stickers.size());
        std::map<char, int> targetMap;

        std:sort(target.begin(), target.end());
        stringToMap(target, targetMap);
        std::set<char> targetSet;
        std::set<char> stickerSet;
        for (int i = 0; i < target.length(); i++) {
            targetSet.insert(target.at(i));
        }
        for (int i = 0; i < stickers.size(); i++) {
            for (int j = 0; j < stickers[i].size(); j++) {
                stickerSet.insert(stickers[i].at(j));
            }
            std::sort(stickers[i].begin(), stickers[i].end());
            stringToMapWithFilter(stickers[i], stickersList[i], targetMap);
        }

        std::set<char>::iterator setIt;
        //for (setIt = targetSet.begin(); setIt != targetSet.end(); setIt++) std::cout << *setIt << ' ';
        //cout << "targetSet \n";
        //for (setIt = stickerSet.begin(); setIt != stickerSet.end(); setIt++) std::cout << *setIt << ' ';
        //cout << "stickerSet \n";

        std::set<char> diff;
        std::set_difference(targetSet.begin(), targetSet.end(), stickerSet.begin(), stickerSet.end(), 
            std::inserter(diff, diff.begin()));

        //for (setIt = diff.begin(); setIt != diff.end(); setIt++) std::cout << *setIt << ' ';
        if (diff.size() != 0) {
            return -1;
        }

        //list<pair<pair<int/*min*/, int/*score*/>, map<char, int> > q;
        list<pair<pair<int/*min*/, int/*score*/>, map<char, int> > > q; 
        q.push_front(make_pair(make_pair(0, 0), targetMap));
        pushCount++;
        int dbg = 0;
        bool done = false;
        maxQsize = 0;
        while (q.size() && !done) {
            pair<pair<int/*min*/, int/*score*/>, map<char, int> > item = q.front();
            q.pop_front();
            if (q.size() > maxQsize) {
                maxQsize = q.size();
            }
            for (int i = (item.first.first); i < stickers.size(); i++) {
                map<char, int> tmp = item.second;
                int score = item.first.second + 1;
                bool check = vectorSub(tmp, stickersList[i]);
                if (check) {
                    if (allZero(tmp)) {
                        done = true;
                        printf("score %d\n", score);
                        return score;
                    }
                    list<pair<pair<int/*min*/, int/*score*/>, map<char, int> > >::iterator it;
                    bool needInsert = true;
                    for (it = q.begin(); it != q.end(); it++) {
                        bool great = greaterThan(tmp, it->second);
                        if (great) {
                            needInsert = false;
                            break;
                        }
                    }
                    if (needInsert) {
                        q.push_back(make_pair(make_pair(i, score), tmp));
                        pushCount++;
                    }
                }
            }
        }
        return -1;
    }

    int compCount;
    int pushCount;
    int subCount;
    int maxQsize;
};

int main()
{
    string input;
    ifstream ifs("test.txt", ios::in);
    ifs >> input;
    cout << input << "\n";
    {
        Solution solution;
        std::vector<std::string> v;
        string tmp;
        while (std::getline(ifs, tmp)) {
            v.push_back(tmp);
        }

        for (int i = 0; i < v.size(); i++) {
            cout << v[i] << "\n";
        }

        clock_t begin = clock();
        int ans = solution.minStickers(v, input);
        clock_t end = clock();
        double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
        printf("res %d, time = %f, \n", ans, time_spent);
    }
    system("pause");
    return 1;
}

留言

張貼留言

這個網誌中的熱門文章

https://leetcode.com/contest/leetcode-weekly-contest-52/problems/longest-univalue-path/

[Implementation idea]: It is the same as longest path of a tree but with limitation. http://www.geeksforgeeks.org/diameter-of-a-binary-tree/ For Diameter of a Binary Tree, we need to recursively find out the height H() of sub-tree rooted at left & right child for each node. Then the answer is the node with max(H(node->left) + H(node->right)) + 1. For this case, an additional limit is the definition  height H'().  It needs to be the same value to it's left or right child now.   If not so, H'(node) is 0. Recursively calculate H'() for each node within the target tree. The answer is max(H'(node->left) + H'(node->right)) + 1 . #include <iostream> #include <set> #include <vector> #include <unordered_map> #include <limits.h> using namespace std; /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(i...
閱讀完整內容

https://leetcode.com/contest/leetcode-weekly-contest-52/problems/maximum-sum-of-3-non-overlapping-subarrays/

圖片
[Implementation idea]: [Native way] A native way is to check all triple candidates, filter out illegals and find the one the maximum sum. Complexity is O(n^3). [Better way] Apply dynamic programming. Complexity is O(nlogn) Complexity is O(n) Input: [1,2,1,2,6,7,5,1], 2 Output: [0, 3, 5] Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5]. We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger. Assume A(i, j) represents the maximum j Non-Overlapping Sub-arrays sum whose last  chosen index is at position i. A(i, 1) = 1. sum(A(k)) k = i, i-1, ... i-k+1, if i  >= (k - 1). 2. 0, otherwise. A(i, 2) = 1. A(i, 1) + max(A(i-k, 1)); if i  >= (2*k - 1).  2. 0, otherwise. A(i, 3) = 1. A(i, 1) + max(A(i-k, 2)); if i  >= (3*k - 1).  2. 0, otherwise. Formula A(i,1) is intuitive; Formula A(i,2) comes from the fact that - we must ended ...
閱讀完整內容