题目链接

小红的多彩糖葫芦

题目描述

小红喜欢吃多彩糖葫芦，多彩糖葫芦上的每一个糖葫芦都有一种颜色。但小红有非常严重的强迫症，她绝对不会连续吃两个相同颜色的糖葫芦。一串糖葫芦只能从上往下吃，一旦小红发现下一颗糖葫芦和她刚吃过的糖葫芦颜色相同时，小红就会把整串多彩糖葫芦丢掉。小红想知道她吃一串多彩糖葫芦时可以吃到几颗糖葫芦。

输入:

  • 一个字符串，表示多彩糖葫芦串上从上到下每一颗糖葫芦的颜色

输出:

  • 一个整数，表示小红最多能吃到的糖葫芦数量

解题思路

这是一个模拟问题，可以通过以下步骤解决：

  1. 关键发现：

    • 小红只能从上往下吃
    • 遇到相同颜色就会停止
    • 需要记录上一个吃的糖葫芦的颜色

  2. 模拟策略：

    • 从第一个糖葫芦开始吃
    • 记录上一个吃的糖葫芦颜色
    • 如果下一个糖葫芦颜色相同，就停止
    • 否则继续吃并更新上一个颜色

  3. 具体步骤：

    • 遍历字符串
    • 维护上一个颜色和已吃数量
    • 遇到相同颜色就退出循环

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    
    int ans = 1;  // 第一个糖葫芦一定能吃
    char last = s[0];  // 记录上一个颜色
    
    for(int i = 1; i < s.length(); i++) {
        if(s[i] == last) {  // 遇到相同颜色就停止
            break;
        }
        last = s[i];  // 更新上一个颜色
        ans++;  // 可以吃这个糖葫芦
    }
    
    cout << ans << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        int ans = 1;  // 第一个糖葫芦一定能吃
        char last = s.charAt(0);  // 记录上一个颜色
        
        for(int i = 1; i < s.length(); i++) {
            if(s.charAt(i) == last) {  // 遇到相同颜色就停止
                break;
            }
            last = s.charAt(i);  // 更新上一个颜色
            ans++;  // 可以吃这个糖葫芦
        }
        
        System.out.println(ans);
    }
}

s = input()

ans = 1  # 第一个糖葫芦一定能吃
last = s[0]  # 记录上一个颜色

for i in range(1, len(s)):
    if s[i] == last:  # 遇到相同颜色就停止
        break
    last = s[i]  # 更新上一个颜色
    ans += 1  # 可以吃这个糖葫芦

print(ans)

算法及复杂度

  • 算法：模拟
  • 时间复杂度： - 最多需要遍历整个字符串
  • 空间复杂度： - 只需要常数空间存储变量