牛客网-剑指offer-11

这里想到的是，要对数组里面的所有数进行一个排序：不只是排长度，还要排最高位的大小。于是可以通过c++的STL的排序，通过自己定义的一个谓语比较函数。在这个比较函数里，把整数转成string进行比较，但是想到string的长度不一样的话也没法比较字符的大小了。所以分别将两个数加在一起，前后顺序不同，这样string的长度就一样了，比较的就是顺序了。
代码如下：
class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        string result;
        sort(numbers.begin(),numbers.end(),cmp);
        for(int i=0;i!=numbers.size();++i){
            result+=to_string(numbers[i]);
        }
        return result;
    }
    static bool cmp(int a,int b){
        string A=to_string(a)+to_string(b);
        string B=to_string(b)+to_string(a);
        return A<B;
    }
};

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index==0)
            return 0;  //解决边界条件
        vector<int> result(index);
        result[0]=1;
        int x=0,y=0,z=0,i;
        for(i=1;i<index;i++){
            result[i]=min(result[x]*2,min(result[y]*3,result[z]*5));
            if(result[i]==result[x]*2)
                x++;
            if(result[i]==result[y]*3)
                y++;
            if(result[i]==result[z]*5)
                z++;
        }
        return result[index-1];
    }
};

很容易想到的一种复杂度为O(n)的算法是采用哈希表，遍历一次，将出现的字符放在键中，出现一次即在值中加1。第二次遍历，直接查找该键对应的值，第一个为1的输出即可。当然，这里由于是字符，所以可以直接采用数组的形式。 一定要记得对数组进行初始化
class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if(str.size()==0)
            return -1;        //处理边界条件
        int res[256]={0};  //局部变量，一定要初始化啊
        int i=0;
        for(;i!=str.size();++i){
            res[(int)str[i]]++;
        }
        for(i=0;i!=str.size();++i){
            if(res[(int)str[i]]==1)
                return i;
        }
        return str.size();
    }
};