labuladong日常刷题-差分数组 | LeetCode 1109航班预定统计 | 花式遍历 151反转字符串里的单词

发布时间:2024年01月01日

差分数组–前缀和数组的升级

LeetCode 1109 航班预定统计 2024.1.1

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        //构建航班人数数组,数组大小为n,初始化为0
        vector<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

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

文章来源:https://blog.csdn.net/weixin_66706867/article/details/135328074
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。