leetcode weekly 417.

[sixB (6B)]

每次都是contest一結束

放鬆下來之後就想到解法了==

我哭：（

不過幸好有先寫第四題出來 沒有被3卡死

1.2題可以暴力解

不過直接用3.4的解放也完全沒問題

==

3.  Count of Substrings Containing Every Vowel and K Consonants II

找出所有substr contain aeiou and just k croissant

原本我是head tail 慢慢推

找到再loop 找tail之後有多少母音（ TLE

改成先suffix count 後面連續接幾個母音

找到直接加

醜到不行==等等去看solution

using ll = long long;
class Solution {
public:
    //suffix vowel cnt
    unordered_map<int , ll> mp;
    //<idx, num>
    long long countOfSubstrings(string word, int k) {
        //slide window
        int A = 0, E = 0, I = 0, O = 0, U = 0;
        ll cnt = 0;
        int head = -1, tail = 0;
        int len = word.length();
        int cons = 0;
        bool mvH = false, mvT = true;

        int num = 0;
        for(int i = len - 1; i >= 0; i--){
            if(isvow(word[i])){
                num++;
                mp[i] = num;
            }
            else num = 0;
        }

        while(tail < len){
            if(mvT){
                // check new t
                char t = word[tail];
                if(t == 'a') A++;
                else if(t == 'e') E++;
                else if(t == 'i') I++;
                else if(t == 'o') O++;
                else if(t == 'u') U++;
                else cons++;
            }
            if(mvH){
                char h = word[head];
                if(h == 'a') A--;
                else if(h == 'e') E--;
                else if(h == 'i') I--;
                else if(h == 'o') O--;
                else if(h == 'u') U--;
                else cons--;
            }

            if(A and E and I and O and U){
                if(cons == k){
                    cnt++;
                    int temp = tail + 1;
                    if(temp < len and isvow(word[temp]) ){
                        cnt += mp[temp];
                    }
                    head++;
                    mvH = true; mvT = false;
                }
                else if(cons < k){
                    mvH = false; mvT = true;
                    tail++;
                }
                else{
                    //cons > k
                    mvH = true; mvT = false;
                    head++;
                }
            }
            else{
                mvH = false; mvT = true;
                tail++;
            }
        }
        return cnt;
    }
    bool isvow(char c){
        return (c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u');
    }
};


==

4. Find the K-th Character in String Game II

dp 往回找

看上一個的位置在哪

就這樣 好像沒啥能講==

using ll = long long;
class Solution {
public:

    char kthCharacter(long long k, vector<int>& operations) {
        map<ll, char> mp;
        mp[1] = 'a';
        ll pf = 1;
        ll op = 0;
        while(pf < k){
            pf *= 2;
            op++;
        }
        //cout << op << " " << operations.size();
        pf /= 2;
        op--;
        return find(k, mp, op, pf, operations);
    }
    char find(ll k, map<ll, char>& mp, ll op, ll pf, vector<int>& operations){
        //cout << k << " " << op << " " << pf << '\n';
        if(!mp.count(k)){
            while(pf >= k){
                pf /= 2;
                op--;
            }
            if(operations[op] == 0)
                mp[k] = find(k - pf, mp, op, pf, operations);
            else{
                char c = find(k - pf, mp, op, pf, operations);
                if (c == 'z'){
                    mp[k] = 'a';
                }
                else mp[k] = c + 1;
            }
        }
        return mp[k];
    }
};


-----
Sent from JPTT on my iPad

--
很姆的咪

姆之咪

http://i.imgur.com/5sw7QOj.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727584647.A.B7D.html
推 DJYOSHITAKA: 別捲了