b*****g
发帖数: 919 | 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*****g
发帖数: 1137 | 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*****g
发帖数: 919 | 3 我没做过。。
【在 c*****g 的大作中提到】
: 经典的编程面试题啊
| h*****0
发帖数: 4889 | 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******s
发帖数: 270 | 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*****g
发帖数: 919 | 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*****0
发帖数: 4889 | 7 哪里？
【在 c******s 的大作中提到】
: 好像都有错。。。
| h*****0
发帖数: 4889 | 8 是啊，不是增数组这个算法就不行了。
【在 b*****g 的大作中提到】
: 第一个原来是递增数组。。。。。
| c******s
发帖数: 270 | 9 第一个题为什么要找出离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*****0 的大作中提到】
: 哪里？
| c******s
发帖数: 270 | 10 第二个我没有看懂你的解法， 为什么要最大的和减去最小的？
题目是求最大的和， 对么？
【在 h*****0 的大作中提到】
: 哪里？
| | | h*****0
发帖数: 4889 | 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*****0
发帖数: 4889 | 12 最小的部分和到最大的部分和之间的那一段，就是最大的一段和。
【在 c******s 的大作中提到】
: 第二个我没有看懂你的解法， 为什么要最大的和减去最小的？
: 题目是求最大的和， 对么？
| c******s
发帖数: 270 | 13 sorry...
我只看了开头， 没有仔细的想。
确实是C。。。
【在 h*****0 的大作中提到】
: 我一开始就是你这么算的，不过担心漏数，才从中间开始找。不过现在想想，两种方法
: 都不会漏。
: BTW：你这是什么语言？好像C啊。
| b*****g
发帖数: 919 | 14 是C啊。。。
【在 h*****0 的大作中提到】
: 我一开始就是你这么算的，不过担心漏数，才从中间开始找。不过现在想想，两种方法
: 都不会漏。
: BTW：你这是什么语言？好像C啊。
| c******s
发帖数: 270 | 15 呵呵。。。我发现是我汉语的理解能力有问题。。。
没有看懂下面这句话的意思，为什么呢？
【在 h*****0 的大作中提到】
: 最小的部分和到最大的部分和之间的那一段，就是最大的一段和。
| b*****g
发帖数: 919 | 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*****g
发帖数: 919 | 17 我从小就审题不清 :(
【在 h*****0 的大作中提到】
: 是啊，不是增数组这个算法就不行了。
| h*****0
发帖数: 4889 | 18 C的数组是用[]的吧。
还有那个i(0)的初始化我也不太熟。C++加入的？感觉对基本数据类型还是写成i=0比较
好读。
【在 c******s 的大作中提到】
: sorry...
: 我只看了开头， 没有仔细的想。
: 确实是C。。。
| h*****0
发帖数: 4889 | 19 话说我这种算法，其实原本是对零和循环数组的……所以这里还有一点问题。
【在 h*****0 的大作中提到】
: 最小的部分和到最大的部分和之间的那一段，就是最大的一段和。
| c******s
发帖数: 270 | 20 哈哈，我乱敲的，
不习惯用[]，
被你发现了。
i=0 和 i(0)效果是一样的， 确实是C++才有。
【在 h*****0 的大作中提到】
: C的数组是用[]的吧。
: 还有那个i(0)的初始化我也不太熟。C++加入的？感觉对基本数据类型还是写成i=0比较
: 好读。
| | | h*****0
发帖数: 4889 | 21 ft，敲真实代码还“不习惯”……
我是记得C++似乎加入了这种初始化，不过是为了给对象初始化，因为静态对象没法用
＝来初始。不过对基本数据类型总感觉别扭。
【在 c******s 的大作中提到】
: 哈哈，我乱敲的，
: 不习惯用[]，
: 被你发现了。
: i=0 和 i(0)效果是一样的， 确实是C++才有。
| c******s
发帖数: 270 | 22 接受批评。。。这就改正。。。
【在 h*****0 的大作中提到】
: ft，敲真实代码还“不习惯”……
: 我是记得C++似乎加入了这种初始化，不过是为了给对象初始化，因为静态对象没法用
: ＝来初始。不过对基本数据类型总感觉别扭。
| h*****0
发帖数: 4889 | 23 第二题怎么做啊？按我那思路修改出来的不能保证最坏情况下空间O(1)。
【在 c******s 的大作中提到】
: 接受批评。。。这就改正。。。
| b*****g
发帖数: 919 | 24 有问题？？
【在 h*****0 的大作中提到】
: 话说我这种算法，其实原本是对零和循环数组的……所以这里还有一点问题。
| h*****0
发帖数: 4889 | 25 循环：
假设数组为10，-10，-10，10，那结果是什么？
按我的算法找出来的就是最后一个和第一个
【在 b*****g 的大作中提到】
: 有问题？？
| b*****g
发帖数: 919 | 26
0 10 0 -10 0
~~~~~~~best?
【在 h*****0 的大作中提到】
: 循环：
: 假设数组为10，-10，-10，10，那结果是什么？
: 按我的算法找出来的就是最后一个和第一个
| h*****0
发帖数: 4889 | 27 什么意思？
【在 b*****g 的大作中提到】
:
: 0 10 0 -10 0
: ~~~~~~~best?
| b*****g
发帖数: 919 | 28 好像确实有问题 不过稍微搞一下应该可以吧？
【在 h*****0 的大作中提到】
: 循环：
: 假设数组为10，-10，-10，10，那结果是什么？
: 按我的算法找出来的就是最后一个和第一个
| h*****0
发帖数: 4889 | 29 那空间复杂度在最坏情况下会到O(n)，因为你有可能得把每个最低点都记下来。
【在 b*****g 的大作中提到】
: 好像确实有问题 不过稍微搞一下应该可以吧？
| b*****g
发帖数: 919 | 30 a=当前最小部分和 b=当前最大部分和
c=最有价值序列
从第一开始扫面 当b-a>c时更新c
最后返回c
【在 h*****0 的大作中提到】
: 那空间复杂度在最坏情况下会到O(n)，因为你有可能得把每个最低点都记下来。
| | | h*****0
发帖数: 4889 | 31 用这个算法对 10 -10 -10 10算一下？
【在 b*****g 的大作中提到】
: a=当前最小部分和 b=当前最大部分和
: c=最有价值序列
: 从第一开始扫面 当b-a>c时更新c
: 最后返回c
| c******s
发帖数: 270 | 32 测试你的数列，通过了， 返回的是最后一个最大的和.
程序如下
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++;
}
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******s
发帖数: 270 | 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*****0
发帖数: 4889 | 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******s
发帖数: 270 | 35 对了， 对于全是负数的，
我给出的是0.。。。一个数都不选，
这个时候e2=0。
最后判断一下e2是否为0，
如果为0， 就返回所有数里面最大的那个， right?
【在 h*****0 的大作中提到】
: 建议把 &&tmp1 > 0 去掉
: 对-3,-2,-1测试一下？
| S****t
发帖数: 1186 | 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*n
发帖数: 202 | 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*n
发帖数: 202 | 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;
|
|
