思路 题目分析 题目给出我们一棵二叉树 我们要逐层存储结点值到一个数据结构中，并且要按照“之”字的顺序规则存储 也就是说当前一层按照从左到右存储后，下一层要从右到左存储 最终返回这个存储后的结构信息 方法一：递归 递归函数意义为前序遍历，并随之记录深度信息 递归函数退出条件是 如果结点为空直接退出 递归函数主体工作任务是 首先根据深度信息查看是否要更新res的空间大小 根据深度信息作为索引，选择是顺序插入res中还是倒序插入到res中 递归左右子树 最终返回res即可 方法二：迭代 利用一个队列来存储每一层的结点信息 同样要记录结点深度，判断是否要顺序还是倒序存储...

思路 题目分析 题目给出了一个链表，链表中元素有序排序 我们要将链表中相邻重复的元素都删去，返回剩下部分的链表头结点 迭代 为了代码简便，我们引入哑结点dummyNode，以便处理头结点的问题 我们选用三个指针，分别指向三个相邻的位置 后两个指针进行对结点是否有相同值进行判断，并引入temp指针来删去重复元素 第一个指针的next成员可以接到后两个指针找到的结点值不同的位置 以上部分循环迭代即可 递归 我们明确递归函数的定义为返回以当前结点为首的不含重复元素的链表 因此首先递归终止条件为当前结点是否为空、当前结点下一节点是否为空，进行判断返回 需要进行递归的情况如下 pHe...

思路 题目分析 题目给出了我们一个字符串 我们要在字符串中找到第一次只出现一次的字符，返回其下标位置 方法一：枚举 我们根据ASCII码知道计算机一共定义了128个字符 因此我们只要给出一个空间大于128就可以统计所有字符的个数 然后再按照str的字符顺序遍历，查找到第一个数量为1的字符，返回下标 方法二：哈希 我们可以通过申请一个哈希表来存储<字符，数量>对 统计每个字符出现的数量存储在哈希表内 最终顺序遍历str，找到第一个数量为1的字符并返回下标 方法一：枚举 class Solution { public: int FirstNotRepea...

思路 题目分析 题目给出一棵二叉树 我们需要判断这棵二叉树是否为左右镜像对称的，返回最终的判断结果 方法一：递归 我们构造一个递归函数，包含两个结点指针参数u,v，这两个结点指针参数本身就是在树中左右对称的 首先要判断两个节点指针本身是否互相对称 然后分别沿着左右子节点进行递归 u指针指向左子节点和v指针指向右子节点进行一次递归调用 u指针指向右子节点和v指针指向左子节点进行一次递归调用 返回判断的结果 方法二：迭代 我们借助队列结构 首先根节点入队两次 然后循环中每次提出两个节点判断对称性 之后将两个节点的左右子节点按照相反的顺序插入队列中 对上述循环中每轮提取...

思路 题目分析 题目给出我们一棵树的其中的某一个结点指针 我们需要返回这棵树按照中序遍历的该节点的下一个顺序结点指针 树的每个节点都有三个指针，指向左子节点、右子节点、父节点 方法一：中序遍历 首先先根据当前给出的结点找到根节点 然后根节点调用中序遍历 将中序遍历结果存储下来 最终拿当前结点匹配是否有符合要求的下一个结点 方法二：直接寻找 直接寻找分为三种情况 如果给出的结点有右子节点，则最终要返回的下一个结点即右子树的最左下的结点 如果给出的结点无右子节点，且当前结点是其父节点的左子节点，则返回其父节点 如果给出的结点无右子节点，且当前结点是其父节点的右子节点，则先要沿着...

思路 题目分析 题目给出了两个数字字符串 这两个字符串代表的数字要进行相乘操作，大数相乘可能会突破一些语言的数值表示的限制 因此我们要通过一些数据结构的表示来最终返回其两数字相乘结果，以字符串形式返回最终数字 方法一：python语言中对数字长度无要求 因此我们只需要将其转换成数字并相乘，最终返回字符串格式即可 方法二：乘法拆解为加法 我们可以将两个大数乘法拆解成竖式运算的概念 让一个大数分别乘另一个大数的每一位，并适当错开位数补0后进行加和 方法一：python语言中对数字位数无要求 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值...

思路 题目分析 题目给出数组的大小，同时给出了一个数组 题目规定数组中元素表示花高 题目的数组围成一圈，相邻元素的差值最大值作为这个圈的丑陋值 我们要合理排序这个圈中的元素，使这个圈的丑陋值最小 返回这个圈的最小丑陋值 方法一：暴力（超时） 枚举出来所有的排序方案 逐个计算出每个圈的丑陋值 选出最小的丑陋值 时间代价巨大 方法二：贪心数学性质 我们可以想到这个圈在数组的表现形式应该是先递增，后递减 因此排序很重要 排序后，将奇数位的元素统一移到前面，偶数位的元素统一移到后面 奇偶交替一前一后向中间逼近，使得中间的值是最大的 这样做的原因是我们需要丑陋值最小，而丑陋值是和相邻...

思路 题目要求我们将同一层按照从左到右的顺序进行合并整理成输出，我们将题目解读并翻译为层序遍历问题 通过层序遍历的方式进行顺序访问 维护一个队列结构，队列可以帮助我们实现先进先出，因此只要层序访问入队出队即可 方法一：非递归层序遍历 具体做法 首先处理特殊情况，比如指针为空的情况，直接返回空结果[] 维护一个队列，其中存储的信息是当前层的结点指针，队列一直在第二个while循环内重复的工作就是出队当前队首结点，同时将其左右子节点入队。 在层与层之间，通过第二次while循环之前的当前队列容量大小来控制层之间的间隔。 层序遍历进行每一层的结点添加统计 以下为c++代码展示 /* struc...

思路 最简单的思路就是暴力进行计算，时间上可能会比较久，尤其是在给定的滑动窗口较大的情况下。 刷题比较多的小伙伴可以发现这是一道单调队列的典型题目，什么情况才满足双端队列呢？ 滑动窗口如果只进元素的话，我们其实不用双端队列，只要保存一个最大值就可以了 但是滑动窗口如果是要退元素的话，就麻烦了起来，没有办法通过只保存一个值的方式来满足短时间复杂度的要求 所以考虑单调队列，并利用双端队列的性质维护这个单调队列 方法一：暴力解决 对每个滑动窗口都进行最大值的计算，最终结果返回到输出中 class Solution { public: vector<int> maxInWind...

思路 题目分析 题目给出了我们一个二叉搜索树 我们要返回该树中第k小的结点值 思路分析 我们发现题目给我们的是二叉搜索树，二叉搜索树有一个性质即中序遍历是按顺序的 因此我们可以采用递归和迭代两种方法进行中序遍历 方法一：递归 递归中序遍历： 我们需要将k值更新在两个递归函数中间，这样才是中序遍历的方法 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), le...

思路 题目分析 题目给出了我们一个字符串和字符串长度 我们需要在该字符串中找到一个最长的子字符串，这个字符串必须满足回文的特征。 方法一：暴力中心拓展 我们可以遍历这个字符串 以每一个遍历到的字符作为中心，进行左右指针的拓展 同时也要考虑到偶数长度的最长回文子字符串的情况 这就要求我们必须将作为起点的字符先进行一个判断，是否右侧有相同的字符 我们直接将右侧指针拉到和起点字符相同字符的最右侧，然后再进行双向拓展即可 方法二：动态规划 我们规定dp[l][r] == true表示从下标l到r的子字符串是回文串 因此我们的动态规划数组递推满足以下逻辑 dp[l][l] ==...

思路 题目分析 题目给出的输入有一个N*N大小的数组，并且给出了维数N 我们需要返回这个数组顺时针翻转90度后的数组 方法一：开辟新数组按照索引关系装填 我们申请一个同样空间大小的新的二维数组ans来承接原数组mat的元素 90度翻转的数组和原数组存在索引上的关系符合ans[j][n-i-1] = mat[i][j] 依照这个关系双重循环即可 方法二：原地旋转 原地我们无法直接进行旋转，因此我们要找90度前后的位置关系 原数组经过水平翻转，再将对角线翻转可以得到90度的顺时针旋转 依据这一规律，我们将原数组原地旋转 方法一：按照索引关系 class Solution {...

思路 题目分析 题目给出了一个整数数组 要求我们返回其中子数组的和的最大值 方法一：暴力 我们可以通过双重循环来对所有的子数组进行求和 一重循环遍历起点，另一重循环遍历终点 返回子数组求和的最大的那一个即可 方法二：动态规划 我们规定dp[n]代表包括array[n]在内的子数组的和的最大值 维护动态规划数组的操作即 如果dp[n-1]>0，则dp[n] = dp[n-1] + array[n]，说明当前的元素要和前面累计的正数和加起来才是当前的子数组和最大 否则dp[n] = array[n] 最终返回dp数组中最大的一个即可 方法一：暴力 class S...

思路 题目分析 题目给出了一棵二叉树 我们需要返回层序遍历这棵二叉树的结果，每层组织一个向量，最终这些向量再组织成一个向量 返回最终组织的向量。 方法一：递归 我们可以采用dfs深度优先遍历的方法进行处理 需要注意的点是我们要才有前序优先的方式保证顺序，还要用一个level变量记录当前结点所在的层数，以便我们成功找到哪一个res索引的子向量需要添加新元素 方法二：迭代 利用队列进行层序遍历 需要注意的点是我们要记录每一层压入队列的结点数量 这样可以保证我们层与层之间互不干预 方法一：递归 /** * struct TreeNode { * int val; * s...