【算法】奇数在偶数后、反转字符串中的单词

目录

奇数在偶数后

解法一：双指针

复杂度

解法二：插入排序思想

复杂度

反转字符串中的单词

解法一：栈

复杂度

解法二：双指针

复杂度

奇数在偶数后

题目描述：

输入一个整数数组，实现一个接口来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

解法一：双指针

#include <vector>
#include <algorithm> //std::swap
using namespace std;
class Solution
{
    public:
    //双指针
    void Func(vector<int>& v)
    {
        int left = 0,right=v.size();
        while(left<right)
        {
            while((left<right)&&(v[left] & 1))
            {
                left++;
            }
            while((left<right)&& !(v[right] & 1))
            {
                right--;
            }
            swap(v[left],v[right]);
        }
    }

复杂度

时间复杂度：O(n)

空间复杂度：O(1)

进阶：如果要求奇数与奇数、偶数与偶数之间的相对位置不变，该如何实现接口?

解法二：插入排序思想

void sort(vector<int>& v)
{
    int size = v.size();
    int k = 0;
    for (int i = 0;i < size;++k)
    {
        if ((v[i] & 1) == 1) //判断是否为奇数
        {
            int j = i;
            int tmp = v[i];
            while (k < j)
            {
                v[j] = v[j - 1];
                --j;
            }
            v[k++] = tmp;
        }
    }
}

复杂度

时间复杂度：O(n^2) (平均情况)

空间复杂度：O(1)

反转字符串中的单词

题目描述：

解法一：栈

遍历字符串，然后注意处理空格，将单词push到栈中，然后出栈即可。

class Solution {
public:
    string reverseWords(string s) {
        int size = s.size();
        string res;
        stack<string> mystack;
        for(int i = 0;i<size;++i)
        {
            if(' ' == s[i])
            {
                if(!res.empty())
                {
                    mystack.push(res);
                    res.clear();
                }
            }
            else
            res.push_back(s[i]);
        }
        while(!mystack.empty())
        {
            if(!res.empty())
            res += ' ';
            res += mystack.top();
            mystack.pop();
        }
        //处理res中最后一个' '  //这种写法很挫，因此上面对该代码做了优化，如果res不为空就给添加' '
        // size = res.size();
        // res.erase(size-1);
        return res;
    }
};

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

解法二：双指针

思路图示：

string reverseWords(string s) {
        //首先反转给定字符串s
        std::reverse(s.begin(),s.end());
        int size = s.size();
        int index = 0;
        for(int i = 0;i < size;++i)
        {
            if(s[i] != ' ')
            {
                if(index != 0)
                s[index++] = ' ';
                int start = i;
                while(start < size && s[start] != ' ')
                {
                    s[index++] = s[start++];
                }
                //对每个单词进行反转
                std::reverse(s.begin()+index-(start-i), s.begin()+index);
                i = start;
            }
        }
        s.erase(index); //s.erase(s.begin()+index,s.end());删除后面的空格
        return s;
        //index相当于一个慢指针
        //start相当于一个临时快指针

复杂度

时间复杂度：O(n)

空间复杂度：O(1)