Leetcode - 130双周赛

目录

一,3142. 判断矩阵是否满足条件

二,3143. 正方形中的最多点数

三,3144. 分割字符频率相等的最少子字符串

四,3145. 大数组元素的乘积


一,3142. 判断矩阵是否满足条件

本题题意,满足每一列的数全部相等,列与列的数不相等,就返回true,否则返回false,直接模拟就行。

代码如下:

class Solution {
    public boolean satisfiesConditions(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(i+1<n && grid[i][j] != grid[i+1][j]
                || j+1<m && grid[i][j] == grid[i][j+1]){
                    return false;
                }
            }
        }
        return true;
    }
}

二,3143. 正方形中的最多点数

方法一:二分边长

这道题具有单调性——正方形的边长越长,就越可能出现不合法的点,所以可以使用二分,但是有一个注意点,二分的是边长,而答案要的是正方形包含的点数,所以需要在check方法中不断更新答案。

class Solution {
    int ans;
    public int maxPointsInsideSquare(int[][] points, String s) {
        int n = s.length();
        int l = 0, r = (int)1e9;
        while(l <= r){
            int mid = (l + r) >>> 1;
            if(check(mid, points, s)){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return ans;
    }
    boolean check(int k, int[][] points, String s){
        Set<Character> set = new HashSet<>();
        for(int i=0; i<s.length(); i++){
            int t = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));
            if(k >= t){
                if(set.contains(s.charAt(i))) 
                    return false;
                set.add(s.charAt(i));
            }
        }
        ans = set.size();
        return true;
    }
}

方法二:数学集合

可以先将点按照正方形的边长(正方形的边上)分组,再从小到大枚举正方形的边长,如果出现两个相同的标签,直接退出循环,否则将点数加入答案

class Solution {
    public int maxPointsInsideSquare(int[][] points, String s) {
        int n = s.length();
        TreeMap<Integer, Integer> map = new TreeMap<>();//<边长,标签(使用数字表示集合)>
        for(int i=0; i<n; i++){
            int[] x = points[i];
            int mx = Math.max(Math.abs(x[0]), Math.abs(x[1]));
            if(!map.containsKey(mx)){
                map.put(mx, 0);
            }
            int t = s.charAt(i) - 'a';//(1<<t)表示字符s.charAt(i)
            if((map.get(mx)&(1<<t)) != 0){//正方形边长上存在相同的标签,存入1<<26表示非法
                map.put(mx, map.get(mx)|(1<<26));
            }else{//否则,存入(1<<t)
                map.put(mx, map.get(mx)|(1<<t));
            }
        }
        int ans = 1<<26;//为了检测是否非法
        for(int x : map.values()){
            if((ans & x) != 0){//正方形内部存在相同的标签
                break;
            }
            ans |= x;
        }
        return Integer.bitCount(ans)-1;//-1表示减去1<<26
    }
}

三,3144. 分割字符频率相等的最少子字符串

划分dp:最少/最多能划分几段

一,dfs + 记忆化

dfs(i):表示 [0,i] 最少可以分成的段数

它只有一个转移来源:

  • 从 i 开始往前枚举 j,如果 [ j,i ] 是一个平衡字符串,那么 dfs(i) = Math.max(dfs(i),dfs(j)+1)

结束条件:i < 0 ,return 0

代码如下:

class Solution {
    int[] memo;
    public int minimumSubstringsInPartition(String s) {
        memo = new int[s.length()];
        Arrays.fill(memo, -1);
        return dfs(s.length()-1, s);
    }
    int dfs(int i, String s){
        if(i == -1) return 0;
        if(memo[i] != -1) return memo[i];
        int res = s.length();
        int[] cnt = new int[26];
        for(int j=i; j>=0; j--){
            cnt[s.charAt(j)-'a']++;
            if(check(cnt)){
                res = Math.min(res, dfs(j-1, s) + 1);
            }
        }
        return memo[i] = res;
    }
    boolean check(int[] cnt){//判断是否是平衡字符串
        int t = -1;
        for(int x : cnt){
            if(x != 0){
                if(t == -1){
                    t = x;
                }else if(x != t){
                    return false;
                }
            }
        }
        return true;
    }
}

二,递推

f [ i ]:表示前 i 个数最少可以分成的段数

从 i 开始往前枚举 j,如果 [ j,i ] 是一个平衡字符串,f[ i+1 ] = Math.max(f[i+1],f[j] + 1)

代码如下:

class Solution {
    //f[j]:前j个数最少能分成f[j]段
    public int minimumSubstringsInPartition(String s) {
        int n = s.length();
        int[] f = new int[n+1];
        Arrays.fill(f, Integer.MAX_VALUE);
        f[0] = 0;
        for(int i=0; i<n; i++){
            int[] cnt = new int[26];
            for(int j=i; j>=0; j--){
                cnt[s.charAt(j)-'a']++;
                if(check(cnt))
                    f[i+1] = Math.min(f[i+1], f[j]+1);
            }
        }
        return f[n];
    }
    boolean check(int[] cnt){
        int t = -1;
        for(int x : cnt){
            if(x != 0){
                if(t == -1){
                    t = x;
                }else if(x != t){
                    return false;
                }
            }
        }
        return true;
    }
}

四,3145. 大数组元素的乘积

膜拜大佬的题解,代码如下:

class Solution {
    public int[] findProductsOfElements(long[][] queries) {
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            long[] q = queries[i];
            long er = sumE(q[1] + 1);
            long el = sumE(q[0]);
            ans[i] = pow(2, er - el, q[2]);
        }
        return ans;
    }

    private long sumE(long k) {//计算幂次之和
        long res = 0, n = 0, cnt1 = 0, sumI = 0;
        for (long i = 63 - Long.numberOfLeadingZeros(k + 1); i > 0; i--) {
            long c = (cnt1 << i) + (i << (i - 1));//新增的幂次个数
            if (c <= k) {
                k -= c;
                res += (sumI << i) + ((i * (i - 1) / 2) << (i - 1));
                sumI += i; // 之前填的 1 的幂次之和
                cnt1++; // 之前填的 1 的个数
                n |= 1L << i; // 填 1
            }
        }
        // 最低位单独计算
        if (cnt1 <= k) {
            k -= cnt1;
            res += sumI;
            n++; // 填 1
        }
        // 剩余的 k 个幂次,由 n 的低 k 个 1 补充
        while (k-- > 0) {
            res += Long.numberOfTrailingZeros(n);
            n &= n - 1;
        }
        return res;
    }

    private int pow(long x, long n, long mod) {
        long res = 1 % mod;
        for (; n > 0; n /= 2) {
            if (n % 2 == 1) {
                res = (res * x) % mod;
            }
            x = (x * x) % mod;
        }
        return (int) res;
    }
}

相关推荐

  1. Leetcode110题解

    2024-05-16 12:54:04       26 阅读

最近更新

  1. .Net Core WebAPI参数的传递方式

    2024-05-16 12:54:04       2 阅读
  2. QT--气泡框的实现

    2024-05-16 12:54:04       3 阅读
  3. LeetCode 968.监控二叉树 (hard)

    2024-05-16 12:54:04       2 阅读
  4. leetcode热题100.完全平方数(动态规划进阶)

    2024-05-16 12:54:04       2 阅读
  5. leetcode328-Odd Even Linked List

    2024-05-16 12:54:04       3 阅读
  6. C 语言设计模式(结构型)

    2024-05-16 12:54:04       2 阅读
  7. v-if 与 v-show(vue3条件渲染)

    2024-05-16 12:54:04       2 阅读
  8. kafka防止消息丢失配置

    2024-05-16 12:54:04       3 阅读

热门阅读

  1. 40-2 了解与安装堡垒机

    2024-05-16 12:54:04       2 阅读
  2. Leetcode 404:左叶子之和

    2024-05-16 12:54:04       3 阅读
  3. 力扣:131. 分割回文串

    2024-05-16 12:54:04       3 阅读
  4. 力扣 72. 编辑距离 python AC

    2024-05-16 12:54:04       4 阅读
  5. 课时126:awk实践_进阶知识_内置函数1

    2024-05-16 12:54:04       4 阅读
  6. 【Python】学生管理系统

    2024-05-16 12:54:04       4 阅读
  7. 2024.5.15晚训题解

    2024-05-16 12:54:04       4 阅读