一、题目
//某系统中有一空间连续的内存,被划分成多个大小相同的内存块。内存的使用状态记录在字符串 memory 中,每个内存块的状态用字符 x 或 . 表示,其中:
//· . 表示该内存块空闲;
//· x 表示该内存块被使用,x 为小写字母。
//现在可释放其中 最多 cnt 个内存块(即字符串中的 x 变成 .),以获得一块空间连续的、且 最长的 空闲内存,请计算并返回该最长空闲内存的内存块数量。
//示例 1:
//输入:
//memory = "..x..x..xx..."
//cnt = 2
//输出:8
//解释:
//
//将 memory[2] 与 memory[5] 的内存块释放,可获得从 memory[0] 到 memory[7]、长度为 8 的连续空闲内存;
//将 memory[5] 与 memory[8] 的内存块释放,可获得从 memory[3] 到 memory[8]、长度为 6 的连续空闲内存;
//将 memory[8] 与 memory[9] 的内存块释放,可获得从 memory[6] 到 memory[12]、长度为 7 的连续空闲内存;
//其他释放方式获得的连续空闲内存都小于 8;
//因此返回 8。
//示例 2:
//输入:
//memory = "....x."
//cnt = 3
//输出:6
//示例 3:
//输入:
//memory = "xx.x..xx....x..."
//cnt = 0
//输出:4
//提示:0 <= cnt <= memory.length <= 10^5
分析:首先这道题采用双指针,我们先拆解,也就是一个字符串连续.最大值,然后就是替换x;将替换后的字符串带入求最大的函数中,即可求解。有了思路之后,编码就比较简单了,但是仍然需要考虑一些边界问题,保证代码健壮。
go 语言版本
func main() {
in := bufio.NewReader(os.Stdin)
b,_,_ := in.ReadLine()
memory := string(b)
b,_,_ = in.ReadLine()
newMemory := memory
cnt,_ := strconv.Atoi(string(b))
temp := 0
i := 0
max := 0
if cnt == 0 {
fmt.Println(FindMax(memory))
return
}
for {
if i >= len(memory) {
break
}
for j := i;j < len(memory);j++ {
if fmt.Sprintf("%c",memory[j]) == "x" {
memory = memory[0:j]+"."+memory[j+1:]
temp++
if temp == cnt {
max = int(math.Max(float64(FindMax(memory)),float64(max)))
temp = 0
memory = newMemory
break
}
}
}
if temp < cnt {
max = int(math.Max(float64(FindMax(memory)),float64(max)))
temp = 0
memory = newMemory
}
i++
}
fmt.Println(max)
}
//找连续最大
func FindMax(str string) int {
i := 0
j := 0
max := 0
for {
if i >= len(str) {
break
}
temp := 0
if fmt.Sprintf("%c",str[i]) == "." {
j = i
}
for {
if j >= len(str) {
break
}
if str[i] == str[j] && fmt.Sprintf("%c",str[i]) == "." {
temp++
j++
}else {
break
}
}
max = int(math.Max(float64(max),float64(temp)))
i = j
if i < len(str) && fmt.Sprintf("%c",str[i]) != "." {
i++
j = i
}
}
return max
}
java 版本
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String memory = sc.nextLine();
String newMemory = memory;
char[] ch = memory.toCharArray();
int cnt = sc.nextInt();
if (cnt == 0) {
System.out.println(findMax(memory));
return;
}
int temp = 0;
int res = 0;
int j = 0;
while(j < ch.length) {
for(int i = j;i<ch.length;i++) {
if (ch[i] == 'x') {
ch[i] = '.';
temp++;
}
if (temp == cnt) {
res = Math.max(findMax(String.valueOf(ch)),res);
temp = 0;
ch = newMemory.toCharArray();
}
}
if (temp < cnt) {
res = Math.max(findMax(String.valueOf(ch)),res);
temp = 0;
ch = newMemory.toCharArray();
}
j++;
}
System.out.println(res);
return;
}
public static int findMax(String s) {
char[] ch = s.toCharArray();
int i = 0,j = 0,max = 0;
while(i < ch.length) {
int temp = 0;
if (ch[i] == '.') {
j = i;
}
while(j < ch.length) {
if(ch[i] == ch[j] && ch[i] == '.') {
temp++;
j++;
}else {
break;
}
}
max = Math.max(temp,max);
i++;
}
return max;
}
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁