1 环形链表
题目描述
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达该节点，则链表中存在环；
如果链表中存在环，则返回 true 。 否则，返回 false 。
解题思路与代码
解法一：哈希表
public static boolean hasCycle(ListNode head) { Set<ListNode> seen = new HashSet<ListNode>(); while (head != null) { if (!seen.add(head)) { return true; } head = head.next; } return false; }
解法二：双指针
public static boolean hasCycle2(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; }
2 排列硬币
题目描述
总共有 n 枚硬币，将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内
解题思路与代码
解法一：迭代
从第一行开始排列，排完一列、计算剩余硬币数，排第二列，直至剩余硬币数小于或等于行数
public static int arrangeCoins(int n) { for(int i=1; i<=n; i++){ n = n-i; if (n <= i){ return i; } } return 0; }
解法二：二分查找
假设能排 n 行，计算 n 行需要多少硬币数，如果大于 n，则排 n/2行，再计算硬币数和 n 的大小关系
public static int arrangeCoins2(int n) { int low = 0, high = n; while (low <= high) { long mid = (high - low) / 2 + low; long cost = ((mid + 1) * mid) / 2; if (cost == n) { return (int)mid; } else if (cost > n) { high = (int)mid - 1; } else { low = (int)mid + 1; } } return high; }
解法三：牛顿迭代
使用牛顿迭代求平方根，(x + n/x)/2
假设能排 x 行 则 1 + 2 + 3 + …+ x = n，即 x(x+1)/2 = n 推导出 x = 2n - x
public static double sqrts(double x,int n){ double res = (x + (2*n-x) / x) / 2; if (res == x) { return x; } else { return sqrts(res,n); } }
3 合并两个有序数组
题目描述
两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。假设 nums1 的空间大小等于 m + n，这样它就
有足够的空间保存来自 nums2 的元素。
解题思路与代码
解法一：合并后排序
public void merge(int[] nums1, int m, int[] nums2, int n) { System.arraycopy(nums2, 0, nums1, m, n); Arrays.sort(nums1); }
- 时间复杂度 : O((n+m)log(n+m))。
- 空间复杂度 : O(1)。
解法二：双指针
从前往后
将两个数组按顺序进行比较，放入新的数组
public void merge(int[] nums1, int m, int[] nums2, int n) { int [] nums1_copy = new int[m]; System.arraycopy(nums1, 0, nums1_copy, 0, m);//拷贝数组1 int p1 = 0;//指向数组1的拷贝 int p2 = 0;//指向数组2 int p = 0;//指向数组1 //将数组1当成空数组，比较数组1的拷贝和数组2，将较小的放入空数组 while ((p1 < m) && (p2 < n)) nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++]; //数组2和数组1不等长，将多出的元素拷贝 if (p1 < m) System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2); if (p2 < n) System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2); }
- 时间复杂度 : O(n + m)。
- 空间复杂度 : O(m)。
解法三：双指针优化
从后往前
public void merge(int[] nums1, int m, int[] nums2, int n) { int p1 = m - 1; int p2 = n - 1; int p = m + n - 1; while ((p1 >= 0) && (p2 >= 0)) nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--]; System.arraycopy(nums2, 0, nums1, 0, p2 + 1); }
- 时间复杂度 : O(n + m)。
- 空间复杂度 : O(1)。
