面试算法题整理
最近面试跪了不少，都基本是跪在算法题上，现在把遇到的一些题目记录下来，方面以后复习
1.一个字符串只有0和1，如“110011110000”，找到这个串中的最长子串，使得子串的0和1个数相等，比如：1000010111000001，阴影的部分有4个0、4个1（出自美团）
思路：最简单的想法就是遍历所有的子串，之后判断该子串是否满足条件N^2子串，每个子串扫一遍判断0、1是否出现的次数相等，复杂度为O(N^3)，稍加思考就会发现， 如果一个长度为n的子串满足条件，加么这n个元素的和加起来一定=(n/2)，这样在循环的过程中，增量加就可以了，不需要每个子串从头计算，复杂度降为O(N^2);伪码：
int maxlen = 0, sum = 0, currlen = 0;
for(int i = 0; i < N; ++i)
{
sum = 0;
for(int j = i; j < N; ++j)
{
currlen = j - i + 1;
sum += int(A[j]);
if(currlen%2 == 0 && sum == currlen/2 && currlen > maxlen)
maxlen = currlen;
}
}
还有没有办法进一步降低算法的复杂度呢？
面试官说有这样一种巧妙的解法：定义一个数据B[N]， B[i]表示从A[0…i]中 num_of_0 - num_of_1，0的个数与1的个数的差，那么如果A[i] ~ A[j]（A[i],A[j]选一个包含）是符合条件的子串，一定有 B[i] == B[j]，因为中间的部分0、1个数相等，相减等于0。 只需要扫一遍A[N]就能把B[N]构造出来了。这样问题就转换成了求距离最远的一对数，使得B[i] == B[j]，因为B[i]的范围一定是[-N,N]，-N到N的范围都存起来，建一个-N到N的hash表，index就是-N到N，value就是index相等的两个数的最长距离，这样每扫到B[i]，如果hash表里的值还不存在，填i，若已经存在，填i和里面值得差，即为当前长度，需要更新最大长度这个值。其实代码真的非常简单，一个循环就搞定了，这就是算法和思考的乐趣:)
int A[N],B[N];
int num[2*N + 1];
int count[2] = {0,0}, maxlen = 0, currlen = 0;
memset(C, 2*N, -1);
for(int i = 0; i < N; ++i)
{
count[ int(A[i]) ] += 1;
B[i] = count[1] - count[0];
if( num[ B[i] + N ] == -1)//尚不存在，B的下标是差，值是A的下标
num[ B[i] + N ] = i;
else//already exist
{
currlen = i - num[ B[i] + N ] + 1; //num[ B[i] + N ]是B[i]已存在的下标
if(currlen > maxlen)
maxlen = currlen;
}
}
2.编程实现把一个字符串从“a1b2c4”转成“abbcccc”，不准申请新的内存，原字符串可以认为后面的空间足够大（出自美团）
思路：统计所有的数字之和何以得到最终字符串的长度，然后利用两个指针str1指向原字符串尾，str2指向新字符串尾，记录str1的数字n，和前面的字符m，str2从后向前写n个m，直到str1指向第一个字符。
问题：可能会出现覆盖问题，例如“a1b2c3”转成“abbccc”，原字符串和新字符串长度都是6，按照我上面的算法，第一步之后字符串会变成“a1bccc”，这是我无法得到b的次数2，因为2被c覆盖了。
为什么会覆盖？
原因在“a1”上，“a1”最后要变成“a”，原字符串多占了一位，导致后面的出现覆盖，所以对于所有的“X1”要进行预处理。
怎么处理？
遍历一遍字符串，每遇到“1”，把后面的字符串向前移动一位，例如“a1b2c3”变成“ab2c3”，这个时候，再对“ab2c3”进行我之前的处理，第一步变成“ab2ccc”，是没有问题的。
注意：因为把1去掉之后，原字符串的格式发生了变化，遍历的时候需要注意判断一下。
3.整数分割，比如给定一整数3，其有如下情况：3=3,3=1+2,3=1+1+1,求一个数的所有分割组合（出自创新工场行云）
n=m1+m2+…+mi; （其中mi为正整数，并且1 <= mi <= n），则{m1,m2,…,mi}为n的一个划分。
如果{m1,m2,…,mi}中的最大值不超过m，即max(m1,m2,…,mi)<=m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);
例如n=4时，他有5个划分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};
该问题是求出n的所有划分个数，即f(n, n)。下面我们考虑求f(n,m)的方法;
根据n和m的关系，考虑以下几种情况：
(1) 当n=1时，不论m的值为多少（m>0)，只有一种划分即{1};
(2) 当m=1时，不论n的值为多少，只有一种划分即n个1，{1,1,1,…,1};
(3) 当n=m时，根据划分中是否包含n，可以分为两种情况：
(a).划分中包含n的情况，只有一个即{n}；
(b).划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分。
因此 当n=m时，f(n,n) =1 + f(n,n-1);
(4) 当n < m时，由于划分中不可能出现负数，因此就相当于f(n,n);
(5) 当n > m时，根据划分中是否包含最大值m，可以分为两种情况：
(a).划分中包含m的情况，即{m, {x1,x2,…xi}}, 其中{x1,x2,… xi} 的和为n-m，因此这种情况下为f(n-m,m)
(b).划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为f(n,m-1);
因此，当n > m时 f(n, m) = f(n-m, m)+f(n,m-1);
综上：
f(n,m)=1;(n=1||m=1)
f(n,m)=f(n,n);(n<m)
f(n,m)=1+ f(n, m-1);(n=m)
f(n,m)=f(n-m,m)+f(n,m-1); (n>m)
blog comments powered by Disqus