题目分析：这道题目要将字符串转化为整数。题目没给出其它的详细的要求，要求coder们自己考虑全部可能出现的情况，那么我们就来详细分析一下。 字符串的可能构成① 字符串是纯数字 可能含有空格，那么去除即可。例如： "1 2" 可能有正负号，那么加上即可。例如： "-12" ② 字符串不是纯数字 可能前面是数字，后面是其它非数字字符。例如："123abcd" 可能前面是非数字字符。例如："abcd123" 所以，鉴于可能出现的字符串有以上几种情况，那么我们就需要完整的验证以上的情况，最后将字符串转化为整数。但是...

题目描述： 题目要求简单易懂，就是在一棵二叉树中找到给定的o1和o2这两个节点的最近的公共祖先。 我们想想，两个节点的最近的公共祖先，无外乎就以下几种情况。第一种，o1和o2恰好分布在根节点root的两侧，那么最近的公共祖先即为根节点root。 第二种，o1和o2分布在根节点的同一侧，那么则会出现两种情况。 ① 首先，出现如下图这种情况，则可以转变为第一种情况，o1和o2分布在了值为5的这个节点的两侧。那么此时o1和o2的最近公共祖先则为值为5这个节点。 ② o1和o2恰好的父子节点的关系，那么此时它们最近的公共祖先则为那个父节点的节点。 所以，基于上面情况的分析，我们可以使用递归的方式...

题目解析： 我们可以从题目中提取出来几个关键点： 第一，抽取出来的数是从0开始到n的； 第二，选出的数字依然保持有序； 第三，缺失一个数。 那么，我们不妨先想想抽出来的数的可能性。① 抽出来形如 [0,2,3,4,5] 的此类数，那么我们很容易知道就是1缺失，简单来说就是头尾完整，中间缺失。② 抽出来形如 [1,2,3,4,5] 的此类数，那么很明显是0缺失，简单来说就是头缺失③ 抽出来形如 [0,1,2,3,4] 的此类数，这一类情况是很容易遗忘的，因为看上去其实没什么问题，都是从0开始，然后到4结束，中间也没有缺失数字。虽然此类情况看上去不缺失，但是我们的题目因为明确说了缺失了一...

题目描述：写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）题目其实很简单，就是反转字符串，这类题目是很常见的。 方法一：双指针使用双指针，一个指针i指向字符串的起点，另外一个指针j指向字符串的最末端，两者指向的位置的字符进行交换，然后两个指针往中间移动。代码: public String solve (String str) { // write code here char[] chars = str.toCharArray(); //定义两个指针，一个指向最前面，一个指向最末端 int...

题目描述: 简单来说，这道题目就是要判断t1树中是否包含t2树。即t2是否为t1树的子树 方法一：递归要判断t2是否为t1的子树，那么就先在t1中找到t2的根节点，然后再进行遍历判断从当前节点的左右子树相不相同，如果一旦出现不同，那么立即返回false。如果t2遍历完节点，t1也遍历完节点，则证明t2为t1的子树。如果t1先遍历完节点，t2还没遍历完节点，那么则证明t2不是t1的子树。代码如下: public boolean isContains (TreeNode root1, TreeNode root2) { // 如果当前节点为空,那么则t2不可能为t1的子树了 ...

题目描述：给定一个链表，请判断该链表是否为回文结构。 例子： 123321 12321 1 11 此类的即为回文结构 方法一：线性表+双指针这个方法其实很容易想到，把题目换了，如果不是一条链表判断是否是回文结构，换成是一个数组。所以我们就可以先遍历一遍链表，然后将里面的值先存放进ArrayList中即可。那么，我们就很容易想到利用双指针去判断是否是回文结构了！ 下面直接给出代码~ public boolean isPail (ListNode head) { if(head == null) return false; if(he...

题目介绍 一个缓存结构需要实现如下功能。set(key, value)：将记录(key, value)插入该结构get(key)：返回key对应的value值但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；如果调用次数最少的key有多个，上次调用发生最早的key被删除这就是LFU缓存替换算法。 概念描述 简单来说，LFU缓存结构就是把数据按照访问的次数来进行排序，当缓存满的时候，则需要根据策略进行淘汰。...

动态规划dp函数 + 记忆数组 算法思路先定义状态，匹配与不匹配两种。当不匹配时，有三种选择: 插入，删除，替换。dp(i, j)为str1[0...i]和str2[0..j]字符串为了匹配做出的代价。对于给定的字符串str1，str2，从右到左，即自顶向下进行匹配。会出现两种情况： 当前字符匹配时，dp(i, j)沿用dp(i-1, j-1)的代价。 当前字符不匹配时，有三种选择。 dp(i, j-1) + 插入的代价 dp(i-1, j) + 删除的代价 dp(i-1, j-1) + 替换的代价当我们每个选择在向下递归时，只有三种选择，第一个选择结束又返回，进行第二个选择时，必定...

题目思路：这道题目就是很典型的回溯类题目。回溯其实也是暴力解法，但是又一些题目可以通过剪枝对算法进行优化，这道题目要找出所有的排列，其实还是比较简单的。算法的思路主要就是：选择与撤销例如：1开头的有，[1,2,3]，接着3撤销，2撤销，然后选择3，再选择2，就有了[1,3,2]。整体用一个图来观看整个过程 方法一：递归 import java.util.*; public class Solution { // 存所有排列的集合 ArrayList<ArrayList<Integer>> res = new ArrayList<>(); ...

题目思路：假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。我们知道题目已经限定了每个节点的值都不为负数了，所以我们就可以不考虑符号的问题了，那么就很简单了。我们先看一下题目给的例子： 例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。从这个例子我们可以得到：1、两个链表的长度可能不等，需要对齐2、相加后可能需要进位对齐进位因为我们无法保证两个链表长度一致，所以我们干脆从后往前对齐，跟我们整数再做加法一样 方法一：反转链表所以我们的入手则是对链表进行对齐，我们可以看...

NC34 求路径 题目思路：这道题目其实很一道很经典的动态规划题目，题目意思很好理解，就是找从起点到终点的所有可行的路径。 约束的两个条件： 机器人每次只能往右或者往下走 机器人不能越界 我们看到这张图就明白一切： 方法一：经典使用dp数组 有了上面的两个条件，我们就可以解决这个题目了。 我们定义一个二维dp数组，dp[i] [j] 表示从起点到我当前位置（i行j列）有多少条可行的路径，因为我们从约束条件中可以知道，机器人每次只能往右或者往下走，则我们当前点必定是从上面或者左边走过来的（除边界外）。 当然，如果在地图的最上面或者最左边的话，最上面的点只能是从左边走到的，最左边的点只能...

35、数组中的逆序对 解题思路： 题目简单易懂就不做过多解释，一开始很容易想到解题可以使用暴力法去统计所有的逆序对，但是这样的话时间复杂度是O(n2) 方法一： 暴力统计法 先直接给出暴力法的代码： public class Solution { public int InversePairs(int[] array) { int cnt = 0; int len = array.length; for (int i = 0; i < len - 1; i++) { for (int j = i + 1; ...

40、数组中只出现一次的两个数字 方法一： 题目给的意思分析之后，很容易想到一种方法，就是用哈希表辅助得到这两个只出现一次的数字。 代码思路： 1、创建一个哈希表 2、当数组元素没有在哈希表中成为key的时候，put进哈希表，当已存在的时候，则remove掉。 3、最后哈希表中剩下的key就是只出现一次的数字 4、遍历key然后返回结果 直接贴出代码： public int[] FindNumsAppearOnce (int[] array) { // write code here // 用于返回结果 int[] res = new int[2...

39、平衡二叉树 解题思路： 这道题目其实跟二叉树的深度这道题用到的方法是一样的，为什么说是一样的呢？因为我们求二叉树的深度，其实就是求了左右子树的深度的最大值，但是这道题目是要让我们判断二叉树是不是平衡树。 我们都知道如何判断一棵二叉树是不是平衡二叉树，就是它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 所以，这个时候我们只需要判断左右子树的深度之差有没有超过1，若超过了则不是平衡的，反之则为平衡二叉树。 我们先来回顾一下求二叉树深度的代码： public int TreeDepth(TreeNode root) { if(roo...