廿半

题解

/ 注册

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

【剑指offer】平衡二叉树

递归。如果当前节点为null，也说明是平衡树，返回true。如果左子树和右子树的高度差大于1，说明以当前节点作为根节点的树不是平衡树，则直接返回false；如果左子树和右子树的高度差小于等于1，说明以当前节点作为根节点的树是平衡树，则递归判断对其左子树和右子树是否是平衡树。计算树的高度可参考上一题的...

递归二叉树

2019-12-28

0 652

【剑指offer】两个链表的第一个公共结点

双指针法。创建两个指针p1和p2,分别指向两个链表的头结点，然后依次往后遍历。如果某个指针到达末尾，则将该指针指向另一个链表的头结点；如果两个指针所指的节点相同，则循环结束，返回当前指针指向的节点。比如两个链表分别为：1->3->4->5->6和2->7->8-&...

链表数据结构

2019-12-27

1 2111

【剑指offer】连续子数组的最大和

典型的动态规划。dp[n]代表以当前元素为截止点的连续子序列的最大和，如果dp[n-1]>0，dp[n]=dp[n]+dp[n-1]，因为当前数字加上一个正数一定会变大；如果dp[n-1]<0，dp[n]不变，因为当前数字加上一个负数一定会变小。使用一个变量max记录最大的dp值返回即可...

算法矩阵数组动态规划

2019-12-26

174 5498

【剑指offer】字符串的排列

该题目其实就是对数组中的每个字符和其它字符进行交换完成的，但是该交换过程是递归完成的。以"abc"为例，在第一层递归中，会将第一个字符'a'和后续字符进行依次交换，形成"abc"、"bac"和"cba"传入下一层递归，在下一次递归中，又会分别以整个字符串的第二个字符开始，与后续字符依次交换。当交换到...

算法递归 Java 字符串

2019-12-25

0 721

【剑指offer】二叉搜索树与双向链表-非递归实现

二叉搜索树的中序遍历就是有序序列，因此对二叉搜索树进行中序遍历，将中序遍历的当前节点与前一个节点进行连接。本解法使用栈完成非递归的遍历。 public static TreeNode Convert(TreeNode pRootOfTree) { if (pRootOfTree ==...

算法 Java 树非递归栈

2019-12-24

1 922

【剑指offer】顺时针打印矩阵

该类题目需要从宏观的角度去考虑。1.首先定义一个方法，给定左上角和右下角两个点，使用四个循环遍历输出矩阵外圈。注：需要考虑只包含一行和一列的情况。2.确定矩阵的左上角和右下角，不断往里递进，调用步骤1中的方法打印当前矩阵的最外圈。 public static ArrayList<Integer...

算法 Java 矩阵顺时针打印矩阵数据结构

2019-12-22

0 603