byu_rself

LC.P481[神奇字符串] 方法一：模拟12345678910111213141516class Solution { public int magicalString(int n) { char[] s = new char[n + 2]; s[0] = 1; s[1] = s[2] = 2; char c = 2; for (int i = 2, j = 3; j < n; ++i) { c ^= 3; // 1^3=2, 2^3=1 s[j++] = c; if (s[i] == 2) s[j++] = c; } int ans = 0; for (int i = 0; i < n; ++i) ans += 2 - s[i]; return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O(n ...

LC.P382[链表随机节点] 方法一：模拟12345678910111213141516171819202122232425262728293031323334/** * 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 { List<Integer> list; Random random; public Solution(ListNode head) { list = new A ...

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 ...