数据结构和算法

题解

读书笔记(1)

/ 注册

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

【数据结构和算法】递归和非递归解路径总和问题来自专栏

递归求解这题让判断从根节点到叶子节点的所有路径中，有没有和等于sum的，如果看过之前讲的《442，剑指 Offer-回溯算法解二叉树中和为某一值的路径》，再来看这一题就觉得这题有点简单了。第442题要求的是把所有的和等于sum的路径都打印出来，而这题只要判断有一个路径的和等于sum即可。我们可...

java DFS 二叉树 BFS 递归

2021-08-03

22 1252

【数据结构和算法】递归解决来自专栏

这道题要求的最大路径和如果是从根节点开始到叶子节点就好办了，我们可以通过递归的方式，从下往上，舍去比较小的路径节点，保留比较大的节点。但这道题要求的最大路径和并不一定经过根节点，如果再使用上面的方式就行不通了，对于这道题我们可以分为4种情况来讨论 1，只要当前节点，舍弃子节点。比如下面结点2的左右...

java 二叉树递归

2021-08-03

7 636

【数据结构和算法】4种方式解决来自专栏

1，递归方式解决这题没说sum是正数还是负数，也没说树中节点的值有没有负数。我们要做的是从根节点到叶子节点遍历他所有的路径，返回他所有路径中和等于sum的节点，这里有两种实现方式，一种是减，一种是加。减就是从根节点开始，用sum不断的减去遍历到的每一个节点，一直到叶子节点，在减去叶子节点之前查看s...

java 二叉树 DFS

2021-07-19

15 1144

【数据结构和算法】DFS和BFS两种方式解决来自专栏

1，DFS解决这题说的是每条从根节点到叶子结点的路径都代表一个数字，然后再把这些数字加起来即可。遍历一棵树从根节点到叶子结点的所有路径，最容易想到的是DFS，所以这题使用DFS是最容易解决的。如果对二叉树的DFS不熟悉的话，可以看下373，数据结构-6,树解决方式就是从根节点往下走的时候，那么...

java 二叉树 DFS BFS

2021-07-19

25 3009

【数据结构和算法】NC102 在二叉树中找到两个节点的最近公共祖先来自专栏

非递归写法要想找到两个节点的最近公共祖先节点，我们可以从两个节点往上找，每个节点都往上走，一直走到根节点，那么根节点到这两个节点的连线肯定有相交的地方，如果是从上往下走，那么最后一次相交的节点就是他们的最近公共祖先节点。我们就以找6和7的最近公共节点来画个图看一下我们看到6和7公共祖先有5和...

java 二叉树

2021-07-06

147 6959

【数据结构和算法】NC95，数组中的最长连续子序列来自专栏

先排序因为数组是无序的，如果要想找出最长的连续序列（这里序列的顺序可以打乱），我们最容易想到的就是先对数组进行排序，然后再查找。使用一个变量count来记录当前有序序列的长度。如果当前元素比前一个大1，说明他们可以构成连续的序列，count就加1。如果相等就跳过。否则就不能构成连续的...

java 数组子序列

2021-07-06

35 1906

【数据结构和算法】动态规划解最长公共子串来自专栏

动态规划解决注意这题求的是最长公共子串，不是最长公共子序列，子序列可以是不连续的，但子串一定是连续的。定义dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最长公共子串。如果要求dp[i][j]，也就是str1的第i个字符和str2的第j个字符为最后一个元...

java 字符串动态规划

2021-07-05

107 8592

【数据结构和算法】替换空格的两种解决方式来自专栏

先把字符串转换为单个字符这里让求的是把字符串中的空格替换成%20，其中一种实现方式就是申请一个临时数组，然后再遍历这个字符串的每个字符，如果不是空格就把遍历的字符添加到临时数组中，如果是空格就添加3个字符'%'，'2'，'0'分别到临时数组中，最后再把临时数组转化为字符串即可。 publi...

java 字符串

2021-07-03

55 5928

【数据结构和算法】回溯算法解矩阵中的路径来自专栏

回溯算法解决回溯算法实际上一个类似枚举的搜索尝试过程，也就是一个个去试，我们解这道题也是通过一个个去试，下面就用示例1来画个图看一下我们看到他是从矩形中的一个点开始往他的上下左右四个方向查找，这个点可以是矩形中的任何一个点，所以代码的大致轮廓我们应该能写出来，就是遍历矩形所有的点，然后从这个...

java 回溯算法

2021-07-03

82 5351

【数据结构和算法】剪绳子的两种解决方式来自专栏

数学方式解决在做这题之前我们先来看这样一个问题，一个整数先把他分成两部分，x+y=n（假设x>=y并且x-y<=1,也就是说x和y非常接近）那么乘积是x*y。然后我们再把这两部分的差放大(x+1)+(y-1)=n(假设x>=y)；他们的乘积是（x+1）*(y-1)=x*y-(x-...

整数 java

2021-07-03

95 3135