携程笔试 携程笔试题 0905

笔试时间:2024年09月05日 秋招

历史笔试传送门:2023秋招笔试合集

第一题

题目

游游有两个整数n,k, 他希望构造出一个1~n的排列p, 需要p的最长上升子序列长度为k, 并且p是所有满足要求的排列中字典序最小的。最长上升子序列是一个序列中最长的严格单调递增的子序列。

输入描述

两个正整数n,k,用空格隔开。

输出描述

输出n个正整数,代表构造的排列。

样例输入

5 3

样例输出

1 2 5 4 3

参考题解

模拟。由于字典序要求最小,因此要贪心的考虑。容易想到首先构造出1, 2, 3, ..., k - 1,n, n - 1, ..., k是字典序最小的。

C++:[此代码未进行大量数据的测试,仅供参考]

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < k - 1; i++) {
        a[i] = i + 1;
    }
    a[k - 1] = n;
    for (int i = k, x = n - 1; i < n; i++, x--) {
        a[i] = x;
    }
    for (int x : a) {
        cout << x << " ";
    }
    cout << "\n";
}

Java:[此代码未进行大量数据的测试,仅供参考]

import java.util.Scanner;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        Vector<Integer> a = new Vector<>(n);

        for (int i = 0; i < k - 1; i++) {
            a.add(i + 1);
        }
        a.add(n);

        for (int i = k, x = n - 1; i < n; i++, x--) {
            a.add(x);
        }

        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

Python:[此代码未进行大量数据的测试,仅供参考]

n, k = map(int, input().split())
a = [0] * n

for i in range(k - 1):
    a[i] = i + 1
a[k - 1] = n

x = n - 1
for i in range(k, n):
    a[i] = x
    x -= 1

print(" ".join(map(str, a)))

第二题

题目

一个长度为k的二进制字符串(下标从1开始)的权值定义如下:每次操作可以选择一个下标i(1 ≤ i ≤ k),将[1, i]中的字符全部取反(0变成1,1变成0),字符串的权值为将字符串变成全1所需要的最小操作次数。给定一个长度为n的01字符串,问:有多少个长度为奇数并且权值为奇数的子字符串?

输入描述

第一行输入一个正整数n,代表字符串的长度。第二行输入字符串S。

输出描述

输出包含一行一个整数,表示长度和权值都是奇数的非空子串数量。

样例输入

5

01010

样例输出

6

参考题解

动态规划。定义三维dp数组,第一个维度表示下标,第二个维度表示长度是奇数还是偶数,第三个维度表示权值是奇数还是偶数

例如:dp[i][0][0]就表示以下标i结尾的长度为偶数并且权值为偶数的子字符串的数量,dp[i][0][1]表示以下标i结尾的长度为偶数的权值为奇数的子字符串的数量,以此类推。

C++:[此代码未进行大量数据的测试,仅供参考]

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(2, vector<int>(2, 0)));
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            dp[i][1][0]++;
            if (i > 0) {
                dp[i][0][0] += dp[i - 1][1][0];
                dp[i][0][1] += dp[i - 1][1][1];
                dp[i][1][0] += dp[i - 1][0][0];
                dp[i][1][1] += dp[i - 1][0][1];
            }
        }else {
            dp[i][1][1]++;
            if (i > 0) {
                 if (s[i - 1] == s[i]) {
                    dp[i][0][0] += dp[i - 1][1][0];
                    dp[i][0][1] += dp[i - 1][1][1];
                    dp[i][1][0] += dp[i - 1][0][0];
                    dp[i][1][1] += dp[i - 1][0][1];
                 } else {
                    dp[i][0][0] += dp[i - 1][1][0];
                    dp[i][0][1] += dp[i - 1][1][1];
                    dp[i][1][0] += dp[i - 1][0][0];
                    dp[i][1][1] += dp[i - 1][0][1];
                 }
            }
        }
        ans += dp[i][1][1];
    }
    cout << ans << "\n";
}

Java:[此代码未进行大量数据的测试,仅供参考]

import java.util.Scanner;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String s = scanner.next();
        int[][][] dp = new int[n][2][2];
        long ans = 0;

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                dp[i][1][0]++;
                if (i > 0) {
                    dp[i][0][0] += dp[i - 1][1][0];
                    dp[i][0][1] += dp[i - 1][1][1];
                    dp[i][1][0] += dp[i - 1][0][0];
                    dp[i][1][1] += dp[i - 1][0][1];
                }
            } else {
                dp[i][1][1]++;
                if (i > 0) {
                    if (s.charAt(i - 1) == s.charAt(i)) {
                        dp[i][0][0] += dp[i - 1][1][0];
                        dp[i][0][1] += dp[i - 1][1][1];
                        dp[i][1][0] += dp[i - 1][0][0];
                        dp[i][1][1] += dp[i - 1][0][1];
                    } else {
                        dp[i][0][0] += dp[i - 1][1][0];
                        dp[i][0][1] += dp[i - 1][1][1];
                        dp[i][1][0] += dp[i - 1][0][0];
                        dp[i][1][1] += dp[i - 1][0][1];
                    }
                }
            }
            ans += dp[i][1][1];
        }

        System.out.println(ans);
    }
}

Python:[此代码未进行大量数据的测试,仅供参考]

n = int(input())
s = input()
dp = [[[0, 0] for _ in range(2)] for _ in range(n)]
ans = 0

for i in range(n):
    if s[i] == '1':
        dp[i][1][0] += 1
        if i > 0:
            dp[i][0][0] += dp[i - 1][1][0]
            dp[i][0][1] += dp[i - 1][1][1]
            dp[i][1][0] += dp[i - 1][0][0]
            dp[i][1][1] += dp[i - 1][0][1]
    else:
        dp[i][1][1] += 1
        if i > 0:
            if s[i - 1] == s[i]:
                dp[i][0][0] += dp[i - 1][1][0]
                dp[i][0][1] += dp[i - 1][1][1]
                dp[i][1][0] += dp[i - 1][0][0]
                dp[i][1][1] += dp[i - 1][0][1]
            else:
                dp[i][0][0] += dp[i - 1][1][0]
                dp[i][0][1] += dp[i - 1][1][1]
              

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

2024 BAT笔试合集 文章被收录于专栏

持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解,包含python、C++、Java多种语言版本,持续更新中。

全部评论
大佬,第二题的状态转移好像是一样的?
点赞 回复 分享
发布于 09-11 12:38 重庆

相关推荐

刚刚笔试4道题只过了两道半,感觉悬了,第二题dp死活只有50%准确率,用dfs又超时了,当时一紧张完全忘了还能加memoization,唉,就是下面这道题,第二题挣扎了1个多小时导致第四题一点没碰,最后交卷前看了一眼好像不太难,亏死了你来到了一个迷宫,迷宫共有&nbsp;n&nbsp;关,每关有左侧和右侧两个宝箱,左侧宝箱的收益为&nbsp;a_i,右侧宝箱的收益为&nbsp;c_i。在每次只可以选择一个宝箱,然后到达下一关。当你在选择宝箱时,如果和上一关选择宝箱的方位相同则无损失。如果上一关选择了左侧宝箱,而这一关想要切换到右侧宝箱,那么需要支付&nbsp;b_i&nbsp;代价;如果上一关选择了右侧宝箱,而这一关想要切换到左侧宝箱,那么需要支付&nbsp;d_i&nbsp;代价(必须在进入下一关之前切换)。有些宝箱的收益和切换代价可能是负数!可以理解为,代价为负值相当于收益。你想知道,当通过&nbsp;n&nbsp;关后,总收益的最大值是多少?输入描述:本题为多组测试数据,第一行输入一个正整数&nbsp;T(1&nbsp;≤&nbsp;T&nbsp;≤&nbsp;100),代表测试数据组数。对于每组测试数据,第一行输入一个正整数&nbsp;n(1&nbsp;≤&nbsp;n&nbsp;≤&nbsp;1000),代表关卡数量。接下来有&nbsp;n&nbsp;行,每行四个整数&nbsp;a_i,&nbsp;b_i,&nbsp;c_i,&nbsp;d_i(-100&nbsp;≤&nbsp;a_i,&nbsp;b_i,&nbsp;c_i,&nbsp;d_i&nbsp;≤&nbsp;100),具体代表题意中所述的数值。这道题dp怎么做,java输出描述:对于每组测试数据,输出一个整数,代表从小红总收益的最大值。
投递携程等公司10个岗位
点赞 评论 收藏
分享
10 18 评论
分享
牛客网
牛客企业服务