这题可以参照《判断链表中是否有环》 ，答案我之前写过《链表是否有环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 = s...

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 (!queu...

要判断括号的有效性，左括号必须和右括号相对应。如果是有效括号，并且他们中间还有括号，那么他们必须也是有效的，所以最简单的一种方式就是使用栈来解决。 我们遍历字符串中的所有字符 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]) ...

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

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 >>> i) &...

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...

1，非递归解决 这题比较简单，因为链表是升序的，我们只需要遍历每个链表的头，比较一下哪个小就把哪个链表的头拿出来放到新的链表中，一直这样循环，直到有一个链表为空，然后我们再把另一个不为空的链表挂到新的链表中。我们就以3→4→7→9和2→5→6两个链表来画个图看一下是怎么合并的。 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //下面4行是空判断 if (l1 == null) return l2; if (l2 == null) ...

1，BFS解决 其实这就是二叉树的BFS，也可以看下之前讲的373，数据结构-6,树 ， 就是这样，一层一层打印，使用队列解决 public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { //边界条件判断 if (root == null) return new ArrayList<>(); //队列 Queue<TreeNode> queue = new LinkedList&lt...

1，从尾部插入 实际上这道题求的是两个字符串相加，我们就用两个很短的字符串"12367"+"89"为例画个图来看下是怎么计算的 它相当于两个字符串从最右边开始相加，比如我们要计算s字符串的最右边的那个数字和t字符串最右边的那个字符相加 int i = s.length() - 1, j = t.length() - 1; int x = s.charAt(i) - '0'; int y = t.charAt(j) - '0'; int sum = x + y;把计算的结果放到一个新的字符串后面，但字符串每一位只能保存一位数字，而我们相加的结果sum可能是个两位数，所以这里我们只取他的个位数，...

1，快慢指针解决 判断链表是否有环应该是老生常谈的一个话题了，最简单的一种方式就是快慢指针，慢指针针每次走一步，快指针每次走两步，如果相遇就说明有环，如果有一个为空说明没有环。代码比较简单 public boolean hasCycle(ListNode head) { if (head == null) return false; //快慢两个指针 ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) {...

1，使用栈解决 链表的反转是老生常谈的一个问题了，同时也是面试中常考的一道题。最简单的一种方式就是使用栈，因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。原理如下 import java.util.Stack; public class Solution { public ListNode ReverseList(ListNode head) { Stack<ListNode> stack= new Stack<>(); //把链表节点全部摘掉放到栈中 while (...