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