本文主要是介绍labuladong日常刷题-差分数组 | LeetCode 1109航班预定统计 | 花式遍历 151反转字符串里的单词,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
差分数组–前缀和数组的升级
LeetCode 1109 航班预定统计 2024.1.1
- 题目链接
- labuladong讲解[链接]
class Solution {
public:vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {//构建航班人数数组,数组大小为n,初始化为0vector<int> people(n, 0);//将人数传入差分类中构造差分数组Diff diff(people);//遍历每条预定记录,从bookings[i][0]-1(与索引差1)开始人数增加,从bookings[i][1]位置人数减少至原来for(int i = 0; i < bookings.size(); i++){int from = bookings[i][0]-1;int to = bookings[i][1];int num = bookings[i][2];//更新差分数组,从bookings[i][0]-1(与索引差1)开始人数增加,从bookings[i][1]位置人数减少至原来diff.increment(from, to, num);}//更新people数组,需要初始化people[0]people[0] = diff.diffnum[0];for(int i = 1; i < n; i++)people[i] = people[i-1]+diff.diffnum[i];//返回更新后的数组return people;}class Diff{public:vector<int> diffnum;Diff(vector<int> people){diffnum = vector<int>(people.size(), 0);}void increment(int from, int to, int num){diffnum[from] += num;if(to < diffnum.size())diffnum[to] -= num;}};
};
花式遍历
LeetCode 151 反转字符串里的单词 2024.1.1
- 题目链接
- labuladong讲解[链接]
class Solution {
public:string reverseWords(string s) {//用栈来实现/*stack<char> st;string str;for(int i = s.size()-1; i >= 0; i--){if(s[i] == ' ' && st.empty())continue;while(s[i] == ' ' && !st.empty()){str.push_back(st.top());st.pop();}if(s[i] == ' ')str.push_back(' '); if(s[i] != ' ')st.push(s[i]);}while(!st.empty()){str.push_back(st.top());st.pop();}if(str[str.size()-1] == ' ')str.pop_back();return str;*///先双指针移出不必要的空格,再整体反转,最后将每个单词反转即可得到答案//移除不必要空格int slow = 0;for(int i = 0; i < s.size(); i++){if(slow != 0 && s[i] != ' ')s[slow++] = ' ';while(i < s.size() && s[i] != ' ')s[slow++] = s[i++];}s.resize(slow);//整体反转reverse(s.begin(), s.end());//最后将每个单词反转即可得到答案int left = 0;for(int i = 0; i < s.size(); i++){if(s[i] == ' '){reverse(s.begin()+left, s.begin()+i);left = i + 1;}}reverse(s.begin()+left, s.end());return s;}
};
这篇关于labuladong日常刷题-差分数组 | LeetCode 1109航班预定统计 | 花式遍历 151反转字符串里的单词的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!