程序员基德

03-13 18:27 中国科学技术大学 C++ 发布于浙江

关注

【春招笔试】携程 2024.03.28 春招笔试题解析

alt

01. 小柯的回文游戏

题目内容

小柯想玩一个有趣的回文游戏。给定一个正整数 $n$ ，她希望你能输出一个由 $n$ 个 "you" 组成的字符串，其中第一个 "you" 正序输出，第二个倒序输出，第三个再正序，以此类推。你能帮帮她吗？

输入描述

输入只有一行，包含一个正整数 $n$ ，表示需要输出的 "you" 的个数。

输出描述

输出一个字符串，表示由 $n$ 个 "you" 组成的字符串，奇数位置的 "you" 正序输出，偶数位置的 "you" 倒序输出。

样例1

输入：

输出：

youuoyyouuoyyou

题解

这是一个简单的字符串构造问题。核心思路是根据位置的奇偶性交替输出正序和倒序的 "you"。

首先定义两个字符串：正序的 "you" 和倒序的 "uoy"。然后根据位置的奇偶性决定输出哪一个。具体来说，当位置是偶数（从 0 开始计数）时输出 "you"，当位置是奇数时输出 "uoy"。

这种方法的时间复杂度是 $O(n)$ ，其中 $n$ 是输入的整数。空间复杂度是 $O(1)$ ，因为我们只需要常数级别的额外空间来存储两个固定的字符串。

对于给定的数据范围（ $n$ 最大为 $10^5$ ），这个算法是高效的，因为最终生成的字符串长度不会超过 $3 \times 10^5$ ，完全在可接受的范围内。

三语言参考代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    int cnt;
    cin >> cnt;
    
    string norm = "you";
    string revs = "uoy";
    string rslt = "";
    
    for (int idx = 0; idx < cnt; idx++) {
        if (idx % 2 == 0) {
            rslt += norm;
        } else {
            rslt += revs;
        }
    }
    
    cout << rslt << endl;
    return 0;
}

Python

def solve():
    cnt = int(input())
    
    norm = "you"
    revs = "uoy"
    rslt = ""
    
    for idx in range(cnt):
        if idx % 2 == 0:
            rslt += norm
        else:
            rslt += revs
    
    print(rslt)

if __name__ == "__main__":
    solve()

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int cnt = scan.nextInt();
        
        String norm = "you";
        String revs = "uoy";
        StringBuilder rslt = new StringBuilder();
        
        for (int idx = 0; idx < cnt; idx++) {
            if (idx % 2 == 0) {
                rslt.append(norm);
            } else {
                rslt.append(revs);
            }
        }
        
        System.out.println(rslt.toString());
    }
}

02. 小柯的花园修剪

题目内容

小柯有一个 $n \times m$ 的花园，每个位置上都种植了一株植物。然而，有些植物长得太茂盛了，需要修剪。小柯可以选择一个 $1 \times 2$ 的区域（即连续的两株植物），将它们修剪整齐。现在，小柯想知道，最少需要多少次修剪，才能让整个花园看起来整齐有序呢？

花园中的每一株植物可以用 0 或 1 来表示，0 表示植物长得刚刚好，不需要修剪，1 表示植物长得太茂盛，需要修剪。

输入描述

第一行包含两个正整数 $n$ 和 $m$ ，表示花园的行数和列数，中间用空格隔开。

接下来 $n$ 行，每行包含 $m$ 个字符，表示花园中植物的状态，0 表示不需要修剪，1 表示需要修剪。

输出描述

输出一个整数，表示最少需要的修剪次数。

样例1

输入：

2 4
1010
1000

输出：

题解

这道题可以用贪心的思路来解决。关键观察是：每次修剪操作会影响两个相邻的植物，我们希望尽可能多地利用每次修剪来处理需要修剪的植物。

最优策略是：遍历花园中的每个位置，当遇到需要修剪的植物（值为 1）时，进行一次修剪操作，并将该植物和它右边的植物（如果存在）都标记为已修剪。这样可以保证每次修剪都是必要的，且尽可能利用了修剪操作的效果。

具体实现时，可以用一个二维数组来表示花园，然后遍历每个位置。如果当前位置的植物需要修剪且尚未被修剪过，就进行一次修剪操作，并更新相应的状态。

时间复杂度为 $O(n \times m)$ ，其中 $n$ 和 $m$ 分别是花园的行数和列数。空间复杂度也是 $O(n \times m)$ ，用于存储花园的状态。

对于给定的数据范围（ $n, m$ 最大为 1000），这个算法是高效的，可以在合理的时间内得到结果。

三语言参考代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int rows, cols;
    cin >> rows >> cols;
    
    vector<string> yard(rows);
    for (int i = 0; i < rows; i++) {
        cin >> yard[i];
    }
    
    int cuts = 0;
    vector<vector<bool>> trim(rows, vector<bool>(cols, false));
    
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (yard[r][c] == '1' && !trim[r][c]) {
                cuts++;
                trim[r][c] = true;
                
                // 修剪右边的植物（如果存在）
                if (c + 1 < cols) {
                    trim[r][c+1] = true;
                }
            }
        }
    }
    
    cout << cuts << endl;
    return 0;
}

Python

def solve():
    rows, cols = map(int, input().split())
    yard = [input() for _ in range(rows)]
    
    cuts = 0
    trim = [[False for _ in range(cols)] for _ in range(rows)]
    
    for r in range(rows):
        for c in range(cols):
            if yard[r][c] == '1' and not trim[r][c]:
                cuts += 1
                trim[r][c] = True
                
                # 修剪右边的植物（如果存在）
                if c + 1 < cols:
                    trim[r][c+1] = True
    
    print(cuts)

if __name__ == "__main__":
    solve()

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int rows = scan.nextInt();
        int cols = scan.nextInt();
        
        char[][] yard = new char[rows][cols];
        for (int r = 0; r < rows; r++) {
            yard[r] = scan.next().toCharArray();
        }
        
        int cuts = 0;
        boolean[][] trim = new boolean[rows][cols];
        
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (yard[r][c] == '1' && !trim[r][c]) {
                    cuts++;
                    trim[r][c] = true;
                    
                    // 修剪右边的植物（如果存在）
                    if (c + 1 < cols) {
                        trim[r][c+1] = true;
                    }
                }
            }
        }
        
        System.out.println(cuts);
    }
}