Weekly Contest 152

Posted on | In , | |
Words count in article: 1.3k | Reading time ≈ 7

1. 求1~n中所有质数对应质数位置的排列的数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int isPrime(int n)
    {
        if(n == 2)
            return 1;
        int t = n;
        for(int i=2; i*i <= t; i++)
        {
            if(t % i == 0)
                return 0;
        }
        return 1;
    }
    int numPrimeArrangements(int n) {
        int count1 = 0;
        int count2 = 0;
        for(int i=2; i<=n; i++)
        {
            if(isPrime(i))
                count1++;
        }
        count2 = n-count1;
        long long ret = 1;
        for(int i=1; i<=count1; i++)
        {
            ret = ret * i % 1000000007;
        }
        for(int i=1; i<=count2; i++)
        {
            ret = ret * i % 1000000007;
        }
        return ret % (1000000000 + 7);
    }
};

2. Can Make Palindrome from Substring

Given a string s, we make queries on substrings of s.

For each query queries[i] = [left, right, k], we may rearrange the substring s[left], …, s[right], and then choose up to k of them to replace with any lowercase English letter.

If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false.

Return an array answer[], where answer[i] is the result of the i-th query queries[i].

Note that: Each letter is counted individually for replacement so if for example s[left..right] = “aaa”, and k = 2, we can only replace two of the letters. (Also, note that the initial string s is never modified by any query.)

1
2
3
4
5
6
7
8
Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
Output: [true,false,false,true,true]
Explanation:
queries[0] : substring = "d", is palidrome.
queries[1] : substring = "bc", is not palidrome.
queries[2] : substring = "abcd", is not palidrome after replacing only 1 character.
queries[3] : substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab".
queries[4] : substring = "abcda", could be changed to "abcba" which is palidrome.

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution {
public:
    // int helper(string s, vector<int> h)   // timeout!!
    // {
    //     int l = h[0];
    //     int r = h[1];
    //     int k = h[2];
    //     int ch[26] = {0};
    //     for(int i=l; i<=r; i++)
    //         ch[s[i]-'a']++;
    //     int count = 0;
    //     for(int i=0; i<26; i++)
    //     {
    //         if(ch[i] % 2 != 0)
    //             count++;
    //     }
    //     int ret = (count / 2 <= k);
    //     return ret;
    // }
    // vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
    //     vector<bool> ret;
    //     for(int i=0; i<queries.size(); i++)
    //     {
    //         int cur = helper(s, queries[i]);
    //         if(cur)
    //         {
    //             bool rem = true;
    //             ret.push_back(rem);
    //         }
    //         else
    //         {
    //             bool rem = false;
    //             ret.push_back(rem);
    //         }
    //     }
    //     return ret;
    // }
    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
        int n=s.length();
        
        int freq[n][26];
        
        memset(freq,0,sizeof(freq));
        
        int i,j;
        
        for(i=0;i<n;i++)
        {
            freq[i][s[i]-'a']++;
        }
        for(i=1;i<n;i++)
        {
            for(j=0;j<26;j++)
            {
                freq[i][j]+=freq[i-1][j];
            }
        }
        vector<bool> answer;
        int u;
        bool ok=true;
        for(i=0;i<queries.size();i++)
        {
            int l,r,k;
            l=queries[i][0];
            r=queries[i][1];
            k=queries[i][2];
            int cnt=0;
            for(j=0;j<26;j++)
            {
                if(l==0)
                    u=freq[r][j];
                else
                    u=freq[r][j]-freq[l-1][j];
                
                if(u%2==1)
                {
                    cnt++;
                }
            }
            
            if((cnt/2)<=k)
            {
                answer.push_back(ok);
            }
            else
            {
                answer.push_back(!ok);
            }
        }
        return answer;
	}
};

3. Number of Valid Words for Each Puzzle

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

word contains the first letter of puzzle.

For each letter in word, that letter is in puzzle.

For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”; while invalid words are “beefed”

(doesn’t include “a”) and “based” (includes “s” which isn’t in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that are valid with respect to the puzzle puzzles[i].

1
2
3
4
5
6
7
8
9
10
11
Input: 
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation:
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There're no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    vector<int> bb;
    void bbit(vector<string>& w)
    {
        for(auto s : w)
        {
            int bit = 0;
            set<char> tmp;
            for(auto t: s)
            {
                tmp.insert(t);
                bit = bit | (1 << (t-'a'));
            }
            if(tmp.size() > 7) continue;
            bb.push_back(bit);
        }
    }
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        vector<int> ret;
        bbit(words);
        
        for(auto& s: puzzles)
        {
            int num = 0;
            int first = 1 << (s[0] - 'a');
            int bit = 0;
            for(auto aa : s)
            {
                bit = bit | (1 << (aa-'a'));
            }
            for(auto v: bb)
            {
                if((v & bit) == v && ((first & v) == first))
                    num++;
            }
            
            ret.push_back(num);
            
        }
        
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        // Lengths
        int P = puzzles.size();
        int W = words.size();
        
        // Letter masks
        vector<int> letterMask(26, 0);
        
        for (int i = 0, mask = 1; i < 26; ++i, mask <<= 1) {
            letterMask[i] = mask;
        }
        
        // Word masks with count info
        unordered_map<int, int> wordsMask;
        
        // For each word
        for (int i = 0; i < W; ++i) {
            // Compute word mask
            int mask = 0;
            
            for (char c: words[i]) {
                mask = mask | letterMask[c - 'a'];
            }
            
            ++wordsMask[mask];
        }
       
         // Result : result[i] => number of words covered by puzzles[i]
        vector<int> result(P, 0); 
        
        // For each puzzle
        for (int i = 0; i < P; ++i) {
            // Compute puzzle mask
            int mask = 0;
            
            for (char c: puzzles[i]) {
                mask = mask | letterMask[c - 'a'];
            }
            
            // Iterate through all valid subset of mask i.e. subset of puzzle chars = 2^7 = 64 in count
            // This makes the complexity O(P*64)
            int subMask = mask;
            
            while (subMask) {
                if ((subMask & letterMask[puzzles[i][0] - 'a']) && wordsMask.count(subMask)) {
                    result[i] += wordsMask[subMask];
                }
                
                // Only select valid bits i.e. bits corresponding to chars in puzzle
                subMask = (subMask - 1) & mask;
            }
        }
        
        return result;
    }
};
Donate? comment?