Chinaunix首页 | 论坛 | 博客
  • 博客访问: 449989
  • 博文数量: 108
  • 博客积分: 46
  • 博客等级: 民兵
  • 技术积分: 1275
  • 用 户 组: 普通用户
  • 注册时间: 2012-08-16 11:36
个人简介

坐井以观天

文章分类

全部博文(108)

文章存档

2014年(13)

2013年(90)

2012年(6)

分类: C/C++

2013-10-07 14:45:34

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;

}

目的只是为了巩固和分享,代码写的比较粗糙,望朋友们多多指正!^_^ ----- ^_^
阅读(2497) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~