[the 83rd fortnight of leetcode]

AK Portal

Luck is part of strength , Oh, roar …

Guess the last question emmm

The best poker hand 3

subject

---

Ideas

simulation , Maybe there is a good way ？

---

Code

class Solution {
    
public:
    string bestHand(vector<int>& ranks, vector<char>& suits) {
    
        string res[10] = {
    "", "Flush", "Three of a Kind", "Pair", "High Card"};
        int n = ranks.size(), m = suits.size();
        bool o1 = true, o2 = true, o3 = true, o4 = true; //  Corresponding to four 
        for (int i = 1; i < m; i++) if(suits[i] != suits[i - 1]) o1 = false;
        if(o1) {
     return res[1]; }
        map<int, int> mp; for (auto &x: ranks) mp[x]++;
        for (auto &x: mp) {
     if(x.second >= 3) o2 = false; else if(x.second >= 2) o3 = false; }
        if(!o2) {
     return res[2]; }
        if(!o3) {
     return res[3]; }
        return res[4];
    }
};

---

whole 0 The number of subarrays 4

subject

---

Ideas

• Find each pile separately 0, such as 1100011,[0] -> 3,[0,0] -> 2,[0,0,0] -> 1. So for every pile 0, Namely (len + 1) * len / 2 individual .

---

Code

class Solution {
    
public:
    #define ll long long
    long long zeroFilledSubarray(vector<int>& nums) {
    
        int n = nums.size();
        ll res = 0;
        for (int i = 0; i < n; i++) {
    
            if(nums[i] == 0) {
    
                int j = i + 1;
                while(j < n && nums[j] == 0) j++;
                res += (ll)(j - i + 1) * (j - i) / 2;
                i = j;
            }
        }
        return res;
    }
};

---

Design digital container system 5

subject

---

Ideas

• Two operations ：

  • change： stay （index,number） Location , Insert a value
  • find： find （number） The subscript with the smallest value

First , Data range 1e9, It can't be normal array maintenance , Consider hashing map.

First look at find, about number Minimum subscript , It's easy to think ,number The value may appear many times in the maintained structure , So here we are map Of key Express number Words , that val All should be stored number The current position of .

Because we need to find fast number Minimum subscript position of , And it has to support fast modification （ Delete ）, So structure map<int, set<int>> It would be a good choice .

One ：*mp[number].begin()： You can get it directly number The minimum subscript of the value store .
Two ：mp[number].erase(index)： Can directly log Class in number When replaced , Delete number Stored subscripts .

int find(int number) {
    
    if(mp[number].size() == 0) return -1;
    return *mp[number].begin();
}

Look again change： According to the meaning of the title , For each subscript stored value , We still have to use map<int, int> a Analog array to store . Then you can replace it or insert it .

It's a little redundant , The game time code will not be revised .

void change(int index, int number) {
    
    if(a.count(index) != 0) {
    
        mp[a[index]].erase(index);
        a[index] = number;
        mp[number].insert(index);
    } else {
    
        a[index] = number;
        mp[number].insert(index);
    }
}

---

Code

class NumberContainers {
    
public:
    map<int, set<int>> mp;
    map<int, int> a; 
    NumberContainers() {
    
        a.clear(), mp.clear();
    }
    
    void change(int index, int number) {
    
        if(a.count(index) != 0) {
    
            mp[a[index]].erase(index);
            a[index] = number;
            mp[number].insert(index);
        } else {
    
            a[index] = number;
            mp[number].insert(index);
        }
    }
    
    int find(int number) {
    
        if(mp[number].size() == 0) return -1;
        return *mp[number].begin();
    }
};

---

The shortest dice sequence that cannot be obtained

subject

---

Ideas

• This question is actually a conclusion I guess .（ Please move to specific proof Official interpretation ）

about len A sequence of lengths , Here's a demonstration rolls = [3,2,1,2,3,2,3,1],k = 3：

len = 1：
【1】、【2】、【3】
len = 2：
【1、1】、【1、2】、【1、3】
【2、1】、【2、2】、【2、3】
【3、1】、【3、1】、【3、3】
len = 3：
【1、1、（ No more ）】 … I won't enumerate below

You can guess boldly , To meet the len A sequence of lengths , So inevitable 【1-k】【1-k】…【1-k】, Must have len Group , Each group must contain （1-k） All the numbers between . Only in this way can we meet all Of len Length sequence .

• Then how to implement the code ？

In fact, it's not hard to , Our goal is to see how much can be formed in the end Group .

So you just need to go through it ,res Indicates how many groups have been formed ,pre Indicates that you are trying to form the res+1 How many values of the group have been satisfied （pre==k There will be one more group ）. We can use res Variable pair array a assignment , In this way, you don't have to empty the array every time to calculate 1 The number of is maintained to be equal to k.

Vaguely trance , Come on , Make persistent efforts ！！！

---

Code

class Solution {
    
public:
    static constexpr int N = 100010;
    int a[N];
    int shortestSequence(vector<int>& rolls, int k) {
    
        int n = rolls.size();
        int pre = 0, res = 1;
        for (int i = 0; i < n; i++) {
    
            if(a[rolls[i]] < res) {
     a[rolls[i]] = res; pre ++; }
            if(pre == k) {
    
                pre = 0; res += 1;
            }
        }
        return res;
    }
};

---