Leetcode每日一题 —— 3740. 三个相等元素之间的最小距离 I
- 内容介绍
- 文章标签
- 相关推荐
3740. 三个相等元素之间的最小距离 I - 力扣（LeetCode）
3740. 三个相等元素之间的最小距离 I - 给你一个整数数组 nums。 如果满足 nums[i] == nums[j] == nums[k]，且 (i, j, k) 是 3 个不同下标，那么三元组 (i, j, k) 被称为有效三元组。 有效三元组的距离被定义为 abs(i - j) + abs(j - k) + abs(k - i)，其中 abs(x) 表示 x 的绝对值。 返回一个整数，表示 有效三元组的最小可能距离。如果不存在有效三元组，返回...
PS
昨天的题放弃了。看了解答，眼睛说我会了，脑子说你不会！看着好像会了，一用就稀里糊涂。还得学习啊。
思路
要求的距离肯定是连续三个相同数，因为如果中间隔一个相同数那么一定比连续的三个相同数更长。实质就是求最后一个数的位置减第一个数的位置的两倍。
应该可以用int[]来代替Map，不过今天数据量小，先这样。
代码
public int minimumDistance(int[] nums) {
int n = nums.length;
Map<Integer, List<Integer>> list = new HashMap<>();
for (int i = 0; i < n; i++) {
list.compute(nums[i], (k, v) -> v == null ? new ArrayList<>() : v).add(i);
}
int ans = Integer.MAX_VALUE;
for (Map.Entry<Integer, List<Integer>> pair : list.entrySet()) {
if (pair.getValue().size() < 3) {
continue;
}
for (int i = 2; i < pair.getValue().size(); i++) {
ans = Math.min(ans, 2 * (pair.getValue().get(i) - pair.getValue().get(i - 2)));
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
网友解答：
--【壹】--：
直接用一个滑动窗口的思想可以做到O(N)， 这样的话就一直i < j < k把上面的式子化简一下就是(k - i) * 2
然后惊喜的发现明天的题目也可以过
class Solution:
def minimumDistance(self, nums: List[int]) -> int:
def cc(dq):
return (dq[-1] - dq[0]) << 1
ans = inf
n = len(nums)
cnt = defaultdict(lambda : [0, deque()])
for i, x in enumerate(nums):
cnt[x][0] += 1
cnt[x][1].append(i)
if cnt[x][0] == 3:
ans = min(ans, cc(cnt[x][1]))
cnt[x][1].popleft()
cnt[x][0] -= 1
return ans if ans != inf else -1
--【贰】--：
昨天的题有点变态了，真整不出来，就写 Hot100 去了…
今天这题还行，暴力能过，也能用哈希表。用哈希表的话维护相邻的两个相等数字的下标即可。
class Solution {
public:
int minimumDistance(vector<int>& nums) {
// 这题的规模其实暴力就足够了
// 如果规模变大了可能就得用到哈希表
// 找相邻的三个相同数字对应的位置
// 记录数字对应上一次出现和上上次出现的下标
unordered_map<int, pair<int, int>> nMap;
int res = INT_MAX;
for (int i = 0; i < nums.size(); i++) {
if (nMap.count(nums[i]) == 0) {
// 还没有见过 nums[i]
// first 为上次出现，second 为上上次出现
nMap[nums[i]] = make_pair(i, -1);
} else {
// 否则更新
int lastLastAppear = nMap[nums[i]].second;
int lastAppear = nMap[nums[i]].first;
nMap[nums[i]].second = lastAppear;
nMap[nums[i]].first = i;
if (lastLastAppear != -1) {
res = min(res, i - lastAppear + lastAppear -
lastLastAppear + i - lastLastAppear);
}
}
}
return res == INT_MAX ? -1 : res;
}
};
接下来继续复习 Hot100。
238. 除了自身以外数组的乘积 - 力扣（LeetCode）
- 这题之前做过，用了前缀积和后缀积。但其实不用额外开数组去存后缀积，后缀积可以在计算结果的过程中一起动态构造。这样以来是符合题目要求的 O(1) 空间的（输出数组不算空间）。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n=nums.size();
vector<int> res(n);
res[0]=nums[0];
// 输出数组不算空间，先生成前缀
for(int i=1;i<n;i++){
res[i]=res[i-1]*nums[i];
}
// 然后动态构造后缀，填回结果
res[n-1]=nums[n-1];
int postfix=1;
for(int i=n-1;i>=1;i--){
res[i]=postfix*res[i-1];
postfix*=nums[i];
}
res[0]=postfix;
return res;
}
};
73. 矩阵置零 - 力扣（LeetCode）
- 这种题如果要原地操作，八成需要利用输入数组做标记。这题注意首行首列单独处理即可。
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
// 仅用常量空间的话，必然要在原数组上做标记
// 无非就是要多几道扫描
// 可以利用首行首列来标记
// 但处理的时候首行首列要单独处理，不然标记后不知道首行首列要不要置 0
bool firstRowZero=false,firstColZero=false;
// 先扫描首行首列
int m=matrix.size(),n=matrix[0].size();
for(int i=0;i<m;i++){
if(matrix[i][0]==0){
firstColZero=true;
break;
}
}
for(int j=0;j<n;j++){
if(matrix[0][j]==0){
firstRowZero=true;
break;
}
}
// 再扫描内层，进行标记
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
if(matrix[i][j]==0){
matrix[i][0]=0;
matrix[0][j]=0;
}
}
}
// 处理行列，进行置 0
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
if(matrix[i][0]==0||matrix[0][j]==0){
matrix[i][j]=0;
}
}
}
// 最后处理首行首列
if(firstColZero){
for(int i=0;i<m;i++){
matrix[i][0]=0;
}
}
if(firstRowZero){
for(int j=0;j<n;j++){
matrix[0][j]=0;
}
}
}
};
160. 相交链表 - 力扣（LeetCode）
- 首先是 408 资料上提出的解法，两个链表可能共享后缀，这样的话只需要统计二者长度，让较长链表的指针先走，对齐两个指针后再齐头并进即可。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==nullptr||headB==nullptr){
return nullptr;
}
// 先找到两个链表的长度
int m=0,n=0;
ListNode* ptr1=headA,*ptr2=headB;
while(ptr1!=nullptr){
m++;
ptr1=ptr1->next;
}
while(ptr2!=nullptr){
n++;
ptr2=ptr2->next;
}
// 两个链表后缀可能有相同的部分，让较长的链表的指针先走
ptr1=headA;
ptr2=headB;
if(m>n){
for(int i=0;i<m-n;i++){
ptr1=ptr1->next;
}
}else if(m<n){
for(int i=0;i<n-m;i++){
ptr2=ptr2->next;
}
}
// 两个指针齐头并进
while(ptr1!=nullptr){
if(ptr1==ptr2){
break;
}
ptr1=ptr1->next;
ptr2=ptr2->next;
}
return ptr1;
}
};
- 还有类似链表求环思想的更简洁的思路，但还是和链表长度有关。让两个指针循环扫描各自的链表。链表长度一致，二者要不相遇要不最终一起到达
null；链表长度不一致，二者会错开，但最终总会有相遇（要不相遇在相交节点，要不相遇于虚无的null）。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==nullptr||headB==nullptr){
return nullptr;
}
// 这题 O(1) 空间解法有难度，和链表求环那题有相似的思路
// 很巧妙利用了两个遍历指针循环扫描时的特性，每个指针扫描到头就回到链表头
// 如果两个指针距离相交处距离一致，那么必然会同时指向相交节点；
// 如果没有相交且链表长度一致，则两个指针会同时指向 null
// 否则两个指针会逐渐错开进行循环，直至再次相交，再次相交时要不都是 null，要不是同一个节点
ListNode *ptr1=headA,*ptr2=headB;
while(ptr1!=ptr2){
if(ptr1!=nullptr){
ptr1=ptr1->next;
}else{
ptr1=headA;
}
if(ptr2!=nullptr){
ptr2=ptr2->next;
}else{
ptr2=headB;
}
}
return ptr1;
}
};
101. 对称二叉树 - 力扣（LeetCode）
- 同时先序遍历根节点的左右子树，左子树和右子树的遍历流向相反。
class Solution {
public:
bool isSymmetric(TreeNode* root) {
// 其实就是分成左子树和右子树分别遍历
// 左子树和右子树先序遍历方向相反，检查是否一致
if(root==nullptr){
return true;
}
auto dfs=[&](auto&& self,TreeNode* n1,TreeNode* n2)->bool{
if(n1==nullptr&&n2==nullptr){
return true;
}
if(n1==nullptr||n2==nullptr){
return false;
}
if(n1->val!=n2->val){
return false;
}
return self(self,n1->left,n2->right)&&self(self,n1->right,n2->left);
};
return dfs(dfs,root->left,root->right);
}
};
--【叁】--：
昨天拼尽全力无法办到喵（今天抚慰受伤的心灵
class Solution {
public:
int minimumDistance(vector<int>& nums) {
std::vector<std::vector<int>> v(101,std::vector<int>());
for(int i = 0; i < nums.size(); i++) {
v[nums[i]].push_back(i);
}
const int inf = std::numeric_limits<int>::max();
int res = inf;
for(int i = 0; i < v.size(); i++) {
if(v[i].size() < 3) {
continue;
}
for(int j = 0; j + 2 < v[i].size(); j++) {
res = min(res,2 * (v[i][j + 2] - v[i][j]));
}
}
return (res == inf ? -1 : res);
}
};
3740. 三个相等元素之间的最小距离 I - 力扣（LeetCode）
3740. 三个相等元素之间的最小距离 I - 给你一个整数数组 nums。 如果满足 nums[i] == nums[j] == nums[k]，且 (i, j, k) 是 3 个不同下标，那么三元组 (i, j, k) 被称为有效三元组。 有效三元组的距离被定义为 abs(i - j) + abs(j - k) + abs(k - i)，其中 abs(x) 表示 x 的绝对值。 返回一个整数，表示 有效三元组的最小可能距离。如果不存在有效三元组，返回...
PS
昨天的题放弃了。看了解答，眼睛说我会了，脑子说你不会！看着好像会了，一用就稀里糊涂。还得学习啊。
思路
要求的距离肯定是连续三个相同数，因为如果中间隔一个相同数那么一定比连续的三个相同数更长。实质就是求最后一个数的位置减第一个数的位置的两倍。
应该可以用int[]来代替Map，不过今天数据量小，先这样。
代码
public int minimumDistance(int[] nums) {
int n = nums.length;
Map<Integer, List<Integer>> list = new HashMap<>();
for (int i = 0; i < n; i++) {
list.compute(nums[i], (k, v) -> v == null ? new ArrayList<>() : v).add(i);
}
int ans = Integer.MAX_VALUE;
for (Map.Entry<Integer, List<Integer>> pair : list.entrySet()) {
if (pair.getValue().size() < 3) {
continue;
}
for (int i = 2; i < pair.getValue().size(); i++) {
ans = Math.min(ans, 2 * (pair.getValue().get(i) - pair.getValue().get(i - 2)));
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
网友解答：
--【壹】--：
直接用一个滑动窗口的思想可以做到O(N)， 这样的话就一直i < j < k把上面的式子化简一下就是(k - i) * 2
然后惊喜的发现明天的题目也可以过
class Solution:
def minimumDistance(self, nums: List[int]) -> int:
def cc(dq):
return (dq[-1] - dq[0]) << 1
ans = inf
n = len(nums)
cnt = defaultdict(lambda : [0, deque()])
for i, x in enumerate(nums):
cnt[x][0] += 1
cnt[x][1].append(i)
if cnt[x][0] == 3:
ans = min(ans, cc(cnt[x][1]))
cnt[x][1].popleft()
cnt[x][0] -= 1
return ans if ans != inf else -1
--【贰】--：
昨天的题有点变态了，真整不出来，就写 Hot100 去了…
今天这题还行，暴力能过，也能用哈希表。用哈希表的话维护相邻的两个相等数字的下标即可。
class Solution {
public:
int minimumDistance(vector<int>& nums) {
// 这题的规模其实暴力就足够了
// 如果规模变大了可能就得用到哈希表
// 找相邻的三个相同数字对应的位置
// 记录数字对应上一次出现和上上次出现的下标
unordered_map<int, pair<int, int>> nMap;
int res = INT_MAX;
for (int i = 0; i < nums.size(); i++) {
if (nMap.count(nums[i]) == 0) {
// 还没有见过 nums[i]
// first 为上次出现，second 为上上次出现
nMap[nums[i]] = make_pair(i, -1);
} else {
// 否则更新
int lastLastAppear = nMap[nums[i]].second;
int lastAppear = nMap[nums[i]].first;
nMap[nums[i]].second = lastAppear;
nMap[nums[i]].first = i;
if (lastLastAppear != -1) {
res = min(res, i - lastAppear + lastAppear -
lastLastAppear + i - lastLastAppear);
}
}
}
return res == INT_MAX ? -1 : res;
}
};
接下来继续复习 Hot100。
238. 除了自身以外数组的乘积 - 力扣（LeetCode）
- 这题之前做过，用了前缀积和后缀积。但其实不用额外开数组去存后缀积，后缀积可以在计算结果的过程中一起动态构造。这样以来是符合题目要求的 O(1) 空间的（输出数组不算空间）。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n=nums.size();
vector<int> res(n);
res[0]=nums[0];
// 输出数组不算空间，先生成前缀
for(int i=1;i<n;i++){
res[i]=res[i-1]*nums[i];
}
// 然后动态构造后缀，填回结果
res[n-1]=nums[n-1];
int postfix=1;
for(int i=n-1;i>=1;i--){
res[i]=postfix*res[i-1];
postfix*=nums[i];
}
res[0]=postfix;
return res;
}
};
73. 矩阵置零 - 力扣（LeetCode）
- 这种题如果要原地操作，八成需要利用输入数组做标记。这题注意首行首列单独处理即可。
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
// 仅用常量空间的话，必然要在原数组上做标记
// 无非就是要多几道扫描
// 可以利用首行首列来标记
// 但处理的时候首行首列要单独处理，不然标记后不知道首行首列要不要置 0
bool firstRowZero=false,firstColZero=false;
// 先扫描首行首列
int m=matrix.size(),n=matrix[0].size();
for(int i=0;i<m;i++){
if(matrix[i][0]==0){
firstColZero=true;
break;
}
}
for(int j=0;j<n;j++){
if(matrix[0][j]==0){
firstRowZero=true;
break;
}
}
// 再扫描内层，进行标记
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
if(matrix[i][j]==0){
matrix[i][0]=0;
matrix[0][j]=0;
}
}
}
// 处理行列，进行置 0
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
if(matrix[i][0]==0||matrix[0][j]==0){
matrix[i][j]=0;
}
}
}
// 最后处理首行首列
if(firstColZero){
for(int i=0;i<m;i++){
matrix[i][0]=0;
}
}
if(firstRowZero){
for(int j=0;j<n;j++){
matrix[0][j]=0;
}
}
}
};
160. 相交链表 - 力扣（LeetCode）
- 首先是 408 资料上提出的解法，两个链表可能共享后缀，这样的话只需要统计二者长度，让较长链表的指针先走，对齐两个指针后再齐头并进即可。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==nullptr||headB==nullptr){
return nullptr;
}
// 先找到两个链表的长度
int m=0,n=0;
ListNode* ptr1=headA,*ptr2=headB;
while(ptr1!=nullptr){
m++;
ptr1=ptr1->next;
}
while(ptr2!=nullptr){
n++;
ptr2=ptr2->next;
}
// 两个链表后缀可能有相同的部分，让较长的链表的指针先走
ptr1=headA;
ptr2=headB;
if(m>n){
for(int i=0;i<m-n;i++){
ptr1=ptr1->next;
}
}else if(m<n){
for(int i=0;i<n-m;i++){
ptr2=ptr2->next;
}
}
// 两个指针齐头并进
while(ptr1!=nullptr){
if(ptr1==ptr2){
break;
}
ptr1=ptr1->next;
ptr2=ptr2->next;
}
return ptr1;
}
};
- 还有类似链表求环思想的更简洁的思路，但还是和链表长度有关。让两个指针循环扫描各自的链表。链表长度一致，二者要不相遇要不最终一起到达
null；链表长度不一致，二者会错开，但最终总会有相遇（要不相遇在相交节点，要不相遇于虚无的null）。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==nullptr||headB==nullptr){
return nullptr;
}
// 这题 O(1) 空间解法有难度，和链表求环那题有相似的思路
// 很巧妙利用了两个遍历指针循环扫描时的特性，每个指针扫描到头就回到链表头
// 如果两个指针距离相交处距离一致，那么必然会同时指向相交节点；
// 如果没有相交且链表长度一致，则两个指针会同时指向 null
// 否则两个指针会逐渐错开进行循环，直至再次相交，再次相交时要不都是 null，要不是同一个节点
ListNode *ptr1=headA,*ptr2=headB;
while(ptr1!=ptr2){
if(ptr1!=nullptr){
ptr1=ptr1->next;
}else{
ptr1=headA;
}
if(ptr2!=nullptr){
ptr2=ptr2->next;
}else{
ptr2=headB;
}
}
return ptr1;
}
};
101. 对称二叉树 - 力扣（LeetCode）
- 同时先序遍历根节点的左右子树，左子树和右子树的遍历流向相反。
class Solution {
public:
bool isSymmetric(TreeNode* root) {
// 其实就是分成左子树和右子树分别遍历
// 左子树和右子树先序遍历方向相反，检查是否一致
if(root==nullptr){
return true;
}
auto dfs=[&](auto&& self,TreeNode* n1,TreeNode* n2)->bool{
if(n1==nullptr&&n2==nullptr){
return true;
}
if(n1==nullptr||n2==nullptr){
return false;
}
if(n1->val!=n2->val){
return false;
}
return self(self,n1->left,n2->right)&&self(self,n1->right,n2->left);
};
return dfs(dfs,root->left,root->right);
}
};
--【叁】--：
昨天拼尽全力无法办到喵（今天抚慰受伤的心灵
class Solution {
public:
int minimumDistance(vector<int>& nums) {
std::vector<std::vector<int>> v(101,std::vector<int>());
for(int i = 0; i < nums.size(); i++) {
v[nums[i]].push_back(i);
}
const int inf = std::numeric_limits<int>::max();
int res = inf;
for(int i = 0; i < v.size(); i++) {
if(v[i].size() < 3) {
continue;
}
for(int j = 0; j + 2 < v[i].size(); j++) {
res = min(res,2 * (v[i][j + 2] - v[i][j]));
}
}
return (res == inf ? -1 : res);
}
};