数据结构和算法

题解

读书笔记(1)

/ 注册

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

【数据结构和算法】最小花费爬楼梯来自专栏

解法一如果到第i个台阶，我们可以从第i-1个台阶跳一步上来，也可以从第i-2个台阶跳两步上来。哪个花费少我们就选择从哪个跳上来。我们定义dp[i]表示到第i个台阶需要的最小花费，那么我们可以得出递推公式 dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i ...

Java 动态规划跳台阶

2022-02-18

16 1360

【数据结构和算法】跳台阶扩展问题来自专栏

解法一这里的青蛙比前面两道题的青蛙更厉害一些，他一次可以跳1阶，2阶，3阶……。所以要想跳到第n个台阶，我们可以从第1个台阶跳上来，也可以从第2个台阶跳上来……，所以递推公式是 f(n)=f(n-1)+f(n-2)+……+f(2)+f(1); 同样如果我们想跳到第n-1个台阶，也可以列出下面这个...

Java 斐波那契数列青蛙跳台阶位运算

2022-02-18

20 1650

【数据结构和算法】青蛙跳台阶来自专栏

这题和前面 DP1 斐波那契数列基本上是一样的，不同的是，这里斐波那契数列的起始项是1,2,3,5,8，我们把它改一下即可解法一题中要求的是空间复杂度 O(1) ，很明显使用递归是行不通的，我们先改成非递归的看一下（这种复杂度也是不行的，我们先看一下代码） import java.util.S...

Java 动态规划斐波那契青蛙跳台阶

2022-02-18

8 1294

【数据结构和算法】斐波那契数列来自专栏

解法一题中要求的是空间复杂度 O(1) ，很明显使用递归是行不通的，我们先改成非递归的看一下（这种复杂度也是不行的，我们先看一下代码） import java.util.Scanner; public class Main { public static void main(Stri...

Java 动态规划斐波那契

2022-02-18

11 1872

【数据结构和算法】四指针解决来自专栏

四指针解决在算法中双指针我们经常听过，但四指针还是比较少的，四指针顾名思义就是使用4个指针来解决。这题是让把节点值小于x的节点都放到前面，最简单的一种解决方式就是把原链表的节点分隔为两个链表，其中一个链表节点的值都是小于x的，另一个链表节点的值都是大于或等于x的，最后再把这两个链表合并即可。这里...

java 链表

2021-08-03

2 1001

【数据结构和算法】顺时针旋转矩阵来自专栏

先上下交换，在对角线交换这题是让把矩阵顺时针旋转90度，最简单的一种方式就是先上下关于中心线翻转，然后再对角线翻转，具体看下图形分析原理比较简单，来直接看下代码 public int[][] rotateMatrix(int[][] matrix, int n) { ...

java 数组

2021-08-03

8 1341

【数据结构和算法】递归和非递归两种方式解决来自专栏

递归解决判断二叉树是否是对称，需要从子节点开始比较，两个子节点的值必须相同，并且左子节点的右子节点（如果有）必须等于右子节点的左子节点，左子节点的左子节点必须等于右子节点的右子节点。就像下面图中那样 public boolean isSymmetric (TreeNode root) { ...

java 二叉树递归

2021-08-03

3 754

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

BFS打印二叉树的的层次遍历就是一层一层的遍历，也就是我们俗称的BFS（宽度优先搜索算法（又称广度优先搜索））,之前在373，数据结构-6,树中讲过树的宽度优先搜索，最简单的方式就是使用队列。但这题打印的时候多了一个条件，就是不能一直从一个方向打印，要先从左边打印然后再从右边打印……，就这样交替...

java DFS BFS 二叉树

2021-08-03

6 1082

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

问题分析做这题之前我们先来看一下树的几种遍历顺序。先序遍历：根节点→左子树→右子树。中序遍历：左子树→根节点→右子树。后续遍历：左子树→右子树→根节点。其实也很好记，他是根据根节点遍历的顺序来定义的，比如先遍历根节点就是先序遍历，中间遍历根节点就是中序遍历，最后遍历根节点就是后续遍历，至于...

java 二叉树

2021-08-03

22 1256

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

递归方式解决题中说了要转换为一棵高度平衡的二叉搜索树，并且数组又是排过序的，这就好办了。我们可以使用递归的方式，每次取数组中间的值比如m作为当前节点，m前面的值都是比他小的，作为他左子树的结点值。m后面的值都是比他大的，作为他右子树的节点值，示例中一个可能的结果是。代码如下 public ...

java 二叉树 DFS 递归

2021-08-03

4 849