byu_rself

LC.P931[下降路径最小和] 方法一：DFS(超时)12345678910111213141516171819class Solution { int[][] matrix; public int minFallingPathSum(int[][] matrix) { int n = matrix.length, ans = Integer.MAX_VALUE; this.matrix = matrix; for (int col = 0; col < n; ++col) { ans = Math.min(ans, dfs(n - 1, col)); } return ans; } private int dfs(int row, int col) { if (col < 0 || col >= matrix.length) return Integer.MAX_VAL ...

Offer.P34[二叉树中和为某一值的路径] 方法一：DFS1234567891011121314151617181920212223242526272829303132333435363738/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution
...

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