LeetCode biweekly-contest-66

LeetCode biweekly-contest-66

晚上唱K失败,团队唱K热情不足呀,还是乖乖回来刷题吧,这次前两题轻松拿下,第三道题DFS又超时,我想了好久的剪枝都没想出来,没想到其实每个格子的权重并不是都不一样,最后一道题就没看了,排名1322 / 2803,唉,一直都是average的水平

5922. 统计出现过一次的公共字符串 [EASY]

给你两个字符串数组 words1 和 words2 ,请你返回在两个字符串数组中 都恰好出现一次 的字符串的数目。

示例 1:
输入:words1 = [“leetcode”,”is”,”amazing”,”as”,”is”], words2 = [“amazing”,”leetcode”,”is”]
输出:2
解释:

  • “leetcode” 在两个数组中都恰好出现一次,计入答案。
  • “amazing” 在两个数组中都恰好出现一次,计入答案。
  • “is” 在两个数组中都出现过,但在 words1 中出现了 2 次,不计入答案。
  • “as” 在 words1 中出现了一次,但是在 words2 中没有出现过,不计入答案。
    所以,有 2 个字符串在两个数组中都恰好出现了一次。

示例 2:
输入:words1 = [“b”,”bb”,”bbb”], words2 = [“a”,”aa”,”aaa”]
输出:0
解释:没有字符串在两个数组中都恰好出现一次。

示例 3:
输入:words1 = [“a”,”ab”], words2 = [“a”,”a”,”a”,”ab”]
输出:1
解释:唯一在两个数组中都出现一次的字符串是 “ab” 。

提示:
1 <= words1.length, words2.length <= 1000
1 <= words1[i].length, words2[j].length <= 30
words1[i] 和 words2[j] 都只包含小写英文字母。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* 
审题:
这题好像做过,迅速搞定了,当然跟那些一分钟写完的大神还是不敢比的(他们真的是人吗)
*/
#include <unordered_map>
#include <set>
class Solution {
public:
int countWords(vector<string>& words1, vector<string>& words2) {
unordered_map<string, int> wordMap1;
unordered_map<string, int> wordMap2;
set<string> wordSet;
for (auto& word : words1) {
wordMap1[word]++;
wordSet.insert(word);
}
for (auto& word : words2) {
wordMap2[word]++;
wordSet.insert(word);
}
int sum = 0;
for (auto& word : wordSet) {
sum += (wordMap1[word] == 1 && wordMap2[word] == 1);
}
return sum;
}
};

5923. 从房屋收集雨水需要的最少水桶数 [MEDIUM]

给你一个下标从 0 开始的字符串 street 。street 中每个字符要么是表示房屋的 ‘H’ ,要么是表示空位的 ‘.’ 。

你可以在 空位 放置水桶,从相邻的房屋收集雨水。位置在 i - 1 或者 i + 1 的水桶可以收集位置为 i 处房屋的雨水。一个水桶如果相邻两个位置都有房屋,那么它可以收集 两个 房屋的雨水。

在确保 每个 房屋旁边都 至少 有一个水桶的前提下,请你返回需要的 最少 水桶数。如果无解请返回 -1 。

示例 1:
输入:street = “H..H”
输出:2
解释:
我们可以在下标为 1 和 2 处放水桶。
“H..H” -> “HBBH”(’B’ 表示放置水桶)。
下标为 0 处的房屋右边有水桶,下标为 3 处的房屋左边有水桶。
所以每个房屋旁边都至少有一个水桶收集雨水

示例 2:
输入:street = “.H.H.”
输出:1
解释:
我们可以在下标为 2 处放置一个水桶。
“.H.H.” -> “.HBH.”(’B’ 表示放置水桶)。
下标为 1 处的房屋右边有水桶,下标为 3 处的房屋左边有水桶。
所以每个房屋旁边都至少有一个水桶收集雨水。

示例 3:
输入:street = “.HHH.”
输出:-1
解释:
没有空位可以放置水桶收集下标为 2 处的雨水。
所以没有办法收集所有房屋的雨水。

示例 4:
输入:street = “H”
输出:-1
解释:
没有空位放置水桶。
所以没有办法收集所有房屋的雨水。

示例 5:
输入:street = “.”
输出:0
解释:
没有房屋需要收集雨水。
所以需要 0 个水桶。

提示:
1 <= street.length <= 105
street[i] 要么是 ‘H’ ,要么是 ‘.’ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
审题:这题写的比较丑,分的情况太多,圈复杂度太大了
*/
class Solution {
public:
int minimumBuckets(string street) {
int length = street.size();
if (length == 1) {
if (street[0] == '.') {
return 0;
} else {
return -1;
}
}
int sum = 0;
bool hasBucket = false;
for (int i = 0; i < length; ++i) {
if (street[i] == 'H') {
if (i == 0) {
if (street[i + 1] == '.') {
street[i + 1] = 'B';
++sum;
} else {
return -1;
}
} else if (i == length - 1) {
if (street[i - 1] == '.') {
++sum;
} else if (street[i - 1] == 'B') {
return sum;
} else {
return -1;
}
} else {
if (street[i - 1] == '.') {
if (street[i + 1] == '.') {
street[i + 1] = 'B';
++sum;
} else {
street[i - 1] = 'B';
++sum;
}
} else if (street[i - 1] == 'B') {
continue;
} else {
// i - 1 == 'H'
if (street[i + 1] == '.') {
street[i + 1] = 'B';
++sum;
} else {
return - 1;
}
}
}
}
}
return sum;
}
};

5924. 网格图中机器人回家的最小代价 [MEDIUM]

给你一个 m x n 的网格图,其中 (0, 0) 是最左上角的格子,(m - 1, n - 1) 是最右下角的格子。给你一个整数数组 startPos ,startPos = [startrow, startcol] 表示 初始 有一个 机器人 在格子 (startrow, startcol) 处。同时给你一个整数数组 homePos ,homePos = [homerow, homecol] 表示机器人的 家 在格子 (homerow, homecol) 处。

机器人需要回家。每一步它可以往四个方向移动:上,下,左,右,同时机器人不能移出边界。每一步移动都有一定代价。再给你两个下标从 0 开始的额整数数组:长度为 m 的数组 rowCosts 和长度为 n 的数组 colCosts 。

如果机器人往 上 或者往 下 移动到第 r 行 的格子,那么代价为 rowCosts[r] 。
如果机器人往 左 或者往 右 移动到第 c 列 的格子,那么代价为 colCosts[c] 。
请你返回机器人回家需要的 最小总代价 。


示例 1:
输入:startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7]
输出:18
解释:一个最优路径为:
从 (1, 0) 开始
-> 往下走到 (2, 0) 。代价为 rowCosts[2] = 3 。
-> 往右走到 (2, 1) 。代价为 colCosts[1] = 2 。
-> 往右走到 (2, 2) 。代价为 colCosts[2] = 6 。
-> 往右走到 (2, 3) 。代价为 colCosts[3] = 7 。
总代价为 3 + 2 + 6 + 7 = 18

示例 2:
输入:startPos = [0, 0], homePos = [0, 0], rowCosts = [5], colCosts = [26]
输出:0
解释:机器人已经在家了,所以不需要移动。总代价为 0 。

提示:
m == rowCosts.length
n == colCosts.length
1 <= m, n <= 105
0 <= rowCosts[r], colCosts[c] <= 104
startPos.length == 2
homePos.length == 2
0 <= startrow, homerow < m
0 <= startcol, homecol < n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
审题:这题审题漏了最重要的
>>>
如果机器人往 上 或者往 下 移动到第 r 行 的格子,那么代价为 rowCosts[r] 。
如果机器人往 左 或者往 右 移动到第 c 列 的格子,那么代价为 colCosts[c] 。
>>>
写了正常的dfs,应该也没有其他剪枝手段了,会超时
要移动到target格子,不管怎么走,都是要走fabs(target_x - start_x)和fabs(target_y - start_y)的代价,所以横直竖下的走是代价最小的

// 超时版本
#include <numeric>
class Solution {
public:
int minCost_ = INT_MAX;
int ites = 0;
void dfs(int curRow, int curCol, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts, int cost, vector<vector<bool>>& visited) {
// cout << curRow << "," << curCol << "," << ites++ << ", " << cost << "," << minCost_ << endl;
if (curRow == homePos[0] && curCol == homePos[1]) {
minCost_ = min(minCost_, cost);
return;
}
if (visited[curRow][curCol] || cost >= minCost_) {
return;
}
visited[curRow][curCol] = true;
// up
if (curRow - 1 >= 0) {
dfs(curRow - 1, curCol, homePos, rowCosts, colCosts, cost + rowCosts[curRow - 1], visited);
}
if (curRow - 1 == homePos[0] && curCol == homePos[1]) {
visited[curRow][curCol] = false;
return;
}
// down
if (curRow + 1 <= rowCosts.size() - 1) {
dfs(curRow + 1, curCol, homePos, rowCosts, colCosts, cost + rowCosts[curRow + 1], visited);
}
if (curRow + 1 == homePos[0] && curCol == homePos[1]) {
visited[curRow][curCol] = false;
return;
}
// left
if (curCol - 1 >= 0) {
dfs(curRow, curCol - 1, homePos, rowCosts, colCosts, cost + colCosts[curCol - 1], visited);
}
if (curRow == homePos[0] && curCol - 1 == homePos[1]) {
visited[curRow][curCol] = false;
return;
}
// right
if (curCol + 1 <= colCosts.size() - 1) {
dfs(curRow, curCol + 1, homePos, rowCosts, colCosts, cost + colCosts[curCol + 1], visited);
}
visited[curRow][curCol] = false;
}

int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {
vector<vector<bool>> visited(rowCosts.size(), vector<bool>(colCosts.size(), false));
dfs(startPos[0], startPos[1], homePos, rowCosts, colCosts, 0, visited);
return minCost_;
}
};

5925. 统计农场中肥沃金字塔的数目 [HARD]

有一个 矩形网格 状的农场,划分为 m 行 n 列的单元格。每个格子要么是 肥沃的 (用 1 表示),要么是 贫瘠 的(用 0 表示)。网格图以外的所有与格子都视为贫瘠的。

农场中的 金字塔 区域定义如下:

区域内格子数目 大于 1 且所有格子都是 肥沃的 。
金字塔 顶端 是这个金字塔 最上方 的格子。金字塔的高度是它所覆盖的行数。令 (r, c) 为金字塔的顶端且高度为 h ,那么金字塔区域内包含的任一格子 (i, j) 需满足 r <= i <= r + h - 1 且 c - (i - r) <= j <= c + (i - r) 。
一个 倒金字塔 类似定义如下:

区域内格子数目 大于 1 且所有格子都是 肥沃的 。
倒金字塔的 顶端 是这个倒金字塔 最下方 的格子。倒金字塔的高度是它所覆盖的行数。令 (r, c) 为金字塔的顶端且高度为 h ,那么金字塔区域内包含的任一格子 (i, j) 需满足 r - h + 1 <= i <= r 且 c - (r - i) <= j <= c + (r - i) 。
下图展示了部分符合定义和不符合定义的金字塔区域。黑色区域表示肥沃的格子。

给你一个下标从 0 开始且大小为 m x n 的二进制矩阵 grid ,它表示农场,请你返回 grid 中金字塔和倒金字塔的 总数目 。

示例 1:

输入:grid = [[0,1,1,0],[1,1,1,1]]
输出:2
解释:
2 个可能的金字塔区域分别如上图蓝色和红色区域所示。
这个网格图中没有倒金字塔区域。
所以金字塔区域总数为 2 + 0 = 2 。

示例 2:

输入:grid = [[1,1,1],[1,1,1]]
输出:2
解释:
金字塔区域如上图蓝色区域所示,倒金字塔如上图红色区域所示。
所以金字塔区域总数目为 1 + 1 = 2 。

示例 3:

输入:grid = [[1,0,1],[0,0,0],[1,0,1]]
输出:0
解释:
网格图中没有任何金字塔或倒金字塔区域。

示例 4:

输入:grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]
输出:13
解释:
有 7 个金字塔区域。上图第二和第三张图中展示了它们中的 3 个。
有 6 个倒金字塔区域。上图中最后一张图展示了它们中的 2 个。
所以金字塔区域总数目为 7 + 6 = 13.

提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 105
grid[i][j] 要么是 0 ,要么是 1 。

1
2
3
审题:这题没怎么看

[官方解答](https://leetcode-cn.com/problems/count-fertile-pyramids-in-a-land/solution/tong-ji-nong-chang-zhong-fei-wo-jin-zi-t-paok/)
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×