链表找环

15

请编写函数，功能为对于一个字符串s，反转其中所有的辅音字母，并返回结果字符串。
举例：
s=“good”
输出：“doog”

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    //判断是否是元音字母
    string a = "aeiou";
    //大写字母转小写
    char my_tolower(char c) {
        if(c >= 'A' && c <= 'Z') {
            char x = c + 32;
            return x;
        }
        return c;
    }
    bool check(char c) {
        //如果元音字符串中找得到c，返回true
//        return a.find(my_tolower(c)) != -1;
        return a.find(tolower(c)) != -1;
    }
    string reverseConsos(string s) {
        //双指针
        for(int i = 0, j = s.size() - 1; i < j; i ++, j --) {
            while(i < j && check(s[i])) i ++;
            while(i < j && check(s[j])) j --;
            swap(s[i], s[j]);
        }
        return s;
    }
};
int main()
{
    Solution s;
    string a;
    cin >> a;
    cout << s.reverseConsos(a) << endl;
}

16

给定整数数组（有正数、有负数），找出总乘积最大的连续数列，返回此最大的总乘积的值。（假设不会产生整数的溢出问题）
函数原型：int findMaxProduct(int *pArr, int arrLen)
举例：
输入：2，-8，3，6，4
输出：18（也就是序列（3，6）的乘积）

DP

• 状态表示：

f[i]：前i个数中，总乘积最大的连续数列的最大乘积
g[i]：前i个数中，总乘积最小的连续数列的最小乘积

• 状态计算

f[i]=

g[i]=

• 时间复杂度 = 状态数量（n)*每个状态转移时间（1） = O(n)

  class Solution {
  public:
    int maxProduct(vector<int>& nums) {
        //一维状态f[i],g[i]可以用f,g一个数表示，并都用nums[0]初始化
        int f = nums[0], g = nums[0];
        int res = nums[0];//记录结果
        for(int i = 1; i < nums.size(); i ++)
        {
            int a = nums[i], fa = a * f, ga = a * g;
            f = max(a, max(fa, ga));
            g = min(a, min(fa, ga));
            res = max(res, f);
        }
        return res;
    }
  };