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

Java每日一练(20230329)

news 2025/7/28 10:00:47

1. 环形链表 II 🌟🌟

2. 基础语句 ※

3. 最小覆盖子串 🌟🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

1. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 10^4] 内
-10^5 <= Node.val <= 10^5
pos 的值为 -1 或者链表中的一个有效索引

出处：

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

代码： 快慢指针

public class ListNode {int val;ListNode next;ListNode(int x) {val = x;}
}
public class Solution {public ListNode detectCycle(ListNode head) {if (head == null || head.next == null) {return null;}ListNode slow = head;ListNode fast = head;while (true) {if (fast == null || fast.next == null) {return null;}fast = fast.next.next;slow = slow.next;if (fast == slow) {break;}}slow = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return fast;}
}

原理：快慢指针判断链表是否存在环

定义两个指针 slow 和 fast，初始值都为链表头结点 head；slow 指针每次移动一步，fast 指针每次移动两步。如果链表不存在环，fast 指针会先到达链表末尾，此时可以返回 null；如果链表存在环，fast 指针最终会追上 slow 指针，此时可以跳出循环。

计算环的起点

因为快指针的速度是慢指针的两倍，所以当它们相遇时，慢指针在环中走了 k 步，快指针在环中走了 2k 步。假设环的长度为 r，那么 2k = k + nr，即 k = nr；从链表头结点开始，定义一个新的指针 p，它和 slow 指针每次都向前移动一步；当 p 指针到达环的起点时，slow 指针也恰好到达环的起点，此时返回 p 指针即可。

2. 基础语句

原标题：输出每天是应该学习还是休息还是锻炼

30天中，从第一天开始五天学习，一天休息、一天锻炼，输出每天是应该学习还是休息还是锻炼

出处：

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

代码：

public class HelloWorld {public static void main(String []args) {int n1=0,n2=0,n3=0,i;for(i=1;i<=30;i++){if(n1<5){System.out.println("学习");n1++;continue;}else{System.out.println("休息");System.out.println("锻炼");n1=0;i++;}}}
}

3. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

输入：s = "a", t = "a"
输出："a"

提示：

1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

出处：

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

代码：

public class Min_Win_Sub {public String minWindow(String s, String t) {int[] ta = new int[128];int[] sa = new int[128];int min = Integer.MAX_VALUE;String minwin = "";for (int i = 0; i < t.length(); i++) {ta[t.charAt(i)]++;}int count = 0;int end = 0;int start = 0;while (end < s.length()) {if (ta[s.charAt(end)] != 0) {if (sa[s.charAt(end)] < ta[s.charAt(end)]) {count++;}sa[s.charAt(end)]++;}if (count == t.length()) {while (ta[s.charAt(start)] == 0 || sa[s.charAt(start)] > ta[s.charAt(start)]) {if (sa[s.charAt(start)] > ta[s.charAt(start)]) {sa[s.charAt(start)]--;}start++;}if (end - start + 1 < min) {minwin = s.substring(start, end + 1);min = end - start + 1;}}end++;}return minwin;}
}

在滑动窗口中，start 指向窗口左边界，end 指向窗口右边界。当窗口中的字符数目达到了 t 中字符的数目，就需要尝试缩小窗口大小。这时候可以让 start 指针不断右移，直到当前窗口不再满足条件。
具体地，如果当前窗口中的字符 c 不在字符串 t 中，或者 c 在窗口中的数目大于等于 c 在 t 中的数目，那么就可以让 start 右移，并更新窗口中字符 c 的数目。直到当前窗口中的字符数目不再满足要求，停止右移。
要注意，在右移 start 指针的过程中，不仅需要更新窗口中字符 c 的数目，还需要判断当前字符是否在 t 中，避免将不在 t 中的字符加入到窗口中。