IT资讯

IT面试题集

来源:博客园 2019-01-01 20:15:23737


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

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::max()可用(unsigned)(-1)>>1表示。

二分查找

6.1 经典二分查找

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

//二分查找array中key int binarySearch(int* array,int low,int high,int key)
{ while(low//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(lowint 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(lowint mid=low+(high-low)/2; if(array[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<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);  
    }  
}

 

----

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


文章推荐