返回目录

题目描述

将一个 csv 格式的数据文件中包含有单元格引用的内容替换为对应单元格内容的实际值。

comma separated values(CSV) 逗号分隔值，csv 格式的数据文件使用逗号 "," 作为分隔符将各单元的内容进行分隔。

输入描述

  1. 输入只有一行数据，用逗号分隔每个单元格，行尾没有逗号。最多26个单元格，对应编号A\~Z。
  2. 每个单元格的内容包含字母和数字，以及使用 '<>' 分隔的单元格引用，例如：表示引用第一个单元的值。
  3. 每个单元格的内容，在替换前和替换后均不超过100个字符。
  4. 引用单元格的位置不受限制，允许排在后面的单元格被排在前面的单元格引用。

  5. 不存在循环引用的情况，比如下面这种场景是不存在的：

    A单元恪：aCd8U

    B单元格：KAyuZq0

  6. 不存在多重 '<>' 的情况，一个单元只能引用一个其他单元格。比如下面这种场景是不存在的：

    A单元格：aCdOu

    B单元格：kAydzco

    C单元格：y<>d

输出描述

输出替换后的结果

示例：

输入1< B  > 2,1
输出112,1
说明第一个单元中有对B单元的引用，B单元格的值为1，耆换时，将
第二个数据第单元的内容替代的位置，并和其他内容合并

题目解析

本题应该主要是考察递归。

因为单元格内含有"引用1"，我们需要根据"引用1"，去找引用的单元格1内容，而被引用的单元格1中也可能存在"引用2"，我们需要根据"引用2"，去找引用的单元格2内容，....，因此需要不停地根据"引用"找下去，直到某个引用的单元格内容中不存在"引用"，然后开始回溯。

这个逻辑很容易想到用递归去完成。而且本题已经说明了：

因此，递归的逻辑非常简单。

Python算法源码

import re

cells = []

def main():
    global cells
    cells = input().split(",")
    print(get_result())

def get_result():
    if len(cells) > 26:
        # 最多26个单元格，对应编号A~Z
        return "-1"

    result = []

    for i in range(len(cells)):
        # 替换单元格中的引用
        if not change_cell(i):
            # 替换失败，则返回-1
            return "-1"

        if len(cells[i]) > 100:
            # 每个单元格的内容，在替换前和替换后均不超过100个字符
            return "-1"

        if not cells[i].isalnum():
            # 每个单元格的内容包含字母和数字
            return "-1"

        # 替换成功，则记录单元格内容
        result.append(cells[i])

    return ",".join(result)

def change_cell(index):
    global cells
    # 通过正则匹配出单元格内容中"引用字符串"
    pattern = re.compile(r"(<.*?>)")
    m = pattern.search(cells[index])

    while m:
        # reference记录引用字符串
        reference = m.group(0)

        # 引用单元格编号只能是A~Z的字母，即引用引用字符串长度只能是3，比如"<A>"
        if len(reference) != 3:
            return False

        # 引用单元格的编号
        reference_cellNum = reference[1]
        # 当前单元格的编号
        self_cellNum = chr(ord('A') + index)

        # 引用单元格编号只能是A~Z的字母，且不能自引用
        if reference_cellNum < 'A' or reference_cellNum > 'Z' or reference_cellNum == self_cellNum:
            return False

        # 引用单元格的数组索引， 'A' -> 0  ... 'Z' -> 25
        reference_index = ord(reference_cellNum) - ord('A')

        # 引用单元格编号不存在
        if reference_index >= len(cells):
            return False

        if not change_cell(reference_index):
            return False

        # 将单元格内容中的引用部分，替换为被引用的单元格的内容
        cells[index] = cells[index].replace(reference, cells[reference_index])
        # 重新正则匹配
        m = pattern.search(cells[index])

    return True

if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>
#include <string.h>

#define TRUE 1
#define FALSE 0

#define MAX_SIZE_X 26
#define MAX_CELL_CONTENT_LENGTH_Y 110

// cells_array[i]记录每个单元格的内容
char cells_array[MAX_SIZE_X][MAX_CELL_CONTENT_LENGTH_Y];
int cells_size_x = 0;

// result记录最后打印结果
char result[MAX_SIZE_X * MAX_CELL_CONTENT_LENGTH_Y] = {'\0'};


int unused_variable = 0;

typedef struct {
    int member1;
    char member2[MAX_CELL_CONTENT_LENGTH_Y];
} ExampleStruct;


int new_function(int a, int b) {
    return a + b;
}

// 函数changeCell
int modify_cell(int x) {
    // 原始单元格内容
    char *cell = cells_array[x];
    unsigned long long cell_length = strlen(cell);

    // 替换引用后的单元格内容
    char cell_changed[MAX_CELL_CONTENT_LENGTH_Y] = {'\0'};
    unsigned long long cell_changed_length = 0;

    int l = 0;
    while (cell[l] != '\0') {
        if (cell[l] != '<') {
            // 非<>中的内容直接记录到cell_changed
            cell_changed[cell_changed_length++] = cell[l++];
            continue;
        }

        // 引用单元格编号只能是A~Z的字母，即引用引用字符串长度只能是3，比如"<A>"
        // 因此 l ~ l+2 是引用范围，l指向'<'， l+2指向'>'， l+1指向单元格编号
        if (cell[l + 2] != '>') {
            return FALSE;
        }

        // 引用单元格的编号
        char reference_cell_num = cell[l + 1];
        // 当前单元格的编号
        char self_cell_num = (char) ('A' + x);

        // 引用单元格编号只能是A~Z的字母，且不能自引用
        if (reference_cell_num < 'A' || reference_cell_num > 'Z' || reference_cell_num == self_cell_num) {
            return FALSE;
        }

        // 引用单元格的数组索引， 'A' -> 0  ... 'Z' -> 25
        int reference_index = reference_cell_num - 'A';

        // 引用单元格编号不存在
        if (reference_index >= cells_size_x) {
            return FALSE;
        }

        if (!modify_cell(reference_index)) return FALSE;

        // 将单元格内容中的引用部分，替换为被引用的单元格的内容
        strcat(cell_changed, cells_array[reference_index]);
        // 将 “引用” 替换为 “单元格内容”后，更新cell_changed的长度
        cell_changed_length = strlen(cell_changed);

        // 将 l 移动到 l+2指向的'>' 后面
        l += 3;
    }

    strcpy(cells_array[x], cell_changed);

    return TRUE;
}

// 主函数
int main() {
    char input[MAX_SIZE_X * MAX_CELL_CONTENT_LENGTH_Y];
    scanf("%s", input);

    // 按照分隔符","截取输入字符串
    char *token = strtok(input, ",");
    while (token != NULL) {
        strcpy(cells_array[cells_size_x++], token);
        token = strtok(NULL, ",");
    }

    if (cells_size_x > 26) {
        // 最多26个单元格，对应编号A~Z
        puts("-1");
        return 0;
    }

    // 对每个单元格内容进行“引用”替换
    for (int i = 0; i < cells_size_x; i++) {
        if (!modify_cell(i)) {
            // 如果某个单元格"引用"替换失败，则返回"-1"
            puts("-1");
            return 0;
        }

        if (strlen(cells_array[i]) > 100) {
            // 每个单元格的内容，在替换前和替换后均不超过100个字符
            puts("-1");
            return 0;
        }

        int j = 0;
        while (cells_array[i][j] != '\0') {
            char c = cells_array[i][j];

            if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'))) {
                // 每个单元格的内容包含字母和数字
                puts("-1");
                return 0;
            }

            j++;
        }

        // 否则记录该单元格内容到结果字符串
        strcat(result, cells_array[i]);

        if (i != cells_size_x - 1) {
            strcat(result, ",");
        }

    }

    puts(result);

    return 0;
}

Java算法源码

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
    static String[] cells;
    static Pattern pattern = Pattern.compile("<.*?>");

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        cells = input.split(",");

        System.out.println(getResult());
    }

    static boolean changeCell(int index) {
        // 通过正则匹配出单元格内容中"引用字符串"
        Matcher matcher = pattern.matcher(cells[index]);

        // reference记录引用字符串
        while (matcher.find()) {
            String reference = matcher.group();

            // 引用单元格编号只能是A~Z的字母，即引用引用字符串长度只能是3，比如"<A>"
            if (reference.length() != 3) {
                return false;
            }

            // 引用单元格的编号
            char reference_cellNum = reference.charAt(1);
            // 当前单元格的编号
            char self_cellNum = (char) (65 + index);

            // 引用单元格编号只能是A~Z的字母，且不能自引用
            if (reference_cellNum < 'A' || reference_cellNum > 'Z' || reference_cellNum == self_cellNum) {
                return false;
            }

            // 引用单元格的数组索引， 'A' -> 0  ... 'Z' -> 25
            int reference_index = reference_cellNum - 'A';

            // 引用单元格编号不存在
            if (reference_index >= cells.length) {
                return false;
            }

            if (!changeCell(reference_index)) {
                return false;
            }

            // 将单元格内容中的引用部分，替换为被引用的单元格的内容
            cells[index] = cells[index].replace(reference, cells[reference_index]);
        }

        return true;
    }

    static String getResult() {
        if (cells.length > 26) {
            // 最多26个单元格，对应编号A~Z
            return "-1";
        }

        for (int i = 0; i < cells.length; i++) {
            // 替换单元格中的引用
            if (!changeCell(i)) {
                // 替换失败，则返回-1
                return "-1";
            }

            if (cells[i].length() > 100) {
                // 每个单元格的内容，在替换前和替换后均不超过100个字符
                return "-1";
            }

            if (!cells[i].matches("^[a-zA-Z0-9]+$")) {
                // 每个单元格的内容包含字母和数字
                return "-1";
            }
        }

        return String.join(",", cells);
    }
}
最后修改：2024 年 04 月 01 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏