1.2万

### 题目描述

#### 样例

示例 1：

1, 2, 3
3, 4, 5

1, 2, 3, 4, 5
3, 4, 5



#### 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;
}
};


### 题目描述

#### 样例

示例 1：

0 <= n <= 5 * 106


#### 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;
}
};


### 题目描述

#### 样例

示例 1：

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


#### 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;
}
};


### 题目描述

#### 样例

示例 1:

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


#### 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;
}
};


### 题目描述

#### 样例

示例 1：

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


#### 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;
}
};


### 题目描述

#### 样例

示例 1:



#### 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;
}
};


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 = [ 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++ 代码

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;
}


### 题目描述

#### 样例

示例 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;
}
};