剑指offer题目大意和思路汇总

发表于 | 分类于 |

LeetCode有点多……先把剑指offer刷一遍复健一下……

二维数组中的查找：
题意：一个从左到右，从上到下都是递增的二维数组，求是否存在n
解法：for一遍，对于第x行，判断n是否在v[x][0]到v[x][v[x].size() - 1]之间，判断成功再for一遍check该行是否存在n就行了

替换空格：
题意：给一个字符串，把其中的空格替换成%20
解法：本来想用纯c的，写来写去都CE，干脆用string来写了，新建一个string逐个字符进行操作，要注意的是最后需要用strcpy函数把string.c_str()拷贝过来，不能直接用等号

从尾到头打印链表：
题意：给一个链表，让你返回链表值从尾到头的vector
解法：先用栈存val，然后再存回vector就好了，需要注意的是结构体里取值是用->，太久不用c++都忘记了…

用两个栈实现队列：
题意：用两个栈实现队列的pop和push操作
解法：一个栈用来做push，需要pop的时候把第一个栈的东西都倒腾到第二个栈里，然后pop就行了，注意不需要再把栈二的东西倒腾回去

旋转数组的最小数字：
题意：对于一个[3,4,5,1,2]这样的数组（非递减），找到该数组中最小的值
解法：O(n)最简单暴力，优化的话用二分，把vector[mid]和数组最后一个比较大小就能判断是往左还是往右二分了
备注：二分姿势为mid = (l + r) >> 1;l = mid + 1;r = mid;

跳台阶：
题意：青蛙一次可以跳1或2个台阶，问跳n个台阶有多少办法
解答：就是求斐波那契，因为n个台阶的跳法必定是n-1个台阶跳一个或者n-2的台阶跳两个

听来的题（一）：
题意：给一个数组，其中一个数只出现了一次，其余都出现了两次，求只出现一次的是什么数
解答：直接异或过去，最后得到的值就是答案

听来的题（二）：
题意：给一个数组，其中一个数只出现了一次，其余都出现了三次，求只出现一次的是什么数
解答：在外面做一个32的for循环，对每一个数的当前二进制位求和算有几个1，然后%3就知道当前这个位数有没有只出现一次的1了

重建二叉树

题意：给你一个二叉树先序遍历和中序遍历的结果，让你重建出这颗二叉树
解答：举例来说一棵树的先序遍历为{1,2,4,7,3,5,6,8}，中序遍历为{4,7,2,1,5,3,8,6}，是这样的，先序遍历的第一个值必定是当前树的根节点，对应到中序遍历就是1的左边为树的左边，右边则为树的右边，理解了这个就好做了，分别把这两个数组拆分成两颗子树的两个遍历序列，不断递归到为空就行了。

高级跳台阶：
题意：青蛙一次可以跳1-n个台阶，问跳n个台阶有多少种办法
解答：可推导出f(n)=f(n-1)+f(n-2)+…+f(0)，又知道f(n-1)=f(n-2)+…+f(0)，所以f(n) = 2f(n-1)

矩形覆盖：
题意：用n个1*2的矩形去构造一个2*n大小的矩形，有多少种办法
解答：还是斐波那契

二进制中1的个数:
题意：对于一个数求他二进制中1的个数
解答：一开始是操作这个n，每次>>1，结果错了……然后反过来用1来<<1就好了……不是很懂这个

数值的整数次方：

题意：求x的y次方
解答：快速幂可以把复杂度降到logn，做法就是把y拆成二进制，这样每做一次右移位运算，将当前的x更新为x^2，这么一来复杂度就下来了

调整数组顺序使奇数位于偶数前面：
题意：给你一个整数数组，要求把所有的奇数移动到偶数前面，但是相对位置不变
解答：可以当作是冒泡排序，只是交换条件换了一下，因为冒泡排序是稳定的；也可以新创建两个数组，分别存奇数和偶数然后再赋值回去

链表中倒数第k个结点：
题意：给你一个链表，返回倒数第k个结点
解答：两个指针都指向头结点，当第一个指针移动到第k个之后，第二个指针同步移动，坑是k可能为0，或者头结点可能为null

反转链表：
题意：给你一个链表，反转他，返回头结点
解答：新建一个头结点n，对于当前遍历到的原头结点，将其next设置为n，然后把这个修改过的结点赋值给n，再还原这个原头结点，就好了（叫头插法）

合并两个排序的链表：
题意：给你两个递增链表，要求合并
解答：直接上就完事了，记得赋值方法是ret->next = pHead

树的子结构：
题意：给你二叉树A和B，判断B是不是A的子树
解答：递归搜一下即可，如果当前点与当前树B的val一致，就左右都递归搜他们的子树对不对，搜到B树为NULL直接返回true，如果val值不一致，则只递归树A的子树，树B保持原样传参

二叉树的镜像：
题意：把一颗二叉树镜像翻转
解答：直接swap(root->right, root->left)，递归到底就好了

顺时针打印矩阵：
题意：把一个n*m的矩形顺时针打印出来
解答：这样跑一边，因为我这里没有考虑奇数情况，所以要check当前loop*2+1是不是等于行数或者列数就直接continue

第一个只出现一次的字符:
题意：输出第一个只出现了一次的字符的位置
解答：vis[i]为-1是未出现，-2为多次出现，否则就是位置，遍历一遍字符串后取最小的vis[i]即可

包含min函数的栈：
题意：实现一个栈类，其中包含一下O(1)查询函数min，返回栈中最小的数
解答：需要一个辅助栈，当一个新数入栈时，对比stack.top()，如果top更小则push(top)，否则push(value)

栈的压入、弹出序列：
题意：给你一个栈的压入序列和弹出序列，判断这个弹出序列是否合法
解答：直接建一个栈，每次push一个，同时用while来check当前的popV[pos]是否和stack.top()一致，一致则pos++，最后看一下栈是不是空的就好了

从上往下打印二叉树：
题意：见题目
解答：广搜就完事了

二叉搜索树的后序遍历序列：
题意：给出一棵树的后序遍历序列，判断其是不是一颗二叉搜索树
解答：后序遍历序列举例为{1,4,3,6,8,7,5}，其特征是最后一个点是根节点，前面的数列可以分为两段，分别全都小于（大于）这个根节点，于是我们就可以递归做了

二叉树中和为某一值的路径：
题意：给你一颗二叉树，要求出所有从根节点到叶子节点（也就是没有子节点的节点），路径上的值之和为e的路径，要求路径长度长的在前面
解答：递归深搜，构造是check(vector<vector> &ret, vector &v, TreeNode *root, e)，当e==root->val且当前节点没有左右子节点的时候，将当前的v存到ret中，当左右子节点都存在时，判断一下，优先递归值比较小的，这样路径长的就在前面了（大概）

复杂链表的复制：
题意：一个复杂链表，比普通链表多了一个指向任意节点的指针，要求复制他
解答：先在每个节点后面插入复制的新节点，然后根据每个节点的随机指针，赋值给复制的节点，因为每个节点后面跟着的就是复制节点，所有只要ptr->random = ptr->random->next就好了，最后把链表拆开来；竟然有坑……random指针竟然有可能会指向空…………

二叉搜索树与双向链表
题意：给你一颗二叉搜索树，把他变成一个有序的双向链表，不允许创建新的结点
解答：对二叉搜索树进行中序遍历，刚好就是按值从小到大遍历的，我们利用这个特性，构造函数check(TreeNode cur, TreeNode& pre)，pre存的是目前为止还没有被转换的最小值节点，每次左子树遍历完回来的时候，就将pre和cur改为互相指向，然后再把pre更新就好了

字符串的排列：
题意：给你一个字符串，按字典树输出他的全排列
解答：虽然他说了有重复，但是直接用next_permutation(str.begin(), str.end())也对了……标准方法是递归，对于当前递归到的位置，for一遍，所有和首字母不同的位置都可以交换，继续递归到底，然后把结果存到vector里。
额外小知识：next_permutation在C++中的实现是用非递归的方法，构造方式是从左往右找到第一个逆序数，然后再找一遍找到第一个大于该数的数，交换位置，然后再翻转从逆序数到末尾的全部数，就能构造出排列的下一个

数组中出现次数超过一半的数字：
题意：找出数组中出现次数超过长度一半的数
解答：首先先到排序后直接取中位数，这样复杂度是nlogn；更优的做法是O(n)的，因为出现次数超过长度的一半，所以count[N]应该大于count[]其余所有数的和，所以直接遍历一遍，存当前出现次数最多的数，最后check一次就好了，扔一下代码

int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size() == 0) return 0;
        int count = 1;
        int num = numbers[0];
        for(int i = 1;i < (int)numbers.size();i++)
        {
            if(num != numbers[i])
                count--;
            else
                count++;
            if(count == 0)
                count = 1, num = numbers[i];
        }
        count = 0;
        for(int i = 0;i < (int)numbers.size();i++)
        {
            if(numbers[i] == num)
                count++;
        }
        if(count * 2 > (int)numbers.size())
            return num;
        else
            return 0;
    }

最小的K个数：
题意：输出数组中最小的k个数
解答：直接用STL的优先队列就好了；或者可以维护一个最小堆，每次和堆顶对比，复杂度是k*logn
额外小知识：优先队列的底层实现就是用堆的，所以其实这两个方法是一样的

连续子数组的最大和：
题意：在数组中找出和最大的连续子序列
解答：双指针扫一遍就好了，当sum[st->ed]<0的时候，把头指针往后挪到sum>0为止，记录一下最大值

整数中1出现的次数（从1到n整数中1出现的次数）：
题意：如题，解答拓展到了任意一个数x
解答：按位置分别计算，拿百位出现x的计算举例，如果百位数小于x，那么出现的次数与高位有关，15311出现4的次数就是15次；如果百位数等于x，那么出现的次数与高位低位都有关，如15411，出现4的次数就是15+11+1；如果大于x的话，那么也只与高位有关，15511出现4的次数就是15+1次，然后就能算了；还需要注意的特性就是高位算次数的时候需要*n，n为当前位数，比如百位n就是100

把数组排成最小的数：
题意：把数组所有的数拼接起来后输出，要求字典序最小
解答：定义个cmp函数sort一下就完事了

丑数
题意：把质因子只含2，3，5的数定义为丑数，默认第一个丑数为1，要求输出第n个丑数
解答：DP，状态转移方程是dp[i] = min(dp[p1] 2, min(dp[p2] 3, dp[p3] 5))，p1,p2,p3分别是上一次乘了2，3，5的丑数位置，取最小的设置为第i个丑数，递推到底就好了。需要注意的是为了防止2\3和3*2判两遍，在判断的时候全都要判一遍

int GetUglyNumber_Solution(int index) {
        if(index <= 0) return 0;
        int p1 = 0, p2 = 0, p3 = 0;
        vector<int>dp(index);
        dp[0] = 1;
        for(int i = 1;i < index;i++)
        {
            dp[i] = min(dp[p1] * 2, min(dp[p2] * 3, dp[p3] * 5));
            if(dp[i] == dp[p1] * 2) p1++;
            if(dp[i] == dp[p2] * 3) p2++;
            if(dp[i] == dp[p3] * 5) p3++;
        }
        return dp[index - 1];
    }

数组中的逆序对：
题意：就是求逆序对
解答：已经完全不会树状数组了……学个简单的用归并来求的方法，复杂度是nlogn，就在归并的时候跑一边前后两个数组，求一下逆序对数。做一遍这样的递归就好了……不知道为什么……二分的时候取(l,mid-1)和(mid,r)一直爆内存，改成(l,mid)和(mid+1,r)就好了

机器人的运动范围：
题意，对于一个由n*m个方格组成的矩形，给出一个k，合法方格为数位和小于k的方格，求最多能从(0,0)出发去多少个方格
解答：广搜即可，不知道为啥我memset没法初始化整个vis数组……然后要注意k可能为负数

热评文章