c语言面试题目作业

1.求子数组的最大和题目：输入一个整形数组，数组里有正数也有负数。

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

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

分析：遍历整个数组，从前往后加。

如果得到负数，则直接取下一个值。

例如：1+（-2）=-1，则最大值肯定不会包含1，-2这两项。

3+10=13，继续加-4=9，此时最大值不用更新，因为13>9，如果-4后面的项加上去之后>13再更新。

同时，只要不为负值，前面的项就不用淘汰，继续加并且和之前的和进行比较。

好了，接着+7=16>13，则和更新为16，接着+2=18，则更新为18.因此最终的和最大值为18。

#include<iostream>using namespace std;int maxk(int a[]){int b = 0;int sum = 0;for(int i=0;i<10;i++){if(b<0)b = a[i];elseb += a[i];if(sum<b)sum = b;}return sum;}int main(){int a[10] = {3,-4,5,7,-2,9,10,-8,4,2};cout<<maxk(a)<<endl;return 0;}2.整数的二进制表示中1的个数题目：输入一个整数，求该整数的二进制表达中有多少个1。

例如输入10，由于其二进制表示为1010，有两个1，因此输出2。

分析：如果某数最低位是1，则和1&的结果就是1，因此考虑如何把每一位的1放在最低位和1&。

可以采用右移，知道某数为0（所有的1都移出来了）。

#include<iostream>using namespace std;int numofone(int n){int i=0;while(n != 0){if((n&1) != 0)i++;n = n>>1;}return i;}int main(){int a = 7;cout<<numofone(659)<<endl;return 0;}3.单词反转输入一个字符串，对其中的单词进行反转。

例如：“How old are you”=>“who dlo era uoy”分析：分两步走。

第一步：把单词分割开，第二步：对分割开的单词进行反转。

#include<iostream>using namespace std;void reverse(char *str,int begin,int end){char *p = str+begin;//char *m = p;char *q = str+end;while(p<=q){char temp;temp = *p;*p = *q;*q = temp;p++;q--;}}void cut(char *str){char *p = str;int end = 0;int begin = 0;int i ;while(*p !='\0'){i = 0;while(*p!=' '&& *p!='\0')//problem1{p++;i++;}if(*p!='\0')p++;end = begin+i-1;reverse(str,begin,end);if(*p!='\0')begin = end+2;//cout<<begin<<" "<<end<<endl;}}int main(){char str[25] = "hello world good morning";cut(str);cout<<str<<endl;return 0;}/*problem1:此处必须加上*p!='\0'，因为p到了字符串尾部时*p==' '，而此时内层循环会继续因而p就指到了未知的位置，大循环就无法终止*/4 左移右移问题分析：假设原数组序列为abcd1234，要求变换成的数组序列为1234abcd，即循环右移了4位。

比较之后，不难看出，其中有两段的顺序是不变的：1234和abcd，可把这两段看成两个整体。

右移K位的过程就是把数组的两部分交换一下。

变换的过程通过以下步骤完成：逆序排列abcd：abcd1234 → dcba1234；逆序排列1234：dcba1234 → dcba4321；全部逆序：dcba4321 → 1234abcd。

#include<iostream>using namespace std;void reverse(char *str,int begin,int end){char *p = str + begin;char *q = str + end;char temp;while(p<=q){temp = *p;*p = *q;*q = temp;p++;q--;}}void rightShift(char *str,int n){int len = strlen(str);reverse(str,0,len-n-1);reverse(str,len-n,len-1);reverse(str,0,len-1);}void leftShift(char *str,int n){int len = strlen(str);reverse(str,0,n-1);reverse(str,n,len-1);reverse(str,0,len-1);}int main(){//char *str = "1234567abcd";//默认为const char*str，因此reverse中的*p = *q就会出问题char str[] = "1234567abcd";cout<<str<<endl;rightShift(str,4);cout<<str<<endl;leftShift(str,5);cout<<str<<endl;return 0;}5 俩个字符串是否包含的问题题目描述：假设这有一个各种字母组成的字符串，假设这还有另外一个字符串，而且这个字符串里的字母数相对少一些。

从算法是讲，什么方法能最快的查出所有小字符串里的字母在大字符串里都有？比如，如果是下面两个字符串：String 1: ABCDEFGHLMNOPQRSString 2: DCGSRQPOM答案是true，所有在string2里的字母string1也都有。

如果是下面两个字符串：String 1: ABCDEFGHLMNOPQRSString 2: DCGSRQPOZ答案是false，因为第二个字符串里的Z字母不在第一个字符串里。

分析：有两个字符串short_str和long_str。

第一步：你标记short_str中有哪些字符，在store数组中标记为true。

(store数组起一个映射的作用，如果有A，则将第1个单元标记true，如果有B,则将第2个单元标记true，... 如果有Z, 则将第26个单元标记true）第二步：遍历long_str，如果long_str中的字符包括short_str中的字符则将store数组中对应位置标记为false。

(如果有A，则将第1个单元标记false，如果有B,则将第2个单元标记false，... 如果有Z, 则将第26个单元标记false)，如果没有，则不作处理。

第三步：此后，遍历store数组，如果所有的元素都是false，也就说明store_str中字符都包含在long_str内，输出true。

否则，输出false。

举个简单的例子好了，如abcd，abcdefg俩个字符串，1、先遍历短字符串abcd，在store数组中想对应的abcd的位置上的单元元素置为true，2、然后遍历abcdefg，在store数组中相应的abcd位置上，发现已经有了abcd，则前4个的单元元素都置为false，当我们已经遍历了4个元素，等于了短字符串abcd的4个数目，所以，满足条件，退出。

（不然，继续遍历的话，我们会发现efg在store数组中没有元素，不作处理。

最后，自然，就会发现store数组中的元素单元都是false的。

）3、遍历store数组，发现所有的元素都已被置为false，所以程序输出true。

#include<iostream>using namespace std;int longincludeshort(char a[],char b[]){bool store[26];int flag = 0;int count = 0;memset(store,false,26);for(int i=0;i<strlen(b);i++)store[b[i]-65] = true;for(int j=0;j<strlen(a);j++)if(store[a[j]-65] == true){Store[a[j]-65] = false;count++;}for(i=0;i<26;i++)if(store[i] != false){flag = 1;break;}if(flag == 1)cout<<"not include"<<endl;elsecout<<"include"<<endl;return count;}int main(){char a[] = "ABCDEFGHLMNOPQRS";char b[] = "DEFGHMX";cout<<longincludeshort(a,b)<<endl;return 0;}6、字符串拷贝题目描述：要求实现库函数strcpy，原型声明：extern char *strcpy(char *dest,char *src);功能：把src所指由NULL结束的字符串复制到dest所指的数组中。