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

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

image.png

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

展开讨论

菜鸟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
展开全部 22 讨论