vampire`blogs

leetcode-200. 岛屿数量 原始思路 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960class Solution { public int numIslands(char[][] grid) { int n1 = grid.length; if (n1 == 0) { return 0; } int n2 = grid[0].length; // 定义并查集的parent int[] parent = new int[n1*n2]; // 初始化并查集 for (int i = 0; i < n1*n2; i++) { parent[i] = i;  ...

leetcode-面试题 08.10. 颜色填充 原始思路 1234567891011121314151617181920212223242526272829303132333435363738class Solution { public int[][] floodFill(int[][] image, int sr, int sc, int newColor) { int n1 = image.length; int n2 = image[0].length; int[][] visit = new int[n1][n2]; int origin = image[sr][sc]; dfs(image, sr, sc, newColor, n1, n2, visit, origin); return image; } public void dfs(int[][] image, int sr, int sc, int newColor, int n1, ...

leetcode-1578. 避免重复字母的最小删除成本 原始思路 123456789101112131415161718192021class Solution { public int minCost(String s, int[] cost) { int result = 0; int n = s.length(); for (int i = 1; i < n; i++) { int j = i; while (j < n && s.charAt(j) == s.charAt(j - 1) ) { j++; } int total = 0; int max = 0; for (int k = i-1; k <= j-1; k++) { total + ...

leetcode-1403. 非递增顺序的最小子序列 123456789101112131415161718192021class Solution { public List<Integer> minSubsequence(int[] nums) { Arrays.sort(nums); int total = 0; for (int i = nums.length - 1; i >= 0; i--) { total += nums[i]; } int curTotal = 0; List<Integer> result = new ArrayList<>(); for (int i = nums.length - 1; i >= 0; i--) { result.add(nums[i]); curTotal += n ...

leetcode-1594. 矩阵的最大非负积 123456789101112131415161718192021222324252627282930313233class Solution { public int maxProductPath(int[][] grid) { int n1 = grid.length; int n2 = grid[0].length; long[][][] dp = new long[n1][n2][2]; dp[0][0][0] = grid[0][0]; dp[0][0][1] = grid[0][0]; //初始化dp,第三维0表示最小值,1表示最大值 for (int i = 1; i < n2; i++) { dp[0][i][0] = dp[0][i - 1][0] * grid[0][i]; dp[0][i][1] = dp[0][i - 1][0] * ...

leetcode-1593. 拆分字符串使唯一子字符串的数目最大 原始思路 12345678910111213141516171819202122232425class Solution { List<String> ans = new ArrayList<>(); Set<String> set = new HashSet<>(); int result = 0; public int maxUniqueSplit(String s) { dfs(0, s); return result; } public void dfs(int cur, String s) { result = Math.max(result, ans.size()); for (int i = cur; i < s.length(); i++) { String str = s.substri ...

leetcode-1592. 重新排列单词间的空格 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061class Solution { public String reorderSpaces(String text) { // 记录单词和空格 List<String> list = new ArrayList<>(); int num = 0; StringBuffer buffer = new StringBuffer(); for (int i = 0; i < text.length(); i++) { if (text.charAt(i) == ' ') { num++; ...

leetcode-47. 全排列 II 原始思路 1234567891011121314151617181920212223242526272829303132333435class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> ans = new ArrayList<>(); Set<Integer> set = new HashSet<>(); Set<List<Integer>> setAns = new HashSet<>(); public List<List<Integer>> permuteUnique(int[] nums) { dfs(0, nums); return result; } public void dfs(int ...

acwing-9. 分组背包问题 12345678910111213141516171819202122232425262728293031323334import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int V = sc.nextInt(); int[][] weight = new int[103][103]; int[][] value = new int[103][103]; for(int i = 1; i<= N; i++){ int k = sc.nextInt(); for(int j = 1; j <= k; j++){ weight[i][j] = ...

acwing-4. 多重背包问题 I 1234567891011121314151617181920212223242526272829303132import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int V = sc.nextInt(); int[] w = new int[N + 1]; int[] value = new int[N + 1]; int[] nums = new int[N+1]; for(int i = 1; i<= N; i++){ w[i] = sc.nextInt(); value[i] = sc.nextInt(); nums[i] = sc.n ...