1816. Усечение предложений

тема

приговорпредставляет собой список слов, разделенных одним пробелом без начальных или конечных пробелов. Каждое слово состоит только из заглавных и строчных букв латинского алфавита (без знаков препинания).

Например,"Hello World","HELLO"и"hello world hello world"все предложения.

дать вам предложениеsи целое числоk, ты будешьs обрезать, так что усеченное предложение содержит тольковперед kслова. возвращениеобрезать s**После вынесения приговора*. *

Пример 1:

输入：s = "Hello how are you Contestant", k = 4
输出："Hello how are you"
解释：
s 中的单词为 ["Hello", "how" "are", "you", "Contestant"]
前 4 个单词为 ["Hello", "how", "are", "you"]
因此，应当返回 "Hello how are you"

Пример 2:

输入：s = "What is the solution to this problem", k = 4
输出："What is the solution"
解释：
s 中的单词为 ["What", "is" "the", "solution", "to", "this", "problem"]
前 4 个单词为 ["What", "is", "the", "solution"]
因此，应当返回 "What is the solution"

Пример 3:

输入：s = "chopper is not a tanuki", k = 5
输出："chopper is not a tanuki"

намекать:

1 <= s.length <= 500
kДиапазон значений[1, s 中单词的数目]
sСостоит только из заглавных и строчных английских букв и пробелов
sСлова в разделены одним пробелом
нет начальных или конечных пробелов

код

class Solution {
public:
    string truncateSentence(string s, int k) {
        int cnt = 0;
        int i = 0;
        for (; i < s.length() && cnt != k; i++) {
            if (s[i] == ' ') cnt++;
        }
        return cnt == k ? s.substr(0, i - 1) : s;
    }
};

1817. Найти активные минуты пользователя

тема

Дает вам журнал действий пользователя в LeetCode и целое числоk. log с двумерным целочисленным массивомlogsозначает, что каждый изlogs[i] = [IDi, timei]Указывает, что идентификаторIDiпользователей вtimeiДействие совершалось за считанные минуты.

несколько пользователейОперации могут выполняться одновременно, в течение одной минуты одним пользователемнесколько операций.

указанного пользователяАктивные минуты пользователя (UAM)Определяется как действие пользователя на LeetCodeуникальные минуты. Даже если за одну минуту выполняется несколько операций, это может быть засчитано только одной минутой.

Пожалуйста, подсчитайте распределение активных минут пользователей. Статистический результат представляет собой длинуkиИндексы начинают считать с 1массивanswer, для каждогоj(1 <= j <= k),answer[j]выражатьАктивные минуты пользователяравныйjпользователей.

Возвращает массив ответов, описанных вышеanswer.

Пример 1:

输入：logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5
输出：[0,2,0,0,0]
解释：
ID=0 的用户执行操作的分钟分别是：5 、2 和 5 。因此，该用户的用户活跃分钟数为 2（分钟 5 只计数一次）
ID=1 的用户执行操作的分钟分别是：2 和 3 。因此，该用户的用户活跃分钟数为 2
2 个用户的用户活跃分钟数都是 2 ，answer[2] 为 2 ，其余 answer[j] 的值都是 0

Пример 2:

输入：logs = [[1,1],[2,2],[2,3]], k = 4
输出：[1,1,0,0]
解释：
ID=1 的用户仅在分钟 1 执行单个操作。因此，该用户的用户活跃分钟数为 1
ID=2 的用户执行操作的分钟分别是：2 和 3 。因此，该用户的用户活跃分钟数为 2
1 个用户的用户活跃分钟数是 1 ，1 个用户的用户活跃分钟数是 2 
因此，answer[1] = 1 ，answer[2] = 1 ，其余的值都是 0

намекать:

1 <= logs.length <= 104
0 <= IDi <= 109
1 <= timei <= 105
kДиапазон значений[用户的最大用户活跃分钟数, 105]

код

class Solution {
public:
    vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {
        unordered_map<int, unordered_set<int>> Map;
        for (auto& log : logs) {
            Map[log[0]].insert(log[1]);
        }
        vector<int> res(k, 0);
        for (auto& m : Map) {
            res[m.second.size() - 1]++;
        }
        return res;
    }
};

1818. Сумма абсолютной разницы

тема

дает вам два массива положительных целых чиселnums1иnums2, длина массиваn.

множествоnums1иnums2изАбсолютная разница иопределяется как все|nums1[i] - nums2[i]|(0 <= i < n)изсумма(индексы начинаются с 0).

ты можешь выбратьnums1серединакто-нибудьэлемент для заменыnums1серединав большинствеэлемент дляминимизироватьСумма абсолютной разницы.

замена массиваnums1не более одного элемента впосле, который возвращает наименьшую сумму абсолютных разностей. Поскольку ответ может быть большим, он должен быть правильным109 + 7 остатокВернуться позже.

|x|определяется как:

еслиx >= 0, значениеx,или
еслиx <= 0, значение-x

Пример 1:

输入：nums1 = [1,7,5], nums2 = [2,3,5]
输出：3
解释：有两种可能的最优方案：
- 将第二个元素替换为第一个元素：[1,7,5] => [1,1,5] ，或者
- 将第二个元素替换为第三个元素：[1,7,5] => [1,5,5]
两种方案的绝对差值和都是 |1-2| + (|1-3| 或者 |5-3|) + |5-5| = 3

Пример 2:

输入：nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
输出：0
解释：nums1 和 nums2 相等，所以不用替换元素。绝对差值和为 0

Пример 3**:**

输入：nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
输出：20
解释：将第一个元素替换为第二个元素：[1,10,4,4,2,7] => [10,10,4,4,2,7]
绝对差值和为 |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20

намекать:

n == nums1.length
n == nums2.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= 105

код

// 因为可以用nums1中的任意数字替换nums1中的一个数字使得绝对差值和最小
// 我们可以枚举每一个nums2中的元素, 最小化其与nums1对应元素的绝对差值
// 也就是可以将nums1当前位置的数字nums1[i]替换成nums1中第一个大于或者等于nums2[i]的数字, 或者最后一个小于nums2[i]的数字
// 取最小差值即可
typedef long long ll;
int mod = 1e9 + 7;
class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        set<int> st; // sort
        ll tot = 0;
        for (int i = 0; i < n; i++) {
            tot += abs(nums1[i] - nums2[i]);
            st.insert(nums1[i]);
        }
        ll ans = tot;
        for (int i = 0; i < n; i++) {
            auto it = st.lower_bound(nums2[i]);
            if (it != st.end()) {
                ll now = tot - abs(nums1[i] - nums2[i]) + abs(*it - nums2[i]);
                ans = min(ans, now);
            } 
            if (it != st.begin()) {
                --it;
                ll pre = tot - abs(nums1[i] - nums2[i]) + abs(*it - nums2[i]);
                ans = min(ans, pre);
            }
        }
        return ans % mod;
    }
};

1819. Количество различных наибольших общих делителей в последовательности.

тема

дает вам массив положительных целых чиселnums.

последовательность чиселнаибольший общий делительОпределяется как наибольшее целое число среди общих делителей всех целых чисел в последовательности.

Например, последовательность[4,6,16]Наибольший общий делитель2.

массивпоследующая последовательностьПо сути, последовательность, которую можно получить, удалив определенные элементы (или нет) из массива.

Например,[2,5,10]да[1,2,1,**2**,4,1,**5**,**10**]подпоследовательность .

рассчитать и вернутьnumsвсене пустойвпоследствииразныенаибольший общий делительномер.

Пример 1:

输入：nums = [6,10,3]
输出：5
解释：上图显示了所有的非空子序列与各自的最大公约数。
不同的最大公约数为 6 、10 、3 、2 和 1 。

Пример 2:

输入：nums = [5,15,40,5,6]
输出：7

намекать:

1 <= nums.length <= 105
1 <= nums[i] <= 2 * 105

код

class Solution {
public:
    int m = 0;
    bool f[200010];
    int gcd(int a,int b){return a%b==0?b:gcd(b,a%b);}
    bool check(int x){
        int t = 0;
        for(int i = x; i <= m; i += x) 
            if(f[i]){
                if(t==0)t = i/x;
                else t=gcd(t,i/x);
            }
        return t == 1;
    }
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for(int i = 0; i < n; ++i){
            m = max(m,nums[i]);
            f[nums[i]] = 1;
        }
        for(int i = 1;i <= m; ++i)
            if(check(i))
                ++ans;
        return ans;
    }
};