5/18题解

1.乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
思路：


方案一：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<int> vec1(nums),vec2(nums);//代表fmax与fmin
        for(int i=1;i<nums.size();i++)
        {
            vec1[i]=max(vec1[i-1]*nums[i],max(vec2[i-1]*nums[i],nums[i]));//找最大的数*正数，最小的数*负数，这个数的最大
            vec2[i]=min(vec1[i-1]*nums[i],min(vec2[i-1]*nums[i],nums[i]));//找最大的数*正数，最小的数*负数，这个数的最小
        }
        return *max_element(vec1.begin(),vec1.end());//返回最大值
    }
};

方案二（简化）

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            int mx = maxF, mn = minF;
            maxF = max(mx * nums[i], max(nums[i], mn * nums[i]));
            minF = min(mn * nums[i], min(nums[i], mx * nums[i]));
            ans = max(maxF, ans);
        }
        return ans;
    }
};

2.表示数字的字符串

class Solution {
public:
    bool isNumeric(char* string)
    {
//注意表示数值的字符串遵循的规则；
//在数值之前可能有一个“+”或“-”，接下来是0到9的数位表示数值的整数部分，如果数值是一个小数，那么小数点后面可能会有若干个0到9的数位
//表示数值的小数部分。如果用科学计数法表示，接下来是一个‘e’或者‘E’，以及紧跟着一个整数（可以有正负号）表示指数。
        if(string==NULL) return false;
        if(*string=='\0') return false;
        if(*string=='+'||*string=='-')
            string++;
        int dot=0,num=0,e=0;//记录小数点，数字和e的个数
        while(*string!='\0')
        {
            if(*string>='0'&&*string<='9')//是数字num+1，继续执行
            {
                num++;
                string++;
            }
            else if(*string=='.')
            {
                if(dot>0||e>0)
                    return false;//出现两个小数点，或e后面有小数点
                dot++;
                string++;
            }
            else if(*string=='e'||*string=='E')
            {
                if(e>0||num==0) return false;//若多余一个e或前面没数字，错误
                e++;
                string++;
                if(*string=='\0') return false;//后面要有数
                if(*string=='+'||*string=='-')
                    string++;//后面为正负号则继续
            }
            else
                return false;    
        }
        return true;
    }
};

3.字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"

class Solution
{
public:
  //Insert one char from stringstream
        //1、用一个128大小的数组统计每个字符出现的次数
        //2、用一个队列，如果第一次遇到ch字符，则插入队列；其他情况不在插入
        //3、求解第一个出现的字符，判断队首元素是否只出现一次，如果是直接返回，否则删除继续第3步骤
    int count[128]={0};
    queue <char> res;
    void Insert(char ch)
    {
         count[ch]++;
        if(count[ch]==1)
            res.push(ch);
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
         while(!res.empty()&&count[res.front()]>=2)//如果不为空且队首元素数量大于2，则pop
             res.pop();
         if(res.empty())
             return '#';
        return res.front();
    }
};