Leetcode

Algorithm 题目描述 给定一个链表，判断链表中是否有环。 Example 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 题目解答 首先能想到的解法是使用一个Set存储已经遍历过的节点，如果在遍历中节点已经存在于Set中，则说明链表是有环的，这种解法额外使用了其它的数据结构。另一种更好的方法就是使用快慢指针的方式，类似于跑道上的套圈，如果快的人追上了慢的人则说明是有环的，否则就是快的人先到达终点（即访问到最后的Null） public class CycleSolution { public static boolean hasCycle(ListNode node) { ListNode slow = node; ListNode fast = node; while (slow != null && fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; } } 快慢指针的解法的时间复杂度为O(n)，空间复杂度为O(1)，因为只使用了两个指针。 ...

Algorithm 题目描述 反转一个单链表。 Example 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 题目解答 迭代解法 class Solution3 { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode current = head; while (current != null) { ListNode tempNode = current.next; current.next = prev; prev = current; current = tempNode; } return prev; } } 第一次搞链表的题，还真是给难住了。此题的核心就是当前节点的指针要指向前一个节点，处理过程中还要考虑节点的丢失问题，所以要有一个变量保存当前节点的前一个节点，还要有一个变量来保存当前节点的下一个节点，方便后续的指针前移。此解法的时间复杂度为O(n)，因其不需要额外的空间，所以空间复杂度为O(1)。 递归解法 class Solution3 { public ListNode reverseList2(ListNode node) { if (node == null || node.next == null) { return node; } ListNode current = reverseList2(node.next); node.next.next = node; node.next = null; return current; } } 此解的核心在于当有一部分是反转时，后续的反转问题，对于node.next.next = node这句，使用A->B两个节点进行示例，A.next为B，A.next.next为B.next，A.next.next = A为B.next = A，这样就实现了A与B两个节点的反转。这个递归看着还是有点懵，多看看就好了。 ...

Algorithm 题目描述 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 Example 输入123->true 输入-123->false 输入12->true 题目解答 class Solution2 { public boolean isPalindrome(int x) { if(x < 0) { return false; } if(x % 10 == 0 && x != 0) { return false; } int reverseNumber = 0; while (x > reverseNumber) { reverseNumber = reverseNumber * 10 + x % 10; x /= 10; } return reverseNumber == x || x == reverseNumber / 10; } } 最简单暴力的方法是把int转换成String进行处理，String反转一半再与后续的进行比较，对于溢出的数字一定不是回文字。此方法则可以更快速的解决问题，关键是怎么找到当前数字的一半位置，可以使用当前数字pop与反转数字的push相比较，当push后的值大于pop后的值则说明到达了数字长度的一半了，对于奇数位的数字则可以使用reverseNumber/10来判断，因为中间的单个字默认就是回文字。此算法的时间复杂度为O(log(n))，空间复杂度为O(1)。 ...

Algorithm 题目描述 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。 Example 输入123->321 输入-123->-321 输入120->21 题目解答 import java.util.*; public class Solution1 { public int[] reverseNumber(int num) { int res = 0; while(num != 0) { int pod = num % 10; if(res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && pod > 7)) { return 0; } if(res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && pod < -8)) { return 0; } res = res * 10 + pod; num = num / 10; } return res; } } 此题主要考察对栈的使用，如果不使用其它辅助类，则要考虑Int的整数溢出问题。时间复杂度O(log(n))，空间复杂度为O(1) ...