Leetcode Weekly Contest 152

退役老人现在连leetcode都不会做了 = =

今天早上做了leetcode第三题题目看错了，加上比赛中间还在调投稿的实验，一心二用直接gg

总结下教训就是本渣现在做题连题目都看不清就开始做。开始写题之前应当把样例过一遍，然后自己再造1-2个例子，然后再开始做

A题：统计素数的个数(素数筛或者sqrt(n)判断都可以)，然后分别计算count!

class Solution {

public:

    int numPrimeArrangements(int n) {

        vector<int> has(n + 5, 0);

        int cntPrime = 0;

        const int MOD = 1e9 + 7;

        for(int i = 2; i <= n; ++i) {

            if(has[i] == 0) cntPrime ++;

            for(int j = i * 2; j <= n; j += i) {

                has[j] = 1;

            }

        }

        int result = 1;

        for(int i = 1; i <= n - cntPrime; ++i) {

            result = 1ll * i * result % MOD;

        }

        for(int i = 1; i <= cntPrime; ++i) {

            result = 1ll * i * result % MOD;

        }

        return result;

    }

};

B题：滚动求和

class Solution {

public:

    int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {

        long long sum = 0;

        for(int i = 0; i < k; ++i) {

            sum += calories[i];

        }

        int result = 0;

        for(int i = k - 1, len = calories.size(); i < len; ++i) {

            if(sum < lower) result --;

            else if(sum > upper) result ++;

            if(i != len - 1) {

                sum -= calories[i - k + 1];

                sum += calories[i + 1];

            }

        }

        return result;

    }

};

C题：我之前把题意看成整个字符串满足是回文，这个复杂很多。。。。

正确解法是判断区间的每种字母个数，我们知道偶数是可以直接配对的(放对称位置就好了)，统计字母个数为奇数的，奇数的需要改一半就好了

class Solution {

private:

    vector<int> has[26];

    int get(int id, int fr, int to) {

        if(fr > to) return 0;

        if(fr == 0) return has[id][to];

        else return has[id][to] - has[id][fr - 1];

    }

public:

    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {

        int slen = s.length();

        for(int i = 0; i < 26; ++i) has[i].clear();

        /***statistic character count*****/

        for(int i = 0; i < 26; ++i) {

            for(int j = 0; j < slen; ++j) {

                has[i].push_back(0);

            }

        }

        for(int i = 0; i < slen; ++i) {

            has[s[i] - 'a'][i] ++;

        }

        for(int i = 0; i < 26; ++i) {

            for(int j = 1; j < slen; ++j) {

                has[i][j] += has[i][j-1];

            }

        }

        vector<bool> result;

        for(int i = 0, len = queries.size(); i < len; ++i) {

            int left = queries[i][0]; int right = queries[i][1]; int k = queries[i][2];

            int cnt = 0;

            for(int j = 0; j < 26; ++j) {

                int t1 = get(j, left, right);

                if(t1 % 2 == 1) {

                    cnt ++;

                }

            }

            cnt /= 2;

            if(cnt <= k) result.push_back(true);

            else result.push_back(false);

        }

        return result;

    }

};

D题：基本思想就是暴力查询，首先我们知道，字符串中的字母排列前后和出现次数都是无所谓的(除了puzzle的第一个字母的问题)，这个是可以进行处理的

除此之外有两种加速的方法

方法1: 位压缩为26位，直接通过数位判断word是否是满足puzzle

方法2: 对word建立字典树，让puzzle在字典树中进行dfs，这里每个puzzle大约会有7!的查询复杂度

下面两个代码分别对应这两种方案，我是直接discuss的大佬里面爬下来了

class Solution {

    vector<int> base;

    void born(vector<string>& words){

        for(auto& s: words){

            set<char> tmp;

            int bit = 0;

            for(auto c:s){

                tmp.insert(c);

                bit = bit | (1<<(c-'a'));

            }

            if(tmp.size() >7)continue;

            base.push_back(bit);

        }

    }

public:

    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {

        vector<int> ans;

        born(words);

        for(auto& s: puzzles){

            int num = 0;

            int bit = 0;

            for(auto c: s){

                bit = bit | (1<<(c-'a'));

            }

            int firstBit = 1 << (s[0] - 'a');

            for(auto v: base){

                if((v & bit) == v && ((firstBit & v) == firstBit)){

                    num++;

                }

            }

            ans.push_back(num);

        }

        return ans;

    }

};

const int ALPHABET_SIZE = 26;

/* The structure of a trie node */

struct TrieNode

{

    struct TrieNode* children[ALPHABET_SIZE];

    int count = 0;

};

/* Creates a new trie node and returns the pointer */

struct TrieNode* getNode()

{

    struct TrieNode* newNode = new TrieNode;

    for(int i=0; i<ALPHABET_SIZE; i++)

        newNode->children[i] = nullptr;

    newNode->count = 0;

    return newNode;

}

/* Inserts the given string to the collection */

void insert(struct TrieNode* root, string str)

{

    struct TrieNode* pCrawl = root;

    for(int i=0; i<str.length(); i++)

    {

        int index = str[i]-'a';

        if(!pCrawl->children[index])

            pCrawl->children[index] = getNode();

        pCrawl = pCrawl->children[index];

    }

    pCrawl->count = (pCrawl->count + 1);

}

/* Returns the count of strings which are valid */

int search(struct TrieNode* root, string str, bool firstSeen, char firstLetter)

{

    if(!root)

        return 0;

    int count = 0;

    if(firstSeen)

        count += root->count;

    for(int i=0; i<str.length(); i++)

    {

        int index = str[i] - 'a';

        if(str[i] == firstLetter)

            count += search(root->children[index], str, true, firstLetter);

        else

            count += search(root->children[index], str, firstSeen, firstLetter);

    }

    return count;

}

class Solution

{

public:

    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles);

};

vector<int> Solution :: findNumOfValidWords(vector<string>& words, vector<string>& puzzles)

{

    struct TrieNode* root = getNode();

    for(auto str : words)

    {

        set<char> temp;

        temp.insert(str.begin(), str.end());

        string sorted = "";

        for(auto ele : temp)

            sorted += ele;

        insert(root, sorted);

    }

    vector<int> count;

    for(auto puzzle : puzzles)

    {

        char firstLetter = puzzle[0];

        sort(puzzle.begin(), puzzle.end());

        count.push_back(search(root, puzzle, false, firstLetter));

    }

    return count;

}

巴特西

Leetcode Weekly Contest 152

最新文章

热门文章