byu_rself

LC.P1503[所有蚂蚁掉下来前的最后一刻] 方法一：模拟12345678class Solution { public int getLastMoment(int n, int[] left, int[] right) { int ans = 0; for (int x : left) ans = Math.max(ans, x); for (int x : right) ans = Math.max(ans, n - x); return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

LC.P143[重排链表] 方法一：线性表+双指针1234567891011121314151617181920212223242526272829/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public void reorderList(ListNode head) { List<ListNode> list = new ArrayList<>(); ...

LC.P142[环形链表II] 方法一：哈希表12345678910111213141516171819202122/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode detectCycle(ListNode head) { Set<ListNode> set = new HashSet<>(); ListNode p = head; while (p != null) { if (!set.add(p)) return p; p ...

LC.P1894[找到需要补充粉笔的学生编号] 方法一：模拟12345678910111213class Solution { public int chalkReplacer(int[] chalk, int k) { int n = chalk.length; long sum = 0; for (int c : chalk) sum += c; k = (int) (k % sum); for (int i = 0; i < n; ++i) { k -= chalk[i]; if (k < 0) return i; } return -1; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

LC.P141[环形链表] 方法一：快慢指针12345678910111213141516171819202122/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public boolean hasCycle(ListNode head) { ListNode fast = head, slow = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; ...

LC.P335[路径交叉] 方法一：找规律1234567891011121314class Solution { public boolean isSelfCrossing(int[] distance) { int n = distance.length; if (n < 4) return false; for (int i = 3; i < n; ++i) { if (distance[i] >= distance[i - 2] && distance[i - 1] <= distance[i - 3]) return true; if (i >= 4 && distance[i - 1] == distance[i - 3] && distance[i] + distance[i - 4] >= distance[i - 2]) return t ...

LC.P1494[并行课程II] 方法一：记忆化搜索+状态压缩123456789101112131415161718192021222324252627282930313233343536373839404142class Solution { int[] pre1, cache; int k, u; public int minNumberOfSemesters(int n, int[][] relations, int k) { this.k = k; pre1 = new int[n]; for (int[] e : relations) { // 先修课程集合 pre1[e[1] - 1] |= 1 << (e[0] - 1); } u = (1 << n) - 1; // 全集 cache = new int[1 << n]; Arra ...

LC.P2050[并行课程III] 方法一：拓扑排序+动态规划1234567891011121314151617181920212223242526272829303132333435class Solution { public int minimumTime(int n, int[][] relations, int[] time) { List<Integer>[] g = new List[n]; Arrays.setAll(g, k -> new ArrayList<>()); int[] in = new int[n]; for (int[] e : relations) { int a = e[0] - 1, b = e[1] - 1; g[a].add(b); ++in[b]; } Deque<Integer> queue = new ...

LC.P749[隔离病毒] 方法一：BFS12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273class Solution { int[][] isInfected; int m, n, ans; static int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; boolean[][] visited; public int containVirus(int[][] isInfected) { this.isInfected = isInfected; m = isInfected.length; n = i ...

LC.P2500[删除每行中的最大值] 方法一：排序12345678910111213141516class Solution { public int deleteGreatestValue(int[][] grid) { for (int[] g : grid) { Arrays.sort(g); } int ans = 0, m = grid.length, n = grid[0].length; for (int j = 0; j < n; ++j) { int max = -1; for (int i = 0; i < m; ++i) { if (grid[i][j] > max) max = grid[i][j]; } ans += max; } re ...