Leetcode - 130双周赛

admin2024-05-15  0

目录

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

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

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

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


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

Leetcode - 130双周赛,第1张

代码如下:

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. 正方形中的最多点数

Leetcode - 130双周赛,第2张

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. 分割字符频率相等的最少子字符串

Leetcode - 130双周赛,第3张

代码如下:

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

代码如下:

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. 大数组元素的乘积

Leetcode - 130双周赛,第4张

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;
    }
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!