IT面试题集 - 编程学习网

清华大佬耗费三个月吐血整理的几百G的资源，免费分享！....>>>

心浮气躁，纵然才俊终仲永。最近准备跳槽，看了些许面试题找感觉，总觉得题解太过粗糙，在此试解几题，打发无聊。

1 单链表环的判断

一个单向链表，怎么判断他是否存在环？如果有环，求出环的入口，如图5-1示。

图 1

1.1 是否有环

由单指针遍历查找，判断当前节点是否曾经访问过时，对访问节点做标记，将弄脏数据；如果不弄脏数据，则需要将访问的历史结点放入容器，且将附带查找开销；

图 5-2

更好的方法是采用双指针，ptr_slow, ptr_fast, 前者每次走一步，后者每次走两步，如果相遇则说明有环。ps:相遇有环是显然的，至于会不会相遇的理由如下：如果有环且不相遇，ptr_slow, ptr_fast随着步数的增加，总会有邻的时候，如果ptr_slow在ptr_fast之前，再走一步就会相遇，因而只会有ptr_slow在 ptr_fast之后的情况。当ptr_slow在ptr_fast之后，ptr_slow走一圈少一步时，ptr_slow和ptr_fast将相遇。

1.2 环的大小与入口

对于环的大小，ptr_slow和ptr_fast在相遇后，继续访问，下次ptr_slow和ptr_fast相遇时，ptr_slow走的步数就是环中结点的数目M。

假设ptr_slow与ptr_fast第一次相遇时，ptr_slow已经走了X步（已知），ptr_fast已经在环中转了N圈，但ptr_slow肯定最多整整走一圈。如图2所示，有ab+bc=X; ab+bc+N*(bc+cb)=2X; 可得ab=cb+(N-1)*(bc+cb); 那么此时，再设一个新的指针cross指向链表头，cross和ptr_slow每次都走一步，他们相遇的结点就是相交的结点 cross。

//单链表定义 typedef struct node_t{ int data; struct node_t *next;
}Node; /**  * @Synopsis  find_circle 判断是否有环并求环入口  *  * @Param head 链表头指针  * @Param cross 有环是为环入口，无环时NULL返回  *  * @Returns 0成功，其它失败  */ int find_circle(Node* head, Node*& cross){ if(NULL == head){ return 1;
    }
    Node* ptr_slow = head;//slow指针 Node* ptr_fast = head;//fast指针 Node* cross = head;//环入口指针 while(ptr_fast = ptr_fast->next && ptr_fast = ptr_fast->next){
        ptr_slow = ptr_slow->next; if(ptr_slow == ptr_fast){ break;
        }
    } if(ptr_fast == NULL){//无环 cross = NULL; return 0;
    } while(ptr_slow != cross){
        cross = cross->next;
        ptr_slow = ptr_slow->next
    } return 0;
}

2 两链表是否相交

判断两链表是否相交，相交时找到相交的第1个节点。

此题比较难，情况很，特别是两链表本身存在环时。

2.1 两链表不存在环时

1) 遍历两链表，判断两链表的尾节点(非NULL节点)是否相同即可。

2) 可将某一链表的尾节点指向另一链表的头节点，构成一个链表后，判断此链表是否有环即可，参见第5题中代码。

2.2 两链表中有环时

如果一个有环，一个无环，此链表一定不相交。如果两列表都有环时，6.1中(1,2)方法无效，因为无法遍历结束链表。可通过5题中，求出两链表环的入口，如果相交，这两个入口(有可能只有一个)，必定是这两链表相交的第1个节点。记录1链表环的入口，从另1链表遍历环一圈查记录的链表入口是否被遍历到即可。

//单链表定义 typedef struct node_t{ int data; struct node_t *next;
}Node; /**  * @Synopsis  _find_circle 判断链表是否有环  *  * @Param head 链表头  * @Param cross 否入口，无环则返回尾节点  *  * @Returns  true有环， false无环  */ bool _find_circle(Node* head, Node*& cross){
    Node* ptr_slow = head;//slow指针 Node* ptr_fast = head;//fast指针 Node* cross = head;//环入口指针 while(ptr_fast->next && ptr_fast->next){
        ptr_fast = ptr_fast->next->next;
        ptr_slow = ptr_slow->next; if(ptr_slow == ptr_fast){ break;
        }
    } if(ptr_fast->next == NULL){//无环 cross = ptr_fast; //指向尾节点 return false;
    } else if(ptr_fast->next->next == NULL){
        cross = ptr_fast->next; return false;
    } while(ptr_slow != cross){
        cross = cross->next;
        ptr_slow = ptr_slow->next
    } return true;
} /**  * @Synopsis  is_list_cross 两链表是否相交  *  * @Param list1 链表1  * @Param list2 链表2  * @Param cross 相交时的第1个节点，不相交返回NULL  *  * @Returns  0成功，其它失败  */ int is_list_cross(Node* list1, Node* list2, Node*& cross)
{ if(NULL == list1 ||| NULL == list2){ return 1;
    } bool ret1,ret2;
    Node* cross_list1;//链表1的环入口 Node* cross_list2;//链表2的环入口 ret1 = _find_circle(list1, cross_list1);
    ret2 = _find_circle(list2, cross_list2); if(ret1 != ret2)//一个有环，一个无环 {
        cross = NULL; return 0;
    } else if(ret1 == false && ret2 == false)//均无环 {
        cross_list2->next = list1;
        _find_circle(list2, cross);
        cross_list2->next = list2; return 0;
    } else//均有环 {
        Node* mark = cross_list1;
        cross_list1 = cross_list1->next; while(mark != cross_list1)//遍历链表1的环 { if(cross_list1 == cross_list2){
                cross = cross_list2;//随意返回1个cross return 0;
            }
        }
        cross = NULL; return 0;
    }
}

3 Min栈

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素，要求函数min、push以及pop的时间复杂度都是O(1)。

双栈实现，一个栈用以维护最小值，另一个栈维护pop和push操作。对于大量相同元素的应用场景，可将min栈中min元素做计数，用以减小存储空间。

/**  * @Synopsis  min栈  */ class MinStack{ public: int min(); int push(int value); int pop(); private:
    std::stack<int> min_stack;
    std::stack<int> main_stack;
} /**  * @Synopsis  min 获取栈中最小值  * @Param value  * @Returns 0成功，其它异常  */ int MinStack::min(int &value)
{ if(min_stack.empty()){ return -1;
   }
   value = min_stack.top(); return 0;
} /**  * @Synopsis  push push元素  * @Param value  * @Returns 0成功，其它异常   */ int MinStack::push(int value)
{
    main_stack.push(value); if(min_stack.empty()){
        min_stack.push(value);
    } else{ int min_value = min_stack.top(); if(value <= min_value){
            min_stack.push(value);
        }
    } return 0;
} /**  * @Synopsis  pop pop元素  * @Returns  0成功，其它异常  */ int MinStack::pop()
{ int value = main_stack.top(); if(value == min_stack.top()){
        min_stack.pop();
    }
    main_stack.pop(); return 0;
}

4 最大子数组和

输入一个整形数组，数组里有正数也有负数，数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

/**  * @Synopsis  max_sub_array 求最大子数组和  *  * @Param array 输入数组  * @Param length 数组长度  * @Param start 子数组始位置  * @Param end 子数组终位置  * @Param value 子数组和  *  * @Returns  0成功，其它失败  */ int max_sub_array(int* array, int length, int& start, int& end, int& value)
{ if(NULL == array || length < 0){ return -1;
    } if(length == 0){
        start = end = -1;
        value = 0; return 0;
    } if(length == 1){
        start = end = 0;
        value = array[0]; return 0;
    }
    value = array[0];
    sum = array[0]; int s,e; //存储包含array[i]元素时，当前最大子数组的起始位置 s = e = start = end = 0; for(int i = 1; i < length; ++i){ if(sum > 0){
            sum += array[i];
            e = i;
        } else{
            sum = array[i];
            s = e = i;
        } if(value < sum){
            start = s;
            end = e;
            value = sum;
        }
    } return 0;
}

5 字符串与int的转换

很多此类的题目，例如将ip字符串（例子“10.27.0.0”）转换成整数，将时间字符串（例子“25h30m22s”）转换成秒数，等等。在此将字符串转换成int。

解：(2013-12-29)

/**  * @Synopsis  str2int 字符串转int  *  * @Param str 字符串指针  * @Param value value  *  * @Returns 0成功，2溢出，其它失败  */ int str2int(const char* str, int &value)
{ if(str == NULL || *str == '\0'){ return 1;
    } long long num = 0;//保存结果 bool flag = false;//符号存储, true为负值,false为正值 //符号处理 if(*str == '+'){
        str++;
    } else if(*str == '-'){
        str++;
        flag = true;
    } //数值处理 while(*str != '\0')
    { if(*str >= '0' && *str <= '9'){
            num = num * 10 + (*str - '0'); if(num > std::numeric_limits<int>::max()){ return 2;
            }
            str++;
        } else{ return 1;
        }
    } //结果处理 if(flag){
        num = -1 * num
    }
    value = static_cast<int>(num); return 0;
}

其中std::numeric_limit<int>::max()可用(unsigned)(-1)>>1表示。

6 二分查找

6.1 经典二分查找

二分查找应用于有序表，经典的代码中防死循环、mid值处理。

//二分查找array中key int binarySearch(int* array,int low,int high,int key)
{ while(low<high-1){//low==mid时，防死循环 int mid=low+(high-low)/2;//防溢出 if(array[mid]>key){
            high=mid;
        } else{
            low=mid;
        }   
    } if(array[low]==key) return array[low]; else if(array[high]==key) return array[high]; else return -1;
}

6.2 查找有序表中key的个数

查找有序表中某元素的个数，方法依然是二分查找，依据上code中的方法，如果key存在时，return的将是最大下标处的key，这样两次二分查找，便可得到array中key的个数。

//二分查找array中key的个数 int binarySearch(int* array,int low,int high,int key)
{ int begin=0; int end=0; //得到key在array中的end下标  while(low<high-1){ int mid=low+(high-low)/2; if(array[mid]>key){
            high=mid;
        } else{
            low=mid;
        }   
    } if(array[high]==key) end=high; else if(array[low]==key) end=low; else return -1; //得到key在array中的begin下标  while(low<high-1){ int mid=low+(high-low)/2; if(array[mid]<key){
            low=mid;
        } else{
            high=mid;
        }   
    } if(array[low]==key) begin=low; else if(array[high]==key) begin=high; else return -1; return (end-begin+1);
}

7 自定义c++的string类

C++的string类，提供一系列繁杂的成员函数，但是对于简单的string类，自定义时需要注意构造函数，拷贝构造函数，析构函数，赋值函数，这都能体现对string的理解。

构造函数和析构函数申请和释放空间；
拷贝构造函数为深拷贝函数；
赋值函数和拷贝构造函数类似，对=运算符重载；
上述所有函数都涉及对空间的操作。

具体代码如下：

/*** *@brief String类:构造函数、析构函数、拷贝构造函数、赋值函数 */ class String{ public:
        String(const char *ptr); 
        ~String();
        String(const String &str);
        String &operator = (const String &str);
    pravite: char *m_data;        
 }
 
 String::String(const char *str){ if(str == NULL){//存空串 m_data = new char[1]; //分配一个字节 *m_data = '\0'; //将之赋值为字符串结束符 } else{ int len = strlen(str);
        m_data = new char[len + 1];
        strcpy(m_data, str);
    }
 }
 
 String:: ~String(){ if(m_data != NULL){//为空判断 delete m_data;
        m_data = NULL;//消除野指针 }
 }
 
 String :: String(const String &str){
    m_data = new char[strlen(str.m_data) + 1];
    strcpy(m_data, str);
 }
 
 String:: String& operate = (const String &str){ if(this == &str){ return *this; delete m_data;//先删后赋值 m_data = new char[strlen(str.m_data) + 1];
        strcpy(m_data, str); return *this;       
    }
 }

8 字符串操作

字符串常用接口有：

char *strcpy(char *des, const char *src);//拷贝字符串
int strcmp(const char *str1, const char *str2);//字符串比较
size_t strlen (const char *s);//求字符串长度，不计字符0
char *strstr(const char *des, const char *src);//字符串匹配，求子串位置

8.1 strcpy和strcmp

前三个原型实现比较简单，在此附上strcpy和strcmp的代码，strlen类似。

//字符串拷贝 char *strcpy(char *des, const char *src)
{
    assert(des != NULL && src != NULL);//断言参数 char *temp = des; while((*des++ = *src++) != '\0'); return temp;
} //字符串比较 int strcmp(const char *str1, const char *str2)
{
    assert(str != NULL && str2 != NULL);//断言参数 while(*str1 != '\0' && *str2 != '\0'&&*str1++ == *str2++); return *str1 - *str2;
}

8.2 strstr字符串匹配

字符串匹配，最简单的方式，为一个一个匹配，复杂度为0(mn)，代码如下：字符串拷贝与比较//字符串匹配，一字符一字符匹配。

char *strstr(const char *des, const char *src)
{
    assert(des != NULL && src != NULL); while(*des != '\0'){ const char* tempDes = des; const char* tempSrc = src; while(*tempDes == *tempSrc){ if(tempStr == '\0') return des;
            tempDes++;
            tempSrc++;          
        }
        des++;
    } return NULL;
}

8.3 kmp字符串匹配

上面的字符串匹配中，每次子串比较不成功时，要重新匹配，在kmp算法中，做要匹配不成功时，从数组next中，获取下一个要比较的src位置，不必回溯des,从而使平均复杂度达到o(m+n)的级别，实现代码稍微有点复杂。

PS：实际应用中，基本都不用kmp算法，字符串的逐字符匹配足以解决实际中的绝大部分问题。

//KMP算法 void getNext(char *str, int &next[]){//求next数组 //next[1] = 0; 如果当前匹配成功，则next[j+1] = next[j] + 1， //如不成功，则相当于j取第k个的next值next[k]时，再匹配. assert(str != NULL); int i = 0; next[1] = 0; int j = 0; while(str[i] != '\0'){ if((j == 0)||str[i] == str[j]){
            i++;
            j++;
            next[i] = j;
        } else{
            j = next[j];
        }
    }
} //KMP字符串匹配，已知next数组 char *strstr(const char *des, const char *src, int &next[])
{
    assert(des != NULL && src != NULL); int i = 0, j = 0;//初始匹配值 while(des[i] != '\0' && src[j] != '\0'){ if(j == 0||des[i] == src[j]){
            i++;
            j++;
        } else{
            j = next[j];
        }
    } //结果判断 if(src[j] == '\0') return &des[i - strlen(j)]; else return NULL;
}

9 单链表基础

单链表是一种基本功，能体现对基础数据结构的了解，从中也能看出代码分格和对指针的理解与应用。对于单链表，需要注意节点空间的释放，参数形式和返回值;完成代码后，检查条件分支情况，并记得对初始条件进行验证。
单链表结构：

//单链表结构定义 typedef struct node_t{ int data; struct node_t *next;
}Node;

9.1 翻转单链表

知道单链表头指针，实现链表翻转。

/***  *@brief 单链表翻转  *@in head, 链表头指针  *@out head, 输出链表指针  *@return 链表头  */ Node* list_reverse(Node &*head){
    Node* p_pre = NULL;
    Node* p_post = NULL;
    Node* p_cur = head; while(p_cur != NULL){
        p_post = p_cur->next; if(p_post == NULL) head = p_cur;//当循环结束时，保存链表头 p_cur->next = p_pre;
        p_pre = p_cur;
        p_cur = p_post;     
    } return head;
}

9.2 删除链表中给定结点

最方便的方法是根据链表中结点结构，修改结点的内容，复杂度为o(1);

/***  *@brief 删除单链表中给定结点  *@in head, 链表头指针  *@in node, 为给定结点  */ void delete_node(Node &*head, Node* node){ if(head == NULL || node == NULL) return; if(node->next != NULL){//当删除结点不为尾结点 Node* tmp_node = node->next;
        node->data = tmp_node->data;
        node->next = tmp_node->next; delete tmp_node;
        tmp_node = NULL;
    } else{//为尾结点时，遍历链表找到头一个指针；PS不可直接将node置空 Node* tmp_node = head; while(tmp_node->next != node){
            tmp_node = tmp_node->next;
        }
        tmp_node->next = NULL; delete node;
        node = NULL;
    }
}

10 全排列或子集问题

求字符集的全排列或子集的问题，如已知字符集{a, b}, 求出其全排列{a, b}、{b、a}；已知字符集{a, b}，求出其所有子集{a}、{b}、{a, b}。

10.1 求字符集的全排列（无重复）

方法一：递归的方法，原理是对于[begin, end)的全排列，等价于arrary[begin]在[begin, end)某一位置上，剩余end - begin - 1个元素的全排列。

/***    *@brief 递归的方法求全排列, 且排列字符无重复  *@in array, 头指针  *@in begin, 首位置  *@in end, 尾位置(不含)  */ void fullPermutation(char *array, int begin, int end)
{ if((array == NULL) || (begin >= end)) 
    { return false;
    } if(begin == end - 1){
        cout << array << endl;
    } else{ for(int i = begin;i < end; i++){
            std::swap(array[begin], array[i]);
            fullPermutation(array, begin + 1, end);
            std::swap(array[begin], array[i]);//一定要换回来，不然扰序 }
    }
}

方法二：字典序法，原理简单，从正序遍历到逆序便得到完整的全排列。要点：假设原序为升序，目标是最终变成将序。例子“1234987”，step1:从最后一位开始找到第一个左边小于右边的数，例子中的4；step2:最后一位开始找，第一个大于step1中找到的数，例子中的7；step3:交换4和7，并倒置step1中找到数的后面的数即可，得到1237489；

/***  *@brief 字典序法求全排列, 且排列字符无重复  *@in array, 头指针  *@in begin, 首位置  *@in end, 尾位置(不含)  */ void fullPermutation(char *array, int begin, int end)
{ //先排成升序 std::sort(array, begin, end); //将升序变成全倒序便完成了对字符的全排序 while(1){
        cout << array << endl; //找第一个左边小于右边的数的位置,temp记录 int temp = 0; int i = end - 1; for(; i >= 0; i--){ if(array[i] < array[i + 1]){
                temp = i; break;
            }
        } if(i == -1){//遍历over return;
        } //找大于array[temp]的倒数第一个数 for(i = end; i > temp; i--){ if(array[i] > array[temp]){
                std::swap(array[i], array[temp]); break;
            }
        } //转置 for(i = 0; i <= (end - temp) / 2; i++){
            std::swap(array[temp + i + 1], array[end - i]);
        }       
    }   
}

10.2 求字符集的全排列（有重复）

字典的方法继续适用；递归的方法不再适用。

10.3 求字符集的所有组合

用递归的方法，对每个字符的选择只有选和不选，递归结束条件为选的元素个数==0或字符串为NULL。

/***  *@brief 求元素数为m的全组合  *@in array, 头指针  *@in m, 选择元素数目  *@in&out result, 结果  */ void Combination_m(char *array, int m, vector<char> &result)  
{ if(array == NULL || (*array == '\0'&& m != 0)) return; if(m == 0) //递归终止条件  { for(unsigned i = 0; i < result.size(); i++)  
            cout<<result[i];  
        cout<<endl; return;  
    } //选择这个元素  result.push_back(*array);  
    Combination_m(array + 1, m - 1, result);  
    result.pop_back(); //不选择这个元素  Combination_m(array + 1, m, result);  
} /***  *@brief 字符集的所有组合  *@in array, 头指针  */ void Combination(char *array)  
{ if(array == NULL || *array == '\0') return; int number = strlen(array); for(int i = 1; i <= number; i++)  
    {  
        vector<char> result;  
        Combination_m(array, i, result);  
    }  
}

----

只能永远把艰辛的劳动看作是生命的必要;即使没有收获的指望,也能心平气和的继续耕种。

扫码二维码 获取免费视频学习资料

Python编程学习

查看2022高级编程视频教程免费获取