摸鱼学大师

分类

未归档(8) 题解(541)

/ 注册

TA的专栏 547篇文章 2人订阅

孤帆远影碧空尽

547篇文章 10912人学习

全部文章（共550篇）

题解 | #拼接所有的字符串产生字典序最小的字符串# 来自专栏

思路：题目要求将所有的小字符串拼接成大字符串，使大字符串字典序最小，需要主要的有两点：字符串越小的应该要在越靠前字符串内部顺序不能动,只能添加连接因此不是将所有较小的字符串排在前面相加，应该是s1+s2 < s2+s1比较，直接连接。比如：方法一：冒泡排序法（超时）数据量过...

字符串最小字符串拼接排序重载快排冒泡法

2021-07-16

1 737

题解 | #完全二叉树结点数# 来自专栏

思路：最简单的办法莫过于遍历所有的结点，统计个数，但是不管是哪种遍历，时间复杂度都要求至少为O(n)，因为要遍历每一个结点。方法一：遍历法不符合复杂度要求！！！方法二：二分法（利用性质）由此，我们可以从完全二叉树的性质下手：完全二叉树叶子结点只能出现在最下两层最下层的叶子一定集中在左...

二叉树完全二叉树满二叉树递归最大深度

2021-07-16

4 718

题解 | #子数组最大乘积# 来自专栏

思路：由题目中给到的信息：数组是double型，可正可负可零，也即是说乘积可能突然变小（正x负）也可能突然变大（负x负）返回的子数组必须是连续的一段这是一道典型的动态规划的题，解题最重要的便是找到状态方程。方法一：动态规划如果设置max[i]表示当前i及之前的乘积最大值，min[i]...

动态规划数组子数组乘积

2021-07-16

2 684

题解 | #把二叉树打印成多行# 来自专栏

思路：题目要求将二叉树按行打印，即按层打印，其中每层分开。不难想到，要使用层次遍历，但是难点在于如何每层分开存储，从哪里知晓分开的时机？在层次遍历的时候，我们通常会借助队列（queue）,事实上，队列中的值大有玄机，让我们一起来看看：当根节点进入队列时，队列长度为1，第一层结点数也为1 若是根...

二叉树层次遍历队列递归非递归

2021-07-15

0 565

题解 | #丑数# 来自专栏

思路：由题目中给到的信息：丑数仅由2、3、5的因子组成 1是第一个丑数现在要寻找第n个丑数，最简单值观的方法莫过于从1开始依次往后递增加1，判断每个数是否将2除尽、3除尽、5除仅为1且不含余数，若是则丑数加1，继续往后找。此方法问题在于随着数字不断增大，要除尽2、3 、5需要多次循环，且中...

丑数数组贪心算法因子

2021-07-15

0 701

题解 | #矩阵中的路径# 来自专栏

思路题中给到的信息：上下左右随便移动，找到字符串路径访问可以重复，但是作为路径不能有重复方法一：递归深度优先搜索我们需要判断这个矩阵中的每一个结点是否可以走一条路径，即找到每个结点为起点，后续结点是否可以走出字符串字串的路径，该子问题又可以作为一个递归。因此，可以用图的递归dfs来解决...

dfs 深度优先路径矩阵字符串栈非递归

2021-07-15

0 663

题解 | #滑动窗口的最大值# 来自专栏

思路根据题意：要寻找每个滑动窗口的最大值，每次只滑一位 size等于0或者大于数组长度，都返回空值方法一：暴力法暴力解法应该是最容易想到的，只需要遍历数组的同时往后遍历每个窗口，找出最大值即可。 class Solution { public: vector<int> m...

滑动窗口双向队列数组

2021-07-15

0 615

题解 | #数据流中的中位数# 来自专栏

思路：题目中给出的信息：寻找中位数数据在不断增长传统的寻找中位数的方法便是排序之后，取中间值或者中间两位的平均即可，但是因为数组在不断增长，每增长一位便排一次，很浪费时间，于是可以考虑在增加数据的同时将其有序化。方法一：插入排序法具体做法：用一vector存储输入的数据流。Ins...

堆中位数数组排序堆排序插入排序

2021-07-15

0 735

题解 | #序列化二叉树# 来自专栏

思路：序列化二叉树即找一种顺序存储二叉树的结点，并以相同的方式能够读取序列重新构建。换种说法，就是遍历二叉树，记录每个结点，再以同样的方式遍历就可以还原二叉树。遍历的方法有四种：先序遍历、中序遍历、后序遍历、层次遍历，理论上只要以相同的方式序列化或者反序列化，都可以解题。方法一：先序遍历 ...

二叉树先序遍历序列化反序列化 char数组

2021-07-15

0 519

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

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

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

2021-07-15

4 662