###### tags: `Weekly Contest`
# Weekly Contest 356

## [2798. Number of Employees Who Met the Target](https://leetcode.com/problems/number-of-employees-who-met-the-target/)(<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>1 &lt;= n == hours.length &lt;= 50</code></li>
<li><code>0 &lt;= hours[i], target &lt;= 10⁵</code></li>
</ul>

### Solution

#### 時間複雜度: $O(n)$

#### 空間複雜度: $O(1)$

程式碼:

class Solution {
public:
    int numberOfEmployeesWhoMetTarget(vector<int>& hours, int target) {
        int ans=0;
        for(int i=0;i<hours.size();i++){
            if(hours[i]>=target)
                ans++;
        }
        return ans;
    }
};

## [2799. Count Complete Subarrays in an Array](https://leetcode.com/problems/count-complete-subarrays-in-an-array/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
<li><code>1 &lt;= nums[i] &lt;= 2000</code></li>
</ul>

### Solution
暴力窮舉所有 subarray，接著用 set 統計 subarray 不同元素的數量來 check 這個 subarray 是否是 complete。

有一個小優化的部分，只要 $nums[i:j]$ 是 complete，那 $nums[i:j+1]$、$nums[i:j+2]\ ...$ 也都是 complete。所以對於每個 $i$ 只需要算出第一個 complete 的 $j$，後面的就不用額外計算。
#### 時間複雜度: $O(n^2)$

#### 空間複雜度: $O(n)$

程式碼:

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        int n=nums.size();
        set<int> target;
        for(auto &num: nums){
            target.insert(num);
        }
        int ans = 0;
        for(int i=0;i<n;i++){
            set<int> si;
            for(int j=i;j<n;j++){
                si.insert(nums[j]);
                if(si.size() == target.size()){
                    ans += n-j;
                    break;
                }
            }
        }
        return ans;
    }
};

## [2800. Shortest String That Contains Three Strings](https://leetcode.com/problems/shortest-string-that-contains-three-strings/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= a.length, b.length, c.length &lt;= 100</code></li>
<li><code>a</code>, <code>b</code>, <code>c</code> consist only of lowercase English letters.</li>
</ul>

### Solution
相當搞的一題，在細節debug上花費了非常多的時間。

核心概念是做出 merge 這個操作，merge 的意義是將 $s$ 字串與 $t$ 字串串接起來並去除重複，以下舉幾個範例:
* merge("abc", "bca") -> "abca"
* merge("abca", "aaa") -> "abcaaa"

答案一定會出現在 abc 這三個字串的所有排列 merge 之中，也就是以下6個答案:
* merge(merge(a, b), c)
* merge(merge(a, c), b)
* merge(merge(b, a), c)
* merge(merge(b, c), a)
* merge(merge(c, a), b)
* merge(merge(c, b), a)

算出六個答案之後照著題目要求選出最短且 lexicographically smallest 的字串即可。

n = max(a.size(), b.size(), c.size())
#### 時間複雜度: $O(n^2)$

#### 空間複雜度: $O(n)$

程式碼:

class Solution {
public:
    bool contain(string &a, string &b, string &c){
        return a.find(b) !=string::npos&&a.find(c) !=string::npos;
    }
    string merge(string a, string b){
        if(a.find(b) !=string::npos||b.find(a) !=string::npos)
            return a.size()>b.size()?a:b;
        int n = min(a.size(), b.size());
        for(int i=n-1, j=0;i>=0;i--, j++){
            if(a.substr(a.size()-i-1) == b.substr(0, i+1))
                return a.substr(0, a.size()-i-1)+a.substr(a.size()-i-1)+b.substr(i+1);
        }
        return a+b;
    }
    static bool cmp(string &a, string &b){
        if(a.size() == b.size())
            return a<b;
        return a.size()<b.size();
    }
    string minimumString(string a, string b, string c) {
        vector<string> d, temp;
        
        temp.push_back(a), temp.push_back(b), temp.push_back(c);
        int cnt=6, i=0;
        while(cnt--){
            d.push_back(merge(merge(temp[0], temp[1]), temp[2]));
            next_permutation(temp.begin(), temp.end());
        }
        sort(d.begin(), d.end(), cmp);

        return d[0];
    }
};

## [2801. Count Stepping Numbers in Range](https://leetcode.com/problems/count-stepping-numbers-in-range/)(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>1 &lt;= int(low) &lt;= int(high) &lt; 10¹⁰⁰</code></li>
<li><code>1 &lt;= low.length, high.length &lt;= 100</code></li>
<li><code>low</code> and <code>high</code> consist of only digits.</li>
<li><code>low</code> and <code>high</code> don't have any leading zeros.</li>
</ul>

### Solution
很搞的題\*2，debug de 了一小時多。

這是經典的 digit dp。因為直接算出 $[low, high]$ 中的 stepping number 的數量很困難，所以我們先算出 $[1, high]$ 的數量，再算出 $[1, low-1]$ 的數量，兩個相減就是 $[low, high]$ 的數量。

問題現在被簡化成如何算出 $[1, limit]$ 的數量了，要快速的算這個問題需要用到 digit dp。

令 $dp[i][j]$ 為長度為 $i$ 且最大位數為 $j$ 的 stepping number 的數量。

顯而易見的，$dp[0][0:9] := 1$，因為 1~9 都是 stepping number，我們可以透過當前位數的答案去計算下一位數有幾個 stepping number，dp式:
$$ dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] $$
以 $dp[1][1]$ 舉例的話，正確答案是 12,10，阿這些答案又是根據上一位數的0跟2個別在最高位接上1所算出來的，所以 $dp[1][1] = dp[0][0]+dp[0][2]$。

m = 10
#### 時間複雜度: $O(n*m)$

#### 空間複雜度: $O(n*m)$

程式碼:

class Solution {
public:
    const int MOD = 1e9+7;
    void dfs(int idx, int sign, int &ans, string &s, vector<vector<int> > &dp){
        if(idx == s.size()-1)
            return ;
        if(s[idx+1]>s[idx]+sign)
            return ;
        else if(s[idx+1]<s[idx]+sign){
            if(s[idx]+sign-'0'>=0&&s[idx]+sign-'0'<10)
                ans = (ans - dp[s.size()-idx-2][s[idx]+sign-'0']　+ MOD)%MOD;
        }
        else {
            dfs(idx+1, 1, ans, s, dp);
            dfs(idx+1, -1, ans, s, dp);
        }
    }
    int countNumber(string &s){
        if(s.size()==1)
            return s[0]-'0';
        int n=s.size();
        vector<vector<int> > dp(n, vector<int>(10));

        for(int i=0;i<=9;i++)
            dp[0][i] = 1;
        
        int ans = 9;
        for(int i=1;i<n;i++){
            for(int j=0;j<10;j++){
                if(j-1>=0)
                    dp[i][j] = (dp[i][j]+dp[i-1][j-1])%MOD;
                if(j+1<10)
                    dp[i][j] = (dp[i][j]+dp[i-1][j+1])%MOD;
                if(j !=0)
                    ans = (ans + dp[i][j])%MOD;
            }
        }

        for(int i=s[0]-'0'+1;i<10;i++)
            ans = (ans - dp[n-1][i] + MOD)%MOD;
        
        dfs(0, 1, ans, s, dp);
        dfs(0, -1, ans, s, dp);
        return ans;
    }
    int countSteppingNumbers(string low, string high) {
        low[low.size()-1]--;
        for(int i=low.size()-1;i>=0;i--){
            if(low[i]<'0'){
                low[i-1]--;
                low[i]+=10;
            }
            else {
                break;
            }
        }

        return (countNumber(high)-countNumber(low) + MOD)%MOD;      
    }
};