每日三题-最大矩形、比特位计数、回文子串

简介: 每日三题-最大矩形、比特位计数、回文子串

最大矩形


8cd082d59e954d87a7dd0704d7f68263.png

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;
    }
}


比特位计数



586d1163a191427285520cba8d08dbe2.png

解法一

奇偶

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;
    }
}


回文子串


6a27c09afaee490aae265f877c9c5bbf.png

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;
    }
}
相关文章
|
7月前
|
BI 测试技术 Windows
【数位】【数论】【分类讨论】2999. 统计强大整数的数目
【数位】【数论】【分类讨论】2999. 统计强大整数的数目
|
7月前
|
算法 测试技术 C++
【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目
【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目
|
算法 测试技术 C++
C++二分算法习题:判断是否是完全平方数[容易]和排列箱子[容易]
C++二分算法习题:判断是否是完全平方数[容易]和排列箱子[容易]
|
2月前
|
人工智能 Java BI
lanqiao OJ 111 区间位移
lanqiao OJ 111 区间位移
15 0
|
7月前
|
算法 测试技术 C#
【二进制求公约数】【数学】【数论】2543. 判断一个点是否可以到达
【二进制求公约数】【数学】【数论】2543. 判断一个点是否可以到达
|
7月前
|
人工智能 算法
前缀和算法题(区间次方和、小蓝平衡和、大石头的搬运工、最大数组和)
前缀和算法题(区间次方和、小蓝平衡和、大石头的搬运工、最大数组和)
|
7月前
每日一题(最大连续1的个数,完全数计算)
每日一题(最大连续1的个数,完全数计算)
37 0
|
7月前
|
Python C++ Java
C/C++每日一练(20230415) 交错字符串、最短回文串、分段函数
C/C++每日一练(20230415) 交错字符串、最短回文串、分段函数
56 0
C/C++每日一练(20230415) 交错字符串、最短回文串、分段函数
|
7月前
|
算法 测试技术 C#
【差分数组】【图论】【分类讨论】【整除以2】100213按距离统计房屋对数目
【差分数组】【图论】【分类讨论】【整除以2】100213按距离统计房屋对数目
【差分数组】【图论】【分类讨论】【整除以2】100213按距离统计房屋对数目
|
7月前
leetcode-338:比特位计数
leetcode-338:比特位计数
39 0