网站开发的费用是怎么计算的,上传附件空间网站,就有公司域名怎么建设网站,做 cad效果图网站文章目录1. 题目2. 解题1. 题目
街上有 n 栋房子整齐地排成一列#xff0c;每栋房子都粉刷上了漂亮的颜色。给你一个下标从 0 开始且长度为 n 的整数数组 colors #xff0c;其中 colors[i] 表示第 i 栋房子的颜色。
返回 两栋 颜色 不同 房子之间的 最大 距离。
第 i 栋房…
文章目录1. 题目2. 解题1. 题目
街上有 n 栋房子整齐地排成一列每栋房子都粉刷上了漂亮的颜色。给你一个下标从 0 开始且长度为 n 的整数数组 colors 其中 colors[i] 表示第 i 栋房子的颜色。
返回 两栋 颜色 不同 房子之间的 最大 距离。
第 i 栋房子和第 j 栋房子之间的距离是 abs(i - j) 其中 abs(x) 是 x 的绝对值。
示例 1
输入colors [1,1,1,6,1,1,1]
输出3
解释上图中颜色 1 标识成蓝色颜色 6 标识成红色。
两栋颜色不同且距离最远的房子是房子 0 和房子 3 。
房子 0 的颜色是颜色 1 房子 3 的颜色是颜色 6 。
两栋房子之间的距离是 abs(0 - 3) 3 。
注意房子 3 和房子 6 也可以产生最佳答案。示例 2 输入colors [1,8,3,8,3]
输出4
解释上图中颜色 1 标识成蓝色颜色 8 标识成黄色颜色 3 标识成绿色。
两栋颜色不同且距离最远的房子是房子 0 和房子 4 。
房子 0 的颜色是颜色 1 房子 4 的颜色是颜色 3 。两栋房子之间的距离是 abs(0 - 4) 4 。示例 3
输入colors [0,1]
输出1
解释两栋颜色不同且距离最远的房子是房子 0 和房子 1 。
房子 0 的颜色是颜色 0 房子 1 的颜色是颜色 1 。两栋房子之间的距离是 abs(0 - 1) 1 。提示
n colors.length
2 n 100
0 colors[i] 100
生成的测试数据满足 至少 存在 2 栋颜色不同的房子来源力扣LeetCode 链接https://leetcode-cn.com/problems/two-furthest-houses-with-different-colors 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
暴力枚举
class Solution {
public:int maxDistance(vectorint colors) {vectorint pos(101, -1); // 记录每种颜色的最左边的位置int ans 0;for(int i 0; i colors.size(); i){if(pos[colors[i]] -1)pos[colors[i]] i;for(int j 0; j 100; j){if(j ! colors[i] pos[j] ! -1)// 颜色不相同且 存在ans max(ans, i-pos[j]);}}return ans;}
};8 ms 8.9 MB C
优化做法判断首尾是否一样不一样直接返回答案否则在中间找到一个不一样的颜色返回到两个端点较大的距离时间复杂度 O(n)
class Solution {
public:int maxDistance(vectorint colors) {if(colors[0] ! colors.back()) return colors.size()-1;int ans 0, n colors.size();for(int i 1; i n-1; i){if(colors[i] ! colors[0]){ans max(ans, max(i, n-1-i));}}return ans;}
};4 ms 8.8 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
