棒棒糖🍭201906101800876

题解

/ 注册

全部文章 / 题解（共46篇）

题解 | #二叉树的中序遍历#

NC161 二叉树的中序遍历题意给定一个二叉树的根节点root，返回它的中序遍历。 1. 递归法所谓中序遍历，就是先中序遍历左子树，在访问遍历树根，然后中序遍历右子树。把上面的汉字翻译成代码，用一个全局变量维护遍历路径即可。 /** * struct TreeNode { * in...

2021-07-29

1 846

题解 | #二分查找-I#

NC160 二分查找-I 题意给你一个不重复、递增的数组nums，和目标值target，求target在nums中的下标，从0开始，如果不存在输出-1. 1. 暴力解法直接遍历数组查找。 class Solution { public: /** * 代码中的类名、方法名、参数名...

2021-07-29

0 570

题解 | #最小生成树#

NC159 最小生成树先复习下最小生成树的概念：生成树是一个图的一颗含有其所有顶点的连通子图，也就是一个树。最小生成树是所有生成树中，边的总权值最小的那个。最小生成树有两种算法，分别是克鲁斯卡尔和prim算法，分别介绍之。题意给你一个无向图，n点m边，求最小生成树 1. 克鲁斯卡尔算法克鲁...

2021-07-29

1 736

题解 | #单源最短路#

NC158 单源最短路单源最短路是图论算法里非常重要的基础算法，似乎没有之一。。。。。。常用的算法有dijkstra算法和SPFA算法，下面分别介绍。题意给你一个有向图，n点m边，有重边无自环，权值为正，求 1 到 n 的最短路，如果不存在，输出-1. 1. 迪杰斯特拉这个似乎是数据结构课...

2021-07-28

1 532

题解 | #最长回文子序列#

NC154 最长回文子序列题意给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。字符串长度 1. 暴力做法(不合要求， tle) 递归计算区间[i, j]的最长回文子序列，设最长回文子序列为f(i, j), 分为三种情况：如果s[i] == s[j], 那么最长子序列可能是2+f...

2021-07-28

1 665

题解 | #信封嵌套问题#

NC153 信封嵌套问题题意给个信封的长度和宽度。如果信封的长和宽都小于信封，那么信封可以放到信封里，请求出信封最多可以嵌套多少层。本题是魔改的最长递增子序列(LIS)问题，所以最长递增子序列的解法都适用于本题。但是这题是二维的，如何降维？我们可以这样思考，不管怎么套娃...

2021-07-28

0 850

题解 | #数的划分#

NC152 数的划分题意将整数分成份，且每份不能为空，任意两个方案不能相同(不考虑顺序)，求方案数，对1e9+7取模。 1. 暴力法（效率很低，数字大了会tle）我们分析下样例的规律： n=7, k=3[1,1,5][1,2,4][1,3,3][2,2,3] 直接使用回溯法，暴力枚...

2021-07-28

15 858

题解 | #二叉树的镜像#

NC72 二叉树的镜像题意操作给定的二叉树，将其变换为源二叉树的镜像。 1. 魔改交换变量（前序遍历1）我们在大一的C语言课上学过，交换两个变量a和b的代码是： int c = a; a = b; b = c;这道题跟交换两个变量差不多，稍微魔改一下上面的交换过程，把左孩子赋值为右子树的镜像，...

2021-07-26

0 403

题解 | #数组中出现次数超过一半的数字#

NC73 数组中出现次数超过一半的数字题意给你一个数组，找出出现次数超过一半的数字。（也叫主元素问题） 1. 暴力法枚举每一个数，看他是不是在数组中出现了超过一半的次数。时间复杂度: , 两重循环空间复杂度: . 2. 排序法既然是众数且超过了一半，那么肯定也是中位数，排序后取中点即...

2021-07-26

0 495

题解 | #旋转数组的最小数字#

NC71 旋转数组的最小数字题意把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 1. 暴力做法（不合要求）思路略。 class Solution { pu...

2021-07-26

0 460