1.最长不含重复字符的子字符串
思路：采用动态规划的思想，定义函数f(i)表示以第i个字符结尾的不包含重复字符的子字符串的最长长度。如果第i个字符之前没出现过，那么f(i)=f(i-1)+1.如果第i个字符之前已经出现过，那么就分为两种情况，我们计算第i个字符和它上次出现在字符串中的位置的距离，并记作d，如果d<=f(i-1)，意味着此时第i个字符上次出现在f(i-1)对应的最长子字符串中，因此f(i)=d，这同时也意味着在第i个字符出现两次所夹的子字符串中再也没有其他重复的字符了；如果d>f(i-1)，那么f(i)=f(i-1)+1。

int longestSubstringWithoutDumplication(const std::string& str)
{
    int curLength=0;
    int maxLength=0;
    int* position=new int[26];//存储每个字符上次出现在字符串中位置的下标
    for(int i=0;i<26;i++)
    {
        position[i]=-1;
    }
    for(int i=0;i<str.length();i++)
    {
        int preIndex=position[str[i]-'a'];
        if(preIndex<0||i-preIndex>curLength)
        {
            curLength++;//没出现过或d>f(i-1),f(i)=f(i-1)+1;
        }
        else
        {
            if(curLength>maxLength)
            {
                maxLength=curLength;//出现过，就与最终结果做对比
            }
            curLength=i-preIndex;//f(i)=d;
        }
        position[str[i]-'a']=i;//更新位置
    }
    if(curLength>maxLength)
    {
        maxLength=curLength;
    }
    delet[] position;
    return maxLength;
}

2.丑数
PS：只包含因子2,3,5的数称为丑数，求第1500个丑数。（1是第一个丑数）
思路1：因为丑数只能被2,3,5整除，因此如果一个数能被2整除，就连续除以2，如果最后得到的数是1，那么这个数就是丑数，否则将不是。(此方***超时)

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index<=0) return 0;
        int count=0;
        int num=0;
        while(count<index)
        {
            num++;
            if(IsUgly(num))
            {
                count++;
            }
        }
        return num;

    }
    bool IsUgly(int number)
    {
        while(number%2==0)
            number/=2;
        while(number%3==0)
            number/=3;
        while(number%5==0)
            number/=5;
        if(number==1)
            return true;
        else
            return false;
    }
};

思路2：以空间换时间，创建一个数组，里面是排好序的丑数，每个丑数都是前面的丑数城以2,3,5得到的。我们设置三个指针，首先都在数组头，这三个指针分别用来乘2，乘3，乘5，每次选择他们中的最小值放入数组的下一个坐标中，然后移动这几个指针，让这几个指针所指的数都大于等于目前已经存好的丑数，然后返回数组尾部的数字。

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        // 0-6的丑数分别为0-6
        if(index < 7) return index;
        //p2，p3，p5分别为三个队列的指针，newNum为从队列头选出来的最小数
        int p2 = 0, p3 = 0, p5 = 0, newNum = 1;
        vector<int> arr;
        arr.push_back(newNum);
        while(arr.size() < index) {
            //选出三个队列头最小的数
            newNum = min(arr[p2] * 2, min(arr[p3] * 3, arr[p5] * 5));
            //这三个if有可能进入一个或者多个，进入多个是三个队列头最小的数有多个的情况
            if(arr[p2] * 2 == newNum) p2++;
            if(arr[p3] * 3 == newNum) p3++;
            if(arr[p5] * 5 == newNum) p5++;
            arr.push_back(newNum);
        }
        return arr.back();
    }
};

3.第一个只出现一次的字符
问题1：找出字符串中第一个只出现一次的字符。
思路：建立一个哈希表，key是不同的字符，value是每个字符出现的次数。

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if(str.length()<=0) return -1;
        //利用数组实现哈希表，key是下标，value是数组的值
        int alpha[256]={0};
        for(int i=0;str[i]!='\0';i++)
        {
            alpha[str[i]]++;//记录次数
        }
        for(int i=0;str[i]!='\0';i++)
        {
            if(alpha[str[i]]==1)
                return i;//返回第一个
        }
        return -1;
    }
};