摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #二叉搜索树的第k个结点# 来自专栏

思路：根据二叉搜索树的性质，其中序遍历是由大到小的，由此仅需要中序遍历找到第k个小的结点即可。中序遍历有两种方式。方法一：递归中序遍历具体做法：另写一函数进行递归中序遍历，设置全局变量count记录遍历了多少个结点，res记录第k个结点。 class Solution { public:...

二叉搜索树递归中序遍历非递归排序

2021-07-15

4 676

题解 | #扑克牌顺子# 来自专栏

思路：题中给出的信息是最多4个零，因此必有一张非零牌，分析顺子两点基本情况：不能有重复的非零牌非零牌之间最大相差为4 若是两张非零牌相差大于4，则需要4张零牌（超出了限制），若是小于等于4，又不重复的情况下，要么零牌补齐，要么本身就是相邻的数字。故有两种解决方案。方法一：哈希表具体做...

哈希模拟数组扑克牌顺子排序顺序

2021-07-14

0 605

题解 | #平衡二叉树# 来自专栏

思路：判断某二叉树是否为平衡二叉树，就需要判断任意一结点两边子树深度相差是否绝对值大于1，同时它的子树也符合平衡二叉树的规则。则可以相当将问题不断分成子问题，使用递归。方法一：递归判断+递归计算深度具体做法：写两个函数，一个递归遍历二叉树所有结点，判断该结点下的子树是否为平衡二叉树，另一个函...

平衡二叉树递归深度二叉树

2021-07-14

0 579

题解 | #两数之和# 来自专栏

思路：题中可以看出：必定存在唯一解，不用考虑特殊情况返回的下标是数组下标加1 最能想到的办法莫过于暴力解决，直接遍历两层循环，相加与target比较，若相同则跳出循环。方法一：暴力比较法 class Solution { public: vector<int> two...

哈希两数之和数组

2021-07-14

8 1328

题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树# 来自专栏

思路：关于搜索二叉树的知识：搜索二叉树左子树上所有值小于根节点，右子树上所有值大于根节点，中序遍历后得到的是一个递增序列。关于完全二叉树的知识：完全二叉树叶节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树，出现叶子节点以后的节点都是叶子。由此，可用二叉树...

二叉搜索树完全二叉树中序遍历层次遍历队列递归栈

2021-07-14

4 958

题解 | #矩阵的最小路径和# 来自专栏

思路：从题目中给出的信息：不会是空矩阵，矩阵值都是非负数只能往右或者往下，不能返回，因此路径长度会累加故常用的方法便是递归或者动态规划。方法一：递归法（超时）具体做法：容易想到的是，在第一步时可以选择向右或者向下，只需要当前的路径值加上(n,m-1)或者(n-1,m)的矩阵路径即可...

最小路径动态规划递归空间记忆搜索

2021-07-14

0 651

题解 | #跳台阶# 来自专栏

思路：题目分析：一只青蛙一次可以跳1阶或2阶，直到跳到第n阶，也可以看成这只青蛙从n阶往下跳，到0阶，按照原路返回的话，两种方法事实上可以的跳法是一样的——即怎么来的，怎么回去！当青蛙在第n阶往下跳，它可以选择跳1阶到n-1，也可以选择跳2阶到n-2，即它后续的跳法变成了f(n-1)+f(n-...

斐波那契数列动态规划递归跳台阶

2021-07-13

0 658

题解 | #汉诺塔问题# 来自专栏

思路：从题中给出的有效信息：汉诺塔，不需要记录次数，但是需要移动的塔的名字对于汉诺塔，无论在哪座塔上，小盘必须要在大盘上面，因此可以逆向思维从结果考虑，left塔最下面的大盘，必定是left塔仅剩它，而right塔上面又什么东西都没有时才可以移动，则其余n-1个盘都在mid塔上，且顺序为从小...

汉诺塔递归动态规划栈非递归

2021-07-13

2 759

题解 | #两个链表的第一个公共结点# 来自专栏

思路：题目中的信息：两个链表含有公共结点或没有，有公共结点则返回第一公共结点指针单链表，无循环采用双指针，可以遍历解决，但并非遍历一次方法一：双指针长度比较法具体做法：我们可以通过单独的遍历比较两个链表的长度，得到长度差n，其中较长的链表先动n次指针，然后两链表同步向后，相等之处便...

链表双指针公共结点

2021-07-13

1 543

题解 | #斐波那契数列# 来自专栏

思路：斐波那契数列公式为:F(n)=F(n-1)+F(n-2) 可以直接从i=0与i=1开始，直接相加得到i=2的值，然后将i=1与i=2相加，依次类推，直到i=n,一个循环可以解决也可以用递归方法解决，将上述公式看作函数，不断调用相加即可，递归更简洁方法一：直接相加法具体做法：设置一...

斐波那契数列递归动态数组

2021-07-13

0 708