byu_rself

LC.P565[数组嵌套] 方法一：模拟12345678910111213141516class Solution { public int arrayNesting(int[] nums) { int ans = 0; for (int i = 0; i < nums.length; ++i) { int cur = i, cnt = 0; while (nums[cur] != -1) { ++cnt; int t = cur; cur = nums[cur]; nums[t] = -1; } ans = Math.max(ans, cnt); } return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O( ...

LC.P451[根据字符出现频率排序] 方法一：哈希表+模拟12345678910111213141516class Solution { public String frequencySort(String s) { Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < s.length(); ++i) { char c = s.charAt(i); map.merge(c, 1, Integer::sum); } List<Character> list = new ArrayList<>(map.keySet()); list.sort((a, b) -> map.get(b) - map.get(a)); StringBuilder builder = new Stri ...

LC.P2544[交替数字和] 方法一：模拟1234567891011class Solution { public int alternateDigitSum(int n) { int ans = 0, sign = 1; for (char c : String.valueOf(n).toCharArray()) { int x = c - '0'; ans += sign * x; sign *= -1; } return ans; }} 时间复杂度：$O(logn)$ 空间复杂度：$O(logn)$

LC.P423[从英文中重建数字] 方法一：模拟+脑经急转弯123456789101112131415161718192021class Solution { static String[] nums = new String[]{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}; static int[] priority = new int[]{0, 8, 6, 3, 2, 7, 5, 9, 4, 1}; public String originalDigits(String s) { int n = s.length(); int[] cnts = new int[26] ...

LC.P419[甲板上的战舰] 方法一：遍历123456789101112131415161718192021class Solution { public int countBattleships(char[][] board) { int m = board.length, n = board[0].length; int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (board[i][j] == 'X') { board[i][j] = '.'; for (int k = j + 1; k < n && board[i][k] == 'X'; ++k) { ...

LC.P1911[最大子序列交替和] 方法一：动态规划123456789101112131415161718class Solution { public long maxAlternatingSum(int[] nums) { int n = nums.length; // dp[i][0]表示以最后一个元素下标为偶数的子序列和 // dp[i][1]表示以最后一个元素下标为奇数的子序列和 long[][] dp = new long[n][2]; dp[0][0] = nums[0]; dp[0][1] = 0; for (int i = 1; i < n; ++i) { for (int j = 0; j < 2; ++j) { dp[i][0] = Math.max(dp[i - 1][1] + nums[i], dp[i - 1][0]); ...

LC.P420[强密码检验器] 方法一：模拟12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849class Solution { public int strongPasswordChecker(String password) { char[] cs = password.toCharArray(); int n = cs.length; int A = 0, B = 0, C = 0; for (char c : cs) { if (c >= 'a' && c <= 'z') A = 1; else if (c >= 'A' && c <= 'Z') B = 1; el ...

LC.P16[最接近的三数之和] 方法一：排序+双指针1234567891011121314151617class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int n = nums.length, ans = nums[0] + nums[1] + nums[2]; for (int i = 0; i < n - 2; ++i) { int j = i + 1, k = n - 1; while (j < k) { int sum = nums[i] + nums[j] + nums[k]; if (sum == target) return sum; if (Math.abs(sum - target) < Math.abs ...

LC.P15[三数之和] 方法一：排序+双指针1234567891011121314151617181920212223242526class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); for (int i = 0; i < n - 2; ++i) { if (nums[i] > 0) break; if (i > 0 && nums[i] == nums[i - 1]) continue; int j = i + 1, k = n - 1; while (j < ...

LC.P1244[最大相等频率] 方法一：模拟123456789101112131415161718class Solution { int[] cnt = new int[100010], sum = new int[100010]; public int maxEqualFreq(int[] nums) { int n = nums.length, max = 0, ans = 0; for (int i = 0; i < n; ++i) { int x = nums[i], cur = ++cnt[x], len = i + 1; sum[cur]++; sum[cur - 1]--; max = Math.max(max, cur); if (max == 1) ans = len; if (max * sum[max] + 1 == len) ans = len; ...