题目的主要信息：  给出一个长度为 n 的单链表和一个值 x 返回一个链表的头结点，要求新链表中小于 x 的节点全部在大于等于 x 的节点左侧 两个部分之内的节点之间与原来的链表要保持相对顺序不变 进阶要求：时间复杂度 O(n)O(n)O(n) ， 空间复杂度 O(1)O(1)O(1)  方法一：两次遍历复制法 具体做法： 可以用一个新链表来复制原来的链表，复制之前先添加一个无用表头，后续返回的时候去掉即可。 第一次遍历原始链表，将小于x的节点按照顺序连接在新链表后面（这里是每个节点值创建一个新节点连接，而非连接原始的节点），然后第二次遍历原始链表按照一个次的方式将大于等于x的节点按照顺序连接...

题目的主要信息：  将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转 进阶要求：时间复杂度 O(n)O(n)O(n)，空间复杂度 O(1)O(1)O(1)  方法一：递归 具体做法： 如果m == 1,就相当于反转链表的前 n 元素； 如果 m != 1我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转，如果把 head.next 的索引视为1，那相对于 head.next，反转的区间应该是从第 m - 1 个元素开始的，以此类推，递归拼接后续已反转的链表； 对于每次反转，如果n等于1，相当于只颠倒第一个节点，如果不是，则进入后续节点（子问题），将后续反转...

题目的主要信息：  有一个只包含数字的字符串，将该字符串转化成IP地址的形式 需要返回所有情况，顺序没有问题  方法一：暴力枚举 具体做法： 对于IP字符串，如果只有数字，则相当于需要我们将IP地址的三个点插入字符串中，而第一个点的位置只能在第一个字符、第二个字符、第三个字符之后，而第二个点只能在第一个点后1-3个位置之内，第三个点只能在第二个点后1-3个位置之内，且要要求第三个点后的数字数量不能超过3，因为IP地址每位最多3位数字。 暴力枚举这三个点的位置，使用substr截取出四段数字，比较数字不能大于255，且除了0以外不能有前导0，然后才能组装成IP地址加入答案中。 class Sol...

题目的主要信息：  输入一个整数，求其平方根 向下取整 要求：空间复杂度 O(1)O(1)O(1)，时间复杂度 O(log2x)O(log_2x)O(log2​x)  方法一：相加和 具体做法： 数学定理：从1开始的连续n个奇数相加的结果一定是n的平方数。 比如：1+3=4，1+3+5=9，1+3+5+7=16等等。 我们可以用x减去从1开始连续的奇数，直到x小于等于为止，等于0说明刚好可以有整数平方根，小于0说明没有整数平方根，这时候我们向下取整需要减去多算的一次。 class Solution { public: int sqrt(int x) { int res = 0; for(int...

题目的主要信息：  给定一个无重复元素的整数数组nums 找出其中没有出现的最小的正整数 要求： 空间复杂度：O(1)O(1)O(1)，时间复杂度：O(n)O(n)O(n)  方法一：哈希表 具体做法： 可以遍历数组用一个哈希表记录数组中哪些数字出现过，然后从1开始找，找到第一个不在哈希表中出现的数字即可。 class Solution { public: int minNumberDisappeared(vector<int>& nums) { int n = nums.size(); unordered_map<int, int> mp; for(int i...

题目的主要信息：  输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组的和 不存在空数组，−100<=a[i]<=100-100<=a[i]<=100−100<=a[i]<=100 基本要求：时间复杂度：O(n)O(n)O(n)，空间复杂度：O(n)O(n)O(n) 进阶要求：时间复杂度：O(n)O(n)O(n)，空间复杂度：O(1)O(1)O(1)  方法一：动态规划 具体做法： 可以用dp数组表示以下标i为终点的最大连续子数组和，则每次遇到一个新的数组元素，连续的子数组要么加上变得更大，要么它本...

题目的主要信息：  给定一棵二叉树以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点 二叉树非空，且每个节点值均不同  方法一：路径比较法 具体做法： 利用dfs求得根节点到两个目标节点的路径，然后遍历两条路径依次比较，找到两条路径第一个不相同的节点即是最近公共祖先。  class Solution { public: bool flag = false; //记录是否找到到o的路径 void dfs(TreeNode* root, vector<int>& path, int o){ //求得根节点到目标节点的路径 if(fl...

题目的主要信息：  输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组 如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个 不存在空数组 返回的数组不计入空间复杂度计算 基本要求：时间复杂度：O(n)O(n)O(n)，空间复杂度：O(n)O(n)O(n) 进阶要求：时间复杂度：O(n)O(n)O(n)，空间复杂度：O(1)O(1)O(1)  方法一：动态规划 具体做法： 可以用dp数组表示以下标i为终点的最大连续子数组和，则每次遇到一个新的数组元素，连续的子数组要么加上变得更大，要么它本身就更大，...

题目的主要信息：  给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点，如下图所示：   方法一：两次dfs 具体做法： 可以使用两次dfs解决，第一次dfs遍历二叉树每个结点，每个结点都作为一次根结点，第二次dfs遍历以每个结点为根的子树，查找该子树是否有路径和等于目标值的。 class Solution { public: int res = 0; void dfs(TreeNode* root, int sum){ //dfs查询以某结点为根的路径数 if(roo...

题目的主要信息：  把一根长度为nnn的绳子分成mmm段，每段长度都是整数 求每段长度乘积的最大值 由于答案过大，请对 998244353 取模 进阶要求：空间复杂度：O(1)O(1)O(1)， 时间复杂度：O(log2n)O(log_2n)O(log2​n)  数学推算 根据均值不等式，有：n1+n2+...+nmm≥n1n2...nmm\frac{n_1+n_2+...+n_m}{m}\geq \sqrt[m]{n_1n_2...n_m}mn1​+n2​+...+nm​​≥mn1​n2​...nm​​，等号当且仅当n1=n2=n3=...nmn_1=n_2=n_3=...n_mn1​=n2...

题目的主要信息：  给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径 路径定义为从树的根结点开始往下一直到叶子结点所经过的结点 路径只能从父节点到子节点，不能从子节点到父节点 要求：空间复杂度 O(n)O(n)O(n)，时间复杂度 O(n)O(n)O(n)  方法一：递归 具体做法： 可以使用递归先序遍历，每次检查遍历到的结点是否为叶子结点，且当前sum值等于结点值，如果可以则返回true；如果不行，则检查左右子节点是否可以有完成路径的，如果任意一条路径可以都返回true，因此这里选用两个子节点递归的或。 class Solution { ...

题目的主要信息：  给定一个二叉树，返回该二叉树的之字形层序遍 第一层从左向右，下一层从右向左，一直这样交替 进阶要求：空间复杂度：O(n)O(n)O(n)，时间复杂度：O(n)O(n)O(n)  方法一：非递归层次遍历 具体做法： 按照层次遍历按层打印二叉树的方式，每层分开打印，然后对于每一层利用flag标记，第一层为false，之后每到一层取反一次，如果该层的flag为true，则记录的数组整个反转即可。 但是难点在于如何每层分开存储，从哪里知晓分开的时机？在层次遍历的时候，我们通常会借助队列（queue）,事实上，队列中的值大有玄机，让我们一起来看看：  当根节点进入队列时，队列长度为1...

题目的主要信息：  实现一个函数用来找出字符流中第一个只出现一次的字符 Insert函数插入字符流的下一个字符， FirstAppearingOnce找到第一个不重复出现的字符 如果找不到返回# 字符串中出现的字符一定在 ASCII 码内 进阶要求：时间复杂度：O(n)O(n)O(n)，空间复杂度：O(n)O(n)O(n)  方法一：哈希表+字符串 具体做法： 可以准备一个字符串string来记录输入的字符流，用哈希表unordered_map统计每个字符的次数，二者都是全局变量。 在Insert函数中对输入的字符，加到字符串最后，然后统计出现次数。 在FirstAppearingOnce函数...

题目的主要信息：  找出所有和为S的连续正数序列，序列至少包括两个数 序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序 进阶要求：时间复杂度 O(n)O(n)O(n)  方法一：暴力枚举 具体做法： 我们可以从数字1开始枚举从每个数开始的连续的数字，将其累加判断其是否等于目标，如果小于目标数则继续往后累加，如果大于目标数说明会超过，跳出，继续枚举下一个数字开始的情况，只有刚好累加和等于目标数才可以记录从开始到结束这一串数字，代表是一个符合的序列。 而因为序列至少两个数，每次枚举区间的起始数字最多到目标数的一半向下取整即可。 class Solution { public: vecto...