1 二维数组的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

class Solution {public:    /**    利用    每一行都按照从左到右递增的顺序排序    每一列都按照从上到下递增的顺序排序    如果 xx 小于target，则 xx 左边的数一定都小于target，我们可以直接排除当前一整行的数；    如果 xx 大于target，则 xx 下边的数一定都大于target，我们可以直接排序当前一整列的数；    参考：    */    bool Find(int target, vector<vector<int> > a) {        //如果a为空 直接返回false        if(a.empty()||a[0].empty())return false;        int i = 0, j = a[0].size() - 1;//要从右上角往左下角找        while(i < a.size() && j >= 0){            if(a[i][j] == target)return true;//找到直接返回            if(a[i][j] > target) j--;//列往左边移动            else i++;//行往下移动找        }        return false;    }};

2 替换空格

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

 class Solution {public:	void replaceSpace(char *str,int length) {        if(str == NULL) return; //如果是空 直接返回        //空格数 原始串的长 新串的长        int blanks = 0, len = 0, newlen = 0;        for(int i = 0;str[i]!='\0';i++){            len++;            if(str[i]==' ')                blanks++;        }        //新串的长 每次替换 多增加两个字符        newlen = len + 2*blanks;                //如果新串的长大于length 直接返回        if(newlen + 1 > length)return;                //str1指针指向旧串的最后一个字符        char * str1 = str + len;                //str2指针指向新串的最后一个字符        char * str2 = str + newlen;                //从后向前自制旧串 并替换空格        while(str1 != str2){            if(*str1 == ' '){                *str2 -- = '0';                *str2 -- = '2';                *str2 -- = '%';            }            else                *str2 -- = *str1;            --str1;        }        	}};

3 从尾到头打印链表

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

/***  struct ListNode {*        int val;*        struct ListNode *next;*        ListNode(int x) :*              val(x), next(NULL) {*        }*  };   没有什么要求，直接遍历一次链表，每次向vector.begin()处插入就行了*/class Solution {public:    vector<int> printListFromTailToHead(ListNode* head) {        vector<int> res;        while(head){            res.insert(res.begin(),head->val);            head = head->next;        }        return res;    }};

4 重建二叉树

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

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; 算法(递归) O(n)O(n)递归建立整棵二叉树：先递归创建左右子树，然后创建根节点，并让指针指向两棵子树。具体步骤如下：先利用前序遍历找根节点：前序遍历的第一个数，就是根节点的值；在中序遍历中找到根节点的位置 kk，则 kk 左边是左子树的中序遍历，右边是右子树的中序遍历；假设左子树的中序遍历的长度是 ll，则在前序遍历中，根节点后面的 ll 个数，是左子树的前序遍历，剩下的数是右子树的前序遍历；有了左右子树的前序遍历和中序遍历，我们可以先递归创建出左右子树，然后再创建根节点；时间复杂度分析我们在初始化时，用哈希表(unordered_map<int,int>)记录每个值在中序遍历中的位置，这样我们在递归到每个节点时，在中序遍历中查找根节点位置的操作，只需要 O(1)O(1) 的时间。此时，创建每个节点需要的时间是 O(1)O(1)，所以总时间复杂度是 O(n)O(n)。参考： */class Solution {public:        TreeNode* dfs(unordered_map<int,int> &pos,vector<int> &pre, vector<int> &vin, int pl, int pr, int vl, int vr){        if(pl > pr)return 0;        int k = pos[pre[pl]] - vl ;//k的左边为左子树，右边为右子树        TreeNode* root = new TreeNode(pre[pl]);//创建根        root->left = dfs(pos, pre, vin, pl + 1, pl + k, vl, vl + k - 1);//递归创建左子树，更新下次pre和vin        root->right = dfs(pos, pre, vin, pl + k + 1, pr,  vl + k + 1, vr);//递归创建右子树，更新下次pre和vin        return root;    }    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {        int n = pre.size();        unordered_map<int,int> pos;//记录中序遍历的位置        for(int i = 0; i < n; i++){            pos[vin[i]] = i;        }        return dfs(pos, pre, vin, 0, n - 1, 0, n - 1);    }    };

5 用栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

/**用两个栈 一个缓存用当操作时 先把主栈的数据先全部放到缓存然后再pop完成后放到主栈**/ class Solution{public:    void copy(stack<int> &a, stack<int> &b) {        while (a.size()) {            b.push(a.top());            a.pop();        }    }    void push(int node) {        stack1.push(node);    }    int pop() {        copy(stack1,stack2);        int res = stack2.top();        stack2.pop();        copy(stack2,stack1);        return res;    } private:    stack<int> stack1;//主栈    stack<int> stack2;//缓存栈};

6 旋转数组中最小的数字

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

/**数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转可以看出因为旋转前数组是递增旋转后有一个这个递增就断了相当于找到一个数比第一个数小的情况就可以返回这个数**/class Solution {public:    int minNumberInRotateArray(vector<int> rotateArray) {        if(!rotateArray.size())return 0;        int res = rotateArray[0];        for(int i = 1; i < rotateArray.size(); i++){            if(rotateArray[i] < res)return rotateArray[i];        }        return res;    }};

7 斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39。

/**这个没什么好说的建议用递推除非面试官要求 否则不要用递归**/class Solution {public:    int Fibonacci(int n) {        if(n == 0) return 0;        if(n == 1) return 1;        int first = 0, second = 1, third = 0;        while(n--){            third = first + second;            first = second;            second = third;        }        return first;    }};

8 跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

/**假设处于当前台阶那么从其他台阶跳上来的要么从前一个台阶跳上来 要么从前面第2个跳过来那么 跳到当前台阶的就有f(n-1) + f(n - 2)**/class Solution {public:    int jumpFloor(int n) {        if(n == 1) return 1;        if(n == 2) return 2;        return jumpFloor(n - 1) + jumpFloor(n - 2);    }};

9 变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

/**因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级跳1级，剩下n-1级，则剩下跳法是f(n-1)跳2级，剩下n-2级，则剩下跳法是f(n-2)所以f(n)=f(n-1)+f(n-2)+...+f(1)因为f(n-1)=f(n-2)+f(n-3)+...+f(1)所以f(n)=2*f(n-1)假设f(1) = 1;所以：f(2)=1+f(1)=1+1=2=2^1;f(3)=1+f(2)+f(1)=1+2+1=4=2^2;f(4)=1+f(3)+f(2)+f(1)=1+4+2+1=8=2^3;......归纳：f(n) = 2^(n-1);（n>=1的整数）**/class Solution {public:    int jumpFloorII(int number) {        int a = 1;         return a << (number - 1);//左移乘2 右移除2 如在折半查找中 可以 int mid = (l + r) >> 1    }};

10 矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

class Solution {public:    int rectCover(int n) {        if(n == 1) return 1;        if(n == 2) return 2;        int first = 1, second = 2, third = 0;        for(int i=3;i<=n;i++){            third = first + second;            first = second;            second = third;        }        return third;    }};

11 二进制中1的个数

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

/**(位运算) O(logn)O(logn)迭代进行如下两步，直到 nn 变成0为止：如果 nn 在二进制表示下末尾是1，则在答案中加1；将 nn 右移一位，也就是将 nn 在二进制表示下的最后一位删掉；这里有个难点是如何处理负数。在C++中如果我们右移一个负整数，系统会自动在最高位补1，这样会导致 nn 永远不为0，就死循环了。解决办法是把 nn 强制转化成无符号整型，这样 nn 的二进制表示不会发生改变，但在右移时系统会自动在最高位补0。时间复杂度每次会将 nn 除以2，最多会除 lognlogn 次，所以时间复杂度是 O(logn)O(logn)。参考大神：**/class Solution {public:     int  NumberOf1(int n) {         int res = 0;         unsigned int u = n;         while(u) res += u & 1, u >>= 1;         return res;     }};

12 数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

/**求幂就是n个base相乘如果是负数，取倒数**/class Solution {public:    double Power(double base, int exponent) {        double res = 1;        for(int i = 0; i < abs(exponent); i++)            res *= base;        if(exponent < 0)            res = 1 / res;        return res;    }};

13 调整数组顺序使奇数位于偶数前面

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

/**由于没有内存申请限制直接用两个队列 一个装奇数 一个装偶数依次按放到原来的数组**/ class Solution {public:    void reOrderArray(vector<int> &array) {        queue<int> s1,s2;        for(auto it: array){            if(it % 2 == 0)                s2.push(it);            else s1.push(it);        }        for(int i = 0; i < array.size(); i++){            if(!s1.empty()){                array[i] = s1.front();                s1.pop();            }            else{                array[i] = s2.front();                s2.pop();            }        }       }};

14 链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

/*struct ListNode {	int val;	struct ListNode *next;	ListNode(int x) :			val(x), next(NULL) {	}    先算出链表的长度n    倒数第k个结点即为顺数第n-k个结点        };*/class Solution {public:    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {        int len = 0;        auto cur = pListHead;        while(cur){            len++;            cur = cur->next;        }        if(pListHead == NULL || k > len || k < 1)return NULL;        int i = len - k;        cur = pListHead;        while(i--){            cur = cur->next;        }        return cur;    }};

15 反转链表

输入一个链表，反转链表后，输出新链表的表头

/*struct ListNode {	int val;	struct ListNode *next;	ListNode(int x) :			val(x), next(NULL) {	}};*/class Solution {public:     ListNode* ReverseList(ListNode* pHead) {        ListNode *pre = NULL, *next = NULL;                while(pHead){            //做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre            //如此就可以做到反转链表的效果            //先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂            next = pHead->next;//记录当前结点的下一个结点             //保存完next，就可以让head从指向next变成指向pre了            pHead->next = pre;             //head指向pre后，就继续依次反转下一个节点            //让pre，head，next依次向后移动一个节点，继续下一次的指针反转            pre = pHead;            pHead = next;        }        //如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点        //直接输出pre就是我们想要得到的反转后的链表        return pre;    }};

16 合并两个有序链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

/*struct ListNode {	int val;	struct ListNode *next;	ListNode(int x) :			val(x), next(NULL) {	}};没有什么可说的就像合并两个有序数组*/class Solution {public:    ListNode* Merge(ListNode* p1, ListNode* p2)    {        auto d = new ListNode(-1);//虚拟头结点        auto t = d;        while(p1&&p2){            if(p1->val < p2->val){//小的先排                t->next = p1;                p1 = p1->next;                t = t->next;            }            else{                t->next = p2;                p2 = p2->next;                t = t->next;            }                        }        if(p1)t->next = p1;//如果还有直接接到t的屁股后面        if(p2)t->next = p2;        return d->next;    }};

17 树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/*struct TreeNode {	int val;	struct TreeNode *left;	struct TreeNode *right;	TreeNode(int x) :			val(x), left(NULL), right(NULL) {	}    算法(二叉树，递归) O(nm)O(nm)代码分为两个部分：遍历树A中的所有非空节点R；判断树A中以R为根节点的子树是不是包含和树B一样的结构，且我们从根节点开始匹配；对于第一部分，我们直接递归遍历树A即可，遇到非空节点后，就进行第二部分的判断。对于第二部分，我们同时从根节点开始遍历两棵子树：如果树B中的节点为空，则表示当前分支是匹配的，返回true；如果树A中的节点为空，但树B中的节点不为空，则说明不匹配，返回false；如果两个节点都不为空，但数值不同，则说明不匹配，返回false；否则说明当前这个点是匹配的，然后递归判断左子树和右子树是否分别匹配即可；时间复杂度最坏情况下，我们对于树A中的每个节点都要递归判断一遍，每次判断在最坏情况下需要遍历完树B中的所有节点。所以时间复杂度是 O(nm)O(nm)，其中 nn 是树A中的节点数， mm 是树B中的节点数。参考大神：};*/class Solution {public:    bool isSubtree(TreeNode* r1, TreeNode* r2){        if(!r2)return true;        if(!r1 || r1->val != r2->val)return false;        return isSubtree(r1->left, r2->left) && isSubtree(r1->right, r2->right);    }    bool HasSubtree(TreeNode* r1, TreeNode* r2)    {        if(!r1 || !r2)return false;        if(isSubtree(r1, r2))return true;        return HasSubtree(r1->left, r2) || HasSubtree(r1->right, r2);    }};

18 二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述:

二叉树的镜像定义：源二叉树

8

/ \

6 10

/ \ / \

5 7 9 11

镜像二叉树

8

/ \

10 6

/ \ / \

11 9 7 5

/*没什么好说的直接交换当前结点的左右孩子如果当前结点还有左右孩子分别递归交换直到递归结束struct TreeNode {	int val;	struct TreeNode *left;	struct TreeNode *right;	TreeNode(int x) :			val(x), left(NULL), right(NULL) {	}};*/class Solution {public:    void Mirror(TreeNode *r) {        if(!r)return;//没有左右孩子则直接返回        swap(r->left,r->right);//交换左右孩子        Mirror(r->left);//递归，继续遍历左子树        Mirror(r->right);//递归，继续遍历右子树    }};

19 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

/**分别得到行和列的开始和末尾索引首先遍历完当前行后 开始行++然后列从开始行索引开始遍历后 列--末尾行从末尾列往回遍历开始列从末尾行到开始行往回遍历直到list长度和size一样 结束循环由于没有其他空间，不算题目要的list的话 空间复杂度O(1) 时间复杂度O(n^2)**/class Solution {public:    vector<int> printMatrix(vector<vector<int> > matrix) {        vector<int> list;        if(matrix.size() == 0) return list;        //水平行的最开始的索引 和 最后的索引         int h_first_index = 0, h_last_index = matrix.size() - 1;        //垂直列的最开始的索引 和 最后的索引         int v_first_index = 0, v_last_index = matrix[0].size() - 1;        //数组的长度        int size = (h_last_index + 1)*(v_last_index + 1);        //是否遍历结束        bool flag = true;                while(flag){            // 先算开始第一行            for(int i = v_first_index;i <= v_last_index;i++) {                list.push_back(matrix[h_first_index][i]);                if(list.size() >= size){                    flag = false;                    break;                }            }            h_first_index ++;            if(list.size() >= size){                break;            }            // 再算最后一列            for(int i=h_first_index;i<=h_last_index;i++) {                list.push_back(matrix[i][v_last_index]);                if(list.size() >= size){                    flag = false;                    break;                }            }            v_last_index --;            if(list.size()>=size){                break;            }            // 再算最后一行            for(int i=v_last_index;i>=v_first_index;i--) {                list.push_back(matrix[h_last_index][i]);                if(list.size() >= size){                    flag = false;                    break;                }            }            h_last_index --;            if(list.size()>=size){                break;            }            // 最后算开始第一列            for(int i = h_last_index;i >= h_first_index;i--) {                list.push_back(matrix[i][v_first_index]);                if(list.size() >= size){                    flag = false;                    break;                }            }            v_first_index ++;            if(list.size() >= size){                break;            }        }        return list;    }};

另外，我还写了一个递归的版本可以用一个bool数组来判断是否遍历，这个消耗一点空间，但是代码看起来很清晰，代码：

int di[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};vector<int> res;vector<vector<bool>> used;bool isArea(int x, int y, int row, int col){    return row>=0 && row<x && col>=0 && col<y;}void dfs(int d, const vector<vector<int> > &matrix, int x, int y, int row, int col){        int dx = di[d%4][0], dy = di[d%4][1];    if(isArea(x,y,row,col) && !used[row][col]){        int tempRow = row, tempCol = col;        row += dx, col += dy;        if(!isArea(x,y,row,col) || used[row][col] ){            if(res.size() + 1 == x * y){//只有最后一个元素了，直接添加并返回                res.push_back(matrix[tempRow][tempCol]);                return;            }            dfs(d + 1, matrix, x, y, row - dx, col - dy);        }else{            cout<<matrix[tempRow][tempCol]<<endl;            res.push_back(matrix[tempRow][tempCol]);            used[tempRow][tempCol] = true;            dfs(d, matrix, x, y, row, col);         }    }    }vector<int> printMatrix(vector<vector<int> > &matrix) {    if(!matrix.size() || !matrix[0].size()) return res;    int x = matrix.size(),y = matrix[0].size();        used = vector<vector<bool>>(x, vector<bool>(y, false));    dfs(0, matrix, x, y, 0, 0);    return res;}

也可以参考yxc大神的方法。

class Solution {public:    vector<int> printMatrix(vector<vector<int>>& matrix) {        vector<int> res;        if (matrix.empty()) return res;        int n = matrix.size(), m = matrix[0].size();        vector<vector<bool>> st(n, vector<bool>(m, false));        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};        int x = 0, y = 0, d = 1;        for (int k = 0; k < n * m; k ++ )        {            res.push_back(matrix[x][y]);            st[x][y] = true;             int a = x + dx[d], b = y + dy[d];            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b])            {                d = (d + 1) % 4;                a = x + dx[d], b = y + dy[d];            }            x = a, y = b;        }        return res;    }};

参考链接：

20 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

class Solution {public:    /**    我们除了维护基本的栈结构之外，还需要维护一个单调栈，来实现返回最小值的操作。    下面介绍如何维护单调栈：    当我们向栈中压入一个数时，如果该数 ≤≤ 单调栈的栈顶元素，则将该数同时压入单调栈中；否则，不压入，这是由于栈具有先进后出性质，所以在该数被弹出之前，栈中一直存在一个数比该数小，所以该数一定不会被当做最小数输出。    当我们从栈中弹出一个数时，如果该数等于单调栈的栈顶元素，则同时将单调栈的栈顶元素弹出。    单调栈由于其具有单调性，所以它的栈顶元素，就是当前栈中的最小数。        时间复杂度    四种操作都只有常数次入栈出栈操作，所以时间复杂度都是 O(1)O(1).    参考链接：    */    stack<int> m;    stack<int> s;    void push(int value) {        s.push(value);        if(m.empty() || m.top() >= value)            m.push(value);    }    void pop() {        if(m.top() == s.top()) m.pop();        s.pop();    }    int top() {        return s.top();    }    int min() {        return m.top();    }};