蒙牛麦片

题解

/ 注册

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

题解 | #最长无重复子数组#

NC41 最长无重复子数组题意分析：找出最长的子数组的长度，要求该子数组中没有重复元素。题解一（暴力）：找出所有的没有重复元素的子数组，然后比较他们的长度。超时。题解二（双指针）：我们设置两个指针left和right，表示子数组的左端点和右端点，用一个set统计left-right中所...

2021-07-22

9 1975

题解 | #两个链表生成相加链表#

NC40 两个链表生成相加链表题意分析：将两个由链表所表示的数相加，求得结果。题解一（反转链表后模拟相加）：链表[9,3,7]和链表[6,3]相加。得到[1,0,0,0]。按照常规加法运算，低位与低位相加。由于我们无法确定哪个位置是低位，因此需要把链表反转后，模拟常规加法运算即可，最后反转加...

2021-07-22

0 651

题解 | #最小编辑代价#

最小编辑代价题意分析：题解一（动态规划）：最优子结构：设输入序列为和，长度分别为m和n。假设为两个序列和在位置和位置的最短编辑数。如果两个序列的最后一个字符相等（或)，则如果两个序列的最后一个字符不相等()，则有三种选择：取三种选择最小操作数如有序列“AGAB” 和“GXAYB”。它们...

2021-07-22

4 958

题解 | #数组中未出现的最小正整数#

数组中未出现的最小正整数题目：给定一个无序整型数组arr，找到数组中未出现的最小正整数。要求时间复杂度为O(N)空间复杂度为O(1)。例如： arr=[-1,2,3,4]。返回1。 arr=[1,2,3,4]。返回5。找到自然数从1-n中，第一个没有出现在给定数组中的题解一（空间复杂度O...

2021-07-21

1 2343

题解 | #在旋转过的有序数组中寻找目标值#

NC48 在旋转过的有序数组中寻找目标值题意分析：在数组中查找target 题解一（直接遍历）：直接遍历判断有没有target，有返回下标，没有返回-1；代码实现如下 int search(vector<int> &nums, int target) { for ...

2021-07-16

20 1803

题解 | #加起来和为目标值的组合#

NC46 加起来和为目标值的组合题意分析：在给定的数组中找到一些子集，这些子集的和等于target 题解一（回溯）：枚举出所有子集，判断这些子集里面的元素和是不是等于target，等于就加入到最后结果中。代码实现如下： void backtrace(vector<int>&...

2021-07-16

0 999

题解 | #实现二叉树先序，中序和后序遍历#

NC45 实现二叉树先序，中序和后序遍历题意分析：实现二叉树的先序，中序，后续遍历题解一（递归遍历）：比如有二叉树先序遍历：按照访问树根，左子树，右子树的顺序对树进行遍历，子树同样遵守这个遍历顺序如图所示的二叉树：先序遍历结果为4,2,1,3,5. 代码实现如下： void preO...

2021-07-16

0 1020

题解 | #通配符匹配#

NC44 通配符匹配题意分析：给定字符串S，模式串P，判断S是否能够被P所匹配，通配符只有？和*，？可以匹配任意一个字符，*可以匹配任意长度的字符串题解一（动态规划）：设置表示字符串S的(0-i)部分是否被字符串P的(0-j)部分匹配初始化：，字符串s的(0-0)为空，那么只要字符串P...

2021-07-16

0 749

题解 | #有重复项数字的所有排列#

NC42 有重复项数字的所有排列题意分析：生成所给数字的所有排列。这一题与JZ27字符串的排列基本一样将字符换成了数字题解一（暴力回溯）：回想一下高中所学的排列组合知识：有3个红球，2个白球，1个黑球，请问有多少中排列方式。我们的计算方式是：一个有6个位置，先选择3个位置放红球，再从剩下...

2021-07-16

10 1628

题解 | #螺旋矩阵#

NC38 螺旋矩阵题意分析：以顺时针螺旋方式打印出矩阵所有的元素题解一（模拟法）：以螺旋的方式进行遍历矩阵。使用深度优先搜索，初始时，我们向右搜索，到达边界或者下一个元素已经访问过了，就转变搜索方向。搜索方向的顺序为向右，向下，向左，向右。我们定义一个方向向量vector<pair&...

2021-07-16

0 709