首页 > 试题广场 >

字母矩阵

[编程题]字母矩阵

热度指数：560 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个 $n \times m$ 的只由小写英文字母组成的矩阵 $A$ ，牛牛想找到一个面积最小的正方形子矩阵满足该正方形子矩阵包含至少 $k$ 种不同的字母。

输入描述:

第一行输入三个正整数 $n,m,k$ 。

接下来 $n$ 行每行输入一个长度为 $m$ 的字符串，其中第 $i$ 行第 $j$ 个字母为 $A_{i,j}$ 。

$(1 \leq n,m \leq 500,1 \leq k \leq 26,A_{i,j} \in S)$

其中 $S$ 为所有小写英文字母'a'-'z'的集合。

输出描述:

输出一个正整数表示包含至少  种不同字母的方形子矩阵的边长，如果不存在该子方阵，输出。

示例1

输入

4 4 3
aabc
aaaa
axaz
abcd

输出

说明

不存在边长为  的方形子矩阵包含至少  种不同的字母。
如图，存在边长为  的方形子矩阵包含至少  种不同的字母：

示例2

输入

2 2 5
ab
cd

输出

-1

说明

显然矩阵总共只有 种字符，因此答案为  。

算法知识视频讲解

牛客734470976号

用的暴力求解的方法，只通过了十几个测试，原本是用numpy包做的，unique方法很好用，后面自己实现了一个类似的unique方法，但估计还是循环这里耗时严重

import math
n,m,k = input().split(' ')
n,m,k = int(n),int(m),int(k)
a = []
for i in range(n):
    a.append(list(input()))
    
# 从矩阵a中找以a[i][j]为首的，边长为r的正方形中唯一字母的个数（用set的长度）
def count_sub_mat(a,i,j,r):
    return len(set([a[x][y] for x in range(i,i+r) for y in range(j,j+r)]))

start_r = int(math.ceil(math.sqrt(k))) # 开始搜索的正方形边长
if start_r>m*n:
    print(-1)
else:
    max_r = min(m,n)
    flag = False
    for r in range(start_r, max_r):
        if flag:
            break
        for i in range(n-r+1):
            if flag:
                break
            for j in range(m-r+1):
                if flag:
                    break
                if(count_sub_mat(a,i,j,r)>=k):
                    print(r)
                    flag = True

发表于 2022-03-24 22:34:19 回复(0)

Java

pein531

二维滑动窗口

这个题思路比较简单，但是coding起来还挺烦的，很多下标变换。为了更新窗口词频表的计算量尽可能小，在滑窗的时候从上往下之字形滑动，验证窗口中的字母种数是否足够 $k$ 个。由于是正方形的窗口，我们可以定出窗口边长的取值范围 $[ceil(\sqrt{k}),min(n,m)]$ ，并且从大边长往小边长进行尝试，因为如果大边长找不到符合条件的窗口，比它小的边长就不用试了。

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        int m = Integer.parseInt(params[1]);
        int k = Integer.parseInt(params[2]);
        char[][] matrix = new char[n][];
        for(int i = 0; i < n; i++){
            matrix[i] = br.readLine().toCharArray();
        }
        int resEdge = -1;
        for(int edge = Math.min(n, m); edge >= (int)Math.ceil(Math.sqrt(k)); edge--){
            if(convolution(matrix, edge, k)){
                resEdge = edge;
            }else{
                break;
            }
        }
        System.out.println(resEdge);
    }
    
    private static boolean convolution(char[][] matrix, int edge, int lb){
        // 从左上角初始化计数器
        int[] counter = new int[26];
        int nunique = 0;
        for(int i = 0; i < edge; i++){
            for(int j = 0; j < edge; j++){
                if(counter[matrix[i][j] - 'a'] == 0){
                    nunique++;
                }
                counter[matrix[i][j] - 'a']++;
            }
        }
        if(nunique >= lb){
            return true;
        }
        // 之字形滑动窗口
        boolean left2right = true;     // 先从左往右滑动
        for(int i = 0; i <= matrix.length - edge; i++){
            if(left2right){
                for(int j = 0; j <= matrix[0].length - edge; j++){
                    if(j > 0){
                        for(int r = i; r < i + edge; r++){
                            counter[matrix[r][j - 1] - 'a']--;
                            if(counter[matrix[r][j - 1] - 'a'] == 0){
                                nunique--;
                            }
                            counter[matrix[r][j + edge - 1] - 'a']++;
                            if(counter[matrix[r][j + edge - 1] - 'a'] == 1){
                                nunique++;
                            }
                        }
                    }
                    if(nunique >= lb){
                        return true;
                    }
                }
                // 构建下一行的初始窗口
                if(i + edge < matrix.length){
                    for(int k = matrix[0].length - edge; k < matrix[0].length; k++){
                        counter[matrix[i][k] - 'a']--;
                        if(counter[matrix[i][k] - 'a'] == 0){
                            nunique--;
                        }
                        counter[matrix[i + edge][k] - 'a']++;
                        if(counter[matrix[i + edge][k] - 'a'] == 1){
                            nunique++;
                        }
                    }
                }
            }else{
                for(int j = matrix[0].length - edge; j >= 0; j--){
                    if(j < matrix[0].length - edge){
                        for(int k = i; k < i + edge; k++){
                            counter[matrix[k][j + edge] - 'a']--;
                            if(counter[matrix[k][j + edge] - 'a'] == 0){
                                nunique--;
                            }
                            counter[matrix[k][j] - 'a']++;
                            if(counter[matrix[k][j] - 'a'] == 1){
                                nunique++;
                            }
                        }
                    }
                    if(nunique >= lb){
                        return true;
                    }
                }
                if(i + edge < matrix.length){
                    for(int k = 0; k < edge; k++){
                        counter[matrix[i][k] - 'a']--;
                        if(counter[matrix[i][k] - 'a'] == 0){
                            nunique--;
                        }
                        counter[matrix[i + edge][k] - 'a']++;
                        if(counter[matrix[i + edge][k] - 'a'] == 1){
                            nunique++;
                        }
                    }
                }
            }
            left2right = !left2right;
        }
        return false;
    }
}

发表于 2022-01-21 12:12:37 回复(0)

ReScale

二进制压缩状态即可

import java.util.*;

public class Main {
    private static int[][] sum;
    private static int cur = 1;
    private static int n, m, k;
    private static int maxLength;
    public static void main(String[] args) {    
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        k = in.nextInt();
        String xx = in.nextLine();
        sum = new int[n][m];
        for (int i = 0; i < n; i ++) {
            String s = in.nextLine();
            int j = 0;
            for (char c : s.toCharArray()) {
                sum[i][j++] = 1 << (c - 'a');
            }
        }
        
       // for (int i = 0; i < n; i ++) System.out.println(Arrays.toString(sum[i]));
        
        maxLength = Math.min(n, m);
        if (maxLength * maxLength < k) {
            System.out.println(-1);
        } else if (k == 1) {
            System.out.println(1);
        } else {
            if (find()) System.out.println(cur);
            else System.out.println(-1);
        }
        // System.out.println(sum[0][0]);
    }
    
    public static boolean find() {
        for (int l = 2; l <= maxLength; l ++) {
            for (int i = 0; i < n - l + 1; i ++) {
                for (int j = 0; j < m - l + 1; j ++) {
                    sum[i][j] = sum[i][j] | sum[i+1][j] | sum[i][j+1] | sum[i+1][j+1];
                }
            }
            if (l * l < k) continue;
            for (int i = 0; i < n - l + 1; i ++) {
                for (int j = 0; j < m - l + 1; j ++) {
                    int t = sum[i][j];
                    int cnt = 0;
                    while (t > 0) {
                        if ((t & 1) == 1) cnt ++;
                        t >>= 1;
                    }
                    if (cnt >= k) {
                        cur = l;
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

编辑于 2022-07-31 11:21:21 回复(0)

牛客757292505号

from math import sqrt

class Array:
    """实现__getitem__，支持序列获取元素、Slice等特性"""

    def __init__(self, lst):
        self.__coll = lst

    def __repr__(self):
        """显示列表"""

        return '{!r}'.format(self.__coll)

    def __getitem__(self, key):
        """获取元素"""
        slice1, slice2 = key
        row1 = slice1.start
        row2 = slice1.stop
        col1 = slice2.start
        col2 = slice2.stop
        return [self.__coll[r][col1:col2] for r in range(row1, row2)]

while True:
    try:
        nmk = input().split(' ')
        n = int(nmk[0])
        m = int(nmk[1])
        k = int(nmk[2])
        if n * m < k:
            print(-1)
            break
        A = []
        for i in range(n):
            A.append(list(map(str, input().strip())))
        A = Array(A)
        S = 0      # 字母的种类
        length = -1
        for l in range(int(sqrt(k)) + 1, min(n, m)):  # 矩阵边长
            for i in range(min(n, m)-int(sqrt(k))):
                for j in range(min(n, m)-int(sqrt(k))):
                    As = A[i:i+l, j:j+l]     # 取边长为l的正方形子矩阵，并降维去重
                    if len(set(sum(As, []))) > S:
                        S = len(set(sum(As, [])))
                    if S >= k:
                        length = l
                        break
                break
            break

        print(length)
        
    except:
        break

暴力搜索，但只能通过前13个用例

发表于 2021-09-06 14:58:38 回复(0)

C++

深水无声

不知道怎么优化了，只能通过7组用例，其他的超时。

#include
#include
#include
#include
using namespace std;
int res,resLen;
void dfs(vector& square, int i, int j, int length,int& k){
    if(resLen==k) return;
    if(j+length>square[0].length()&&i+length<square.size()){
        i++;
        j=0;
    }else if(j+length > square[0].length()||i+length>square.size()) return;
    set st;
    for(int row = i;row < i+length;row++){
        for(int col = j;col<j+length;col++){
            st.insert(square[row][col]);
        }
    }
    if(st.size()==k){
        res = length;
        resLen = k;
    }
    dfs(square, i, j+1, length, k);
}
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    vector square(n);
    for(int i = 0; i < n; i++){
        cin>>square[i];
    }
    int length = n>m?m:n;
    res = length+1;
    for(int i = 2; i <= length;i++){
        dfs(square, 0, 0, i, k);
        if(res<length+1) break;
    }
    if(res==length+1) res = -1;
    cout<<res<<endl;
}

发表于 2021-09-01 11:25:28 回复(0)

Python 3

落荒草

class Solution:
    def check(self, n, m, s, k, pre):
        # s表示边长
        # pre[i][j][t]表示以array[i][j]为右下角元素，array[0][0]为左上角元素正方形内 字母t出现的次数
        for i in range(1, n+1):
            for j in range(1, m+1):
                if i + s -1 > n&nbs***bsp;j + s - 1 > m:
                    continue
                count = 0
                for t in range(26):  
                    if pre[i+s-1][j+s-1][t]-pre[i+s-1][j-1][t]-pre[i-1][j+s-1][t]+pre[i-1][j-1][t]>=1:
                        count += 1
                    if count >= k:
                        return True
        return False
    
    def  minSideLength(self, array, n, m, k):
        import math
        pre = [[[0]*26 for _ in range(m+1)] for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                for t in range(26):
                    pre[i][j][t] = pre[i-1][j][t] + pre[i][j-1][t] - pre[i-1][j-1][t]
                t = ord(array[i-1][j-1]) - ord("a")
                pre[i][j][t] += 1
        minS, maxS = int(math.sqrt(k)), min(n, m)
        res = -1
        while minS <= maxS:
            midS = (minS + maxS)>>1
            if self.check(n, m, midS, k, pre):
                maxS = midS -1
                res = midS
            else:
                minS = midS + 1
        return res
    
if __name__ == "__main__":
    [n, m, k] = list(map(int, input().strip().split()))
    array = []
    for i in range(n):
        string = input()
        array.append(string)
    s = Solution()
    res = s.minSideLength(array, n, m, k)
    print(res)

请问Python 3这样写有问题吗？老是显示超时是语言的问题吗

发表于 2021-08-27 17:05:12 回复(1)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师游戏研发工程师 2021 数据库工程师信息技术岗区块链测试开发工程师大数据开发工程师数据分析师牛客

上传者：小小

难度：

6条回答 39收藏 4218浏览

通过挑战的用户

wangjy520

2023-03-06 23:41:39
牛客71356...

2022-09-30 10:16:13
热情的小黄鸭要冲外企

2022-09-11 15:48:40
果果爱丫头

2022-09-01 21:08:18
檐上的月光

2022-08-22 21:50:54