1. 链表插入排序
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
出处：
https://edu.csdn.net/practice/23630781
代码：
import java.util.Arrays; public class insertionSortList { public static class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public static ListNode createLinkedList(int[] nums) { if (nums == null || nums.length == 0) { return null; } ListNode head = new ListNode(nums[0]); ListNode cur = head; for (int i = 1; i < nums.length; i++) { cur.next = new ListNode(nums[i]); cur = cur.next; } return head; } public static void printLinkedList(ListNode head) { ListNode cur = head; while (cur != null) { System.out.print(cur.val + "->"); cur = cur.next; } System.out.println("null"); } public static class Solution { public ListNode insertionSortList(ListNode head) { if (head == null) return head; ListNode res = new ListNode(head.val); ListNode left = head.next; while ((left != null)) { ListNode cur = left; left = left.next; if (cur.val <= res.val) { cur.next = res; res = cur; continue; } ListNode p = res; ListNode last = p; while (p != null && p.val < cur.val) { last = p; p = p.next; } last.next = cur; last.next.next = p; } return res; } } public static void main(String[] args) { Solution s = new Solution(); int[] nums = {4,2,1,3}; ListNode head = createLinkedList(nums); printLinkedList(head); head = s.insertionSortList(head); printLinkedList(head); int[] nums2 = {-1,5,3,4,0}; head = createLinkedList(nums2); printLinkedList(head); head = s.insertionSortList(head); printLinkedList(head); } }
输出：
4->2->1->3->null
1->2->3->4->null
-1->5->3->4->0->null
-1->0->3->4->5->null
2. 最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4
出处：
https://edu.csdn.net/practice/23630782
代码：
import java.util.Arrays; public class threeSumClosest { public static class Solution { public int oneSumCloset(int[] nums, int i, int j, int start, int end, int target) { if (start == i || start == j) start = start + 1; if (end == i || end == j) end = end - 1; if (start == end) { return nums[start]; } else if (end == start + 1 || end == start - 1) { if (Math.abs(nums[end] - target) > Math.abs(nums[start] - target)) { return nums[start]; } else { return nums[end]; } } else { int middle = (int) Math.floor((start + end) / 2); if (nums[middle] > target) { end = middle; } else { start = middle; } return oneSumCloset(nums, i, j, start, end, target); } } public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int minValue = 0; boolean hasMin = false; for (int i = 0; i < nums.length - 2; i++) { for (int j = i + 1; j < nums.length - 1; j++) { int twoSum = nums[i] + nums[j]; int rest = target - twoSum; int restClost = oneSumCloset(nums, i, j, j + 1, nums.length - 1, rest); int newValue = restClost + twoSum; ; if (!hasMin) { minValue = newValue; hasMin = true; } else { int d1 = Math.abs(minValue - target); int d2 = Math.abs(newValue - target); if (d1 > d2) { minValue = newValue; } } } } return minValue; } } public static void main(String[] args) { Solution s = new Solution(); int[] nums = {-1,2,1,-4}; System.out.println(s.threeSumClosest(nums, 1)); } }
输出：
2
3. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
出处：
https://edu.csdn.net/practice/23630783
代码：
public class findMin { public static class Solution { public int findMin(int[] nums) { int low = 0, high = nums.length - 1, mid = 0; while (low <= high) { mid = (low + high) / 2; if (nums[mid] > nums[high]) low = mid + 1; else if (nums[mid] < nums[high]) high = mid; else high--; } return nums[low]; } } public static void main(String[] args) { Solution s = new Solution(); int[] nums = {3,4,5,1,2}; System.out.println(s.findMin(nums)); int[] nums1 = {4,5,6,7,0,1,2}; System.out.println(s.findMin(nums1)); int[] nums2 = {11,13,15,17}; System.out.println(s.findMin(nums2)); } }
输出：
1
0
11
