1，反转后半部分链表 这题是让判断链表是否是回文链表，所谓的回文链表就是以链表中间为中心点两边对称。我们常见的有判断一个字符串是否是回文字符串，这个比较简单，可以使用两个指针，一个最左边一个最右边，两个指针同时往中间靠，判断所指的字符是否相等。  但这题判断的是链表，因为这里是单向链表，只能从前往后访问，不能从后往前访问，所以使用判断字符串的那种方式是行不通的。但我们可以通过找到链表的中间节点然后把链表后半部分反转（关于链表的反转可以看下432，剑指 Offer-反转链表的3种方式），最后再用后半部分反转的链表和前半部分一个个比较即可。这里以示例2为例画个图看一下。   最后再来看下代码 pu...

1，递归的写法 这题我们可以参照之前分析的青蛙跳台阶问题，其实原理是完全一样的 我们来分析一下：  当n等于1的时候，只需要跳一次即可，只有一种跳法，记f(1)=1 当n等于2的时候，可以先跳一级再跳一级，或者直接跳二级，共有2种跳法，记f(2)=2 当n等于3的时候，他可以从一级台阶上跳两步上来，也可以从二级台阶上跳一步上来，所以总共有f(3)=f(2)+f(1)；  同理当等于n的时候，总共有f(n)=f(n-1)+f(n-2)(这里n>2)种跳法。 所以如果我们求上到n阶有多少种，代码很简单，直接递归就行  public static int JumpFloor(int n) { ...

1，通过集合set解决 做这题最容易想到的一种解决方式就是先把第一个链表的节点全部存放到集合set中，然后遍历第二个链表的每一个节点，判断在集合set中是否存在，如果存在就直接返回这个存在的结点。如果遍历完了，在集合set中还没找到，说明他们没有相交，直接返回null即可，原理比较简单，直接看下代码 public class Solution { public ListNode FindFirstCommonNode(ListNode headA, ListNode headB) { //创建集合set HashSet<listnode> set = new HashSet&amp...

这题可以参照《判断链表中是否有环》 ，答案我之前写过《链表是否有环3种方式解决》 ，这两道题有非常大的相似地方。 1，快慢指针解决 在前面我们提到过快慢指针，先判断是否有环，如果有环，在来找环的入口。我们假设是有环的，那么会有两种情况，我们来画个图看一下 1，环很大  假如他们在相遇点相遇了，那么慢指针走过的距离是a+b，快指针走过的距离就是a+b+c+b，因为相同时间内快指针走的距离是慢指针的2倍，所以有a+b+c+b = 2*(a+b)，整理得到a=c，也就是说从相遇点到环的入口和链表的起始点到环的入口，距离是一样的。在相遇点的时候我们可以使用两个指针，一个从相遇点开始，一个从链表头开始，...

1，双指针解决 题中说了只有小写字母，最简单的就是使用双指针，一个指向前，一个指向后，两个指针同时往中间走，如果两个指针指向的字符不一样就返回false，来看下代码  public boolean judge(String str) { if (str.length() == 0) return true; //两个指针，一个从左边开始，一个从右边开始，每次两个 //指针都同时往中间挪，只要两个指针指向的字符不一样就返回false int left = 0; int right = str.length() - 1; while (left < right) { if (str....

1，动态规划解决 这题是让求完成一笔交易所获得的最大利润，首先我们来看一下使用动态规划该怎么解决，动态规划还是那常见的几个步骤  确定状态 找到转移公式 确定初始条件以及边界条件 计算结果   我们来定义一个二维数组dp[length][2]，其中dp[i][0]表示第i+1天（i是从0开始的）结束的时候没持有股票的最大利润，dp[i][1]表示第i+1天结束的时候持有股票的最大利润。  如果我们要求第i+1天结束的时候没持有股票的最大利润dp[i][0]，那么会有两种情况。 第一种情况就是第i+1天我们即没买也没卖，那么最大利润就是第i天没持有股票的最大利润dp[i-1][0]。 第二种情况...

1，BFS打印 二叉树的BFS打印，就是一层一层的往下打印，就像下面这样 具体可以看下373，数据结构-6,树，这里介绍了递归和非递归的解法。非递归的代码如下  public static void levelOrder(TreeNode tree) { if (tree == null) return; Queue<treenode> queue = new LinkedList<>(); queue.add(tree);//相当于把数据加入到队列尾部 while (!queue.isEmpty()) { //poll方法相当于移除队列头部的元素 Tr...

要判断括号的有效性，左括号必须和右括号相对应。如果是有效括号，并且他们中间还有括号，那么他们必须也是有效的，所以最简单的一种方式就是使用栈来解决。  我们遍历字符串中的所有字符 1，如果遇到了左括号，就把对应的右括号压栈（比如遇到了字符'('，就把字符')'压栈）。 2，如果遇到了右括号  1）查看栈是否为空，如果为空，说明不能构成有效的括号，直接返回false。 2）如果栈不为空，栈顶元素出栈，然后判断出栈的这个元素是否等于这个右括号，如果不等于，说明不匹配，直接返回false。如果匹配，就继续判断字符串的下一个字符。   3，最后如果栈为空，说明是完全匹配，是有效的括号，否则如果栈不为空，...

1，参照归并排序 可以参照归并排序，具体可以看下《排序-归并排序》  public void merge(int[] nums1, int m, int[] nums2, int n) { int temp[] = new int[m + n]; int index = 0; int i = 0; int j = 0; while (i < m && j < n) { if (nums1[i] <= nums2[j]) temp[index++] = nums1[i++]; else temp[index++] = nu...

1，非递归解决 每k个一组进行反转，如果不够k个就不需要反转，关于链表的反转，不会的可以看下《432，剑指 Offer-反转链表的3种方式》 。最简单的一种方式就是把链表每k个分成一组，然后反转这每一组的节点，接着在把他们串起来即可。  public ListNode reverseKGroup(ListNode head, int k) { //先创建一个哑节点 ListNode dummy = new ListNode(0); //让哑节点的指针指向链表的头 dummy.next = head; //开始反转的前一个节点，比如反转的节点范围是[link1，link2], //那么pre就是...

java的18种写法，之前在公众号《数据结构和算法》中分为3个系列专门写过，这里就不在细写了，我把答案全部列出来，因为太多，我只给一些简单的提示，如果不懂的可以看下前面写的那3个系列，有图文分析 364，位1的个数系列（一） 385，位1的个数系列（二） 402，位1的个数系列（三） 或者也可以在下面留言，我来给你解答。 1，把n往右移32次，每次都和1进行与运算 public int NumberOf1(int n) { int count = 0; for (int i = 0; i < 32; i++) { if (((n >>> ...

1，递归 这题最容易想到的就是递归，啥叫“递归”，也就是下面这张图 开个玩笑，我们画个图来看下 原理很简单，代码如下  public int TreeDepth(TreeNode root) { return root==null? 0 : Math.max(TreeDepth(root.left), TreeDepth(root.right))+1; }  看一下运行结果   2，BFS BFS的实现原理就是一层层遍历，统计一下总共有多少层，我们来画个图分析一下。 代码如下  public int TreeDepth(TreeNode root) { if (root == null) re...