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

zl程序教程

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

当前栏目

Java每日一练(20230320)

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

目录

1. 两数之和  🌟🌟

2. 盛最多水的容器  🌟🌟

3. 反转链表 II  🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 10^3
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • 只会存在一个有效答案
import java.util.*;
public class twoSum {
    public static class Solution {
        public static int[] twoSum(int[] nums, int target) {
            Map<Integer, Integer> cache = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                int distance = target - nums[i];
                if (cache.containsKey(distance)) {
                    return new int[] { cache.get(distance), i };
                } else {
                    cache.put(nums[i], i);
                }
            }
            return new int[] {};
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int nums[] = {2,7,11,5};
        int res[] = s.twoSum(nums, 9);
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i] + " ");
        }
        System.out.println();

        int nums2[] = {3,2,4};
        int res2[] = s.twoSum(nums2, 6);
        for (int i = 0; i < res2.length; i++) {
            System.out.print(res2[i] + " ");
        }
        System.out.println();
 
        int nums3[] = {3,3};
        int res3[] = s.twoSum(nums3, 6);
        for (int i = 0; i < res3.length; i++) {
            System.out.print(res3[i] + " ");
        }
        System.out.println();
   }
}

输出：

0 1 
1 2 
0 1 

2. 盛最多水的容器

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

示例 3：

输入：height = [4,3,2,1,4]
输出：16

示例 4：

输入：height = [1,2,1]
输出：2

提示：

  • n = height.length
  • 2 <= n <= 3 * 10^4
  • 0 <= height[i] <= 3 * 10^4

代码：

import java.util.*;
public class maxArea {
    public static class Solution {
        public int maxArea(int[] height) {
            int N = height.length;
            int i = 0;
            int j = N - 1;
            int max = 0;
            while (i < j) {
                int c = (j - i) * Math.min(height[i], height[j]);
                if (c > max) {
                    max = c;
                }
                if (height[i] > height[j]) {
                    j--;
                } else {
                    i++;
                }
            }
            return max;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int height[] = {1,8,6,2,5,4,8,3,7};
        System.out.println(s.maxArea(height));

        int height2[] = {1,1};
        System.out.println(s.maxArea(height2));

        int height3[] = {4,3,2,1,4};
        System.out.println(s.maxArea(height3));

        int height4[] = {1,2,1};
        System.out.println(s.maxArea(height4));
    }
}

输出：

49
1
16
2

3. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

代码：


import java.util.Arrays;
public class reverseBetween {
    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 reverseBetween(ListNode head, int m, int n) {
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode pre = dummy;
            for (int i = 1; i < m; i++) {
                pre = pre.next;
            }
            head = pre.next;
            for (int i = m; i < n; i++) {
                ListNode nex = head.next;
                head.next = nex.next;
                nex.next = pre.next;
                pre.next = nex;
            }
            return dummy.next;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1,2,3,4,5};
        ListNode head = createLinkedList(nums);
        printLinkedList(head);
        head = s.reverseBetween(head, 2, 4);
        printLinkedList(head);
 
        int[] nums2 = {5};
        head = createLinkedList(nums2);
        printLinkedList(head);
        head = s.reverseBetween(head, 1, 1);
        printLinkedList(head);
   }
}

输出：

1->2->3->4->5->null
1->4->3->2->5->null
5->null
5->null

递归法：

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            return reverseN(head, right);
        }
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
    ListNode successor = null; // 后驱节点
    // 反转以 head 为起点的 n 个节点，返回新的头结点
    ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return last;
    }
} 

完整代码如下：

public class reverseBetween {
    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 reverseBetween(ListNode head, int left, int right) {
            if (left == 1) {
                return reverseN(head, right);
            }
            head.next = reverseBetween(head.next, left - 1, right - 1);
            return head;
        }
        ListNode successor = null; // 后驱节点
        // 反转以 head 为起点的 n 个节点，返回新的头结点
        ListNode reverseN(ListNode head, int n) {
            if (n == 1) {
                successor = head.next;
                return head;
            }
            ListNode last = reverseN(head.next, n - 1);
            head.next.next = head;
            head.next = successor;
            return last;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1,2,3,4,5};
        ListNode head = createLinkedList(nums);
        printLinkedList(head);
        head = s.reverseBetween(head, 2, 4);
        printLinkedList(head);
 
        int[] nums2 = {5};
        head = createLinkedList(nums2);
        printLinkedList(head);
        head = s.reverseBetween(head, 1, 1);
        printLinkedList(head);
   }
}

🌟 每日一练刷题专栏 🌟

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

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

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

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

​

Golang每日一练 专栏

​

Python每日一练 专栏

​

C/C++每日一练 专栏

​

Java每日一练 专栏

相关文章