目录

1. 链表插入排序  🌟🌟

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

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

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

1. 链表插入排序

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

示例 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

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏