Maokt

题解

/ 注册

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

题解 | #二叉搜索树的第k个结点#

算法思想一：递归解题思路：主要通过对二叉树进行中序遍历朝招第K个节点 1、创建中序遍历存储数组 res 2、按照中序遍历：左子树-根节点-右子树，并将遍历的节点信息存储到res中 3、遍历结束，直接返回 res[k-1] 图解：代码展示： ...

二叉搜索树的第k个结点

2021-07-27

2 558

题解 | #丑数#

算法思想一：优先队列解题思路：采用一个简单的解法是使用优先队列：1、起始先将最小丑数 1 放入队列2、每次从队列取出最小值 x，然后将 x 所对应的丑数 2x、3x 和 5x 进行入队。3、对步骤 2 循环多次，第 n 次出队的值即是答案。注：为了防止同一丑数多次进队，需要使用数据结构 Set（...

丑数

2021-07-27

1 599

题解 | #矩形覆盖#

算法思想一：迭代解题思路：图示：分析从n=3到n=4，有2种情况： 1、直接在n=3的情况下，再后面中添加一个竖着的。这个很显然成立，有3种情况 2、然后横着的显然能添加到n-2的情况上，也就是在n=2后面，添加2个横着的。有2种情况总结以上规律发现 fn 表示覆...

矩形覆盖

2021-07-25

1 481

题解 | #跳台阶扩展问题#

算法思想一：动态规划解题思路：设置dp数组，其中dp[i] 表示当前跳道第 i 个台阶的方法数 1、最后跳 1 步到达第 n 个台阶，说明上一步在第 n-1 个台阶。已知跳到第n-1个台阶的方法数为dp[n-1] 2、最后跳 2 步到达第 n 个台阶，说明上一步在第 n-2 个台阶。...

跳台阶扩展问题

2021-07-25

1 608

题解 | #二分查找-II#

算法思想一：顺序遍历解题思路：对数组nums进行顺序遍历，因为数组是有序的，所以当遍历的元素与目标target相同时，即为第一个出现的target，返回该元素的索引即可代码展示： Python版本 class Solution: def search(self...

二分查找-II

2021-07-25

1 468

题解 | #旋转数组#

算法思想一：使用额外数组解题思路：可以使用额外的数组来将每个元素放至正确的位置。遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+m) mod n （为了防止右移的长度大于数组的长度，所以才有取余）的位置，最后返回新数组即可图解：代码展示： ...

旋转数组

2021-07-24

18 2291

题解 | #最大正方形#

算法思想一：暴力法解题思路：由于正方形的面积等于边长的平方，因此要找到最大正方形的面积，首先需要找到最大正方形的边长，然后计算最大边长的平方即可。暴力法是最简单直观的做法，具体做法如下： 1、遍历矩阵中的每个元素，每次遇到 1，则将该元素作为正方形的左上角； 2、确定正方形的左上角...

最大正方形

2021-07-24

4 807

题解 | #岛屿数量#

算法思想一：深度优先搜索解题思路：可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。为了求出岛屿的数量，可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索（四周）。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。最终岛屿...

岛屿数量

2021-07-24

3 998

题解 | #寻找峰值#

算法思想一：遍历+峰值对比解题思路： 1、找到索引最大的那个山峰元素并返回其索引，考虑从后往前遍历 2、假设，需要对端点做处理即：在对于数组的最后一个值，只需要考虑是否大于等于前面一个值，代码如(&&)，对于数组的第一个值，只需要考虑是否大于后面一个值，代码如(&a...

寻找峰值

2021-07-23

3 812

题解 | #三个数的最大乘积#

算法思想一：排序解题思路：首先将数组排序1、如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数相乘同样也为最大乘积。2、如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。3、综上，在给数组排...

三个数的最大乘积

2021-07-23

7 728