数组/字符串

目录

1768 交替合并字符串?

1431 拥有最多糖果的孩子

605 种花问题

345 反转字符串中的元音字母

1768 交替合并字符串?

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int n = max(word1.size(),word2.size());
        string res;
        for(int i = 0;i < n;i++){
            if(i < word1.size()){
                res += word1[i];
            }
            if(i < word2.size()){
                res += word2[i];
            }
        }
        return res;
    }
};

时间复杂度O(n+m)

空间复杂度O(1)

1431 拥有最多糖果的孩子

class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        vector<bool>res(candies.size());
        int mx = -1;
        for(auto candy : candies){
            mx = max(mx,candy);
        }
        for(int i = 0;i < candies.size();i++){
            if(candies[i] + extraCandies >= mx){
                res[i] = true;
            }
        }
        return res;
    }
};

时间复杂度O(n)

空间复杂度O(1)

605 种花问题

数组前后都加上0，全部统一起来处理。?

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int res = 0;
        flowerbed.insert(flowerbed.begin(),0);
        flowerbed.push_back(0);
        for(int i = 1;i < flowerbed.size() - 1;i++){
            if(flowerbed[i] == 0 && flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0){
                res++;
                flowerbed[i] = 1;
            }
        }
        return res >= n;
    }
};

时间复杂度O(n)

空间复杂度O(1)

345 反转字符串中的元音字母

注意边界问题?

class Solution {
public:
    string reverseVowels(string s) {
        unordered_set<char>set{'a','e','i','o','u','A','E','I','O','U'};
        int l = 0;int r = s.size() - 1;
        while(r > l){
            while(r > l && !set.count(s[l]))l++;
            while(r > l && !set.count(s[r]))r--;
            if(r > l){
                s[l] ^= s[r];
                s[r] ^= s[l];
                s[l] ^= s[r];
            }
            l++;r--;
        }
        return s;
    }
};

时间复杂度O(n)

空间复杂度O(1)