byu_rself

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

LC.P2578[最小和分割] 方法一：排序+贪心1234567891011class Solution { public int splitNum(int num) { char[] s = Integer.toString(num).toCharArray(); Arrays.sort(s); int[] ans = new int[2]; for (int i = 0; i < s.length; ++i) { ans[i & 1] = ans[i & 1] * 10 + (s[i] - '0'); } return ans[0] + ans[1]; }} 时间复杂度：$O(nlogn)$ 空间复杂度：$O(n)$ 方法二：计数+贪心123456789101112131415161718class Solution { public int ...

LC.P901[股票价格跨度] 方法一：暴力123456789101112131415161718192021222324class StockSpanner { List<Integer> list; public StockSpanner() { list = new ArrayList<>(); } public int next(int price) { list.add(price); int ans = 0; for (int i = list.size() - 1; i >= 0; --i) { if (list.get(i) <= price) ++ans; else break; } return ans; }}/** * Your StockSpanner object will be i ...