byu_rself

Offer.P44[数字序列中某一位的数字] 方法一：模拟1234567891011121314class Solution { public int findNthDigit(int n) { int digit = 1; long start = 1, count = 9; while (n > count) { n -= count; digit += 1; // 位数：1,10,100... start *= 10; // 起始数字：1,2,3... count = digit * start * 9; // 数位数量:9,180,2700... } long num = start + (n - 1) / digit; // 确定数字 return Long.toString(num).charAt((n - 1) % digit) - '0&# ...

LC.P722[删除注释] 方法一：模拟1234567891011121314151617181920212223242526272829303132333435class Solution { public List<String> removeComments(String[] source) { List<String> ans = new ArrayList<>(); StringBuilder builder = new StringBuilder(); boolean blockComment = false; for (String s : source) { int n = s.length(); for (int i = 0; i < n; ++i) { if (blockComment) { if (i ...

LCR.P11[0和1个数相同的子数组] 方法一：前缀和+哈希表1234567891011121314151617class Solution { public int findMaxLength(int[] nums) { int ans = 0, sum = 0; Map<Integer, Integer> map = new HashMap<>(); map.put(0, -1); for (int i = 0; i < nums.length; ++i) { sum += nums[i] == 1 ? 1 : -1; if (map.containsKey(sum)) { int preIndex = map.get(sum); ans = Math.max(ans, i - preIndex); } else & ...

LCR.P10[和为k的子数组] 方法一：暴力枚举12345678910111213class Solution { public int subarraySum(int[] nums, int k) { int ans = 0, n = nums.length; for (int left = 0; left < n; ++left) { int sum = 0; for (int right = left; right >= 0; --right) { sum += nums[right]; if (sum == k) ++ans; } } return ans; }} 时间复杂度：$O(n^2)$ 空间复杂度：$O(1)$ 方法二：前缀和+哈希表1234567891011121314class ...

LCR.P9[乘积小于K的子数组] 方法一：滑动窗口123456789101112class Solution { public int numSubarrayProductLessThanK(int[] nums, int k) { if (k <= 1) return 0; int n = nums.length, prod = 1, ans = 0; for (int left = 0, right = 0; right < n; ++right) { prod *= nums[right]; while (prod >= k) prod /= nums[left++]; ans += right - left + 1; } return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

LCR.P7[数组中和为0的三个数] 方法一：排序+双指针1234567891011121314151617181920212223242526272829303132class Solution { public List<List<Integer>> threeSum(int[] nums) { int n = nums.length; Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<>(); for (int i = 0; i < n - 2; ++i) { if (nums[i] > 0) break; if (i > 0 && nums[i] == nums[i - 1]) continue; int sum = nums[i] + nums[i + 1] + ...

LC.P822[翻转卡片游戏] 方法一：哈希表12345678910111213141516class Solution { public int flipgame(int[] fronts, int[] backs) { Set<Integer> set = new HashSet<>(); int n = fronts.length, ans = Integer.MAX_VALUE; for (int i = 0; i < n; ++i) { if (fronts[i] == backs[i]) set.add(fronts[i]); } for (int x : fronts) { if (!set.contains(x)) ans = Math.min(ans, x); } for (int x : backs) { ...

LC.P769[最多能完成排序的块] 方法一：贪心12345678910class Solution { public int maxChunksToSorted(int[] arr) { int ans = 0, max = -1; for (int i = 0; i < arr.length; ++i) { max = Math.max(max, arr[i]); if (max == i) ++ans; } return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

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