当前位置：首页 > news >正文

Java每日一练(20230324)

news 2025/8/8 1:14:39

1. 链表插入排序 🌟🌟

2. 最接近的三数之和 🌟🌟

3. 寻找旋转排序数组中的最小值 🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

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));}
}

输出：

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;elsehigh--;}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