整理几道算法题

1.求子数组的最大和
题：输入一个整形数组，数组里有正数也有负数。
   数组中连续的一个或者多个整数组成一个子数组，每个子数组都有一个和。
   求所有子数组的和的最大值。要求时间复杂度为0（N)。

例如输入的数组为1,-2,3,10,-4,7,2，-5 和最大的子数组为3,10,-4,7,2
因此输出为该子数组的和18

代码：
int maxSum(int a[],int n){
int pre_sum = 0; // pre_sum 是预想的最佳子数组的和
int sum =0; // sum是最佳子数组的和
for(int i = 0;i < n;i++){
// 在遍历过程中如果发现预想的和为负，
// 立马重置pre_sum初值
// 否则继续累加
if(pre_sum < 0){
pre_sum = a[i];
}
else{
pre_sum += a[i];
}
// 遍历过程中时刻保证sum是最大的
if(sum < pre_sum){
sum = pre_sum;
}
}
return sum;
}
2.查找最小的K个元素（海量数据源）
网上有很多种解法，这里列出了我认为可行或者说比较好的两种解法
解法一：
先从数据源只取前K个数存放到大小为K的容器中，存放的时候做一下升序排序，
然后再从数据源中逐一取出其余的数与容器中的最大值进行比较，小于当前最大
值则把取出的这个数给插入到这个容器中并把当前最大值给“挤掉”。
这个算法的时间复杂度应该就是插入排序的时间复杂度。
解法二：
最大堆
先定义一个大小为K的堆容器（其实就一数组），从数据源中取出先K个数放到堆容器
中，并构建出一个最大堆出来，之后从数据源中逐一取出每一个数并与堆顶的值进行
比较，如果小于堆顶值则更新堆顶值并调整堆使之依旧是最大堆。
注意：如果需要按序输出最小K个元素，则在最后还需要将堆容器进行一次堆排序
3.不用判断、选择等语句，请写出1+2+3+...+N的值
可以采用C++的思想，构造出一个N个类C的对象，类中设置一个全局的
成员变量，在构造函数里面来实现累加。
代码：
int Temp::N = 0;
int Temp::SUM = 0;
class Temp{
public:
Temp(){
++N;
SUM += N;
}
static int GetSum(){
return SUM;
}
private:
static int N;
static int SUM;
}
int main(void){
Temp* p = new[10];
cout << p->SUM< return 0;
}
4.输入一个单向链表，输出该链表中倒数第K个结点。
丈量法
int SearchK(Link* L,int k){
int count = 0;
Link* p = L;
Link* q = L;
while(p){
if(count < k){
count++;
}
else{
q = q->next;
}
p = p->next;
}
if(count < k){
return 0;
}
else{
return q->data;
}
}
5. 输入一个已经升序排序过的整形数组和一个整数。
　　求出数组中某两个数，使得它们的和等于输入的这个整数。
代码：
bool FindTwoNumbersWithSum(int data[],int length,int sum,int* num1,int* num2){
int begin = 0;
int end = length - 1;
bool found = 0;
while(begin < end){
pre_sum = a[begin] + a[end];
if(pre_sum == sum){
found = 1;
*num1 = a[begin];
*num2 = a[end];
break;
}
esle if(pre_sum > sum){
end--;
}
else{
begin++;
}
}
return found ;
}
6.在一个字符串中找到第一个只出现一次的字符。
利用空间换时间的方法，开辟一个256个元素的整形数组用来记录每个字符出现
的次数。先遍历一遍字符串，把每个字符出现的次数记录到开辟的数组中，再
遍历这个数组找出第一个1的下标，该下标就是要找的字符。
代码：
int FindFirstChar(char str[],int length){
int cnt[256];
for(int i = 0;i < 256;i++){
cnt[i] = 0;
}
char* p = str;
while(*p){
cnt[*p]++;
p++;
}
p = str;
char ret = 0;
while(*p){
if(cnt[*p] == 1){
ret = *p;
break;
}
p++;
}
return ret;
}
7.给定一个整数N，列出从1到N的数列1、2、3。。。N中“1”出现的总次数
思路：
如果按照常规的做法，遍历所有的数列元素，一一求出“1”出现的次数，然后求和。
这种算法的时间复杂度为 0（N*N对10求对数）
另一种可行的思路是这样的（纵向求和），把各位上的1出现的次数加起来就是。
第K位上1的个数计算方法如下：
如果第K位的值大于1，用K位以上的数加1后乘以10的K-1次方；
如果第K位的值等于1，用K位以上的数乘以10的K-1次方，然后加上K位以上的数加1
如果第K位的值等于0，用K位以上的数乘以10的K-1次方

例举一个例子，12 167 ，这个数计算如下
个位上1的个数：（1216 + 1）* 1
十位上1的个数：（121 + 1）* 10
百位上1的个数：12 * 100 + （67 + 1）
千位上1的个数：（1 + 1）* 1000
万位上1的个数：2167 + 1

代码：
k = 0;
int lowVal,curVal,higVal;
while(N/pow(10,k)){
curVal = N%pow(10,k + 1);
higVal = N/pow(10,k + 1);
lowVal = N%pow(10,K);
switch(curVal){
case 1:
higVar * pow(10,k）+ (lowVar + 1) ; break;
case 0:
higVar * pow(10,k); break;
default:
       （higVar + 1）* pow(10,k) break;
}
k++;
}
8.判断两个链表是否相交（两链表为非相交链表）
思路：
常规做法是，把链表1的节点取来一一与链表2进行比对，看地址是否有相同的。
这里有另外两种解法：
一、把链表2接到链表1的最后，然后从链表2的头结节开始遍历，看是否构成环，
二、直接判断链表1和链表2的尾结节是否相同就成（如果两个非相交链表相交，
   那么从相交节点处到尾节点应该都是重合的）
9.将一个整数序列循环左移P个位置
 如：R（X0,X1,X2,X3,X4,X5,X6,X7）循环左移3个位置变成 R（X3,X4,X5,X6,X7,X0,X1,X2）
代码：
int Reverse(int a[],int left,int right){
int i = left;
int j = right;
while(i < j){
a[i++] <-> a[j++];
}
return 0;
}
int LeftShift(int a[],int n,int p){
if(p <= 0&& p >= n){
return 1;
else{
Reverse(a,0,p-1);
Reverse(a,p,n-1);
Reverse(a,0,n-1);
return 0;
}
}
10.求两个等长的升序整数序列的中位数。
  所谓中位数指的是一个序列中中间位置的那个数，如序列R（11，13，15，17，19）中位数是15
  序列L（2，4，6，8，20）中位数是6,序列R和序列L的中位数是11
  思路：
其实两个升序序列的中位数就是两个数组合并后的第K个元素，所以只要做一个逻辑的合并
排序，返回第K个元素就行。
代码：
int M_Search(int a[],int b[],int n){
int i = 0;
int j = 0;
int k = 0;
while(i < n&&&j < n){
k++;
if(a[i] < b[j]){
i++;
if(k == n){
return a[i - 1];
}
}
else{
j++;
if(k == n){
return b[j - 1];
}
}
}
}
11.求两个递增有序的链表中公共元素组成的子链表。
如：L1（X0,X1,X7,X10,X11）和L2（X1,X8,X10,X11,X15）公共元素组成的子链表是
   L3（X1,X10,X11）
代码：
int Common(Link* L1,Link* L2,Link** L3){
*L3 = (Link*)malloc(sizeof(Link));
Link* p = L1;
Link* q = L2;
Link* m = *L3;
while(p != NULL&&q != NULL){
if(p->data < q->data){
p = p->next;
}
else if(p->data > q->data){
q = q->next;
}
else{
node = (Link*)malloc(sizeof(Link));
node->data = p->data;
m->next = node;
m = node;
p = p->next;
q = q->next;
}
}
m->next = NULL;

}

目的只是为了巩固和分享，代码写的比较粗糙，望朋友们多多指正！^_^ ----- ^_^