1. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
分析：第一个想法是先对数组排序，如果某数字出现次数超过一半，那么排序后数组第 size/2 位置的数一定是它；但如果不存在出现次数超过一半的数，那么第 size/2 位置的数就不应该被输出。因此我们再次遍历数组计数该数字出现的次数，以排除符合条件的数并不存在的情况。时间复杂度是 O(nlogn)，空间复杂度是 O(1)。附官方解答，有个候选法，时间复杂度减小到 O(n)，主要思想在链接里有描述。先记录一下，以后再看。

class Solution {
public:int MoreThanHalfNum_Solution(vector<int> numbers) {int size = numbers.size(), i, cnt=0;sort(numbers.begin(), numbers.end());for(i=0; i<size; ++i)if(numbers[size/2]==numbers[i]){++cnt;if(cnt>size/2) return numbers[i];}return 0;}
};

2. 最小的k个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
分析：本题可以用快排的思想解决。然后注意边界细节！！

class Solution {
public:vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {vector<int> ret;int size = input.size(), l=0, r=size-1;if(k==0 || k>size) return ret;if(k==size) return input;while(1){int lc =l, rc = r;while(l<r){while(l<r && input[r]>=input[lc]) --r;while(l<r && input[l]<=input[lc]) ++l;swap(input[r], input[l]);}swap(input[lc],input[r]);if(l+1==k) break;else if(l+1>k) l=lc;else{l = l+1;r = rc;}}copy(input.begin(),input.begin()+k, back_inserter(ret));return ret;}
};

3. 连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
分析：这是一个动态规划的题目，如果前面n个数的和是负数，那它一定不会为接下来的数据带来增益，所以直接抛弃，否则即使当前数是负数也要留下，或许之后会有更大的数出现弥补损失。每次得到一个新的和，都去更新 ret，虽然可能并不一定会更新。还有一个很绕的地方是每次循环要做什么工作，见代码的注释。

class Solution {
public:int FindGreatestSumOfSubArray(vector<int> array) {int size=array.size(), i, sum=0, ret=INT_MIN;if(size==0) return 0;for(i=0; i<size; ++i){//每次循环讨论要不要array[i]sum += array[i];ret = (ret<sum)?sum:ret;if(sum<=0) sum=0;}return ret;}
};

4. 从1到n所有整数中1出现的个数

求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）
分析：可以这样考虑：从 1 到 n 所有整数中 1 出现的次数等于 1 在各个数位出现的次数之和。所以问题简化为如何求 1 在某一数位上出现的次数。
假设某五位数为 abcde，那么除去万位和个位外，1 出现在十位百位千位的规律是一致的。此处以百位为例，如果c==0，则百位为 1 的情况有 ab00 （ab*100）种 [0000--a(b-1)99]；如果c==1，则有 abde+1 种情况 [0000--abde]；如果 c>1，则有 a(b+1)00（a（b+1）*100） 种情况 [0000--ab99]。
考虑 1 出现在最高位的情况，首先可以肯定的是最高位一定不是 0。当 a==1 时，则最高位为 1 的情况有 abde+1 种情况 [0000--abde]；当 a>1 时，则最高位为 1 的情况有 10000 种[0000--9999]。
考虑 1 出现在最低位的情况，当 e==0 时，有 abcd 种情况 [0000--abd(e-1)]；当 e>0 时，有 abcd+1 种情况 [0000--abde]。

class Solution {
public:int pow(int base, int exp){if(exp == 0) return 1;int ret = base;while(--exp)ret *= base;return ret;}int NumberOf1Between1AndN_Solution(int n){int nc=n, digit=0, sum=0;while(nc){nc /= 10;++digit;}for(int i=0; i<digit; ++i){if(i!=0 && i!=digit-1){int number = n/pow(10, i)%10;if(number>1) sum += (n/pow(10, i+1)+1) * pow(10, i);else if(number==1) sum += n/pow(10, i+1)*pow(10, i)+n%pow(10, i)+1;else sum += n/pow(10, i+1)*pow(10, i);}else if(i==0){sum += n/10+(n%10>=1?1:0);}else{sum += n/pow(10, i)>1?pow(10, i):n%pow(10, i)+1;}}return sum;}
};