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;
    }
};