栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > 资讯 > 高等教育 > 考研政策

经典笔试面试知识整理,数据结构与算法(代码演示)

经典笔试面试知识整理,数据结构与算法(代码演示)

一,二维数组中的查找

题目描述:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。输入描述: array: 待查找的二维数组 target:查找的数字输出描述:查找到返回true,查找不到返回false

class Solution {public:    bool Find(vector<vector<int> > array,int target) {        bool found = false;        int rows = array.size();        int columns = array[0].size();        if(!array.empty() && rows > 0 && columns > 0){            int row=0;            int column = columns-1;            while(row < rows && column >= 0){                if(array[row][column] == target){                    found = true;                    break;                }                else if(array[row][column] > target)                    --column;                else                    ++row;            }        }        return found;    }};
二,替换空格

题目描述:请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

class Solution {   public: void replaceSpace(char *str,int length) {        if(str == NULL || length <= 0)            return;        int originalLength = 0;        int numberOfSpace = 0;        int i=0;        while(str[i] != ''){            ++ originalLength;            if(str[i]==' ')                ++ numberOfSpace;            ++i;        }        int newLength = originalLength + 2*numberOfSpace;        if(newLength > length)            return;        int originalIndex = originalLength;        int newIndex = newLength;        while(originalIndex >= 0 && newIndex > originalIndex){            if(str[originalIndex] == ' '){                str[newIndex--] = '0';                str[newIndex--] = '2';                str[newIndex--] = '%';            }            else                str[newIndex--] = str[originalIndex];            --originalIndex;        } }};
三,从尾到头打印链表

题目描述: 输入一个链表,从尾到头打印链表每个节点的值。输入描述: 输入为链表的表头输出描述: 输出为需要打印的“新链表”的表头

class Solution {public:    vector<int> printListFromTailToHead(struct ListNode* head) {        std::stack<ListNode*> nodes;        vector<int> result;        ListNode* pNode = head;        while(pNode != NULL){            nodes.push(pNode);            pNode = pNode->next;        }        while(!nodes.empty()){            pNode = nodes.top();            result.push_back(pNode->val);            nodes.pop();        }        return result;    }};
四,重建二叉树

题目描述:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

class Solution {public:    struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {        if(pre.empty() || in.empty())            return NULL;        return ConstructBinaryTree(pre.begin(),pre.end()-1,in.begin(),in.end()-1);    }    struct TreeNode* ConstructBinaryTree    (vector<int>::iterator startPre,vector<int>::iterator endPre,     vector<int>::iterator startIn,vector<int>::iterator endIn){        int rootValue = *startPre;        TreeNode* root = new TreeNode(rootValue);        if(startPre == endPre){            if(startIn == endIn && *startPre == *startIn)                return root;            else                return NULL;        }        vector<int>::iterator rootInOrder = startIn;        while(rootInOrder <= endIn && *rootInOrder != rootValue)            ++rootInOrder;        if(rootInOrder == endIn && *rootInOrder != rootValue)            return NULL;        int leftLength = rootInOrder - startIn;        vector<int>::iterator leftPreEnd = startPre + leftLength;        if(leftLength>0)            root->left = ConstructBinaryTree(startPre+1,leftPreEnd,startIn,rootInOrder-1);        if(leftLength < endIn - startIn)            root->right = ConstructBinaryTree(leftPreEnd+1,endPre,rootInOrder+1,endIn);        return root;    }};
五,旋转数组的最小数字

题目描述:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

class Solution {public:    int minNumberInRotateArray(vector<int> rotateArray) {        if(rotateArray.empty())            return 0;        int index1 = 0;        int index2 = rotateArray.size()-1;        int indexMid = index1;        while(rotateArray[index1] >= rotateArray[index2]){            // quit condition            if(index2 - index1 == 1){                indexMid = index2;                break;            }            indexMid = (index1 + index2) / 2;            //the three numbers are equal            if(rotateArray[index1] == rotateArray[index2]               && rotateArray[indexMid] == rotateArray[index1]){                return MinInOrder(rotateArray,index1,index2);            }            //no equal            if(rotateArray[indexMid] >= rotateArray[index1]){                index1 = indexMid;            }            else if(rotateArray[indexMid] <= rotateArray[index2]){                index2 = indexMid;            }        }        return rotateArray[indexMid];    }    int MinInOrder(vector<int> rotateArray,int index1,int index2){        int result = rotateArray[index1];        for(int i=index1+1;i<=index2;i++){            if(result > rotateArray[i])                result = rotateArray[i];        }        return result;    }};
六,Fibonacci数列及其变形

1、题目描述:大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。n<=39

class Solution {public:    int Fibonacci(int n) {        if(n == 0)            return 0;        if(n == 1)            return 1;        int i;        long long temp1 = 1;        long long temp2 = 0;        long long temp = 0;        for (i=2;i<= n;i++){            temp = temp1+temp2;            temp2 = temp1;            temp1 = temp;        }  return temp;    }};

2、题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

class Solution {public:    int jumpFloor(int number) {        if(number==1)            return 1;        if(number==2)            return 2;        long long temp2 = 1;        long long temp1 = 2;        long long temp =0;        for(int i=3;i<=number;i++){            temp = temp1+temp2;            temp2 = temp1;            temp1 = temp;        }        return temp;    }};

3、题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

class Solution {public:    int jumpFloorII(int number) {        int result = 1;        for(int i=1;i<number;i++)            result *=2;  return result;    }};

4、题目描述:我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

class Solution {public:    int rectCover(int number) {        if(number < 2)            return 1;        if(number == 2)            return 2;        long long temp2=1;        long long temp1=2;        long long temp=0;        for(int i=3;i<=number;i++){            temp = temp1 + temp2;            temp2 = temp1;            temp1 = temp;        }        return temp;    }};
七,1的个数和数值的整次方

1、题目描述:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

class Solution {   public:     int  NumberOf1(int n) {         int count = 0;         while(n){             ++count;             n = (n-1)&n;         }         return count;     }};

2、题目描述:给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

class Solution {public:    double Power(double base, int exponent) {        if(equal(base, 0.0) && exponent < 0) return 0.0;        double result = 1.0;        unsigned int abs_exponent = (unsigned int)exponent;        if(exponent < 0) abs_exponent = (unsigned int)(-exponent);        for(int i=0;i<abs_exponent;++i){            result *= base;        }        if(exponent < 0)            return 1.0 / result;        else            return result;    }    bool equal(double num1, double num2){        if(num1 - num2 < 0.0000001 && num1 - num2 > -0.0000001)            return true;        else            return false;    }};
八,调整数组顺序使奇数位于偶数前面

题目描述:输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

class Solution {public:    //时间复杂度O(n),空间复杂度O(n)    void reOrderArray(vector<int> &array) {        if(array.empty()) return;        vector<int> array_tmp;        vector<int>::iterator itor, itor_tmp;        for(auto itor = array.begin(); itor != array.end();){            if((*itor % 2) == 0){                array_tmp.push_back(*itor);                itor = array.erase(itor);            }else{                itor++;            }        }        for(auto itor_tmp = array_tmp.begin(); itor_tmp != array_tmp.end(); itor_tmp++){            array.push_back(*itor_tmp);        }    }};
九,用两个栈实现队列

题目描述:用两个栈来实现一个队列,完成队列的Push和Pop操作, 队列中的元素为int类型。

class Solution{public:    void push(int node) {        stack1.push(node);    }    int pop() {        if(stack2.size()<=0){            while(stack1.size()){                int data = stack1.top();                stack1.pop();                stack2.push(data);            }        }        int head = stack2.top();        stack2.pop();        return head;    }private:    stack<int> stack1;    stack<int> stack2;};
十,链表中倒数第k个结点

题目描述:输入一个链表,输出该链表中倒数第k个结点。

class Solution {public:    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {     if(pListHead == nullptr || k == 0) return nullptr;        ListNode *pAhead = pListHead;        ListNode *pBehind = nullptr;        for(int i=0;i<k-1;++i){            if(pAhead->next)                pAhead = pAhead->next;            else                return nullptr;        }        pBehind = pListHead;        while(pAhead->next){            pAhead = pAhead->next;            pBehind = pBehind->next;        }        return pBehind;    }};
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/news/1550486.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号