头像

只要是你呀ღ

华北水利水电大学




离线:20小时前



题目描述

给你一个按升序排序的整数数组 num(可能包含重复数字),请你将它们分割成一个或多个子序列,其中每个子序列都由连续整数组成且长度至少为 3 。

如果可以完成上述分割,则返回 true ;否则,返回 false 。

样例

示例 1:

输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 : 
1, 2, 3
3, 4, 5

示例 2:

输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 : 
1, 2, 3, 4, 5
3, 4, 5

示例 3:

输入: [1,2,3,4,4,5]
输出: False

提示:

输入的数组长度范围为 [1, 10000]

思路

看完官方的题解,wc,真nb,我真fw
这一题的思路是这样的,由于需要将数组分割成一个或多个由连续整数组成的子序列,因此只要知道子序列的最后一个数字和子序列的长度,就能确定子序列。
当x在数组中时,如果存在一个子序列以x-1结尾,长度为k,则可以将x加入该子序列中,得到长度为k+1的子序列。如果不存在以x-1结尾的子序列,则必须新建一个只包含x的子序列,长度为1。
当x在数组中时,如果存在多个子序列以x-1结尾,应该让最短的子序列尽可能长,因此应该将x加入其中最短的子序列。
通过哈希表加小根堆来实现上述操作。
哈希表的键为子序列的最后一个数字,值为小根堆,存储以该数字结尾的子序列的长度。最小堆满足堆顶的元素是最小的,因此堆顶的元素即为最小的子序列长度。
遍历数组,当遍历到元素x时,可以得到一个以x结尾的子序列。
如果哈希表中存在以x−1结尾的子序列,则取出以x−1结尾的最小的子序列长度,将子序列长度加1之后作为以x结尾的子序列长度。此时,以x−1结尾的子序列减少了一个,以x结尾的子序列增加了一个。
如果哈希表中不存在以x−1结尾的子序列,则新建一个长度为1的以x结尾的子序列。
由于数组是有序的,因此当遍历到元素x时,数组中所有小于x的元素都已经被遍历过,不会出现当前元素比之前的元素小的情况。
遍历结束之后,检查哈希表中存储的每个子序列的长度是否都不小于3,即可判断是否可以完成分割。由于哈希表中的每条记录的值都是最小堆,堆顶元素为最小的子序列长度(以当前的键为最后一个数字的子序列),因此只要遍历每个最小堆的堆顶元素,即可判断每个子序列的长度是否都不小于3。

C++ 代码

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, priority_queue<int, vector<int>, greater<int>>> mp;
        for(auto i : nums) {
            if(mp.find(i) == mp.end()) {
                mp[i] = priority_queue<int, vector<int>, greater<int>>();
            }
            if(mp.find(i - 1) != mp.end()) {
                int prelen = mp[i - 1].top();
                mp[i - 1].pop();
                if(mp[i - 1].empty()) 
                    mp.erase(i - 1);
                mp[i].push(prelen + 1);            
            }
            else {
                mp[i].push(1);
            }
        }
        for(auto it = mp.begin(); it != mp.end(); it ++) {
            priority_queue<int, vector<int>, greater<int>> q = it -> second;
            if(q.top() < 3)
                return false;
        }
        return true;
    }
};




题目描述

统计所有小于非负整数 n 的质数的数量。

样例

示例 1:

输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2:

输入:n = 0
输出:0

示例 3:

输入:n = 1
输出:0

提示:

0 <= n <= 5 * 106

思路(埃氏筛法求质数)

这一题很简单,模板题
模板在算法基础课 第四讲数学知识 质数
链接:https://www.acwing.com/problem/content/870/
如果不会了可以看看y总的视频讲解,肯定比我写的好,所以我就不写这个算法的思路了。ヾ(゚∀゚ゞ)

C++代码

class Solution {
public:
    int countPrimes(int n) {
        int cnt = 0;
        vector<int> primes(n, 0);
        vector<bool> st(n, false);

        for(int i = 2; i < n; i ++)
        {
            if(!st[i])
                primes[cnt ++] = i;
            for(int j = 0; primes[j] <= n / i; j ++)
            {
                st[primes[j] * i] = true;
                if(i % primes[j] == 0)
                    break;
            }
        }

        return cnt;
    }
};




题目描述

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

进阶:

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗

样例

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:

输入:nums = [], target = 0
输出:[-1,-1]
 

提示:

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

思路(二分查找)

题目中说用O(logn)的时间复杂度解决,那就是用二分法查找
这一题是一道简单的模板题,题目在算法基础课第一讲
链接:https://www.acwing.com/problem/content/791/
这道题的思路就是,先创建一个vector数组,并初始化其长度为2,大小为-1
写这道题的时候需要特判一下给定数组的长度为0的情况,然后开始进行二分查找
二分查找每次都取左右端点的中间位置,然后用中间位置的值与目标值进行比对,根据比对结果移动左右端点。最后如果数组中存在目标值就把vector数组里的值更新为端点值,如果不存在就直接返回vector数组即可。

C++ 代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2, -1);
        if(nums.size() == 0)
            return res;
        int l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if(nums[l] != target)  
            return res;
        res[0] = l;
        l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        res[1] = l;
        return res;
    }
};




对不起,怪我太弱了,这题不会写。
看看官方的题解吧。


题目描述

给定一个字符串S,检查是否能重新排布其中的字母,使得两相邻的字符不同。

若可行,输出任意可行的结果。若不可行,返回空字符串。

样例

示例 1:

输入: S = "aab"
输出: "aba"
示例 2:

输入: S = "aaab"
输出: ""
注意:

S 只包含小写字母并且长度在[1, 500]区间内。

思路

假设字符串的长度为n,当n是偶数时,有n/2个偶数下标和n/2个奇数下标,因此每个字母的出现次数都不能超过n/2次,否则出现次数最多的字母一定会出现相邻。
当n是奇数时,由于共有(n+1)/2个偶数下标,因此每个字母的出现次数都不能超过(n+1)/2次,否则出现次数最多的字母一定会出现相邻。
由于当n是偶数时,在整数除法下满n/2和(n+1)/2相等,因此可以合并n是偶数与n是奇数的情况:如果可以重新排布成相邻的字母都不相同的字符串,每个字母最多出现(n+1)/2次。
因此首先遍历字符串并统计每个字母的出现次数,如果存在一个字母的出现次数大于(n+1)/2,则无法重新排布字母使得相邻的字母都不相同,返回空字符串。如果所有字母的出现次数都不超过(n+1)/2,则考虑如何重新排布字母。
然后维护最大堆存储字母,堆顶元素为出现次数最多的字母。首先统计每个字母的出现次数,然后将出现次数大于0的字母加入最大堆。
当堆的元素个数大于1时每次取出两个字母构建新的字符串,然后将两个字母的出现的次数减一,如果出现次数还是大于0再继续加入到堆中。由于堆中的元素都是不同的,因此取出的两个字母一定不同,不会出现两个相同字母相邻的情况。
如果最大堆变成空,则已经完成字符串的重构。如果最大堆剩下1个元素,则取出最后一个字母,拼接到重构的字符串。
最后返回拼接完成的字符串即可。

C++ 代码

class Solution {
public:
    string reorganizeString(string S) {
        if(S.size() < 2)
            return S;
        vector<int> v(26, 0);
        int maxCount = 0;
        for(int i = 0; i < S.size(); i ++) // 统计每个字母的个数同时找出出现次数最多的次数
        {
            v[S[i] - 'a'] ++;
            maxCount = max(maxCount, v[S[i] - 'a']);
        }
        if(maxCount > (S.size() + 1) / 2) // 如果最大出现次数大于(n + 1) / 2 则直接返回空字符串
            return "";
        auto cmp = [&](const char& letter1, const char& letter2) { // 定义比较函数,根据字母出现的次数排序
            return v[letter1 - 'a'] < v[letter2 - 'a'];
        };
        priority_queue<char, vector<char>, decltype(cmp)> q{cmp}; // 利用优先队列定义大根堆
        for(char i = 'a'; i <= 'z'; i ++) // 存储出现过的每个字母
            if(v[i - 'a'] > 0)
                q.push(i);
        string s = "";
        while(q.size() > 1)
        {
            char letter1 = q.top(); q.pop(); // 取出堆中的两个字母
            char letter2 = q.top(); q.pop();
            s += letter1, s += letter2;
            v[letter1 - 'a'] --, v[letter2 - 'a'] --; // 出现次数减一
            if(v[letter1 - 'a'] > 0) // 如果出现次数不为零,继续加入到堆中
                q.push(letter1);
            if(v[letter2 - 'a'] > 0)
                q.push(letter2);
        }
        if(q.size() > 0)
            s += q.top();
        return s;
    }
};




题目描述

给定由一些正数(代表长度)组成的数组 A,返回由其中三个长度组成的、面积不为零的三角形的最大周长。

如果不能形成任何面积不为零的三角形,返回 0。

样例

示例 1:

输入:[2,1,2]
输出:5

示例 2:

输入:[1,2,1]
输出:0

示例 3:

输入:[3,2,3,4]
输出:10

示例 4:

输入:[3,6,2,3]
输出:8
 

提示:

3 <= A.length <= 10000
1 <= A[i] <= 10^6

思路

这是一道简单的贪心加排序的题目
题目要求使得三角形的周长最大,如果构不成三角形则返回0
要使三角形的周长最大就要使三角形的三条边在数组中都是最长的
所以先对数组进行排序,然后从后往前遍历数组(遍历数组时要注意i == 2时就结束,否则会出现数组越界)
每次枚举相邻的三条边,如果这三条边能够构成三角形就把标记值设置为true(其实直接返回就可以了,当时写的时候不知道咋想的)
否则最后返回false。

C++ 代码

class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        int res = INT_MIN;
        sort(A.begin(), A.end());
        bool right = false;
        for(int i = A.size() - 1; i >= 2; i --)
        {
            if(A[i - 1] + A[i - 2] > A[i] && A[i] - A[i - 1] < A[i - 2])
            {
                res = max(res, A[i] + A[i - 1] + A[i - 2]);
                right = true;
            }
        }
        if(right == false)
            return 0;
        return res;
    }
};




题目描述

给定一个数组 nums ,如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

样例

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

给定数组的长度不会超过50000。
输入数组中的所有数字都在32位整数的表示范围内。

思路(归并排序)

看到题目中的翻转对就想起了基础课中的逆序对,然后比对发现好像就是一回事,所以就套用逆序对那一题的模板就好了
逆序对的存在分为三种情况,左右端点都在左半部分,左右端点都在右半部分,左端点在左半部分右端点在右半部分
其中前两种情况可以通过归并的方式进行计算
第三种方式通过双指针算法,在序列中找到第一个nums[j] * 2 >= nums[i]的点,这样j这个点到mid之间的部分全部都符合条件,把这些点的个数加入到答案中
最后输出即可

C++ 代码

class Solution {
public:
    vector<int> tmp;
    int reversePairs(vector<int>& nums) {
        return margin_sort(nums, 0, nums.size() - 1);
    }

    int margin_sort(vector<int>& nums, int l, int r)
    {
        if(l >= r)
            return 0;
        int mid = l + r >> 1;
        int res = margin_sort(nums, l, mid) + margin_sort(nums, mid + 1, r); // 通过归并求同在一部分的逆序对的个数
        for(int i = l, j = mid + 1; i <= mid; i ++) // 通过双指针求不在同一部分的点的个数
        {
            while(j <= r && nums[i] > nums[j] * 2ll) j ++;
            res += j - (mid + 1);
        }
        tmp.clear();
        int i = l, j = mid + 1;
        while(i <= mid && j <= r) // 进行归并
        {
            if(nums[i] <= nums[j])
                tmp.push_back(nums[i ++]);
            else
                tmp.push_back(nums[j ++]);
        }
        while(i <= mid) tmp.push_back(nums[i ++]);
        while(j <= r) tmp.push_back(nums[j ++]);
        for(int i = l, j = 0; j < tmp.size(); i ++, j ++)
            nums[i] = tmp[j];
        return res;
    }
};



活动打卡代码 LeetCode 542. 01 矩阵

typedef pair<int, int> PII;
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        queue<PII> q;
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> d(n, vector<int>(m, -1));
        for(int i = 0; i < matrix.size(); i ++)
        {
            for(int j = 0; j < matrix[i].size(); j ++)
            {
                if(matrix[i][j] == 0)
                {
                    q.push({i, j});
                    d[i][j] = 0;
                }
            }
        }
        while(q.size())
        {
            auto t = q.front();
            q.pop();
            int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
            for(int i = 0; i < 4; i ++)
            {
                int x = t.first + dx[i], y = t.second + dy[i];
                if(x >= 0 && x < n && y >= 0 && y < m && d[x][y] == -1)
                {
                    d[x][y] = d[t.first][t.second] + 1;
                    q.push({x, y});
                }
            }
        }
        return d;
    }
};



题目描述

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间,最终结果不会超过 231 - 1 。

样例

例如:

输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

输出:
2

解释:
两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

思路

利用哈希表来求解这道题
首先把数组C和数组D的和加入到哈希表中,同时存储每种和出现的个数(存储数组A和数组B也是可以的,都是一样的)
然后通过查找遍历数组A和数组B,使答案加上-(a + b)在哈希表中出现的次数
最后出现次数的和就为答案。

C++ 代码

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> hash;
        for(int c : C)
        {
            for(int d : D)
            {
                hash[c + d] ++;
            }
        }
        int res = 0;
        for(int a : A)
        {
            for(int b : B)
            {
                res += hash[-(a + b)];
            }
        }
        return res;
    }
};




#include <iostream>

using namespace std;

typedef long long LL;

int main()
{
    string s1, s2;
    cin >> s1 >> s2;

    LL sum1 = 1, sum2 = 1;
    for(int i = 0; i < s1.size(); i ++)
    {
        sum1 *= ((s1[i] - 'A') + 1);
        sum1 %= 47;
    }
    for(int i = 0; i < s2.size(); i ++)
    {
        sum2 *= ((s2[i] - 'A') + 1);
        sum2 %= 47;
    }

    if(sum1 == sum2)
        cout << "GO" << endl;
    else
        cout << "STAY" << endl;

    return 0;
}



恬不知耻的我看了一遍y总的讲解,然后把y总的代码拿了过来

题目描述

给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。

如果数组元素个数小于 2,则返回 0。

样例

示例 1:

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2:

输入: [10]
输出: 0
解释: 数组元素个数小于 2,因此返回 0。

说明:

你可以假设数组中所有元素都是非负整数,且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。


思路

因为题目中要求用线性的时间复杂度和空间复杂度,那么瞅了瞅这几个排序算法。呦,桶排序可以耶
所以这题的思路围绕着桶排序展开
设0~x的一个区间,在分桶的时候左开右闭,所以区间的最大值为x,最小值为1,不难发现相邻两数之间差的最大值不会取在桶内部。
用反正法,如果答案在桶内部,那么桶内部差的最大值为(x - 1),一共有n - 1个差,如果每个差都取到最大值(x - 1),那么总差值为(x - 1) * (n - 1),如果这样都小于最大值和最小值的差值,那么存在矛盾,就说明相邻两个数的差值的最大值在桶间
只要每个区间长度x满足(MAX - MIN)/ (n - 1) + 1,那么就能保证相邻两个数的差值的最大值在桶间
然后就进行桶排序,只需要找到每个桶中的最小值和最大值
然后找到桶间差的最大值即可。

C++ 代码

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        struct Range {
            int min, max;
            bool used;
            Range() : min(INT_MAX), max(INT_MIN), used(false) {}
        }; // 定义桶结构
        int Min = INT_MAX, Max = INT_MIN;
        for(auto x : nums)
        {
            Min = min(Min, x);
            Max = max(Max, x);
        } // 找到数组中的最大值和最小值
        if(nums.size() < 2 || Min == Max) // 如果数组长度小于2或者最大值等于最小值(说明数组中的数都相等)就返回0
            return 0;
        int n = nums.size();
        vector<Range> r(n - 1); // 桶的个数
        int len = (Max - Min + n - 2) / (n - 1); // 定义每个桶的长度
        for(auto x : nums) // 找到每个桶中的数值的最大值和最小值
        {
            if(x == Min)    continue;
            int k = (x - Min - 1) / len;
            r[k].used = true;
            r[k].min = min(r[k].min, x);
            r[k].max = max(r[k].max, x);
        }
        int res = 0;
        for(int i = 0, last = Min; i < n - 1; i ++) // 遍历每个桶,找出相邻桶之间差的最大值
        {
            if(r[i].used)
            {
                res = max(res, r[i].min - last);
                last = r[i].max;
            }   
        }
        return res;
    }
};