常见：面试中常见的23个算法题1

1.求一个集合中的连续串，使得这个连续串中各个数相加的和最大

#include<stdio.h>

int getmax(int a[], int n, int *begin, int *end);

into main(void) {

int a[] = {-1,-2,-3,100,-4,-5,6,-7,9,200};

int begin;

int end;

int sum;

sum = getmax(a,10,&begin,&end);

期间，保存这些和值中的最大值为 max。如果 sum 小于零，则从 sum 小于零的后一个重新计算。*/

/**

int getmax(int *a, int n, int *begin, int *end) {

int max = a[0];

int sum = a[0];

int tempbegin = 0;

*begin = 0;

*end = 0;

for (int i = 1; i < n; i++) {

if(sum > 0) {

*begin = tempbegin;

*end = i;

}

}

return max;

}

///////////////////////////////////////////////////////////////////////////////////////////

////////

2.求一个集合中的连续串，使得这个连续串中各个数相加的和最小

#include <stdio.h>

// int a[] = {-1, 100, -1000, 100, -1};

// int a[] = {1, 1, 1, 1, 1};

// int a[] = {-1, -1, -1, -1, -1};

// int a[] = {1, -1, 1, -1};

// int a[] = {8, 9, -3, -10, 7, 0, 8, -12, 9, 8, -1, -2, 9};

int a[] = {8, 9, -3, -10, 7, -5, 2, -12, 9, 8, -1, -2, 9};

int begin;

int end;

int sum;

int k = sizeof(a)/sizeof(int);

int min = a[0];

int sum = a[0];

int tempbegin = 0;

*begin = 0;

*end = 0;

for (int i = 1; i < n; i++) {

if(sum < 0) {

sum = sum + a[i];

} else {

tempbegin = i;

}

}

return min;

}

////////////////////////////////////////////////////////////////////////////

///////////////////////

3.动态规划求组合

思想：C(n,k)=C(n-1,k-1)+C(n-1,k)

利用动态规划法，用一个二维数组把前面算出的组合数

保存起来，这样就不用重复对一个小的组合数算很多次

#include <iostream>

}

int Com(int n, int k) {

for(int i=0;i<=n;++i) {

for(int j=0;j<=min(i,k);++j) {

if (j==0 || j==i){//每行第 0 列(最左边，C(n,0)=1，主对角线元素也为 1)

a[i][j]=1;

} else {

a[i][j]=a[i-1][j-1]+a[i-1][j];//根据递推式

}

}

////////////////////////////////////////////////////////////////////////////

///////////////////////

4.寻找发贴“水王”

1）题目

一个论坛中有一大“水王”，他不但喜欢发帖，还会回复其他 ID 发的每个帖子。

该“水王”发帖数目超过了总数的一半。如果你有一个当前论坛所有帖子（包括回

帖）的列表，其中帖子作者的 ID 也在表中，你能快速找出这个传说中的“水王”

吗？

如果每次删除两个不同的 ID（不管是否包含“水王”的 ID），那么，在剩下的 ID

列表中，“水王”ID 出现的次数仍然超过总数的一半。看到这一点之后，就可以

通过不断重复这个过程，把 ID 列表中的 ID 总数降低（转化为更小的问题），

从而得到问题的答案。新的思路，总的时间复杂度只有 O（N），且只需要常数

的额外内存。

3）代码

#include<iostream>

using namespace std;

candidate = ID[i];

nTimes = 1;

}

return candidate;

}

int main(void){

int id[] = {1,2,2,4,2,4,2,2};

int iD = Find(id, 8);

cout<<"The water king's id is "<<iD<<endl;

return 0;

}

4）结论

在这个题目中，有一个计算机科学中很普遍的思想，就是如何把一个问题转化为规模较小的若干个问题。

分治、递推和贪心等都是基于这样的思路。在转化过程中，小的问题跟原问题本质上一致。

这样，我们可以通过同样的方式将小问题转化为更小的问题。因此，转化过程是很重要的。

像上面这个题目，我们保证了问题的解在小问题中仍然具有与原问题相同的性质：水王的 ID 在 ID 列表中

的次数超过一半。

转化本身计算的效率越高，转化之后问题规模缩小得越快，则整体算法的时间复杂度越低。

////////////////////////////////////////////////////////////////////////////

///////////////////////

5.求一个字符串中最长的重复子串，'0000……'不算在内