红绿正方形染色问题
2023-02-18 16:35:16 时间
红绿正方形染色问题
作者:Grey
原文地址:
题目描述
有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。目标是在完成染色之后,每个红色 R 都比每个绿色 G 距离最左侧近。 返回最少需要涂染几个正方形,示例: s = RGRGR,我们涂染之后变成 RRRGG 满足要求了,涂染的个数为 2, 没有比这个更好的涂染方案。
题目链接见:牛客:红和绿
思路
要满足染色后,每个红色 R 都比每个绿色 G 距离最左侧近,只有可能是下述三种情况:
-
R 都在左边,G 都在右边;
-
全 G;
-
全 R。
定义两个数组
int[] leftG = new int[N];
leftG[i]
表示 i 位置的左边包括 i 在内有几个 G。
通过从右往左遍历一次数组可以预处理得到leftG
数组。
int[] rightR = new int[N];
rightR[i]
表示 i 位置右边包括 i 在内有几个 R。
通过从左往右遍历一次数组可以预处理得到rightR
数组
如果rightR[0] == N || leftG[N - 1] == N
,说明数组全为 R 或者全为 G,此时无需染色,直接返回 0。
如果是普遍情况,那就直接判断每个位置为分割点,左侧都变为 R,右侧都变为 G,需要的最小染色次数是多少,即:leftG[i] + rightR[i] - 1
,之所以要减 1 是因为重复算了 i 位置的情况。
完整代码见
import java.util.Scanner;
// R都在左边,G都在右边,或者全G,全R
public class Main {
// 两个预处理数组
// TODO 空间方面可以优化
public static int minColors(String str) {
if (str == null || str.length() <= 1) {
return 0;
}
char[] strs = str.toCharArray();
int N = strs.length;
// leftG[i]表示左边包括i在内有几个G
int[] leftG = new int[N];
// rightR[i]表示右边包括i在内有几个R
int[] rightR = new int[N];
for (int i = 0; i < N; i++) {
if (strs[i] == 'G') {
if (i == 0) {
leftG[i]++;
} else {
leftG[i] = leftG[i - 1] + 1;
}
} else {
if (i != 0) {
leftG[i] = leftG[i - 1];
}
}
}
for (int i = N - 1; i >= 0; i--) {
if (strs[i] == 'R') {
if (i == N - 1) {
rightR[i]++;
} else {
rightR[i] = rightR[i + 1] + 1;
}
} else {
if (i != N - 1) {
rightR[i] = rightR[i + 1];
}
}
}
// 全R或者全G的情况
if (rightR[0] == N || leftG[N - 1] == N ) {
return 0;
}
int min = N;
for (int i = 0; i < N; i++) {
// 之所以要-1是因为重复算了i位置的处理情况
min = Math.min(leftG[i] + rightR[i] - 1, min);
}
return min;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String colors = in.nextLine();
System.out.println(minColors(colors));
in.close();
}
}
空间复杂度O(N)
,时间复杂度O(N)
。
更多
相关文章
- 数说,世界杯让你印象最深刻的面孔
- 记一次docker虚拟机横向移动渗透测试
- 华为秋招面经分享!
- 面试官:如何保证接口幂等性?一口气说了12种方法!
- 网易秋招高频面试题汇总
- 《前端图形学实战》几何学在前端边界计算中的应用和原理分析
- 前端图形学实战: 从零实现编辑器的图层管理面板和实时缩略图(vue3 + vite版)
- 结构建模设计——Solidworks软件之装配体操作基本总结一(装配体功能界面简介、插入零件操作、基本配合操作)
- 程序员如何准备好一次面试
- 面试问到DCL失效不知所措
- Kafka大厂高频面试题:在保证高性能、高吞吐的同时保证高可用性
- 域渗透-横向移动命令总结
- PHP程序员面试时经常会被考的冒泡排序算法
- Spring框架学习笔记(2)——面向切面编程AOP
- Jsp学习笔记(2)——页面导航、表单、EL表达式
- ArcGIS QGIS学习二:图层如何只显示需要的部分几何面数据(附最新坐标边界下载全国省市区县乡镇)
- 新开源HTML5单文件网页版ACME客户端,可在线申请Let's Encrypt、ZeroSSL免费HTTPS多域名通配符泛域名SSL/TLS证书(RSA/ECC/ECDSA)
- Java开发桌面程序学习(13)——Javafx多线程 下载功能
- 移动端实现HTML5 mp3录音踩坑指南:系统播放音量变小、一些机型录音断断续续 之 MediaRecorder和AudioWorklet的终极对决
- 最新全国省市区县乡镇街道行政区划数据提取(2022年)