两个程序题 - 未名空间MITBBS历史存档

b*g2008-01-19 08:01

1 楼

一. 已知一个有序递增数组.有n个元素.现在给一个数x,问这n个数里面是否存在两个数
,他
们的和为 x,假设都是整数. 要求, 时间复杂度为O(n),空间复杂度为O(1)...
二. 已知一个数组,有n个元素,要求找出它的一个子数组(必须是连续的元素),使得这个
子数
组各数之和为最大. 输出这个和即可. 要求,时间复杂度为O(n),空间复杂度为O(1)...
比如数组 3,8,-19,2,9,7,-6,10,-5,6,-7,1
找到了发现 2,9,7,-6,10,-5,6 是所求,只需要输出他们的和23即可

c*g2008-01-19 08:01

2 楼

经典的编程面试题啊

【在 b*****g 的大作中提到】

: 一. 已知一个有序递增数组.有n个元素.现在给一个数x,问这n个数里面是否存在两个数
: ,他
: 们的和为 x,假设都是整数. 要求, 时间复杂度为O(n),空间复杂度为O(1)...
: 二. 已知一个数组,有n个元素,要求找出它的一个子数组(必须是连续的元素),使得这个
: 子数
: 组各数之和为最大. 输出这个和即可. 要求,时间复杂度为O(n),空间复杂度为O(1)...
: 比如数组 3,8,-19,2,9,7,-6,10,-5,6,-7,1
: 找到了发现 2,9,7,-6,10,-5,6 是所求,只需要输出他们的和23即可

b*g2008-01-19 08:01

3 楼

我没做过。。

【在 c*****g 的大作中提到】

: 经典的编程面试题啊

h*02008-01-19 08:01

4 楼

不难：
一、
1. 先折半查找到x/2或离x/2最近的一个数，用时log n
2. 往数组增方向走一个数得到y，看其与x的差，往减方向找这个差x-y，找到
即返回true，没找到则此时会出现一个小于x-y的数z,再往增方向去找x-z……
总用时log n + n = n
二、
1.用第一个数开始，计算部分和，只需记下部分和中最大的一个和与最小的一
个，此两和之差即为所求。

【在 b*****g 的大作中提到】

: 一. 已知一个有序递增数组.有n个元素.现在给一个数x,问这n个数里面是否存在两个数
: ,他
: 们的和为 x,假设都是整数. 要求, 时间复杂度为O(n),空间复杂度为O(1)...
: 二. 已知一个数组,有n个元素,要求找出它的一个子数组(必须是连续的元素),使得这个
: 子数
: 组各数之和为最大. 输出这个和即可. 要求,时间复杂度为O(n),空间复杂度为O(1)...
: 比如数组 3,8,-19,2,9,7,-6,10,-5,6,-7,1
: 找到了发现 2,9,7,-6,10,-5,6 是所求,只需要输出他们的和23即可

c*s2008-01-19 08:01

5 楼

好像都有错。。。

【在 h*****0 的大作中提到】

: 不难：
: 一、
: 1. 先折半查找到x/2或离x/2最近的一个数，用时log n
: 2. 往数组增方向走一个数得到y，看其与x的差，往减方向找这个差x-y，找到
: 即返回true，没找到则此时会出现一个小于x-y的数z,再往增方向去找x-z……
: 总用时log n + n = n
: 二、
: 1.用第一个数开始，计算部分和，只需记下部分和中最大的一个和与最小的一
: 个，此两和之差即为所求。

b*g2008-01-19 08:01

6 楼

第一个原来是递增数组。。。。。

【在 h*****0 的大作中提到】

: 不难：
: 一、
: 1. 先折半查找到x/2或离x/2最近的一个数，用时log n
: 2. 往数组增方向走一个数得到y，看其与x的差，往减方向找这个差x-y，找到
: 即返回true，没找到则此时会出现一个小于x-y的数z,再往增方向去找x-z……
: 总用时log n + n = n
: 二、
: 1.用第一个数开始，计算部分和，只需记下部分和中最大的一个和与最小的一
: 个，此两和之差即为所求。

h*02008-01-19 08:01

7 楼

哪里？

【在 c******s 的大作中提到】

: 好像都有错。。。

h*02008-01-19 08:01

8 楼

是啊，不是增数组这个算法就不行了。

【在 b*****g 的大作中提到】

: 第一个原来是递增数组。。。。。

c*s2008-01-19 08:01

9 楼

第一个题为什么要找出离x/2最近的一个数？
这样你可能会漏掉很多潜在的数。
下面是个线性的算法，指针对有两个数的和为x的情况
int i(0), j(n-1);
temp=A(i)+A(j);
while(iif (x==temp) return;
else temp = (x>temp)? A(++i)+A(j): A(i)+A(--j);
}

【在 h*****0 的大作中提到】

: 哪里？

c*s2008-01-19 08:01

10 楼

第二个我没有看懂你的解法，为什么要最大的和减去最小的？
题目是求最大的和，对么？

【在 h*****0 的大作中提到】

: 哪里？

h*02008-01-19 08:01

11 楼

我一开始就是你这么算的，不过担心漏数，才从中间开始找。不过现在想想，两种方法
都不会漏。
BTW：你这是什么语言？好像C啊。

【在 c******s 的大作中提到】

: 第一个题为什么要找出离x/2最近的一个数？
: 这样你可能会漏掉很多潜在的数。
: 下面是个线性的算法，指针对有两个数的和为x的情况
: int i(0), j(n-1);
: temp=A(i)+A(j);
: while(i: if (x==temp) return;
: else temp = (x>temp)? A(++i)+A(j): A(i)+A(--j);
: }

h*02008-01-19 08:01

12 楼

最小的部分和到最大的部分和之间的那一段，就是最大的一段和。

【在 c******s 的大作中提到】

: 第二个我没有看懂你的解法，为什么要最大的和减去最小的？
: 题目是求最大的和，对么？

c*s2008-01-19 08:01

13 楼

sorry...
我只看了开头，没有仔细的想。
确实是C。。。

【在 h*****0 的大作中提到】

: 我一开始就是你这么算的，不过担心漏数，才从中间开始找。不过现在想想，两种方法
: 都不会漏。
: BTW：你这是什么语言？好像C啊。

b*g2008-01-19 08:01

14 楼

是C啊。。。

【在 h*****0 的大作中提到】

: 我一开始就是你这么算的，不过担心漏数，才从中间开始找。不过现在想想，两种方法
: 都不会漏。
: BTW：你这是什么语言？好像C啊。

c*s2008-01-19 08:01

15 楼

呵呵。。。我发现是我汉语的理解能力有问题。。。
没有看懂下面这句话的意思，为什么呢？

【在 h*****0 的大作中提到】

: 最小的部分和到最大的部分和之间的那一段，就是最大的一段和。

b*g2008-01-19 08:01

16 楼

这个和我想的差不多

【在 c******s 的大作中提到】

: 第一个题为什么要找出离x/2最近的一个数？
: 这样你可能会漏掉很多潜在的数。
: 下面是个线性的算法，指针对有两个数的和为x的情况
: int i(0), j(n-1);
: temp=A(i)+A(j);
: while(i: if (x==temp) return;
: else temp = (x>temp)? A(++i)+A(j): A(i)+A(--j);
: }

b*g2008-01-19 08:01

17 楼

我从小就审题不清 :(

【在 h*****0 的大作中提到】

: 是啊，不是增数组这个算法就不行了。

h*02008-01-19 08:01

18 楼

C的数组是用[]的吧。
还有那个i(0)的初始化我也不太熟。C++加入的？感觉对基本数据类型还是写成i=0比较
好读。

【在 c******s 的大作中提到】

: sorry...
: 我只看了开头，没有仔细的想。
: 确实是C。。。

h*02008-01-19 08:01

19 楼

话说我这种算法，其实原本是对零和循环数组的……所以这里还有一点问题。

【在 h*****0 的大作中提到】

: 最小的部分和到最大的部分和之间的那一段，就是最大的一段和。

c*s2008-01-19 08:01

20 楼

哈哈，我乱敲的，
不习惯用[]，
被你发现了。
i=0 和 i(0)效果是一样的，确实是C++才有。

【在 h*****0 的大作中提到】

: C的数组是用[]的吧。
: 还有那个i(0)的初始化我也不太熟。C++加入的？感觉对基本数据类型还是写成i=0比较
: 好读。

h*02008-01-19 08:01

21 楼

ft，敲真实代码还“不习惯”……
我是记得C++似乎加入了这种初始化，不过是为了给对象初始化，因为静态对象没法用
＝来初始。不过对基本数据类型总感觉别扭。

【在 c******s 的大作中提到】

: 哈哈，我乱敲的，
: 不习惯用[]，
: 被你发现了。
: i=0 和 i(0)效果是一样的，确实是C++才有。

c*s2008-01-19 08:01

22 楼

接受批评。。。这就改正。。。

【在 h*****0 的大作中提到】

: ft，敲真实代码还“不习惯”……
: 我是记得C++似乎加入了这种初始化，不过是为了给对象初始化，因为静态对象没法用
: ＝来初始。不过对基本数据类型总感觉别扭。

h*02008-01-19 08:01

23 楼

第二题怎么做啊？按我那思路修改出来的不能保证最坏情况下空间O(1)。

【在 c******s 的大作中提到】

: 接受批评。。。这就改正。。。

b*g2008-01-19 08:01

24 楼

有问题？？

【在 h*****0 的大作中提到】

: 话说我这种算法，其实原本是对零和循环数组的……所以这里还有一点问题。

h*02008-01-19 08:01

25 楼

循环：
假设数组为10，-10，-10，10，那结果是什么？
按我的算法找出来的就是最后一个和第一个

【在 b*****g 的大作中提到】

: 有问题？？

b*g2008-01-19 08:01

26 楼

0 10 0 -10 0
~~~~~~~best?

【在 h*****0 的大作中提到】

: 循环：
: 假设数组为10，-10，-10，10，那结果是什么？
: 按我的算法找出来的就是最后一个和第一个

h*02008-01-19 08:01

27 楼

什么意思？

【在 b*****g 的大作中提到】

:
: 0 10 0 -10 0
: ~~~~~~~best?

b*g2008-01-19 08:01

28 楼

好像确实有问题不过稍微搞一下应该可以吧？

【在 h*****0 的大作中提到】

: 循环：
: 假设数组为10，-10，-10，10，那结果是什么？
: 按我的算法找出来的就是最后一个和第一个

h*02008-01-19 08:01

29 楼

那空间复杂度在最坏情况下会到O(n)，因为你有可能得把每个最低点都记下来。

【在 b*****g 的大作中提到】

: 好像确实有问题不过稍微搞一下应该可以吧？

b*g2008-01-19 08:01

30 楼

a=当前最小部分和 b=当前最大部分和
c=最有价值序列
从第一开始扫面当b-a>c时更新c
最后返回c

【在 h*****0 的大作中提到】

: 那空间复杂度在最坏情况下会到O(n)，因为你有可能得把每个最低点都记下来。

h*02008-01-19 08:01

31 楼

用这个算法对 10 -10 -10 10算一下？

【在 b*****g 的大作中提到】

: a=当前最小部分和 b=当前最大部分和
: c=最有价值序列
: 从第一开始扫面当b-a>c时更新c
: 最后返回c

c*s2008-01-19 08:01

32 楼

测试你的数列，通过了，返回的是最后一个最大的和.
程序如下
int maxSubSum(vector A){
int s1(0),s2(0),e1(0),e2(0);
float tmp1(0),tmp2(0);
int i=0;
while(iif (tmp1+A[i]>=tmp1){
tmp1+=A[i];
e1++;
}
else{
if (tmp1>=tmp2 && tmp1>0){
s2=s1; e2=e1;
tmp2=tmp1;
}
if (tmp1+A[i]>=0){
tmp1+=A[i];
e1++;
}
else{
tmp1=0

【在 h*****0 的大作中提到】

: 用这个算法对 10 -10 -10 10算一下？

c*s2008-01-19 08:01

33 楼

注释:
用s1,e1记录当前的子数列的开始和长度，tmp1记录当前的和，这个和要大于0才要。
用s2,e2记录历史的子数列的开始和长度，tmp1记录历史的最大和。

【在 c******s 的大作中提到】

: 测试你的数列，通过了，返回的是最后一个最大的和.
: 程序如下
: int maxSubSum(vector A){
: int s1(0),s2(0),e1(0),e2(0);
: float tmp1(0),tmp2(0);
: int i=0;
: while(i: if (tmp1+A[i]>=tmp1){
: tmp1+=A[i];
: e1++;

h*02008-01-19 08:01

34 楼

建议把 &&tmp1 > 0 去掉
对-3,-2,-1测试一下？

【在 c******s 的大作中提到】

: 测试你的数列，通过了，返回的是最后一个最大的和.
: 程序如下
: int maxSubSum(vector A){
: int s1(0),s2(0),e1(0),e2(0);
: float tmp1(0),tmp2(0);
: int i=0;
: while(i: if (tmp1+A[i]>=tmp1){
: tmp1+=A[i];
: e1++;

c*s2008-01-19 08:01

35 楼

对了，对于全是负数的，
我给出的是0.。。。一个数都不选，
这个时候e2=0。
最后判断一下e2是否为0，
如果为0，就返回所有数里面最大的那个， right?

【在 h*****0 的大作中提到】

: 建议把 &&tmp1 > 0 去掉
: 对-3,-2,-1测试一下？

S*t2008-01-19 08:01

36 楼

(1)
bool SumX(int *a, int n, int x)
{
int i = 0, j = n - 1;
while (i < j)
{
if (a[i] + a[j] > x)
{
j--;
countinue;
}//if
else if (a[i] + a[j] < x)
{
i++;
countinue;
}//else if
else
{
return true;
}//else
}//while
return false;
}//SumX
(2)
int MaxSubArray(int *a, int n)
{
maxSoFar = 0;
maxEndingHere = 0;

for (int i = 0; i < n; i++)
{
maxEndingHere = ((maxEndingHere + a[i]) > 0) ? (maxEndingHere + a[i]) :
0;

【在 b*****g 的大作中提到】

: 一. 已知一个有序递增数组.有n个元素.现在给一个数x,问这n个数里面是否存在两个数
: ,他
: 们的和为 x,假设都是整数. 要求, 时间复杂度为O(n),空间复杂度为O(1)...
: 二. 已知一个数组,有n个元素,要求找出它的一个子数组(必须是连续的元素),使得这个
: 子数
: 组各数之和为最大. 输出这个和即可. 要求,时间复杂度为O(n),空间复杂度为O(1)...
: 比如数组 3,8,-19,2,9,7,-6,10,-5,6,-7,1
: 找到了发现 2,9,7,-6,10,-5,6 是所求,只需要输出他们的和23即可

n*n2008-01-19 08:01

37 楼

1. 太简单，不做
2. 教科书上的，不做
发包子吧

【在 b*****g 的大作中提到】

: 一. 已知一个有序递增数组.有n个元素.现在给一个数x,问这n个数里面是否存在两个数
: ,他
: 们的和为 x,假设都是整数. 要求, 时间复杂度为O(n),空间复杂度为O(1)...
: 二. 已知一个数组,有n个元素,要求找出它的一个子数组(必须是连续的元素),使得这个
: 子数
: 组各数之和为最大. 输出这个和即可. 要求,时间复杂度为O(n),空间复杂度为O(1)...
: 比如数组 3,8,-19,2,9,7,-6,10,-5,6,-7,1
: 找到了发现 2,9,7,-6,10,-5,6 是所求,只需要输出他们的和23即可

n*n2008-01-19 08:01

38 楼

抄书啊，哈哈

【在 S****t 的大作中提到】

: (1)
: bool SumX(int *a, int n, int x)
: {
: int i = 0, j = n - 1;
: while (i < j)
: {
: if (a[i] + a[j] > x)
: {
: j--;
: countinue;