20.有效括号对
/* * 有效括号对 * 思路：即将入栈的是前括号则直接入栈，若是后括号则比较栈顶元素，匹配则出栈 */ public boolean isValid(String s) { if(s==null||s.length()%2!=0) return false;//如果允许空，则不能这么判断 else if(s.trim().equals("")) return true; Stack<Character> stack =new Stack<>(); char ch; for(int i=0;i<s.length();i++) { ch =s.charAt(i); if(ch=='('||ch=='['||ch=='{') stack.add(ch); else if(!stack.isEmpty()&&((ch==')'&& stack.peek()=='(')||(ch==']'&&stack.peek()=='[')|| (ch=='}'&&stack.peek()=='{'))) { stack.pop(); } else return false; } return stack.isEmpty(); }
48.旋转图像
/* * 顺时针90度旋转矩阵，来源：LeetCode * 即先转置，然后列翻转（逆时针旋转为先转置，再行翻转） */ public void clockwiseMatrix(int[][] matrix) { transpose(matrix); reverseColumn(matrix); } /* * 按主对角线转置矩阵 */ public void transpose(int[][] matrix) { int n =matrix.length; for(int i=0;i<n;i++) { for(int j=i;j<n;j++)//j不能从0开始，会出现重复翻转而复原了 { int temp =matrix[i][j]; matrix[i][j] =matrix[j][i]; matrix[j][i] =temp; } } } /* * 列翻转 */ public void reverseColumn(int[][] matrix) { int column =matrix.length; for(int i=0;i<column/2;i++) { for(int j=0;j<column;j++) { int temp =matrix[j][i]; matrix[j][i] =matrix[j][column-i-1]; matrix[j][column-i-1] =temp; } } } /* * 行翻转 */ public void reverseRow(int[][] matrix) { int n =matrix.length; for(int i=0;i<=n/2;i++) { for(int j=0;j<n;j++) { int temp =matrix[i][j]; matrix[i][j] =matrix[n-i-1][j]; matrix[n-i-1][j] =temp; } } }
120.三角形最小路径和
/* * 三角形最小路径和 * 来源：LeetCode * 思路：自底向上的动态规划。类似于跳台阶，每次考虑的是从第n-1步到第n步的走法，假设f(n-1)为走到 * n步的最小数，则走到n步为f(n-1)+min(n)，这是自底向上的思路。而动态规划则体现在，f(n-1)与第 * n步是有约束的，只能走下一层的相邻的路径，那么此时必须f(n-1)必须是一个集合，最终结果应该是 * min(f(n-1)+min(n))，使用O(n)的复杂度则必须是多次更新一个集合的值，应当联想到存储的是min(k,n) * 的值，即k步到最后一步的最小路径和，那么需要动态计算f(k-1)，即第1步到k-1步的路径和 */ public int minTriangleSum(List<List<Integer>> triangle) { if(triangle==null||triangle.size()==0) return 0; int length =triangle.size(); int[] dp =new int[length]; for(int i=0;i<length;i++) dp[i] =triangle.get(length-1).get(i); for(int k=length-2;k>=0;k--) for(int j=0;j<=k;j++) { dp[j] =triangle.get(k).get(j) + Math.min(dp[j], dp[j+1]); } return dp[0]; }
221.最大正方形
/* * 最大正方形 * 思路：动态规划，用一个相同大小的矩阵记录以每个点为右下角的最大矩阵，若matrix[i][j]==1，则 * result[i][j]取左上相邻的三个点的最小值+1，即(i-1,j-1)，(i-1,j)，(i,j-1)的最小值+1， * 则对于m*n的矩阵，复杂度是O(m*n)，行优先遍历 */ public int maxSquare(int[][] matrix) { if(matrix==null||matrix.length==0) return 0; int m =matrix.length-1; int n =matrix[0].length-1; int[][] result =new int[m+1][n+1]; int res =0; //初始化 for(int i=0;i<=m;i++) { result[i][0] =matrix[i][0]; res =Math.max(matrix[i][0], res); } for(int j=0;j<=n;j++) { result[0][j] =matrix[0][j]; res =Math.max(matrix[0][j], res); } for(int k=1;k<=m;k++) for(int l=1;l<=n;l++) { if(matrix[k][l]==1) result[k][l] =Math.min(result[k-1][l-1], Math.min(result[k-1][l], result[k][l-1]))+1; res =Math.max(result[k][l], res); } for(int i=0;i<=m;i++) for(int j=0;j<=n;j++) { System.out.print(result[i][j]+" "); if(j==n) System.out.println(); } return res*res; } /* * 最大正方形 * 思路：使用同等大小的矩阵，dp[i][j]作为矩阵的右下角，其值根据左上相邻的3个值确定，与maxSquare() * 思路完全一样，也是行优先遍历，只是对i=0和j=0的初始化方法不一样而已，代码更简洁 */ public int maximalSquare(char[][] matrix) { if (matrix==null || matrix.length==0) return 0; int m = matrix.length-1, n = matrix[0].length-1, res = 0; int[][] dp =new int[m+1][n+1]; for (int i = 0; i <= m; ++i) { for (int j = 0; j <= n; ++j) { if (i == 0 || j == 0) dp[i][j] = matrix[i][j] - '0'; else if (matrix[i][j] == '1') { dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1; } res = Math.max(res, dp[i][j]); } } return res * res; } /* * 最大正方形 * 思路：只用了一个长度比原矩阵行长1的数组，空间复杂度更小，本质上上和同等大小矩阵的思路是一样的，只不过 * 使用了动态更新，巧妙地利用了已有的值而已，按列计算，保留了一个更新前的值pre作为dp[j-1[i-1]， * 使用dp[j-1]和dp[j]分别表示本次计算的上和左的相邻点 */ public int maxSquare1(char[][] matrix) { if(matrix==null||matrix[0].length==0) return 0; int m =matrix.length-1; int n =matrix[0].length-1; int[] dp =new int[m+2]; int pre=0; int res=0; for(int i=0;i<=n;i++) for(int j=1;j<=m+1;j++) { int temp =dp[j]; if(matrix[j-1][i]=='1') { /* 此次修改时，dp[j-1]相当于同大矩阵法的dp[j-1][i]，即同列上一行的数 * dp[j]相当于dp[j][i-1]，即同行上一列的数 */ dp[j] =Math.min(Math.min(dp[j], dp[j-1]), pre)+1; res =Math.max(res, dp[j]); } else dp[j] =0; pre =temp;//pre保存了修改之前的dp[j]的值，其实相当于同等矩阵中的dp[j-1][i-1] } return res*res; }
重要的不是源码，而是思路。源码网上一大把，有的精简而且高效无比，但是却看不懂，这样的毫无意义。算法的学习，核心方法应该就是见多识广，触类旁通吧，找到算法问题的本质的数学问题，多写多练方能融会贯通。
