力扣面试经典——12题

💡 参考代码：

/**
 * 将整数转换为罗马数字
 * @param num 输入的整数 (范围: 1 <= num <= 3999)
 * @return 返回对应的罗马数字字符串，调用者负责释放返回的字符串内存
 */
char* intToRoman(int num) {
    // 定义数值数组，包含所有可能的数值（包括特殊的减法形式）
    // 按从大到小的顺序排列，便于贪心算法处理
    int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    
    // 定义与数值数组对应的罗马数字字符串数组
    char* symbols[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    
    // 计算数组长度
    int size = sizeof(values) / sizeof(values[0]);
    
    // 分配结果字符串内存，最大情况下3999对应"MMMDCCCCLXXXXVIIII"，长度不会超过20
    // 但为了安全起见，分配足够大的空间
    char* result = (char*)malloc(20 * sizeof(char));
    // 初始化结果字符串为空字符串
	//strcat 函数要求目标字符串必须是以 \0 结尾的有效C字符串，否则行为未定义
    result[0] = '\0';
    
    // 使用贪心算法，从最大的数值开始处理
    for (int i = 0; i < size; i++) {
        // 当前数字大于等于当前数值时，重复处理
        while (num >= values[i]) {
            // 将对应的罗马数字符号追加到结果字符串
            strcat(result, symbols[i]);
            // 从原数字中减去已处理的数值
            num -= values[i];
        }
    }
    
    return result;
}

📖 总结：

点击展开题目总结

🤔 整数转罗马数字

---

1️⃣ 题目核心信息

🎯 功能描述：将给定的整数按照罗马数字规则转换为对应的罗马数字字符串表示

📥 输入输出：

• 输入：int num - 需要转换的整数，范围为1-3999
• 输出：char* - 返回表示该整数的罗马数字字符串

---

2️⃣ 实现原理

💡 核心思路：采用贪心算法，从最大的罗马数字值开始匹配，逐步减去已匹配的值，直到数值为0

📋 实现步骤：

1. 预先定义所有可能的数值和对应的罗马数字符号（包括特殊减法形式）
2. 创建结果字符串并初始化为空
3. 从最大值开始遍历数值数组
4. 对于每个数值，只要原数字大于等于它，就将对应符号添加到结果中并减去该数值
5. 重复步骤4直到原数字变为0，返回结果字符串

---

3️⃣ 关键点解析

🎯 代码技巧

• 使用并行数组存储数值和符号，便于同步处理
• 采用贪心策略，每次都选择能匹配的最大数值
• 预先处理特殊减法形式（如4=IV, 9=IX等），简化主逻辑

4️⃣ 使用场景

✅ 适用情况：

• 数字转换系统中的罗马数字表示
• 教学或演示数字系统转换
• 历史文献或特殊格式的数字显示

⚠️ 前提条件：

• 输入必须是1到3999之间的整数
• 只能处理正整数，不支持0或负数

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(1) - 虽然是循环结构，但处理的数值范围有限，最多处理13种不同的数值

• 💾 空间复杂度：O(1) - 使用固定大小的数组和有限长度的结果字符串

6️⃣ 注意事项

🚩 边界情况：

• 输入为1时，应返回"I"
• 输入为3999时，应返回"MMMCMXCIX"
• 输入为特殊减法形式如4、9、40等

💥 易错点：

• 忘记处理特殊减法形式（4、9、40、90、400、900）
• 数值数组和符号数组不同步或顺序错误
• 内存管理问题，忘记释放动态分配的内存
• 没有考虑输入范围限制

加载评论中...