byu_rself

LC.P1488[避免洪水泛滥] 方法一：贪心+哈希表+有序集合12345678910111213141516171819202122232425class Solution { public int[] avoidFlood(int[] rains) { int n = rains.length; int[] ans = new int[n]; Arrays.fill(ans, -1); TreeSet<Integer> sunny = new TreeSet<>(); Map<Integer, Integer> rainy = new HashMap<>(); for (int i = 0; i < n; ++i) { int k = rains[i]; if (k > 0) { if (rainy.containsKey ...

LC.P1201[丑数III] 方法一：容斥原理+二分12345678910111213141516171819202122class Solution { public int nthUglyNumber(int n, int a, int b, int c) { long ab = lcm(a, b), ac = lcm(a, c), bc = lcm(b, c), abc = lcm(a, lcm(b, c)); long left = 0, right = (long) Math.min(a, Math.min(b, c)) * n; while (left < right) { long mid = left + right >> 1; if (mid / a + mid / b + mid / c - mid / ab - mid / ac - mid / bc + mid / abc >= n) right = mid; ...

LC.P878[第N个神奇数字] 方法一：容斥原理+二分123456789101112131415161718192021class Solution { private static final int MOD = (int) 1e9 + 7; public int nthMagicalNumber(int n, int a, int b) { // 最大公倍数 int c = a * b / gcd(a, b); long left = 0, right = (long) Math.min(a, b) * n; while (left < right) { long mid = left + right >> 1; // 容斥原理 if (mid / a + mid / b - mid / c >= n) right = mid; else left = mid + 1; ...

LC.P2562[找出数组的串联值] 方法一：模拟1234567891011class Solution { public long findTheArrayConcVal(int[] nums) { long ans = 0; int n = nums.length; for (int i = 0, j = n - 1; i < j; ++i, --j) { ans += Integer.parseInt(nums[i] + "" + nums[j]); } if (n % 2 == 1) ans += nums[n / 2]; return ans; }} 时间复杂度：$O(nlogM)$，其中$M$为数组中元素的最大值 空间复杂度：$O(logM)$，遍历数组时需要将数组中每个元素转换为字符串

LC.P162[寻找峰值] 方法一：二分1234567891011class Solution { public int findPeakElement(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = left + right >>> 1; if (nums[mid] > nums[mid + 1]) right = mid; else left = mid + 1; } return right; }} 时间复杂度：$O(logn)$ 空间复杂度：$O(1)$

LC.P2512[奖励最顶尖的K名学生] 方法一：哈希表+排序12345678910111213141516171819202122class Solution { public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) { Set<String> positiveSet = new HashSet<>(List.of(positive_feedback)); Set<String> negativeSet = new HashSet<>(List.of(negative_feedback)); int n = report.length; int[][] arr = new int[n][2]; for (int i = 0; ...

LC.P911[在线选举] 方法一：哈希表+二分查找1234567891011121314151617181920212223242526272829303132class TopVotedCandidate { List<int[]> list = new ArrayList<>(); public TopVotedCandidate(int[] persons, int[] times) { Map<Integer, Integer> map = new HashMap<>(); int max = 0; for (int i = 0; i < persons.length; ++i) { map.merge(persons[i], 1, Integer::sum); if (map.get(persons[i]) >= max) { max = map.g ...

LC.P81[搜索旋转排序数组II] 方法一：两次二分1234567891011121314151617181920212223242526272829class Solution { public boolean search(int[] nums, int target) { int n = nums.length; if (n == 1) return nums[0] == target; int left = 0, right = n - 1; // 忽略与 nums[0] 相同的元素，恢复二段性 while (left < right && nums[0] == nums[right]) --right; int idx = right; // 从中间开始找，找到满足 >= nums[0] 的分割点（旋转点） while (left < right) { int mid = ...

LC.P33[搜索旋转排序数组] 方法一：两次二分1234567891011121314151617181920212223242526class Solution { public int search(int[] nums, int target) { int n = nums.length; if (n == 1) return nums[0] == target ? 0 : -1; int left = 0, right = n - 1; // 从中间开始找，找到满足 >= nums[0] 的分割点（旋转点） while (left < right) { int mid = left + right + 1 >> 1; if (nums[mid] >= nums[0]) left = mid; else right = mid - 1; } ...

LC.P2731[移动机器人] 方法一：脑筋急转弯+排序123456789101112131415161718class Solution { private static final int MOD = (int) 1e9 + 7; public int sumDistance(int[] nums, String s, int d) { int n = nums.length; long[] arr = new long[n]; for (int i = 0; i < n; ++i) { arr[i] = (long) nums[i] + (s.charAt(i) == 'L' ? -d : d); } Arrays.sort(arr); long ans = 0, sum = 0; for (int i = 0; i < n; ++i) { ans ...