提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

Java每日一练(20230328)

JAVA 每日
2023-09-14 09:01:29 时间

目录

1. 四数之和  🌟🌟

2. 重排链表  🌟🌟

3. 填充每个节点的下一个右侧节点指针 II  🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

1. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [], target = 0
输出：[]

提示：

  • 0 <= nums.length <= 200
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9

出处：

https://edu.csdn.net/practice/23951361

代码： 暴力枚举

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        long l_target = target;
        Arrays.sort(nums);
        List<List<Integer>> results = new ArrayList<>();
        int N = nums.length;
        for (int i = 0; i < N - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1])  // 跳过相等的元素
                continue;
            for (int j = i + 1; j < N - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1])  // 跳过相等的元素
                    continue;
                for (int k = j + 1, l = N - 1; k < l; k++) {
                    if (k > j + 1 && nums[k] == nums[k - 1])  // 跳过相等的元素
                        continue;
                    while (k < l && (l_target - nums[i] - nums[j] - nums[k] - nums[l]) < 0) {
                        l--;
                    }
                    if (k >= l) {
                        break;
                    }
                    if ((target - nums[i] - nums[j] - nums[k] - nums[l]) == 0) {
                        List<Integer> item = new ArrayList<>();
                        item.add(nums[i]);
                        item.add(nums[j]);
                        item.add(nums[k]);
                        item.add(nums[l]);
                        results.add(item);
                    }
                }
            }
        }
        return results;
    }
}

代码2： 双指针

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        if (n < 4) {
            return res;
        }
        Arrays.sort(nums);
        for (int i = 0; i < n - 3; i++) {
            // 如果当前数字与前一个数字相同，会导致重复，跳过
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 剪枝，如果当前数字加上剩下三个数字的最小和都大于目标值，就没必要继续了
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            // 剪枝，如果当前数字加上剩下三个数字的最大和都小于目标值，就没必要继续了
            if (nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) {
                continue;
            }
            for (int j = i + 1; j < n - 2; j++) {
                // 如果当前数字与前一个数字相同，会导致重复，跳过
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                // 剪枝，如果当前数字加上剩下两个数字的最小和都大于目标值，就没必要继续了
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                // 剪枝，如果当前数字加上剩下两个数字的最大和都小于目标值，就没必要继续了
                if (nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target) {
                    continue;
                }
                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 如果左指针和右指针指向的数字与它们前面的数字相同，会导致重复，跳过
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

代码3： 哈希表

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);  // 排序
        Map<Integer, List<int[]>> map = new HashMap<>();  // 哈希表
        for (int i = 0; i < n-1; i++) {
            for (int j = i+1; j < n; j++) {
                if (!map.containsKey(nums[i]+nums[j])) {  // 如果不存在，创建一个新的列表
                    map.put(nums[i]+nums[j], new ArrayList<>());
                }
                map.get(nums[i]+nums[j]).add(new int[]{i, j});  // 将下标加入到列表中
            }
        }
        for (int i = 0; i < n-1; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;  // 跳过相等的元素
            for (int j = i+1; j < n; j++) {
                if (j > i+1 && nums[j] == nums[j-1]) continue;  // 跳过相等的元素
                if (map.containsKey(target-nums[i]-nums[j])) {  // 如果存在，将所有满足条件的四元组加入到结果中
                    List<int[]> temp = map.get(target-nums[i]-nums[j]);
                    for (int[] t : temp) {
                        if (t[0] > j) {  // 确保四元组不重复
                            List<Integer> quadruplet = new ArrayList<>();
                            quadruplet.add(nums[i]);
                            quadruplet.add(nums[j]);
                            quadruplet.add(nums[t[0]]);
                            quadruplet.add(nums[t[1]]);
                            res.add(quadruplet);
                        }
                    }
                }
            }
        }
        return res;
    }
}

2. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

 L0 → L1 → … → Ln-1 → Ln 
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

输入: head = [1,2,3,4]
输出: [1,4,2,3]

示例 2:

输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]

提示：

  • 链表的长度范围为 [1, 5 * 10^4]
  • 1 <= node.val <= 1000

出处：

https://edu.csdn.net/practice/23951362

代码：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}
class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next, pre = null, next = null;
        slow.next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        ListNode p1 = head, p2 = pre;
        while (p1 != null && p2 != null) {
            next = p2.next;
            p2.next = p1.next;
            p1.next = p2;
            p1 = p2.next;
            p2 = next;
        }
    }
}

代码2：

public void reorderList(ListNode head) {
    if (head == null || head.next == null) {
        return;
    }
    List<ListNode> nodeList = new ArrayList<>();
    ListNode node = head;
    while (node != null) {
        nodeList.add(node);
        node = node.next;
    }
    int left = 0, right = nodeList.size() - 1;
    while (left < right) {
        nodeList.get(left).next = nodeList.get(right);
        left++;
        if (left == right) {
            break;
        }
        nodeList.get(right).next = nodeList.get(left);
        right--;
    }
    nodeList.get(left).next = null;
}

3. 填充每个节点的下一个右侧节点指针 II

给定一个二叉树

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

提示：

  • 树中的节点数小于 6000
  • -100 <= node.val <= 100

出处：

https://edu.csdn.net/practice/23951363

代码：

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
    public Node() {
    }
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
class Solution {
    public Node connect(Node root) {
        if (root == null || (root.left == null && root.right == null)) {
            return root;
        }
        if (root.left != null && root.right != null) {
            root.left.next = root.right;
            root.next = getrightnext(root);
        }
        if (root.left != null) {
            root.left.next = getrightnext(root);
        }
        if (root.right != null) {
            root.right.next = getrightnext(root);
        }
        connect(root.right);
        connect(root.left);
        return root;
    }
    public static Node getrightnext(Node root) {
        while (root.next != null) {
            if (root.left != null) {
                return root.left;
            }
            if (root.right != null) {
                return root.right;
            }
            root = root.next;
        }
        return null;
    }
}

 

🌟 每日一练刷题专栏 🌟

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

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

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

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

☸ 主页：https://hannyang.blog.csdn.net/ 

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

相关文章