Java实现LeetCode算法精选与笔记解析

资源摘要信息:"leetcode答案-Algorithm:算法使用Java" 在编程和算法的世界中，LeetCode 是一个广受欢迎的在线平台，它提供了一系列编程挑战，帮助开发者练习和提高算法和数据结构的应用能力。在本资源中，将详细介绍如何使用Java语言解决几个典型的算法问题，并提供相关的实现和笔记。 1. 判断正整数是否为回文数 问题描述：编写一个函数，检查一个正整数是否是回文数。回文数指的是正序（从左到右）和倒序（从右到左）读都是一样的数。 Java实现思路：可以通过将整数反转后与原数比较的方法来判断。需要注意的是，对于大整数，直接反转可能会导致整数溢出，因此可以考虑反转一半的数字进行比较。 Java实现示例代码片段： ```java public class IsPalindrome { public boolean isPalindrome(int x) { // 特殊情况： // 如上所述，当 x < 0 时，x 不是回文数。 // 同样地，如果数字的最后一位是 0，为了使该数字为回文， // 则其第一位数字也应该是 0 // 只有 0 满足这一属性 if (x < 0 || (x % 10 == 0 && x != 0)) { return false; } int revertedNumber = 0; while (x > revertedNumber) { revertedNumber = revertedNumber * 10 + x % 10; x /= 10; } // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。 // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123， // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。 return x == revertedNumber || x == revertedNumber / 10; } } ``` 2. 无序数组中两数之和等于目标数 问题描述：给定一个无序数组 arr 和一个整数 aim，找到数组中哪两个数的和等于 aim。假设数组中只有一对数的和等于目标值。 Java实现思路：可以使用一个哈希表来存储已经遍历过的数字及其索引，对于当前数字，通过哈希表查找是否存在一个数与当前数字的和等于 aim。 Java实现示例代码片段： ```java public class TowSum { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> numMap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (numMap.containsKey(complement)) { return new int[]{numMap.get(complement), i}; } numMap.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } } ``` 3. 链表排序 问题描述：给定一个链表，重新调整其节点顺序，使得奇数节点位于偶数节点之前，并且保持奇数节点和偶数节点内部的相对顺序。 Java实现思路：可以使用两个链表分别保存奇数和偶数节点，最后将两个链表连接起来。 Java实现示例代码片段： ```java public class LinkListApart { public static ListNode oddEvenList(ListNode head) { if (head == null) return head; ListNode even = head.next, evenHead = even; while (even != null && even.next != null) { head.next = even.next; head = head.next; even.next = head.next; even = even.next; } head.next = evenHead; return head; } } ``` 4. 搜索二叉树转换为双向链表 问题描述：将一个搜索二叉树（BST）转换为一个排序的双向链表。 Java实现思路：可以使用中序遍历的方法，中序遍历本身就可以按照排序顺序访问树中的所有节点，然后在遍历过程中逐步构建双向链表。 Java实现示例代码片段： ```java public class BstToDoubleLinkedList { private TreeNode prev = null; private TreeNode head = null; public TreeNode convert(TreeNode root) { if (root == null) { return null; } inOrder(root); return head; } private void inOrder(TreeNode node) { if (node == null) { return; } inOrder(node.left); if (prev == null) { head = node; } else { node.left = prev; prev.right = node; } prev = node; inOrder(node.right); } } ``` 5. 数组中子数组的最大差值不超过给定数num的个数 问题描述：给定一个数组 arr 和一个整数 num，返回数组中满足 max(arr[i...j]) - min(arr[i...j]) <= num 的子数组个数。 Java实现思路：使用滑动窗口的方法，维护一个当前子数组的最大值和最小值，并根据当前值更新窗口的左右边界。 Java实现示例代码片段： ```java public class MaxMinDiffSubarray { public int countSubarray(int[] arr, int num) { int count = 0; int left = 0, right = 0; int currentMax = arr[0]; int currentMin = arr[0]; while (right < arr.length) { currentMax = Math.max(currentMax, arr[right]); currentMin = Math.min(currentMin, arr[right]); while (currentMax - currentMin > num) { currentMax = Math.max(currentMax, arr[left]); currentMin = Math.min(currentMin, arr[left]); left++; } count += right - left + 1; right++; } return count; } } ``` 以上就是使用Java语言解决LeetCode上的几个典型算法问题的实现方法和相关笔记。通过这些练习，可以加深对算法和Java编程的理解，并提升解决实际问题的能力。