# LeetCode 第 27 场双周赛（1125/1966，前57.2%）

## 2. 题目

### 1. LeetCode 5408. 通过翻转子数组使两个数组相等 easy

示例 1：

1- 翻转子数组 [2,4,1] ，arr 变成 [1,4,2,3]
2- 翻转子数组 [4,2] ，arr 变成 [1,2,4,3]
3- 翻转子数组 [4,3] ，arr 变成 [1,2,3,4]

target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000

• 翻转任意次，那就排序后，相等即可
class Solution {
public:
bool canBeEqual(vector<int>& target, vector<int>& arr) {
sort(target.begin(), target.end());
sort(arr.begin(),arr.end());
return target == arr;
}
};

### 2. LeetCode 5409. 检查一个字符串是否包含所有长度为 K 的二进制子串 medium

示例 1：

1 <= s.length <= 5 * 10^5
s 中只含 0 和 1 。
1 <= k <= 20

• 大小为k的滑动窗口，把字符串取出来，转成int放入集合，看集合中数的种类是不是 2k 个
class Solution {
public:
bool hasAllCodes(string s, int k) {
if(s.size() <= k)
return false;
int i, l = 0, r = 0, num;
set<int> st;
for( ; r < s.size(); ++r)
{
if(r-l+1 == k)//长度为 k
{
num = 0;
for(i = l; i <= r; ++i)//转成数字
num = s[i]-'0' + (num<<1);
st.insert(num);
l++;
}
}
return st.size()== (1<<k);
}
};

968 ms 38.9 MB

将字符串从给定下标开始的字符子串，从base进制 转成 10 进制int
int stoi (const string&  str, size_t* idx = 0, int base = 10);
int stoi (const wstring& str, size_t* idx = 0, int base = 10);
class Solution {
public:
bool hasAllCodes(string s, int k) {
if(s.size() <= k)
return false;
int i, l = 0, r = 0;
set<int> st;
string str;
for( ; r < s.size(); ++r)
{
if(r-l+1 == k)
{
str = s.substr(l,k);
st.insert(stoi(str,0,2));
l++;
}
}
return st.size()== (1<<k);
}
};

1392 ms 50.2 MB

### 3. LeetCode 5410. 课程安排 IV medium （Floyd-Warshall）

输入：n = 2, prerequisites = [[1,0]],
queries = [[0,1],[1,0]]

示例 2：

queries = [[1,0],[0,1]]

输入：n = 3, prerequisites = [[1,2],[1,0],[2,0]],
queries = [[1,0],[1,2]]

queries = [[0,1],[2,0]]

queries = [[0,4],[4,0],[1,3],[3,0]]

2 <= n <= 100
0 <= prerequisite.length <= (n * (n - 1) / 2)
0 <= prerequisite[i][0], prerequisite[i][1] < n
prerequisite[i][0] != prerequisite[i][1]

1 <= queries.length <= 10^4
queries[i][0] != queries[i][1]

• 注意 i,j,k 的顺序
For each cell (i, j) in M:
if i == j:
M[i][j] = 0
if (i, j) is an edge in E:
M[i][j] = weight(i, j)
else:
M[i][j] = infinity
for k from 1 to |V|:
for i from 1 to |V|:
for j from 1 to |V|:
if M[i][j] > M[i][k] + M[k][j]:
M[i][j] = M[i][k] + M[k][j]
class Solution {
public:
vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
vector<vector<bool>> m(n, vector<bool>(n,false));
for(auto& pre : prerequisites)
m[pre[0]][pre[1]] = true;
int i, j, k;
for(i = 0; i < n; ++i)
{
for(j = 0; j < n; ++j)
{
for(k = 0; k < n; ++k)
{
if(m[j][i] && m[i][k])//连通判断
m[j][k] = true;
}
}
}
vector<bool> ans(queries.size());
i = 0;
for(auto& q : queries)
ans[i++] = m[q[0]][q[1]];
return ans;
}
};

1068 ms 59.5 MB

### 4. LeetCode 5411. 摘樱桃 II hard

• 从格子 (i,j) 出发，机器人可以移动到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
• 当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
• 当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
• 两个机器人在任意时刻都不能移动到 grid 外面。
• 两个机器人最后都要到达 grid 最底下一行。

输入：grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]

输入：grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100 

• 状态定义很难，参考的大佬们的思路
• dp[i][j1][j2],表示第 i 层，两机器人位置为 j1 , j2 的最大值
class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int i, j1, j2, nj1, nj2,k1,k2, m = grid.size(), n = grid[0].size();
vector<vector<vector<int>>> dp(m,vector<vector<int>>(n, vector<int>(n,-1)));
//dp[i][j1][j2],表示第i层，两机器人位置为 j1, j2 的最大值
dp[0][0][n-1] = grid[0][0]+grid[0][n-1];
vector<int> dir = {-1,0,1};
int maxPick = 0;
for(i = 1; i < m; ++i)
{
for(j1 = 0; j1 < n; ++j1)
{
for(j2 = 0; j2 < n; ++j2)
{
if(dp[i-1][j1][j2] != -1)
{
for(k1 = 0; k1 < 3; ++k1)
{
nj1 = j1 + dir[k1];
for(k2 = 0; k2 < 3; ++k2)
{
nj2 = j2 + dir[k2];
if(nj1 >= 0 && nj1 < n && nj2 >= 0 && nj2 < n)
{
if(nj1 == nj2)
dp[i][nj1][nj2] = max(dp[i][nj1][nj2], dp[i-1][j1][j2]+grid[i][nj1]);
else
dp[i][nj1][nj2] = max(dp[i][nj1][nj2], dp[i-1][j1][j2]+grid[i][nj1]+grid[i][nj2]);
}
}
}
}
}
}
}
for(j1 = 0; j1 < n; ++j1)
for(j2 = 0; j2 < n; ++j2)
maxPick = max(maxPick, dp[m-1][j1][j2]);
return maxPick;
}
};

140 ms 14.5 MB

0 条评论

• ### LeetCode 885. 螺旋矩阵 III

每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。

• ### 剑指Offer - 面试题40. 最小的k个数（排序/大顶堆）

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

• ### 腾讯居然也在做“雾霾”治理？因为腾讯举报中心正式上线啦！

如果还没有听说过雾霾蓝，那你就out了！2016年时尚界最火的颜色之一就是“雾霾蓝”。据说一个雾霾蓝的手袋真是时尚时尚最时尚呢。

• ### (38) 剖析ArrayList / 计算机程序的思维逻辑

从本节开始，我们探讨Java中的容器类，所谓容器，顾名思义就是容纳其他数据的，计算机课程中有一门课叫数据结构，可以粗略对应于Java中的容器类，我们不会介绍所有...

• ### C# 快速释放内存的大数组

本文告诉大家如何使用 Marshal 做出可以快速释放内存的大数组。 最近在做 3D ，需要不断申请一段大内存数组，然后就释放他，但是 C# 对于大内存不是立刻...

• ### cPanet面板绑定域名和删除已绑定域名教程

cPanel面板是一款功能强大的主机面板，国外众多大型主机商都在使用。对于cPanel面板中几十个上百个按钮功能，其实能用上的也不多。这里我们直接先步入正题，把...

• ### MYSQL io_capacity 哥俩，你调了吗？

innodb_io_capacity and innodb_io_capacity_max，这两个参数真的是innodb数据库引擎需要的参数吗？是innodb...