牛客网-剑指offer-10

T28：最小的K个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

• 解法一：剑指offer上给的有两种办法，一种是对数组进行排序，类似于快速排序的方式，假设基于第k个数来调整，就可以将比k小的数全放在左边，比k大的数都放在右边，于是，最后k左边的数即为最小的k个数。 优点：平均时间复杂度：O(n)，思路较快 缺点：需要修改数组
• 解法二：算法复杂度O(nlogk)，适合海量的数据。需要我们一个能存储k个数的容器，当容器中的数不足k个的时候，直接装进容器，当超过的时候，需要拿容器中最大的数与新的数进行比较，新数小的时候，替换已有的最大。如此，每一个新的数都需要判断，这样会增加复杂度，但是在海量数据处理的时候比较适合，因为无法一次把所有的数据都载入内存。 下面是解法二的代码：（没有采用multiset，直接用的vector排序的，原理一样，但是我的stl确实没有用好，下次再改吧）

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        //没有考虑复杂度的情况，都是直接写的
        vector<int> result;
        //判断输入为空，或者k大于input的个数的情况
        if(input.size()<=0||k==0||k>input.size())
            return result;
        vector<int>::iterator iter=input.begin();
        for(;iter!=input.end();++iter){
            sort(result.begin(),result.end());
            if(result.size()<k)
                result.push_back(*iter);
            else if(*iter<*(result.end()-1)){
                result.pop_back();
                result.push_back(*iter);
            }
        }
        return result;
    }
};

T29：连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)

主要是想为什么会有最大的和，一个情况是，新加上的数比原来的数都要大，就要开始考虑需不需要原来的数了。所以我们需要两个数，一个保存最大的和，用来返回，一个 保存当前的和，可以在适当的时候丢掉。 另一种情况，加入的数都比原来的小，即都是负数的时候，可能最大和只是一个最小的数；另外，当都是正数的时候也比较好解决。 代码如下：

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size()==0)
            return 0;
        int curSum=array[0];//注意这里不能用0，因为会出现数组值全小于0的情况
        int maxSum=array[0];
        for(int i=1;i!=array.size();++i){
            curSum+=array[i];
            if(curSum<array[i])
                curSum=array[i];
            if(maxSum<curSum)
                maxSum=curSum;
        }
        return maxSum;
    }
};

T30:整数中1出现的个数(从1到n整数中1出现的个数)

题目描述：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数

显然，最简单的思路，从1遍历到n是吧，因为要找到每个数中1的个数。先不说这个，问题的重点是，这个1的个数怎么找。 于是想到的是关于1存在的规律。比如很简单的就个位数而言，从0–9，只会出现一个1。由此想到，我们可以把n分成很多段进行计算。具体怎么分段，《剑指offer》上有个方法，不过确实有点难看明白了，就没有看，自己觉得可以按照从按10的倍数来分，1,10,100之类的，不过又有点问题，每个段内1的个数不一样，因为这样的话1的个数就不好算了。不过牛客网厉害的还是多啊，思路清晰，代码简洁。自己真的需要学习的有点多。不过后来又回头看了一下《剑指offer》上其实也是这样的。 那就直接复述一遍具体的思路吧：根据设定的整数位置，对n进行分割。这里就直接选10了，高位是a=n/10，低位是b=n%10，循环条件直接就是n*10了，这样就可以从最后一位到最高位的遍历了。 这里需要考虑的就是，a的最后一位，就是高位对应的最低位。

• 当i表示百位，且百位对应的数>=2,如n=31456,i=100，则a=314,b=56，此时百位为1的次数有a/10+1=32（最高两位0~31），每一次都包含100个连续的点，即共有(a%10+1)*100个点的百位为1。
• 当i表示百位，且百位对应的数为1，如n=31156,i=100，则a=311,b=56，此时百位对应的就是1，则共有a%10(最高两位0-30)次是包含100个连续点，当最高两位为31（即a=311），本次只对应局部点00~56，共b+1次，所有点加起来共有（a%10*100）+(b+1)，这些点百位对应为1。
• 当i表示百位，且百位对应的数为0,如n=31056,i=100，则a=310,b=56，此时百位为1的次数有a/10=31（最高两位0~30）。 代码如下：

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int count=0;
        //n=1的情况
        if(n==1)
            return 1;
        //考虑的边界情况，n=10,100,1000之类的，同时循环中没有考虑n=0的情况
        if(n>1&&n%10==0)
            count++;
        //没有考虑n=1的情况
        for(int i=1;i<n;i*=10){
            int a=n/i,b=n%i;
            //补8的效果：当百位为0，则a/10==(a+8)/10，
            //当百位>=2，补8会产生进位位，效果等同于(a/10+1)
            count+=(a+8)/10*i+(a%10==1)*(b+1);

        }
        return count;
    }
};