Leetcode Weekly Contest 420

[oin1104 (是oin的說)]

https://i.imgur.com/VULhdUt.png

問就是衝擊Guardian

爽



Q1
一開始有個空的字串跟target
有兩種操作
1 在右邊加上a
2 讓右邊的字母++
要把空字串
把所有操作後的字串記錄下來回傳

思路:
暴力的從右邊慢慢加
同時紀錄

class Solution {
public:
    vector<string> stringSequence(string target)
    {
        vector<string> res ;
        string now ;
        int n = target.size();
        for(int i = 0 ; i < n ; i ++)
        {
            now.push_back('a');
            res.push_back(now);
            while(now[i] < target[i])
            {
                now[i]++;
                res.push_back(now);
            }
        }

        return res;
    }
};


Q2
有多少個子字串
裡面至少有一個字母重複k次

思路:
因為字串長度比較小
所以直接暴力檢查

class Solution {
public:
    int numberOfSubstrings(string s, int k)
    {
        int res = 0;
        int n = s.size();

        for(int i = 0 ; i < n ; i ++)
        {
            vector<int> save(26,0);
            int ok = 0;
            for(int j = i ; j < n ; j ++)
            {
                save[s[j]-'a'] ++;
                if(save[s[j]-'a'] >= k)ok = 1;
                if(ok) res++;
            }
        }

        return res;
    }
};

Q3
要讓一個陣列變成遞增
可以把數字除以他的最大因數
請問要幾次才可以
不行的話就回傳-1

思路:
做個回傳最小因數的函式
然後把那個數字除以最小因數
就會是最大因數
然後從後面開始檢查
只要一個不符合
就不行


class Solution {
public:

    int gpd(int k)
    {
        for(int i = 2 ; i <= sqrt(k) ; i ++)
        {
            if(k%i == 0)return i;
        }
        return k;
    }

    int minOperations(vector<int>& nums)
    {
        int res = 0 ;
        int n = nums.size();

        for(int i = n-1 ; i > 0 ; i --)
        {
            if(nums[i] < nums[i-1])
            {
                nums[i-1] /= (nums[i-1]/gpd(nums[i-1]));
                res ++;
            }
            if(nums[i] < nums[i-1])
            {
                return -1;
            }
        }

        return res;
    }
};


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.29.79 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729399859.A.FB3.html
推 sustainer123: 大師
推 Meaverzt: 大師
推 mrsonic: 刷爽沒