2012.10.23往哪儿网笔试题

2012.10.23去哪儿网笔试题
1.将IPV4转换成整数，要求高效。
2.定义一个栈的数据结构，实现min函数，要求push,pop,min时间复杂度是0(1);
3.数组a[n]里存有1到n的所有数，除了一个数removed，找出这个missing的数。

4.找出字符串中的最长子串，要求子串不含重复字符，时间复杂度是O（n）;

第一题答案：

表中，字符串有3个‘a’，有2个‘b’，其余为单一字符。next[]记录了下一个与之重复的字符的位置，如str[0]=str[8]=str[12]=‘a’，这时next[0]=8，next[8]=12，next[12]=13，其余同理。值得注意的是，对于没有重复字符的，next[]存储字符结束符‘\0’的下标，即13。
这里，first[i]表示i之后，第一次出现重复字符的那个位置。例如，str[0]之后，第一次出现的重复字符是str[5]=‘b’，当然，从str[1]，str[2]开始也是一样。而从str[3]开始，要到str[12]才出现重复字符‘a’。可以证明，从str[i]起的最长符合要求的长度为first[i]-i，区间为[i,first[i]-1]由此得解。上述最长串是当i=3时，first[i]-i=12-3=9。结果最长无重复子串为“debpqawuv”。
#include<stdio.h>//得到字符串最长的无重复的前缀长度int longestlen(char * p){int hash[256];int len = 0;memset(hash,0,sizeof(hash));while(*p && !hash[*p]){    hash[*p] = 1;++len;++p;}return len;}//使用后缀数组解法int max_unique_substring4(char * str){char *p=str;int maxlen = -1;int begin = 0;int i;for (i=0; i<strlen(p); i++){int temlen = longestlen(str+i);if (temlen > maxlen){maxlen = temlen;begin = i;}}printf("%.*s\n", maxlen, p+begin);return maxlen;}int main(int argc,char *argv[]){char *str = "abcdafeeg";printf("%d\n",max_unique_substring4(str));return 0;}