讨论/题目交流/🏆 第 162 场力扣周赛/
🏆 第 162 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 奇数值单元格的数目
4 分 - 重构 2 行二进制矩阵
5 分 - 统计封闭岛屿的数目
6 分 - 得分最高的单词集合

展开讨论
共 22 个讨论

第一题:

看着数据量暴力模拟统计即可,其实也可以,直接统计一下每个行每个列分别加了多少次,对于每个格子,就可以通过对应的行和列直接计算出值

class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        vector<vector<int>> data(n, vector<int>(m, 0));
        for (auto& indice : indices) {
            for (int i = 0;i < n;i++) {
                data[i][indice[1]]++;
            }
            for (int i = 0;i < m;i++) {
                data[indice[0]][i]++;
            }
        }
        int ret = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (data[i][j] & 1) {
                    ret++;
                }
            }
        }
        return ret;
    }
};

第二题

这个题理解题意后就不难了。2值,要么就是0要么就是1,如果某一列加起来等于0,那么这一列两个数都是0,如果某一列加起来等于2,那么这一列两个数都是1。
把和为0和2的列先填了,把upper和lower减去相应的1,剩下的upper和lower相加必须等于和为1的列,第一行填upper个1,第二行填lower个1即可

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        vector<vector<int>> ret(2, vector<int>(colsum.size(), 0));
        int cal = 0;
        for (int i = 0;i < colsum.size();i++) {
            if (colsum[i] == 0) {
                ret[0][i] = ret[1][i] = 0;
            } else if (colsum[i] == 1) {
                cal++;
            } else {
                ret[0][i] = ret[1][i] = 1;
                upper--;
                lower--;
            }
        }
        if (upper < 0 || lower < 0 || upper + lower != cal) {
            return {};
        } else {
            for (int i = 0;i < colsum.size();i++) {
                if (colsum[i] == 1) {
                    if (upper > 0) {
                        ret[0][i] = 1;
                        ret[1][i] = 0;
                        upper--;
                    } else {
                        ret[0][i] = 0;
                        ret[1][i] = 1;
                        lower--;
                    }
                }
            }
            return ret;
        }
    }
};

第三题:

跟leetcode-130相似。找陆地的题大家应该做得挺多了,循环找到一个陆地,从这个陆地开始把相邻能到达的陆地一起连起来算作一片陆地,访问到的陆地置为已访问。直到把所有的陆地都访问过,就可以得到总共多少封闭岛屿了。

这个题还有一个条件,如果岛屿靠近矩阵边缘,就不算封闭岛屿。这个也容易处理,只需要把矩阵边缘的陆地先访问,把能到达矩阵边缘的陆地全部置为已访问,再进行封闭岛屿的统计

class Solution {
public:
    void run(vector<vector<int>>& grid, int x, int y) {
        int n = grid.size();
        int m = grid[0].size();
        
        queue<vector<int>> Q;
        Q.push({x, y});
        grid[x][y] = 1;
        
        int vx[] = {0,0,1,-1};
        int vy[] = {1,-1,0,0};
        
        while (!Q.empty()) {
            vector<int> res = Q.front();
            Q.pop();
            
            for (int i = 0;i < 4;i++) {
                vector<int> next = {res[0] + vx[i], res[1] + vy[i]};
                if (next[0] >= 0 && next[0] < n && next[1] >= 0 && next[1] < m && grid[next[0]][next[1]] == 0) {
                    grid[next[0]][next[1]] = 1;
                    Q.push(next);
                }
            }
        }
    }
    int closedIsland(vector<vector<int>>& grid) {
        
        int n = grid.size();
        int m = grid[0].size();
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
                    if (grid[i][j] == 0) {
                        run(grid, i, j);
                    }
                }
            }
        }
        int ret = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (grid[i][j] == 0) {
                    ret++;
                    run(grid, i, j);
                }
            }
        }
        return ret;
    }
};

第四题:

跟上一周一样,纯枚举,words的数量才15,枚举words子集总共2^15种情况,对于每个子集,统计一下这个子集每个字母用了多少次,是不是letters的子集,如果是,计算得分

class Solution {
public:
    vector<int> group(vector<string>& words, int bit) {
        vector<int> ret(26, 0);
        for (int i = 0;i < words.size();i++) {
            if (bit & (1 << i)) {
                for (int j = 0;j < words[i].size();j++) {
                    ret[words[i][j] - 'a']++;
                }
            }
        }
        return ret;
    }
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<int> stat(26, 0);
        for (char& c: letters) {
            stat[c - 'a']++;
        }
        
        int ret = 0;
        for (int i = 1;i < (1 << words.size());i++) {
            vector<int> g = group(words, i);
            int temp = 0;
            for (int j = 0;j < 26;j++) {
                if (g[j] > stat[j]) {
                    temp = -1;
                    break;
                } else {
                    temp += g[j] * score[j];
                }
            }
            if (temp != -1) {
                ret = max(ret, temp);
            }
        }
        return ret;
    }
};
10

惯例占坑,详细题解稍晚来~:

  • 奇数值单元格的数目
    数据范围小,可以直接模拟每行每列的情况,时间复杂度为 O(n2)O(n^2)。不过也可以只统计行和列的计数情况,我们分别统计被增加偶数次和奇数次的行,以及被增加偶数次和奇数次的列,那么对应的 偶数行奇数列偶数行*奇数列奇数行偶数列奇数行*偶数列 都可以被统计入结果,时间复杂度降为 O(n)O(n)

  • 重构 2 行二进制矩阵
    sum0sum2 的都是固定策略的,重点就是 sum1 的该如何分配,首先如果 upper+lowersum22sum1upper+lower-sum_2*2≠sum_1,那么肯定是无解的。如果有接,我们直接遍历原矩阵列,如果 upper 大于0那么就把1分配给upper行,否则分配给lower行。时间复杂度为 O(n)O(n)
    还有一种无解的情况是 upper<sum2upper<sum_2 或者 lower<sum2lower<sum_2,也需要判断。

  • 统计封闭岛屿的数目
    经典的搜索题目,只是现在我们在搜索的同时还需要记录一个当前是否触碰到边界的状态,如果触碰到边界那么当前岛屿不计入答案。

  • 得分最高的单词集合
    由于单词最多只有 1414 个,我们可以暴力每个单词是否选取来计算当前得分更新结果。比如我们现在枚举选择了 [1,2,4][1,2,4] 单词,那么就统计这三个单词所需要的字母数量,然后看看我们的字典是否能满足,能满足的话就计算得分并更新我们的结果。如果有 nn 个单词,单词平均长度为 mm,时间复杂度为 O(nm2n)O(nm2^n)

4

第一题 奇数值单元格的数目

模拟

int oddCells(int n, int m, vector<vector<int>>& indices)
{
    vector<vector<int>> matrix(n, vector<int>());
    for (auto &ma : matrix) ma.resize(m);

    for (auto in : indices)
    {
        for (auto x = 0; x < n; x++)
        {
            matrix[x][in[1]]++;
        }
        for (auto y = 0; y < m; y++)
        {
            matrix[in[0]][y]++;
        }
    }

    int ans = 0;
    for (auto a : matrix)
    {
        for (auto b : a)
        {
            ans += (b & 1);
        }
    }
    return ans;
}

第二题 重构 2 行二进制矩阵

不用回溯,不用贪心,模拟即可

第三题 统计封闭岛屿的数目

普通的dfs即可

第四题 得分最高的单词集合

位压缩

感谢观看

1

小菜鸡路过

1

四道暴力

第一题

暴力枚举

第二题

先把colsum==2的填了,剩下的从左到右去填就行了,中间发现无法填直接返回empty

第三题

BFS染色,在染的过程中注意标记一下是不是染到边界了,染到边界了就不是isolated island,否则才是

第四题

看了下数据规模,2^14,完全可以暴力。因此,先dfs出要拼哪几个单词,最后算一下每种组合的总得分,取最大值即可


impl Solution {
    pub fn max_score_words(words: Vec<String>, letters: Vec<char>, score: Vec<i32>) -> i32 {
        let n = words.len();
        if n == 0 {
            return 0;
        }
        if letters.is_empty() {
            return 0;
        }
        let mut letter_count = vec![0; 26];
        for c in letters {
            letter_count[(c as u8 - b'a') as usize] += 1;
        }
        let mut used = vec![false; n];
        let mut ans = 0;
        Self::dfs(0, &words, &mut used, &letter_count, &score, &mut ans);
        ans
    }
    fn dfs(cur: usize, words: &Vec<String>, used: &mut Vec<bool>, char_count: &Vec<i32>, score: &Vec<i32>, ans: &mut i32) {
        if cur >= words.len() {
            let mut count = vec![0; 26];
            let mut get_score = 0;
            for i in 0..words.len() {
                if used[i] {
                    for &c in words[i].as_bytes() {
                        let pos = (c - b'a') as usize;
                        count[pos] += 1;
                        get_score += score[pos];
                        if count[pos] > char_count[pos] {
                            return;
                        }
                    }
                }
            }
            if get_score > *ans {
                *ans = get_score;
            }
            return;
        }
        for i in cur..words.len() {
            Self::dfs(i+1, words, used, char_count, score, ans);
            used[i] = true;
            Self::dfs(i+1, words, used, char_count, score, ans);
            used[i] = false;
        }
    }
}
1

菜鸟C语言,3小时才做完 --'
代码轻喷

第一题

#define MAX_N 56
int matrix[MAX_N][MAX_N] = { 0 };

int oddCells(int n, int m, int** indices, int indicesSize, int* indicesColSize)
{
    int i, j, k;
    int row, col;
    int ans = 0;
    memset(matrix, 0, sizeof(matrix));
    
    for (k = 0; k < indicesSize; k++) {
        row = indices[k][0];
        col = indices[k][1];
        for (j = 0; j < m; j++) {
            matrix[row][j]++;
        }
        for (i = 0; i < n; i++) {
            matrix[i][col]++;
        }
    }
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (matrix[i][j] % 2 == 1) {
                ans++;
            }
        }
    }
    
    return ans;
}

第二题

int** reconstructMatrix(int upper, int lower, int* colsum, int colsumSize, int* returnSize, int** returnColumnSizes)
{
	int **ans = (int **)calloc(1, sizeof(int *) * 2);
	int i, tmp1, tmp2;
	int upIndex = 0, lowIndex = 0;
	int flag = 0;

	for (i = 0; i < 2; i++) {
		ans[i] = (int *)calloc(1, sizeof(int) * colsumSize);
	}

	tmp1 = 0;
	tmp2 = 0;

	for (i = 0; i < colsumSize; i++) {
		if (colsum[i] == 2) {
			ans[0][upIndex++] = 1;
			ans[1][lowIndex++] = 1;
			tmp1++;
			tmp2++;
		} else if (colsum[i] == 0) {
			ans[0][upIndex++] = 0;
			ans[1][lowIndex++] = 0;
		} else {
			/* 贪心,优先给剩余空间的大的加 */
			if (upIndex < colsumSize && tmp1 < upper && (upper - tmp1 > lower - tmp2)) {
				ans[0][upIndex++] = 1;
				tmp1++;
				ans[1][lowIndex++] = 0;
			} else if (lowIndex < colsumSize && tmp2 < lower) {
				ans[0][upIndex++] = 0;
				ans[1][lowIndex++] = 1;
				tmp2++;
			} else {
				/* 两边都装满了 */
				flag = 1;
				//printf("error\n");
				break;
			}
		}
	}

	*returnSize = 2;
	if (flag == 1 || tmp1 != upper || tmp2 != lower) {
		*returnSize = 0;
	}

	(*returnColumnSizes) = (int *)calloc(1, sizeof(int) * 2);
	for (i = 0; i < 2; i++) {
		(*returnColumnSizes)[i] = colsumSize;
	}
	return ans;
}

第三题

#include <stdio.h>
#define MAX_N 128
#define DIRECT 4
static int iGo[] = {-1, 0, 1, 0};
static int jGo[] = {0, 1, 0, -1};
static int **matrix;
static int m, n;

static bool isAns = false;

static bool IsValid(int i, int j)
{
	if (i < 0 || i >= m ||
		j < 0 || j >= n) {
			return false;
	}
	return true;
}

static void Dfs(int i, int j)
{
	int k;
	if (!IsValid(i, j)) {
		/* 如果是碰到了边界,不是完全包围的 */
		isAns = false;
		return;
	}

	if (matrix[i][j] == 1) {
		return;
	}

	matrix[i][j] = 1;

	for (k = 0; k < DIRECT; k++) {
		Dfs(i + iGo[k], j + jGo[k]);
	}
}

int closedIsland(int** grid, int gridSize, int* gridColSize)
{
	int i, j;
	int ans = 0;
	matrix = grid; 
	m = gridSize;
	n = *gridColSize;

	//memset(visited, 0, sizeof(visited));

	for (i = 0; i < m; i++) {   
		for (j = 0; j < n; j++) { 
			if (matrix[i][j] == 0) {
				isAns = true;
				Dfs(i, j);
				if (isAns == true) {
					ans++;
				}
			}
		}
	}
	return ans;
}


第四题

#include <stdio.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

static bool IsValid(int *a, int *b)
{
	int i;
	for (i = 0; i < 26; i++) {
		if (a[i] < b[i]) {
			return false;
		}
	}

	return true;
}

static int GetSc(int *a, int *score)
{
	int ans = 0;
	int i;
	for (i = 0; i < 26; i++) {
		if (a[i] == 0) {
			continue;
		}

		ans += a[i] * score[i];
	}

	return ans;
}

int maxScoreWords(char ** words, int wordsSize, char* letters, int lettersSize, int* score, int scoreSize)
{
	/* 暴力枚举,枚举出所有的组合,判断是否合法,如果合法则统计结果,更新最大值 */
	int max = 1 << wordsSize;
	int ans = 0;
	int i, j, k;
	int cCnt[26] = { 0 };
	int tmpCnt[26] = { 0 };
	int wordLen = 0;
	int sc;
	bool flag = true;

	for (i = 0; i < lettersSize; i++) {
		cCnt[letters[i] - 'a']++;
	}

	for (i = 0; i < max; i++) {
		memset(tmpCnt, 0, sizeof(tmpCnt));
		for (j = 0; j < wordsSize; j++) {
			if (i & (1 << j)) {
				wordLen = strlen(words[j]);
				for (k = 0; k < wordLen; k++) {
					tmpCnt[words[j][k] - 'a']++;
				}                
			}

			if (!IsValid(cCnt, tmpCnt)) {
				/* 如果选择超出了,则退出 */
				break;
			}
			sc = GetSc(tmpCnt, score);
			ans = MAX(ans, sc);
			//printf("%s, sc:%d, ans:%d\n", words[j], sc, ans);
		}
		//printf("*************\n");
	}
	return ans;
}


1

难道就没有用Java做出第四道题的吗?

1

第一题:

比较简单的模拟题,也可以通过计数的方法进行优化,减少时空复杂度。
题解传送门

第二题:

构造题,解法不唯一,注意考虑无法构造的情况。
题解传送门

第三题:

使用 DFS 或 BFS 在二维数组中进行不重复的搜索,比较常规。
题解传送门

第四题:

使用递归对所有可能的状态进行不重复的搜索,是比较容易想的 Hard 题。
题解传送门

1

第三题 在内圈开始dfs 如果从某点出发 到达过边界的陆地 则此次dfs形成的联通块必不被水包围 判定为 0 不计入答案

class Solution {
public:
    int n,m,dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
    void dfs(vector<vector<int>>& g, int x, int y, int &flag){
        g[x][y] = 1;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&!g[nx][ny]){//合法位置
                if(nx==0||ny==0||nx==n-1||ny==m-1) flag = 0;//搜到了边界处的陆地 则这一片不被水包围
                dfs(g,nx,ny,flag);
            }
        }
    }
    int closedIsland(vector<vector<int>>& g) {
        int sum = 0,flag;
        n = g.size(), m = g[0].size();//无需再定义,这里注意是全局变量(⊙o⊙)…
        for(int i = 1; i < n-1; i++)//边界点必定不计入答案 所以从内侧的点开始搜索
            for(int j = 1; j < m-1; j++)
                if(!g[i][j]) flag = 1, dfs(g,i,j,flag), sum += flag;//从i,j出发是否可以碰到边界 假设碰不到flag=1 
        return sum;
    }
};
1

第二题再一次碰见宛如智障的编译器。这个用golang写的,输出是对的,在结果里就变成了空,我也很是无奈。

func reconstructMatrix(upper int, lower int, colsum []int) [][]int {
    tmp:=make([][]int,2)

    if (upper+lower)!=sum(colsum){
        return [][]int{}
    }
    for _,i:=range(colsum){
 
        switch i{
            case 2: tmp[0]=append(tmp[0],1)
                    tmp[1]=append(tmp[1],1)
                    upper--
                    lower--
            case 0: tmp[0]=append(tmp[0],0)
                    tmp[1]=append(tmp[1],0)
            case 1: if upper>=lower{
                    tmp[0]=append(tmp[0],1)
                    tmp[1]=append(tmp[1],0)
                    upper--
            }else{
                    tmp[0]=append(tmp[0],0)
                    tmp[1]=append(tmp[1],1)
                    lower--
            }
        }
    }
    fmt.Println(tmp)
    return tmp
}
func sum(data []int)int{
    ans:=0
    for _,i:=range(data){
        
        ans+=i
    }
    return ans
}