我要招人

去企业版

首页 > 试题广场 >

小红的字母填写

[编程题]小红的字母填写

热度指数：434 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红拿到了一排格子，每个格子的背景是红色或者蓝色。

小红希望你将每个格子上填写一个小写字母，需要满足相同的字母的背景颜色是相同的。

小红希望最终出现次数最多的字母的出现次数尽可能小。你能帮帮她吗？

输入描述:

一个仅由字符'0'和'1'组成的字符串，长度不超过200000。
字符串用于表示小红拿到的格子的颜色。第个字符为'0'代表第第个格子为蓝色背景，字符'1'代表红色背景。

输出描述:

一个仅由小写字母构成的字符串，第个字符为第个格子上填写的字母，请务必保证字符串是合法的。如果有多解，输出任意即可。

示例1

输入

输出

abc

说明

'a'为蓝色，'b'为红色，'c'为蓝色。三种字母均只出现了一次

示例2

输入

000000000000000000000000001

输出

bbcdefghijklmnopqrstuvwxyza

说明

我们这个填空方案中，两个'b'都是蓝色，符合题目要求。除了'b'出现2次以外，其余的字母均只出现了1次。

算法知识视频讲解

Handa_Rei

import sys
from math import ceil


def minTime(s: str):
    x = "abcdefghijklmnopqrstuvwxyz"
    n = len(s)
    if n <= 26:
        return x[:n]
    num0 = s.count("0")
    num1 = s.count("1")
    if num0 == 0 or num1 == 0:
        num = max(num0, num1)
        a, b = divmod(num, 26)
        return x * a + x[:b]
    t = 0
    if num0 < num1:
        t = ceil(num0 / (num0 + num1) * 26)
    else:
        t = 26 - ceil(num1 / (num0 + num1) * 26)
    alpha_for0 = x[:t]
    alpha_for1 = x[t:]
    i, j = 0, 0
    ans = ""
    for c in s:
        if c == "0":
            ans += alpha_for0[i]
            i = (i + 1) % len(alpha_for0)
        else:  # c=='1'
            ans += alpha_for1[j]
            j = (j + 1) % len(alpha_for1)
    return ans


s = input()
print(minTime(s))

发表于 2023-08-27 00:20:24 回复(0)

尽量理智的狗狗

输入少于等于26时直接输出。

大于时，根据0/1的数量分配应该给他们的字母的个数，然后从a-z 26个字母里面给他们分配,然后用两个指针赋值。

发表于 2023-09-20 11:55:16 回复(0)

一笑而过2222

, 1

发表于 2025-03-14 16:08:05 回复(1)

牛客197479562号

实在想不通为什么是 Math.ceil

试了 Math.round 会卡在19/20样例；Math.floor 会卡在10/20样例

可是为什么呢，相对少的那个不应该分配相对少一些的字母吗，为什么反而使用ceil向上取整

import java.util.Scanner;
import java.lang.Math.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
        String s = in.nextLine();
        char[] ch = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        if (s.length() <= 26) {
            for (int i = 0; i < s.length(); i++) {
                sb.append((char)('a' + i));
            }
            System.out.println(sb);
        } else {
            int t1 = 0, t0 = 0;
            for (char c : ch) {
                if (c == '0') t0++;
                else t1++;
            }
            if (t0 == 0 || t1 == 0) {
                for(int i=0;i<s.length();i++){
                    sb.append((char)('a'+(i%26)));
                }
            } else {
                // 试了一下 Math.round 会卡在19/20；Math.floor 会卡在10/20  
                // 可是为什么呢，t0是少的那个，不应该分配相对少一点的字母吗，为什么是ceil啊
                if(t0<t1) t0 = (int)(Math.ceil((t0 * 1.0 / (t0 + t1)) * 26));
                else{
                    t0=26-(int)(Math.ceil((t1 * 1.0 / (t0 + t1)) * 26));
                }
               
                //t1 = 26-t0;
                for (int i = 0, tt0 = 0, tt1 = t0; i < s.length(); i++) {
                    if (tt0 == t0) tt0 = 0;
                    if (tt1 == 26) tt1 = t0;
                    if (ch[i] == '0') {
                        sb.append((char)('a' + tt0));
                        tt0++;
                    } else {
                        sb.append((char)('a' + tt1));
                        tt1++;
                    }
                }
            }
            System.out.println(sb);
            //System.out.println(t0+"  "+t1+"   "+t0*1.0/(t0+t1)+"   "+t0*1.0/(t0+t1)*26+"    "+(int)(t0*1.0/(t0+t1)*26));
        }
    }
}

发表于 2024-03-21 20:39:19 回复(0)

爱看剧的孤勇者在秋招

谁能告诉我java如何拿到正确的输入

发表于 2024-01-04 21:11:46 回复(0)

提交观点

问题信息

来自：2023年蚂蚁春招技术...

难度：

5条回答 29收藏 1353浏览

小红的字母填写

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题