题目的主要信息：  两个无环的单向链表，找出它们的第一个公共结点 如果没有公共节点则返回空 要求：空间复杂度O(1)O(1)O(1)，时间复杂度O(n)O(n)O(n)  方法一：长度比较法 具体做法： 我们可以分别统计两个链表的长度，然后对于较长的一个链表先走长度之差这么多步，在同步往后遍历，遇到的第一个相同的结点就是第一个公共结点。 public class Solution { public int Lenth(ListNode pHead){//计算链表的长度 ListNode p = pHead; int n = 0; while(p != null){ //遍历每一个结点 n++;...

题目的主要信息：  在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。 输入一个数组，求一个数组的全部逆序对，答案对1000000007取模 要求：空间复杂度O(n)O(n)O(n)，时间复杂度O(nlog2n)O(nlog_2n)O(nlog2​n) 保证输入的数组中没有的相同的数字  方法一：归并排序 具体做法： 因为我们在归并排序过程中会将数组划分成最小2个元素的子数组，然后依次比较子数组的长度，这里我们也可以用相同的方法统计逆序对。我们主要有三个阶段：  划分阶段：将待划分区间从中点划分成两部分； 排序阶段：使用归并排序递归地处理子序列，同时统计逆序对； ...

题目的主要信息：  在给定字符串中找到第一个只出现一次的字符的位置，从0开始 如果找不到则返回-1 字符串只有大小字母组成 要求：空间复杂度O(n)O(n)O(n)，时间复杂度O(n)O(n)O(n)  方法一：哈希表统计频率 具体做法： 我们可以建立一个无序哈希表，遍历字符串的同时，统计每个字符出现的频率，然后再从头遍历一次字符串，在哈希表中查看每个字符串的频率，找到第一个只出现一次的字符串，返回位置，如果没找到返回-1即可。 class Solution { public: int FirstNotRepeatingChar(string str) { unordered_map<c...

题目的主要信息：  把只包含质因子2、3和5的数称作丑数 求按从小到大的顺序的第n个丑数 1视作第一个丑数 要求：空间复杂度O(n)O(n)O(n)，时间复杂度O(n)O(n)O(n)  方法一：最小堆（能过，时间不符合要求） 具体做法： 我们都知道如果xxx是丑数，则2x2x2x、3x3x3x、5x5x5x都是丑数，丑数也是从1开始由每个丑数这样构建而来的，我们要做的就是找到前nnn个，即最小的nnn个。 我们可以利用小顶堆，每次取出堆顶元素一定是最小的，一共取nnn次就可以了，每次取出来的元素我们分别乘2、乘3、乘5后入堆，当然为了防止重复比如2∗3=62*3=62∗3=6、3∗2=63*...

题目的主要信息：  输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数  方法一：暴力统计法 具体做法： 我们可以尝试遍历1到n的每个数字，然后对每个数字单独遍历它的每一位，检查是否是1，如果是1则计数。 class Solution { public: int NumberOf1Between1AndN_Solution(int n) { int res = 0; for(int i = 1; i <= n; i++){ //遍历1-n for(int j = i; j > 0; j = j / 10){ //遍历每个数的每一位 if(j % 10 == 1) //...

题目的主要信息：  给定两棵二叉树的层次遍历序列 判断二叉树B是否为A树的子树 我们约定空树不是任意一个树的子结构  方法一：两层先序遍历 具体做法： 对A树的每个结点递归先序遍历，寻找是否有这样的子树，而寻找是否有子树的时候也是用递归，但这次是A树与B树同步先序遍历，遍历完一个B树或者有不相等的结点为止。  class Solution { public: bool recursion(TreeNode* root1, TreeNode* root2){ if(root1 == NULL && root2 != NULL) //当一个结点存在另一个不存在时 return fa...

题目的主要信息：  两个递增的链表，单个链表的长度为nnn 合并这两个链表并使新链表中的节点仍然是递增排序的 要求：空间复杂度 O(1)O(1)O(1)，时间复杂度 O(n)O(n)O(n)  方法一：递归（能过，空间不符合要求） 具体做法： 连接链表可以递归解决。我们每次比较两个链表当前结点的值，然后取较小值的链表指针往后，另一个不变送入递归中，添加后续的结点，而递归回来的结果我们要加在较小值的结点后面，相当于不断在较小值后面添加结点。而递归的终止是两个链表为空。 class Solution { public: ListNode* Merge(ListNode* pHead1, ListN...

题目的主要信息：  给定一个长度为nnn的链表，反转该链表，输出表头 要求：时间复杂度为O(n)O(n)O(n)，空间复杂度为O(1)O(1)O(1)  方法一：递归（能过，空间不符合要求） 具体做法： 我们可以利用递归的反向工作来实现逆转。对于每个结点我们递归向下遍历到最后，然后往上依次逆转两个结点，递归终止就是后面遇到了空结点。 class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(pHead == NULL || pHead->next == NULL) return pHead; ListNode...

题目的主要信息：  一个长度为nnn的链表，返回原链表中从倒数第k个结点至尾节点的全部节点 如果该链表长度小于k，请返回一个长度为 0 的链表 要求：时间复杂度O(n)O(n)O(n)，空间复杂度O(n)O(n)O(n)，进阶要求空间复杂度O(1)O(1)O(1)  方法一：先找长度再找最后k 具体做法： 我们可以先遍历一次链表找到链表的长度，然后比较链表长度是否比k小，如果比k小返回一个空链表，否则遍历n-k次即可找到所求。 class Solution { public: ListNode* FindKthToTail(ListNode* pHead, int k) { int n = 0...

题目的主要信息：  输入一个长度为nnn的数组，经过调整使所有的奇数在前半部分，所有的偶数在后半部分 奇数与奇数之间、偶数与偶数之间的相对位置关系不能变 要求：时间复杂度O(n)O(n)O(n)，空间复杂度O(n)O(n)O(n)  方法一：双指针复制法 具体做法： 可以准备一个待返回的长度为nnn的数组，我们先遍历数组array找到其中的奇数有多少个，然后准备两个起始坐标，x表示奇数的起始坐标从0开始，y表示偶数的起始坐标，从刚刚找到的奇数个数开始，然后遍历数组array，将所有的元素复制到待返回的数组中，遇到奇数我们用下标x，遇到偶数我们用下标y。  class Solution { pu...

题目的主要信息：  要从一个n∗mn*mn∗m网格的(1,1)(1,1)(1,1)位置走到(n.m)(n.m)(n.m)，每次只能往下或者往右，其中网格中有一块区域不能走 不能走的区域，左下角坐标是(x0,y0)(x_0,y_0)(x0​,y0​)，右下角坐标是(x1,y1)(x_1,y_1)(x1​,y1​) 问有多少条路径，要取模1000000007  方法一：空间记忆递归 具体做法： 我们考虑没有那个不能走的区域的情况，一个(n,m)(n,m)(n,m)问题，可以由两个(n−1,m)(n-1,m)(n−1,m) (n,m−1)(n,m-1)(n,m−1)子问题相加而来，因为最后一个位置要...

题目的主要信息：  一只青蛙一次可以跳上1级台阶，也可以跳上2级，先后次序算不同的方案 求该青蛙跳上一个n级的台阶总共有多少种跳法 要求：时间复杂度O(n)O(n)O(n)，空间复杂度O(1)O(1)O(1)  方法一：动态规划 具体做法： 我们用可以考虑第n级台阶，它可以由第n-1级台阶跳1级而来，也可以由第n-2级台阶跳2级而来，那么第n级台阶的方案就是第n-1级的方案数加上第n-2级的方案。不断往前推，每个台阶的方案数都可以由前两个台阶相加得到，这就是得到了斐波那契数列的递推公式：f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2)f(n)=f(n−1)+f(n−2)...

题目的主要信息：  给出两个等长的数列，求使第一个数列严格降序，第二个数列严格升序的最少交换次数 交换是指第一个数组中相对应的位置交换到第二个数组相对应位置 若无法交换成严格有序，返回“-1”  方法一：动态规划 具体做法：我们用两个动态规划数组来描述，其中dp1[i]表示第i个元素不需要调整即可满足要求，最少调整dp1[i]次，dp2[i]表示第i个元素需要调整才可以满足要求，最少调整dp2[i]次。初始时，必定有和.我们遍历数组，两个数组的相邻两元素进行下面四种检查：（i表示当前元素也即后一个元素）  如果数组1相邻两个元素递减，数组2相邻两个元素递增，那么我们不需要调整，有; 如果数组1...

题目的主要信息：  根据二叉树的前序遍历序列和中序遍历序列，重建该二叉树，并返回根节点 两个遍历都没有重复的元素  方法一：递归 具体做法：对于二叉树的前序遍历，我们知道序列的第一个元素必定是根节点的值，因为序列没有重复的元素，因此中序遍历中可以找到相同的这个元素，而我们又知道中序遍历中根节点将二叉树分成了左右子树两个部分，如下图所示：  我们可以发现，数字1是根节点，并将二叉树分成了(247)和(3568)两棵子树，而子树的的根也是相应前序序列的首位，比如左子树的根是数字2，右子树的根是数字3，这样我们就可以利用前序遍历序列找子树的根节点，利用中序遍历序列区分每个子树的节点数。我们可以递归解...