摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #兑换零钱(一)# 来自专栏

题目的主要信息：给定数组arr，arr中所有的值都为正整数且不重复 arr中每个值代表一种面值的货币，每种面值的货币可以使用任意组成aim的最少货币数如果无解，请返回-1 方法一：空间记忆递归具体做法：对于需要凑成aimaimaim的钱，第一次我们可以选择使用arr[0]arr[0]a...

C++ 递归动态规划

2021-12-09

1 697

题解 | #岛屿数量# 来自专栏

题目的主要信息：给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，则这两个1属于同一个岛只考虑上下左右为相邻判断岛屿的个数方法一：dfs 具体做法：可以从上到下从左到右依次遍历矩阵，每次遇到一个1则岛屿数记为1，然后将与这个1及与其相邻的所有1全部置为0，相当于这个岛屿已经被统...

C++ bfs dfs

2021-12-09

0 557

题解 | #最大正方形# 来自专栏

题目的主要信息：给定一个由'0'和'1'组成的2维矩阵，返回该矩阵中最大的由'1'组成的正方形的面积输入的矩阵是字符形式而非数字形式方法一：动态规划具体做法：对于这类区间内找最大某某值的问题，一般采用动态规划。可以用dp[i][j]dp[i][j]dp[i][j]表示以[i,j][i...

C++ 动态规划

2021-12-09

1 465

题解 | #三个数的最大乘积# 来自专栏

题目的主要信息：给定一个长度为 n 的无序数组 A ，包含正数、负数和 0 找出 3 个数，使得乘积最大，返回这个乘积方法一：排序法具体做法：如果数组全是正数，则数组最大的三个数相乘乘积最大；如果数组全是负数，则数组最大的三个数相乘乘积最大；如果数组只有1个正数，其余都是负数，则数...

C++ 数组排序

2021-12-08

2 972

题解 | #比较版本号# 来自专栏

题目的主要信息：给出2个版本号version1和version2，比较它们的大小版本号是由修订号组成，修订号与修订号之间由一个"."连接修订号可能有前导0，按从左到右的顺序依次比较它们的修订号，比较修订号时，只需比较忽略任何前导零后的整数值如果版本号没有指定某个下标处的修订号，则该修订号视...

C++ 字符串

2021-12-08

0 414

题解 | #二分查找-II# 来自专栏

题目的主要信息：给定一个元素非降序的、有重复数字的整型数组 nums 和一个目标值 target 找到第一个目标值的下标如果找不到返回-1 进阶要求：时间复杂度O(log2n)O(log_2n)O(log2n) ，空间复杂度O(1)O(1)O(1) 方法一：遍历查找具体做法：遍历数组，...

C++ 二分法

2021-12-07

0 378

题解 | #旋转数组的最小数字# 来自专栏

题目的主要信息：有一个长度为 n 的非降序数组，把一个数组最开始的若干个元素“平移”到数组的末尾，变成一个旋转数组找到这个旋转数组的最小值进阶要求：时间复杂度O(log2n)O(log_2n)O(log2n)，空间复杂度O(1)O(1)O(1) 方法一：遍历查找具体做法：直接遍历数组...

C++ 二分

2021-12-07

0 375

题解 | #找到搜索二叉树中两个错误的节点# 来自专栏

题目的主要信息：一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值该二叉树每个节点值不同方法一：中序非递归具体做法：使用栈辅助进行二叉树的中序遍历：栈记录当前节点，不断往左深入，直到左边子树为空，再弹出栈顶（即为当前...

C++ 递归栈

2021-12-07

3 1128

题解 | #反转数字# 来自专栏

题目的主要信息：给定一个32位的有符号整数num，将num中的数字部分反转只反转数字部分，符号位部分不反转最后的结果需要在32位有符号数范围之内，超出范围返回0 方法一：取模反转具体做法：数对10取余可以得到数字最后一位，将最后一位加在答案数字最前面，然后数除10即可去掉最后一位数字，...

C++ 模拟

2021-12-07

0 359

题解 | #最长的括号子串# 来自专栏

题目的主要信息：一个长度为nnn的仅包含左右括号的字符串计算最长的格式正确的括号子串的长度方法一：栈具体做法：可以使用栈来记录左括号下标，每次遇到右括号则弹出左括号的下标，然后长度则更新为当前下标与栈顶下标的距离。因为遇到不符合的括号，可能会会使栈为空，因此需要使用start记录上一次...

C++ 栈动态规划字符串

2021-12-07

0 336