题目的主要信息：  在一个非降序的链表中，存在重复的结点，删除该链表中重复的结点，重复的结点不保留 进阶要求：时间复杂度：O(n)O(n)O(n)，空间复杂度：O(n)O(n)O(n)  方法一：哈希表 具体做法： 可以遍历一次链表用哈希表记录每个结点值出现的次数，然后在链表前加一个结点值为0的表头（返回的时候，直接返回res->next，加表头是为了防止删除时全部结点删完了）。再次遍历该链表，对于每个结点值检查哈希表中的计数，只留下计数为1的，其他情况都删除。 class Solution { public: ListNode* deleteDuplication(ListNode* ...

题目的主要信息：  查找两个字符串str1，str2中的最长的公共子串 保证str1和str2的最长公共子串存在且唯一 进阶要求：时间复杂度：O(n2)O(n^2)O(n2)，空间复杂度：O(n2)O(n^2)O(n2)  方法一：暴力枚举 具体做法： 遍历str1每个字符作为起点，然后遍历以其为起点的每个长度的长度，即暴力枚举字符串str1的所有子串，用find函数查看每个子串是否在字符串str2中出现，如果出现比较长更新为较长的子串长度。 class Solution { public: string LCS(string str1, string str2) { string res =...

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

题目主要信息： 将一棵n个节点的二叉树按照从上到下按层的方式打印，每层按照从左到右的顺序输出。 思路： 题目要求将二叉树按行打印，即按层打印，其中每层分开。不难想到，要使用层次遍历，但是难点在于如何每层分开存储，从哪里知晓分开的时机？在层次遍历的时候，我们通常会借助队列（queue）,事实上，队列中的值大有玄机，让我们一起来看看：  当根节点进入队列时，队列长度为1，第一层结点数也为1 若是根节点有两个子节点，push进队列后，队列长度为2，第二层结点数也为2；若是根节点一个子节点，push进队列后，队列长度为为1，第二层结点数也为1. 由此，我们可知，每层的结点数等于进入该层时队列长度，因为...

题目主要信息：  给定一棵结点数为n二叉搜索树，需要其中的第k小的TreeNode结点值 返回第k小的节点值即可 不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1 保证n个节点的值不一样  思路： 根据二叉搜索树的性质，其中序遍历是由大到小的，由此仅需要中序遍历找到第k个小的结点即可。 中序遍历有两种方式。  方法一：递归中序遍历 具体做法： 另写一函数进行递归中序遍历，设置全局变量count记录遍历了多少个结点，res记录第k个结点。 class Solution { public: TreeNode* res = NULL;//记录返回的结点 int count = ...

题目的主要信息：  输入一棵二叉树，求该树的深度 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度  方法一：递归（dfs） 具体做法： 对于一棵二叉树而言，其深度等于根结点这个1层+左子树和右子树深度的最大值，而每个子树我们都可以看成根节点，于是我们可以对这个问题划为子问题，利用递归来解决: rootdepth=max(leftdepth,rightdepth)+1root_{depth} = max(left_{depth}, right_{depth})+1rootdepth​=max(leftdepth​,rightdepth​)+1 递归的终点...

题目的主要信息：  给定一个长度为n的非降序数组和一个数字k，求k在数组中出现的次数 要求：时间复杂度O(log2n)O(log_2n)O(log2​n) ，空间复杂度O(1)O(1)O(1)  方法一：暴力遍历法（能过，时间不符合要求） 具体做法： 直接遍历数组data，查看每个数是否是等于k，然后计数即可。 class Solution { public: int GetNumberOfK(vector<int> data ,int k) { int res = 0; for(int i = 0; i < data.size(); i++) //遍历数组 if(data[...

题目中的信息：  两个链表含有公共结点或没有，有公共结点则返回第一公共结点指针 单链表，无循环 没有公共节点返回空 要求：时间复杂度：O(n)O(n)O(n)，空间复杂度：O(1)O(1)O(1)  方法一：双指针长度比较法 具体做法： 我们可以通过单独的遍历比较两个链表的长度，得到长度差n，其中较长的链表先动n次指针，然后两链表同步向后，相等之处便是第一个公共结点。  class Solution { public: int ListLenth( ListNode* pHead){ //计算链表长度的函数 ListNode* p = pHead; int n = 0; while(p != ...

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

题目主要信息： 判断给出的二叉树是否是平衡二叉树 思路 判断某二叉树是否为平衡二叉树，就需要判断任意一结点两边子树深度相差是否绝对值大于1，同时它的子树也符合平衡二叉树的规则。 则可以相当将问题不断分成子问题，使用递归。 方法一：递归判断+递归计算深度 具体做法： 写两个函数，一个递归遍历二叉树所有结点，判断该结点下的子树是否为平衡二叉树，另一个函数则递归计算该结点深度。 图中为判断函数的递归图，其中计算深度函数递归也是如此。  class Solution { public: int deep(TreeNode* root){//计算该子树深度 if(root == NULL) //空结点深...

题目的主要信息：  将一个英文语句以单词为单位逆序排放 所有单词之间用一个空格隔开，没有仅含空格的案例 进阶要求：时间复杂度O(n)O(n)O(n)，空间复杂度O(n)O(n)O(n)  方法一：两次反转 具体做法： 将输入的字符串反转，得到了完全逆序的字符串，单词与单词之间确实是逆序了，但是单词内部也是逆序的，因此我们还要再遍历逆序后的字符串，以空格为界限，分割出单词，然后只对单词这部分进行反转，使之从逆序变成正序。  class Solution { public: string ReverseSentence(string str) { int n = str.length(); rev...

题目的主要信息：  对于n阶台阶，青蛙每次可以选择跳1到n中任意一个数的阶梯数 n为正整数，求青蛙跳上n级台阶的方案数  方法一：暴力解法 具体做法： 对于n个阶梯，如果青蛙第一次选择跳1阶，那么它有还剩下n-1阶，如果选择跳2阶，那么它还剩下n-2阶以此类推，后面剩下的都是子问题，则数学化公式即为： f(n)=f(n−1)+f(n−2)+...+f(n−(n−1))+f(n−n)f(n)=f(n-1)+f(n-2)+...+f(n-(n-1))+f(n-n)f(n)=f(n−1)+f(n−2)+...+f(n−(n−1))+f(n−n) 我们可以用一个辅助数组依次保存0-n的跳法数，每个数都...

题目的主要信息：  一只青蛙一次可以跳上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)...

题目的主要信息： 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先：  对于该题的最近的公共祖先定义：对于有根树T的两个结点p、q，最近公共祖先LCA(T,p,q)表示一个结点x，满足x是p和q的祖先且x的深度尽可能大 一个节点也可以是它自己的祖先 二叉搜索树是若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值 所有节点的值都是唯一的，可以通过节点值直接比较 p、q 为不同节点且均存在于给定的二叉搜索树中  方法一：两次遍历 具体做法： 二叉搜索树且没有相同值的节点，因此分别从根节点往下利用二叉搜索树找到p、q，...