最大矩形
class Solution { public int maximalRectangle(char[][] mat) { int n = mat.length, m = mat[0].length, ans = 0; int[][] sum = new int[n + 10][m + 10]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { sum[i][j] = mat[i - 1][j - 1] == '0' ? 0 : sum[i - 1][j] + 1; } } int[] l = new int[m + 10], r = new int[m + 10]; for (int i = 1; i <= n; i++) { int[] cur = sum[i]; Arrays.fill(l, 0); Arrays.fill(r, m + 1); Deque<Integer> d = new ArrayDeque<>(); for (int j = 1; j <= m; j++) { while (!d.isEmpty() && cur[d.peekLast()] > cur[j]) r[d.pollLast()] = j; d.addLast(j); } d.clear(); for (int j = m; j >= 1; j--) { while (!d.isEmpty() && cur[d.peekLast()] > cur[j]) l[d.pollLast()] = j; d.addLast(j); } for (int j = 1; j <= m; j++) ans = Math.max(ans, cur[j] * (r[j] - l[j] - 1)); } return ans; } }
比特位计数
解法一
奇偶
class Solution { public int[] countBits(int n) { int dp[] = new int[n+1]; for(int i = 1;i <=n;i++){ if(i% 2 == 0){ dp[i] = dp[i/2]; }else{ dp[i] = dp[i-1]+1; } } return dp; } }
回文子串
class Solution { public int countSubstrings(String s) { int n = s.length(); boolean dp[][] = new boolean[n][n]; int res = 0; for(int i = 0;i<n;i++){ for(int j = 0;j <=i;j++){ if(s.charAt(i) == s.charAt(j) && (i-j < 2 || dp[j+1][i-1])){ dp[j][i] = true; res++; } } } return res; } }