Leetcode每日一题 —— 2573. 找出对应 LCP 矩阵的字符串
- 内容介绍
- 文章标签
- 相关推荐
2573. 找出对应 LCP 矩阵的字符串 - 力扣（LeetCode）
2573. 找出对应 LCP 矩阵的字符串 - 对任一由 n 个小写英文字母组成的字符串 word ，我们可以定义一个 n x n 的矩阵，并满足： * lcp[i][j] 等于子字符串word[i,...,n-1] 和 word[j,...,n-1] 之间的最长公共前缀的长度。 给你一个 n x n 的矩阵 lcp 。返回与 lcp 对应的、按字典序最小的字符串word 。如果不存在这样的字符串，则返回空字符串。 对于长度相同的两个字符串 a 和 b ，如果在 a 和 b...
思路
题目到不是太难
- 根据lcp，如果
chr[i]=chr[j]那么lcp[i][j]>0，可以确定这个字符的内容。(PS，如果超过26位字符要返回空字符串) - 之前我们通过第一个字符是否相同做了判断，长度是否一致无法确定，所以要进行验证。
- 对角线肯定是n-1..1
- 对角线分割的上下三角对称
- 只验证上三角或者下三角。如果字符不相同，
lcp[i][j]=0。否则lcp[i][j]=lcp[i+1][j+1]+1（边界为lcp[x][n-1]=1
PS 通过递推dp[i][j]时间复杂度也是一样的。
代码
class Solution {
public String findTheString(int[][] lcp) {
int n = lcp.length;
char[] ans = new char[n];
char chr = 'a';
// 获取字符串
for (int i = 0; i < n; i++) {
if (ans[i] > 0) {
continue;
}
if (chr > 'z') {
return "";
}
ans[i] = chr++;
for (int j = i + 1; j < n; j++) {
if (lcp[i][j] > 0) {
ans[j] = ans[i];
}
}
}
// 验证1，对角线
for (int i = 0; i < n; i++) {
if (lcp[i][i] != n - i) {
return "";
}
}
// 验证2，上下三角对称
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (lcp[i][j] != lcp[j][i]) {
return "";
}
}
}
// 验证3，上三角数值有效
for (int i = n - 2; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (ans[i] != ans[j]) {
if (lcp[i][j] > 0) {
return "";
}
} else {
// 最右边是1，之后向左上依次+1
if (j == n - 1) {
if (lcp[i][j] != 1) {
return "";
}
} else if (lcp[i][j] != lcp[i + 1][j + 1] + 1) {
return "";
}
}
}
}
return new String(ans);
}
}
网友解答：
--【壹】--：
怎么做到这么短的，看完你的，我觉得我写的简直就是一坨
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [0] * size
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
rootA = self.find(a)
rootB = self.find(b)
if rootA == rootB:
return
if self.rank[rootA] < self.rank[rootB]:
self.parent[rootA] = rootB
elif self.rank[rootA] > self.rank[rootB]:
self.parent[rootB] = rootA
else:
self.parent[rootB] = rootA
self.rank[rootA] += 1
def connected(self, a, b):
return self.find(a) == self.find(b)
class Solution:
def validate(self, lcp: List[List[int]]) -> bool:
n = len(lcp)
for i in range(n):
if lcp[i][i] != n - i:
return False
for j in range(i + 1, n):
if lcp[i][j] > n - i:
return False
return all(lcp[i][j] == lcp[j][i] for i in range(n) for j in range(i+1, n))
def check_lcp(self, word: List[str], lcp: List[List[int]]) -> bool:
n = len(word)
for i in range(n):
for j in range(i + 1, n):
expected = 0
if word[i] == word[j]:
if i + 1 < n and j + 1 < n:
expected = lcp[i + 1][j + 1] + 1
else:
expected = 1
if lcp[i][j] != expected:
return False
return True
def findTheString(self, lcp: List[List[int]]) -> str:
"""
1. LCP矩阵对称
2. LCP矩阵对角线从n递减至1
3. 每行元素必定小于等于 (n - i)
4. LCP[i][j] > 0，那么字符串位置[i]和[j]至少是相同的，否则没有common prefix
5. 构造的字符串，必须是[a-z]+
"""
n = len(lcp)
ans = []
# 特判
if not self.validate(lcp):
return ""
# 构造Union Find
uf = UnionFind(n)
for i in range(n):
for j in range(i + 1, n):
if lcp[i][j] > 0:
uf.union(i, j)
# 从最小索引寻找同一组连通分量
# mp: root -> char
mp = {}
ch = ord('a')
for i in range(n):
root = uf.find(i)
if root not in mp:
mp[root] = chr(ch)
ch += 1
if ch > ord('a') + 26:
return ""
ans.append(mp[root])
# 检查ans以及ans构造的LCP
if not self.check_lcp(ans, lcp):
return ""
return ''.join(ans)
--【贰】--：
今天做了三道 hot 100 的经典题。
53. 最大子数组和 - 力扣（LeetCode）
动态规划写法：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 这题似乎是基础动态规划题
// 当当前和为负数时就从下一个位置重新开始，期间不断更新结果
int res=nums[0];
int currSum=0;
for(int i=0;i<nums.size();i++){
if(currSum<0){
currSum=nums[i];
}else{
currSum+=nums[i];
}
res=max(res,currSum);
}
return res;
}
};
分治写法，稍微慢一些，不过这个分治处理的思想值得回顾：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 这题还可以用分治法做
// 分治法要考虑中间横跨的部分
auto div = [&](auto&& self, int left, int right){
if(left==right){
return nums[left];
}
int mid=(left+right)>>1;
// 拿到左右各自的最大和
int leftMaxSum=self(self,left,mid);
int rightMaxSum=self(self,mid+1,right);
// 除此之外还要算一下横跨中间部分的最大和
// 以 mid 为中线向两边延展计算后缀和前缀最大和
// 之所以是后缀和前缀，是因为要保证是连续子数组
int postSum=-1e9;
int currSum=0;
for(int i=mid;i>=left;i--){
currSum+=nums[i];
postSum=max(postSum,currSum);
}
int preSum=-1e9;
currSum=0;
for(int i=mid+1;i<=right;i++){
currSum+=nums[i];
preSum=max(preSum,currSum);
}
// 要不取左边的、要不取右边的，要不取横跨中间的
return max(leftMaxSum,max(rightMaxSum,postSum+preSum));
};
return div(div,0,nums.size()-1);
}
};
42. 接雨水 - 力扣（LeetCode）
极其经典的接雨水，短木板原理。
class Solution {
public:
int trap(vector<int>& height) {
// 依旧短木板原理
// 从左至右、从右至左扫描生成前后缀最大值
int n=height.size();
vector<int> prefix(n,0),postfix(n,0);
prefix[0]=height[0];
postfix[n-1]=height[n-1];
for(int i=1;i<n;i++){
prefix[i]=max(prefix[i-1],height[i]);
postfix[n-1-i]=max(postfix[n-i],height[n-1-i]);
}
// 然后再扫描一遍，每个位置前缀和后缀最低高度决定了储水量
int res=0;
for(int i=1;i<n-1;i++){
// 别忘了每个位置自己还有个高度要减去
res+=max(0,min(prefix[i-1],postfix[i+1])-height[i]);
}
return res;
}
};
300. 最长递增子序列 - 力扣（LeetCode）
经典动态规划题，注意最长递增子序列不一定是以 n-1 结尾，因此在递推过程中就要不断更新结果。
O(n^2) 解法：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// 最长递增子序列，动规题
// dp[i] 代表 0...i 的最长严格递增子序列长度
int n=nums.size();
vector<int> dp(n,0);
// 显然 dp[0] 为 1
dp[0]=1;
int res=1; // 至少是 1
// 发现输入规模不大，这题可以 O(n^2) 解决
for(int i=1;i<n;i++){
dp[i]=1; // 默认情况下为 1
for(int j=0;j<i;j++){
if(nums[j]<nums[i]){
// 出现了严格递增，在前面的状态上 +1 取最大值
dp[i]=max(dp[i],dp[j]+1);
}
}
// 注意！递增子序列不一定是以 n-1 结尾，中途可能有最长递增子序列！
// 因此在推演过程中就要根据 dp[i] 更新结果
res=max(res,dp[i]);
}
return res;
}
};
--【叁】--：
每日一题
--【肆】--：
并查集本身就必须得有一大段，这没办法，都是正常情况
--【伍】--：
做晕了TAT
--【陆】--：
994. 腐烂的橘子 - 力扣（LeetCode）
994. 腐烂的橘子 - 在给定的m x n网格grid中，每个单元格可以有以下三个值之一： * 值0代表空单元格； * 值1代表新鲜橘子； * 值2代表腐烂的橘子。 每分钟，腐烂的橘子周围4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回-1。 示例...
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
ans = 0
m, n = len(grid), len(grid[0])
dq = deque()
cnt = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
cnt += 1
elif grid[i][j] == 2:
dq.append((i, j))
while cnt and len(dq) > 0:
ans += 1
l = len(dq)
for _ in range(l):
i, j = dq.popleft()
if i - 1 >= 0 and grid[i - 1][j] == 1:
grid[i - 1][j] = 2
cnt -= 1
dq.append((i - 1, j))
if i + 1 < m and grid[i + 1][j] == 1:
grid[i + 1][j] = 2
cnt -= 1
dq.append((i + 1, j))
if j - 1 >= 0 and grid[i][j - 1] == 1:
grid[i][j - 1] = 2
cnt -= 1
dq.append((i, j - 1))
if j + 1 < n and grid[i][j + 1] == 1:
grid[i][j + 1] = 2
cnt -= 1
dq.append((i, j + 1))
return -1 if cnt else ans
2573. 找出对应 LCP 矩阵的字符串 - 力扣（LeetCode）
2573. 找出对应 LCP 矩阵的字符串 - 对任一由 n 个小写英文字母组成的字符串 word ，我们可以定义一个 n x n 的矩阵，并满足： * lcp[i][j] 等于子字符串word[i,...,n-1] 和 word[j,...,n-1] 之间的最长公共前缀的长度。 给你一个 n x n 的矩阵 lcp 。返回与 lcp 对应的、按字典序最小的字符串word 。如果不存在这样的字符串，则返回空字符串。 对于长度相同的两个字符串 a 和 b ，如果在 a 和 b...
思路
题目到不是太难
- 根据lcp，如果
chr[i]=chr[j]那么lcp[i][j]>0，可以确定这个字符的内容。(PS，如果超过26位字符要返回空字符串) - 之前我们通过第一个字符是否相同做了判断，长度是否一致无法确定，所以要进行验证。
- 对角线肯定是n-1..1
- 对角线分割的上下三角对称
- 只验证上三角或者下三角。如果字符不相同，
lcp[i][j]=0。否则lcp[i][j]=lcp[i+1][j+1]+1（边界为lcp[x][n-1]=1
PS 通过递推dp[i][j]时间复杂度也是一样的。
代码
class Solution {
public String findTheString(int[][] lcp) {
int n = lcp.length;
char[] ans = new char[n];
char chr = 'a';
// 获取字符串
for (int i = 0; i < n; i++) {
if (ans[i] > 0) {
continue;
}
if (chr > 'z') {
return "";
}
ans[i] = chr++;
for (int j = i + 1; j < n; j++) {
if (lcp[i][j] > 0) {
ans[j] = ans[i];
}
}
}
// 验证1，对角线
for (int i = 0; i < n; i++) {
if (lcp[i][i] != n - i) {
return "";
}
}
// 验证2，上下三角对称
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (lcp[i][j] != lcp[j][i]) {
return "";
}
}
}
// 验证3，上三角数值有效
for (int i = n - 2; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (ans[i] != ans[j]) {
if (lcp[i][j] > 0) {
return "";
}
} else {
// 最右边是1，之后向左上依次+1
if (j == n - 1) {
if (lcp[i][j] != 1) {
return "";
}
} else if (lcp[i][j] != lcp[i + 1][j + 1] + 1) {
return "";
}
}
}
}
return new String(ans);
}
}
网友解答：
--【壹】--：
怎么做到这么短的，看完你的，我觉得我写的简直就是一坨
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [0] * size
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
rootA = self.find(a)
rootB = self.find(b)
if rootA == rootB:
return
if self.rank[rootA] < self.rank[rootB]:
self.parent[rootA] = rootB
elif self.rank[rootA] > self.rank[rootB]:
self.parent[rootB] = rootA
else:
self.parent[rootB] = rootA
self.rank[rootA] += 1
def connected(self, a, b):
return self.find(a) == self.find(b)
class Solution:
def validate(self, lcp: List[List[int]]) -> bool:
n = len(lcp)
for i in range(n):
if lcp[i][i] != n - i:
return False
for j in range(i + 1, n):
if lcp[i][j] > n - i:
return False
return all(lcp[i][j] == lcp[j][i] for i in range(n) for j in range(i+1, n))
def check_lcp(self, word: List[str], lcp: List[List[int]]) -> bool:
n = len(word)
for i in range(n):
for j in range(i + 1, n):
expected = 0
if word[i] == word[j]:
if i + 1 < n and j + 1 < n:
expected = lcp[i + 1][j + 1] + 1
else:
expected = 1
if lcp[i][j] != expected:
return False
return True
def findTheString(self, lcp: List[List[int]]) -> str:
"""
1. LCP矩阵对称
2. LCP矩阵对角线从n递减至1
3. 每行元素必定小于等于 (n - i)
4. LCP[i][j] > 0，那么字符串位置[i]和[j]至少是相同的，否则没有common prefix
5. 构造的字符串，必须是[a-z]+
"""
n = len(lcp)
ans = []
# 特判
if not self.validate(lcp):
return ""
# 构造Union Find
uf = UnionFind(n)
for i in range(n):
for j in range(i + 1, n):
if lcp[i][j] > 0:
uf.union(i, j)
# 从最小索引寻找同一组连通分量
# mp: root -> char
mp = {}
ch = ord('a')
for i in range(n):
root = uf.find(i)
if root not in mp:
mp[root] = chr(ch)
ch += 1
if ch > ord('a') + 26:
return ""
ans.append(mp[root])
# 检查ans以及ans构造的LCP
if not self.check_lcp(ans, lcp):
return ""
return ''.join(ans)
--【贰】--：
今天做了三道 hot 100 的经典题。
53. 最大子数组和 - 力扣（LeetCode）
动态规划写法：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 这题似乎是基础动态规划题
// 当当前和为负数时就从下一个位置重新开始，期间不断更新结果
int res=nums[0];
int currSum=0;
for(int i=0;i<nums.size();i++){
if(currSum<0){
currSum=nums[i];
}else{
currSum+=nums[i];
}
res=max(res,currSum);
}
return res;
}
};
分治写法，稍微慢一些，不过这个分治处理的思想值得回顾：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 这题还可以用分治法做
// 分治法要考虑中间横跨的部分
auto div = [&](auto&& self, int left, int right){
if(left==right){
return nums[left];
}
int mid=(left+right)>>1;
// 拿到左右各自的最大和
int leftMaxSum=self(self,left,mid);
int rightMaxSum=self(self,mid+1,right);
// 除此之外还要算一下横跨中间部分的最大和
// 以 mid 为中线向两边延展计算后缀和前缀最大和
// 之所以是后缀和前缀，是因为要保证是连续子数组
int postSum=-1e9;
int currSum=0;
for(int i=mid;i>=left;i--){
currSum+=nums[i];
postSum=max(postSum,currSum);
}
int preSum=-1e9;
currSum=0;
for(int i=mid+1;i<=right;i++){
currSum+=nums[i];
preSum=max(preSum,currSum);
}
// 要不取左边的、要不取右边的，要不取横跨中间的
return max(leftMaxSum,max(rightMaxSum,postSum+preSum));
};
return div(div,0,nums.size()-1);
}
};
42. 接雨水 - 力扣（LeetCode）
极其经典的接雨水，短木板原理。
class Solution {
public:
int trap(vector<int>& height) {
// 依旧短木板原理
// 从左至右、从右至左扫描生成前后缀最大值
int n=height.size();
vector<int> prefix(n,0),postfix(n,0);
prefix[0]=height[0];
postfix[n-1]=height[n-1];
for(int i=1;i<n;i++){
prefix[i]=max(prefix[i-1],height[i]);
postfix[n-1-i]=max(postfix[n-i],height[n-1-i]);
}
// 然后再扫描一遍，每个位置前缀和后缀最低高度决定了储水量
int res=0;
for(int i=1;i<n-1;i++){
// 别忘了每个位置自己还有个高度要减去
res+=max(0,min(prefix[i-1],postfix[i+1])-height[i]);
}
return res;
}
};
300. 最长递增子序列 - 力扣（LeetCode）
经典动态规划题，注意最长递增子序列不一定是以 n-1 结尾，因此在递推过程中就要不断更新结果。
O(n^2) 解法：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// 最长递增子序列，动规题
// dp[i] 代表 0...i 的最长严格递增子序列长度
int n=nums.size();
vector<int> dp(n,0);
// 显然 dp[0] 为 1
dp[0]=1;
int res=1; // 至少是 1
// 发现输入规模不大，这题可以 O(n^2) 解决
for(int i=1;i<n;i++){
dp[i]=1; // 默认情况下为 1
for(int j=0;j<i;j++){
if(nums[j]<nums[i]){
// 出现了严格递增，在前面的状态上 +1 取最大值
dp[i]=max(dp[i],dp[j]+1);
}
}
// 注意！递增子序列不一定是以 n-1 结尾，中途可能有最长递增子序列！
// 因此在推演过程中就要根据 dp[i] 更新结果
res=max(res,dp[i]);
}
return res;
}
};
--【叁】--：
每日一题
--【肆】--：
并查集本身就必须得有一大段，这没办法，都是正常情况
--【伍】--：
做晕了TAT
--【陆】--：
994. 腐烂的橘子 - 力扣（LeetCode）
994. 腐烂的橘子 - 在给定的m x n网格grid中，每个单元格可以有以下三个值之一： * 值0代表空单元格； * 值1代表新鲜橘子； * 值2代表腐烂的橘子。 每分钟，腐烂的橘子周围4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回-1。 示例...
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
ans = 0
m, n = len(grid), len(grid[0])
dq = deque()
cnt = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
cnt += 1
elif grid[i][j] == 2:
dq.append((i, j))
while cnt and len(dq) > 0:
ans += 1
l = len(dq)
for _ in range(l):
i, j = dq.popleft()
if i - 1 >= 0 and grid[i - 1][j] == 1:
grid[i - 1][j] = 2
cnt -= 1
dq.append((i - 1, j))
if i + 1 < m and grid[i + 1][j] == 1:
grid[i + 1][j] = 2
cnt -= 1
dq.append((i + 1, j))
if j - 1 >= 0 and grid[i][j - 1] == 1:
grid[i][j - 1] = 2
cnt -= 1
dq.append((i, j - 1))
if j + 1 < n and grid[i][j + 1] == 1:
grid[i][j + 1] = 2
cnt -= 1
dq.append((i, j + 1))
return -1 if cnt else ans