vampire`blogs

leetcode-1512. 好数对的数目 1234567891011121314class Solution { public int numIdenticalPairs(int[] nums) { int n = nums.length; int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[i] == nums[j]) { count++; } } } return count; }}

leetcode-1480. 一维数组的动态和 1234567891011class Solution { public int[] runningSum(int[] nums) { int n = nums.length; int[] dp = new int[n]; dp[0] = nums[0]; for (int i = 1; i < n; i++) { dp[i] = dp[i - 1] + nums[i]; } return dp; }}

leetcode-516. 最长回文子序列 题解思路 12345678910111213141516171819202122class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; // 初始化dp for (int i = 0; i < n; i++) { dp[i][i] = 1; } for (int i = n - 2; i >= 0; i--) { for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i + ...

leetcode-983. 最低票价 题解思路 1234567891011121314151617181920class Solution { public int mincostTickets(int[] days, int[] costs) { int n = days.length; int last = days[n - 1]; int[] dp = new int[last + 1]; int idx = 0; for (int i = 1; i <= last; i++) { if (i == days[idx]) { int d1 = i - 1; int d2 = i - 7 < 0 ? 0 : i - 7; int d3 = i - 30 < 0 ? 0 : i - 30; dp[i] = Ma ...

leetcode-1277. 统计全为 1 的正方形子矩阵 原始思路 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667class Solution { public int countSquares(int[][] matrix) { int n1 = matrix.length; int n2 = matrix[0].length; int[][] dp = new int[n1][n2]; // 初始化dp dp[0][0] = matrix[0][0]; for (int i = 1; i < n1; i++) { dp[i][0] = dp[i-1][0] + matrix[i][0]; } f ...

leetcode-1002. 查找常用字符 题解思路 12345678910111213141516171819202122232425262728class Solution { public List<String> commonChars(String[] A) { List<String> result = new ArrayList<>(); int n = A.length; int[] ans = new int[26]; Arrays.fill(ans, 1000000000); for (String str : A) { int[] tmp = new int[26]; for (int i = 0; i < str.length(); i++) { tmp[str.charAt(i) - 'a'] += 1; ...

leetcode-5. 最长回文子串 题解思路：中心扩散法 12345678910111213141516171819202122class Solution { public String longestPalindrome(String s) { String ans = ""; for(int i = 0; i < s.length(); i++){ String s1 = palindrome(s, i, i); String s2 = palindrome(s, i, i+1); ans = ans.length() > s1.length() ? ans : s1; ans = ans.length() > s2.length() ? ans : s2; } return ans; } // 中心扩散法 public S ...

leetcode-647. 回文子串 原始思路 1234567891011121314151617181920212223242526272829303132class Solution { public int countSubstrings(String s) { int n = s.length(); int[] dp = new int[n+1]; // 初始化 dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + 1; for (int j = i - 1; j > 0; j--) { String str = s.substring(j - 1, i); if (judge(str)) { dp[i] += 1; ...

leetcode-剑指 Offer 14- I. 剪绳子 12345678910111213class Solution { public int cuttingRope(int n) { int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 1; for (int i = 3; i <= n; i++) { for (int j = 1; j < i; j++) { dp[i] = Math.max(dp[i], j * Math.max(dp[i - j], i - j)); } } return dp[n]; }}

leetcode-1261. 在受污染的二叉树中查找元素 原始思路 1234567891011121314151617181920212223242526272829303132333435363738class FindElements { Set<Integer> set = new HashSet<>(); public FindElements(TreeNode root) { dfs(root, null, 0); } public void dfs(TreeNode root, Integer rootValue, int flag) { if (root == null) { return; } if (rootValue == null) { root.val = 0; }else { if (fl ...