当前位置:网站首页>LeetCode_Nov_5th_Week
LeetCode_Nov_5th_Week
2022-08-04 06:30:00 【KuoGavin】
November 29th : 786. 第 K 个最小的素数分数
December 1st : 1446. 连续字符
December 2nd : 506. 相对名次
December 3rd : 1005. K 次取反后最大化的数组和
December 4th : 383. 赎金信
November 29th : 786. 第 K 个最小的素数分数

class Solution {
public:
vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
int n = arr.size();
auto cmp = [&](const pair<int, int>& x, const pair<int, int>& y) {
//Fractions are cross-multiplied,The comparison relationship can be obtained as follows:
return arr[x.first] * arr[y.second] > arr[x.second] * arr[y.first];
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
//Initialize the elements in the priority queue,将n-1The elements in the list are added to the priority queue
for (int j = 1; j < n; ++j) q.emplace(0, j);
//Take the smallest value from the priority queue in order,And join the next smallest value in the corresponding list,循环k次,The head of the priority queue is what is requested
for (int _ = 1; _ < k; ++_) {
auto [i, j] = q.top();
q.pop();
if (i + 1 < j) q.emplace(i + 1, j);
}
return {
arr[q.top().first], arr[q.top().second]};
}
};
/********************************************************************************************/
//brutal force. 超时
class Solution {
public:
vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
unordered_map<float, vector<int>> mp;
priority_queue<float, vector<float>, greater<float>> pq;
for(int i = 0; i < arr.size(); ++i) {
for(int j = i+1; j < arr.size(); ++j) {
float frac = (float)arr[i] / (float)arr[j];
pq.push(frac);
mp[frac] = {
arr[i], arr[j]};
}
}
while(k-- != 1) {
cout << pq.top() << endl; pq.pop();};
return mp[pq.top()];
}
};
December 1st : 1446. 连续字符
典型的滑动窗口问题,Whether the characters newly added to the window are consistent with the characters in the window,If they are consistent, the window will expand,If not, reset the window.
class Solution {
public:
int maxPower(string s) {
int ret = 0, l = 0, r = 0;
while(r < s.size()) {
if(s[l] == s[r]) ret = max(ret, r-l+1);
else l = r;
r++;
}
return ret;
}
};
December 2nd : 506. 相对名次
哈希表+排序,时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn).
class Solution {
public:
vector<string> findRelativeRanks(vector<int>& score) {
unordered_map<int, int> mp;
vector<string> vecStr(score.size());
for(int i = 0; i < score.size(); ++i) mp[score[i]] = i;
sort(score.begin(), score.end(), greater<int>());
vecStr[mp[score[0]]] = "Gold Medal";
if(score.size() > 1) vecStr[mp[score[1]]] = "Silver Medal";
if(score.size() > 2) vecStr[mp[score[2]]] = "Bronze Medal";
for(int i = 3; i < score.size(); ++i) vecStr[mp[score[i]]] = to_string(i+1);
return vecStr;
}
};
open anotherO(n+k)的数组,进行一次遍历,Get each score inscore数组中的下标,Then traverse the array from left to right,And modify the resulting string array according to the table below.
class Solution {
public:
vector<string> findRelativeRanks(vector<int>& score) {
int max_score = *max_element(score.begin(), score.end()); //Get the maximum value of the score
vector<int> index(max_score + 1, -1); // 申请一个包含max+1个全是-1的数组
// Set the value at the corresponding subscript of this element to the index subscript in the original array
for(int i = 0; i < score.size(); i++) index[score[i]] = i;
vector<string> vecStr(score.size());//存放输出结果
int rank = score.size(), j = 0; //rank排名, j是index数组的下标.
while(rank > 0){
if(index[j] != -1){
if(rank == 1) vecStr[index[j]] = "Gold Medal";
else if(rank == 2) vecStr[index[j]] = "Silver Medal";
else if(rank == 3) vecStr[index[j]] = "Bronze Medal";
else vecStr[index[j]] = to_string(rank);
rank--;
}
j++;
}
return vecStr;
}
};
December 3rd : 1005. K 次取反后最大化的数组和
Sorts an array by the absolute value of the numbers in the array,Then invert the non-positive numbers in it,If the non-positive number is greater than k k k 个,Then if the remaining inversion times are even, the sum of the array can be directly returned,If it is odd, it will be the first element of the array/The element with the smallest absolute value is reversed and returned to the array to accumulate the sum.
//思想:If they can be all non-negative numbers, they will all become non-negative numbers,
//If all are non-negative, there are still an odd number of inversions remaining,
//Then the smallest non-negative number after the reversal operation is reversed and returned to the accumulated sum
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size() && k > 0; ++i) {
if(nums[i] > 0) break;
nums[i] = -nums[i];
k--;
}
sort(nums.begin(), nums.end()); //Get the new numerical ordering,A non-positive number with a larger absolute value was previously inverted
if(k & 0x1) return -nums[0] + accumulate(nums.begin()+1, nums.end(), 0);
else return accumulate(nums.begin(), nums.end(), 0);
}
};
/*********************************************************************************************************/
//more intuitive
class Solution {
static bool cmp(int a, int b) {
return abs(a) > abs(b);}
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), cmp); //按照绝对值大小排序,大的在前
for (int i = 0; i < nums.size() && k > 0; ++i) {
//遍历数组,Reverse non-negative numbers
if (nums[i] < 0) {
nums[i] = -nums[i];
k--;
}
}
if (k & 0x1) nums[nums.size() - 1] *= -1; //If there are an odd number of inversion operations remaining,Invert the number with the smallest absolute value
return accumulate(nums.begin(), nums.end(), 0); //Returns the cumulative sum of the array
}
};
December 4th : 383. 赎金信
统计 m a g a z i n e magazine magazineThe frequency of the characters in it,然后对应 r a n s o m − n o t e ransom-note ransom−noteThe frequency of characters in .If it traverses the whole r a n s o m − n o t e ransom-note ransom−note,所有 m a g a z i n e magazine magazineThe frequency of characters in is greater than or equal to r a n s o m − n o t e ransom-note ransom−noteThe character frequency is returnedtrue
,否则返回false
.
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int dict[26] = {
0};
//vector<int> dict(26, 0);
for(int i = 0; i < magazine.size(); ++i) dict[magazine[i]-'a']++;
for(int i = 0; i < ransomNote.size(); ++i) {
if(dict[ransomNote[i]-'a'] == 0) return false;
dict[ransomNote[i]-'a']--;
}
return true;
}
};
边栏推荐
- MVC自定义配置
- 第一章 绪论
- LeetCode_Nov_1st_Week
- Comparison of oracle's number and postgresql's numeric
- 卷积神经网络入门详解
- 安装MySQL的详细步骤
- 度量学习(Metric learning)—— 基于分类损失函数(softmax、交叉熵、cosface、arcface)
- 【Copy攻城狮日志】飞浆学院强化学习7日打卡营-学习笔记
- (Navigation page) OpenStack-M version - manual construction of two nodes - with video from station B
- Amazon Cloud Technology Build On-Amazon Neptune's Knowledge Graph-Based Recommendation Model Building Experience
猜你喜欢
随机推荐
Comparison of oracle's number and postgresql's numeric
审稿意见回复
第二章 STA相关概念
Copy Siege Lions "sticky" to AI couplets
Copy攻城狮5分钟在线体验 MindIR 格式模型生成
tensorRT5.15 使用中的注意点
arm-3-中断体系结构
【Copy攻城狮日志】飞浆学院强化学习7日打卡营-学习笔记
【论文阅读】Multi-View Spectral Clustering with Optimal Neighborhood Laplacian Matrix
[Copy Siege Lion Log] Flying Pulp Academy Intensive Learning 7-Day Punch Camp-Study Notes
LeetCode_22_Apr_2nd_Week
(Navigation page) OpenStack-M version - manual construction of two nodes - with video from station B
TensorRT 5 初步认识
集合--LinkedList
详解近端策略优化
Copy Siege Lion 5-minute online experience MindIR format model generation
LeetCode_22_Apr_4th_Week
lstm pipeline 过程理解(输入输出)
Tencent and NetEase have taken action one after another. What is the metaverse that is so popular that it is out of the circle?
MNIST手写数字识别 —— 基于Mindspore快速构建感知机实现十分类