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

Java每日一练(20230501)

news 2025/8/23 13:17:20

1. 路径交叉 🌟🌟

2. 环形链表 🌟🌟

3. 被围绕的区域 🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

1. 路径交叉

给你一个整数数组 distance 。

从 X-Y 平面上的点 (0,0) 开始，先向北移动 distance[0] 米，然后向西移动 distance[1] 米，向南移动 distance[2] 米，向东移动 distance[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。

判断你所经过的路径是否相交。如果相交，返回 true ；否则，返回 false 。

示例 1：

输入：distance = [2,1,1,2]
输出：true

示例 2：

输入：distance = [1,2,3,4]
输出：false

示例 3：

输入：distance = [1,1,1,1]
输出：true

提示：

1 <= distance.length <= 10^5
1 <= distance[i] <= 10^5

出处：

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

代码：

class Solution {public boolean isSelfCrossing(int[] x) {if (x.length < 4)return false;int a = 0, b = 0, c = 0;int d = x[0], e = x[1], f = x[2];for (int i = 3; i < x.length; i++) {a = b;b = c;c = d;d = e;e = f;f = x[i];if (e < c - a && f >= d)return true;if (c - a <= e && e <= c && f >= (d - b < 0 ? d : d - b))return true;}return false;}
}

输出：

true
false
true

2. 环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

出处：

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

代码：

import java.util.*;
public class hasCycle {public static class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}public static class Solution {public boolean hasCycle(ListNode head) {if (head == null || head.next == null)return false;ListNode fast = head.next;ListNode slow = head;while (fast != slow) {if (fast.next == null || fast.next.next == null)return false;fast = fast.next.next;slow = slow.next;}return true;}}public static ListNode createRingNodeList(int[] nums, int pos) {if (nums == null || nums.length == 0) {return null;}ListNode head = new ListNode(nums[0]);ListNode tail = head;for (int i = 1; i < nums.length; i++) {tail.next = new ListNode(nums[i]);tail = tail.next;}if (pos >= 0) {ListNode p = head;while (pos > 0) {p = p.next;pos--;}tail.next = p;}return head;}public static void main(String[] args) {Solution s = new Solution();int[] nums = {3,2,0,-4};ListNode head = createRingNodeList(nums, 1);System.out.println(s.hasCycle(head));int[] nums2 = {1,2};head = createRingNodeList(nums2, 0);System.out.println(s.hasCycle(head));int[] nums3 = {1};head = createRingNodeList(nums3, -1);System.out.println(s.hasCycle(head));}
}

输出：

true
true
false

3. 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例 1：

输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

输入：board = [["X"]]
输出：[["X"]]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 'X' 或 'O'

出处：

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

代码：

import java.util.*;
import java.util.LinkedList;
public class solve {public static class Solution {int[] dx = { 1, -1, 0, 0 };int[] dy = { 0, 0, 1, -1 };public void solve(char[][] board) {int n = board.length;if (n == 0) {return;}int m = board[0].length;Queue<int[]> queue = new LinkedList<int[]>();for (int i = 0; i < n; i++) {if (board[i][0] == 'O') {queue.offer(new int[] { i, 0 });}if (board[i][m - 1] == 'O') {queue.offer(new int[] { i, m - 1 });}}for (int i = 1; i < m - 1; i++) {if (board[0][i] == 'O') {queue.offer(new int[] { 0, i });}if (board[n - 1][i] == 'O') {queue.offer(new int[] { n - 1, i });}}while (!queue.isEmpty()) {int[] cell = queue.poll();int x = cell[0], y = cell[1];board[x][y] = 'A';for (int i = 0; i < 4; i++) {int mx = x + dx[i], my = y + dy[i];if (mx < 0 || my < 0 || mx >= n || my >= m || board[mx][my] != 'O') {continue;}queue.offer(new int[] { mx, my });}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (board[i][j] == 'A') {board[i][j] = 'O';} else if (board[i][j] == 'O') {board[i][j] = 'X';}}}}}public static void main(String[] args) {Solution s = new Solution();char[][] board = {{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}};s.solve(board);System.out.println(Arrays.deepToString(board));}
}

输出：

[[X, X, X, X], [X, X, X, X], [X, X, X, X], [X, O, X, X]]