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确实没有用好,下次再改吧)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)。
    代码如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    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;
    }
    };