携程秋季笔试三道编程题（2021-09-09）

电玩女神 2022-09-11 00:05 184阅读 0赞

> 通知：最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在【TechGuide】了，私信公众号回复【美团】或者【百度】即可获得最实时的笔试题解啦！

> 通知：最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在【TechGuide】了，私信公众号回复【美团】或者【百度】即可获得最实时的笔试题解啦！  
> ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAVGVjaEd1aWRl_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]

【2021-09-04】美团秋招笔试五道编程题（附题目）  
【2021-09-03】贝壳秋招笔试四道编程题（前三道ac）  
【2021-09-01】阿里巴巴秋招笔试两道编程题  
【2021-09-01】华为秋招机试三道编程题（附题目，后两题AC）  
【2021-08-29】美团秋招笔试四道编程题  
【2021-08-29】字节跳动秋招笔试四道编程题  
【2021-08-26】腾讯音乐秋招笔试编程三道题  
【2021-08-25】华为秋招机试三道编程题  
【2021-08-23】阿里巴巴秋招笔试两道编程题  
【2021-08-22】腾讯秋招笔试五道编程题  
【2021-08-22】美团秋招笔试五道编程题（待更新）  
【2021-08-21】网易秋招机试四道编程题（待更新）  
【2021-08-14】荣耀秋招机试三道编程题（已更新）  
【2021-08-18】华为秋招机试三道编程题（已更新）  
【2021-08-18】阿里秋招笔试两道编程题  
【2021-08-15】美团秋招笔试五道编程题（已更新）  
【2021-08-12】携程秋招笔试三道编程题  
【2021-08-11】华为秋招机试三道编程题(已更新)  
【2021-08-09】阿里巴巴秋招笔试两道编程题  
【2021-08-08】拼多多秋招笔试四道编程题  
【2021-08-08】美团秋招笔试五道编程题  
【2021-08-08】好未来秋招三道编程题  
【2021-08-07】网易互娱秋招笔试三道编程题  
【2021-08-04】华为秋招两道编程题

### 文章目录 ###

*  第一道：目录命令
 *   *  题目描述
     *  参考代码
     *   *  Java版本
         *  Python版本
         *  CPP版本
 *  第二道：分段（100%）
 *   *  题目描述
     *  参考代码：
     *   *  Python版本
         *  CPP版本
 *  第三道：子序列（100%）
 *   *  题目描述
     *  参考代码
     *   *  Java版本
         *  Python版本
         *  CPP版本

# 第一道：目录命令 #

## 题目描述 ##

你需要编写一个程序来模拟目录的操作，一开始，你在根目录""，一共有两种命令：

● cd s: s为一个目录名，表示从当前工作目录的路径进入名为s的目录。

特别地，“cd …”(即s=="…")表示返回上一级目录，若当前已为根目录，则无视该次操作。数据保证若s不为"…"，则一定为小写字母组成的长度不超过10的字符串。

● pwd: 表示查看当前工作目录的路径，

你需要输出这个路径。

**输入描述**  
第一个行是一个整数n，表示一共会有n个操作。 接下来每行是一条命令，命令的种类为问题描述中的二种之一。 注意，测试用例中cd s的操作，中间有空格。 输出描述 对于每个"pwd"命令，你需要单行输出当前的工作路径。 【样例输入】 7 cd a cd b pwd cd … pwd cd … pwd

**样例输出**  
\\a\\b \\a \\ （提示 1<=n<=300）

## 参考代码 ##

### Java版本 ###

public class Main { 
        public static void main(String[] args) throws IOException { 
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            Scanner sc = new Scanner(System.in);
            List<String> list = new ArrayList<>();
            int n = Integer.parseInt(br.readLine());
            for (int i = 0; i < n; i++) { 
                String line = sc.nextLine();
                String[] strs = line.split(" ");
                if ("cd".equals(strs[0])) { 
                    if ("..".equals(strs[1])) { 
                        if (!list.isEmpty()) { 
                            list.remove(list.size() - 1);
                        }
                    } else { 
                        list.add("\\" + strs[1]);
                    }
                } else if ("pwd".equals(strs[0])) { 
                    if (list.isEmpty()) { 
                        System.out.println('\\');
                    } else { 
                        StringBuilder sb = new StringBuilder();
                        for (String s : list) { 
                            sb.append(s);
                        }
                        System.out.println(sb);
                    }
                }
            }
        }
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

### Python版本 ###

def func1():
        n=int(input())
        dirlist=[]
        for i in range(n):
            dir=input()
            dirlist.append(dir)
        basedir="\\"
        for i in dirlist:
            command=i.strip().split()
            if command[0]=="cd":
                if command[1]=="..":
                    index=len(basedir)-1
                    while index>0:
                        if basedir[index]=="\\":
                            basedir=basedir[:index]
                            break
                        index-=1
                elif command[1]==".":
                    pass
                else:
                    basedir+="\\"+command[1]
            elif  command[0]=="pwd":
                if len(basedir[1:])==0:
                    print("\\")
                else:
                    print(basedir[1:])
     # 关注TechGuide！ 大厂笔经面经闪电速递！

### CPP版本 ###

#include<iostream>
    #include<queue>
    #include<string>
    using namespace std;
    int main()
    { 
     int n; cin >> n;
     queue<string> st;
     for (int i = 0; i < n; i++)
     { 
      string s1;
      string s2;
      cin >> s1;
      if (s1 == "cd")
      { 
       cin >> s2;
       if (s2 == "..")
       { 
        if (st.size() >= 2)
        { 
         st.pop();
         st.pop();
        }
       }
       else
       { 
        st.push("\\");
         st.push(s2);
       }
      }
      else
      { 
       if (st.empty())
        cout << "\\"<<endl;
       else { 
        queue<string> tmp(st);
        while (!tmp.empty())
        { 
         cout << tmp.front();
         tmp.pop();
        }
       }
      }
     }
    return 0;
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第二道：分段（100%） #

## 题目描述 ##

有一个长度为n的序列A，序列中的第i个数为A\[i\] (1<=i<=n)，现在你可以将序列分成至多连续的k段。  
对于每一段，我们定义这一段的不平衡度为段内的最大值减去段内的最小值。显然，对于长度为1的段，其不平衡度为0。  
对于一种合法的分段方式（即每一段连续且不超过k段），我们定义这种分段方式的不平衡度为每一段的不平衡度的最大值。  
现在你需要找到不平衡度最小的分段方式，输出这种分段方式的不平衡度即可。

**输入描述**  
第一行两个空格隔开的整数n，k，分别表示序列的长度和最多可分成的段数。 第二行是n个用空格隔开的整数，第i个数表示A\[i\]的值。

5 3 3 5 5 2 5

**输出描述**  
一行一个整数，表示最小的不平衡度。

**解释**  
最终分为\[3 5 5\], \[2\], \[5\]，该种分段方式的不平衡度为2。

## 参考代码： ##

public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int k = sc.nextInt();
            int[] nums = new int[n];
            for(int i=0; i < n; i++) nums[i] = sc.nextInt();
            int max = nums[0], min = nums[0];
            for(int num : nums){ 
                max = Math.max(max, num);
                min = Math.min(min, num);
            }
            int l = 0, r = max - min, m = 0;
            while(l < r){ 
                m = (l + r) / 2;
                if(check(nums, k, m)) r = m;
                else l = m + 1;
            }
            System.out.println(l);
        }
        private static boolean check(int[] nums, int k, int x){ 
            int max = nums[0], min = nums[0];
            for(int i=1; i < nums.length; i++){ 
                max = Math.max(max, nums[i]);
                min = Math.min(min, nums[i]);
                if(max - min > x){ 
                    k--;
                    if(k <= 0) return false;
                    max = min = nums[i];
                }
            }
            return k > 0;
        }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

### Python版本 ###

def func2():
        n, k = [int(i) for i in input().split()]
        numlist = [int(i) for i in input().split()]
        from itertools import combinations
        def calc(numlist, n, k):
            res=max(numlist)
            if k >= n:
                return 0
            chioce=combinations([i for i in range(1,n)],k-1)
            for one in chioce:
                temp=cut(list(one),numlist,n)
                if temp<res:
                    res=temp
            return res
        def cut(pos,nums,n):
            pos=[0]+pos+[n]
            res=[]
            for i in range(1,len(pos)):
                temp=nums[pos[i-1]:pos[i]]
                res.append(max(temp)-min(temp))
            return max(res)
        print(calc(numlist, n, k))
     # 关注TechGuide！ 大厂笔经面经闪电速递！

### CPP版本 ###

#include<bits/stdc++.h>
    
    using namespace std;
    
    bool check(const vector<int>& vec, int k, int diff)
    { 
        int n = vec.size();
        int cnt = 1;
        int maxn = vec[0];
        int minn = vec[0];
        for (int i = 1; i < n; ++i)
        { 
            if (vec[i] - minn > diff || maxn - vec[i] > diff)
            { 
                ++cnt;
                maxn = vec[i];
                minn = vec[i];
                if (cnt > k)
                    return false;
            }
            else
            { 
                maxn = max(maxn, vec[i]);
                minn = min(minn, vec[i]);
            }
        }
        return true;
    }
    int solve(const vector<int>& vec, int k)
    { 
        int n = vec.size();
        int l = 0;
        int r = 100000;
        while (l < r)
        { 
            int mid = l + (r - l) / 2;
            if (check(vec, k, mid))
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
    int main()
    { 
        int n, k;
        cin >> n >> k;
        vector<int> vec(n);
        for (int i = 0; i < n; ++i)
            cin >> vec[i];
        cout << solve(vec, k) << endl;
        return 0;
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第三道：子序列（100%） #

## 题目描述 ##

现在给你一个长度为n的01序列，你可以通过消除连续的1的序列来获取一定的分数。 题目中将给你若干个长度和分数的对应关系，你需要正确求解出对应的答案。

例如：现在给你一个长度为12的01序列111111011111。

现在给你如下可以获取得分的消除方式： 消除三个连续的1，获取得分10 消除四个连续的1，获取得分15

对于前面的六个连续的1，你的消除方案有两种： 消除一次连续的四个1，获得得分15，或者进行两次连续的三个1消除，获取得分20. 对于后面的五个连续的1，你有两种消除方案： 消除一次连续的四个1，获得得分15，或者消除一次连续的三个1，获得得分10

上述方案中可以获得的最大分数是20 + 15 = 35. 你的任务就是设法获得最大的消除分数。

请注意：不一定需要把所有的1的消除完毕，我们的目标是最大化分数而不是最大化消除个数。 【输入描述】 输出描述 。 样例输入 11

**输入描述**  
第一行两个空格隔开的正整数n,m，分别表示01串的长度和消除规则的数量。 接下来一行字符串长度为n，每个字符只能是0或者1中的一种。 接下来m行，每行两个空格隔开的正整数k, x，为消除连续的k个1可以获得的分数x。

11 2 
    11111101111 
    3 10 
    4 15

**输出描述**  
输出可以获得的最大分数。

## 参考代码 ##

### Java版本 ###

public class Main { 
        public static void main(String[] args) throws IOException { 
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String ss = br.readLine();
            String[] sss = ss.split(" ");
            int line = Integer.parseInt(sss[1]);
            char[] nums = br.readLine().toCharArray();  // 01序列
            int[][] wvs = new int[line + 1][2];
            for (int i = 1; i <= line; i++) { 
                String[] wv = br.readLine().split(" ");
                wvs[i][0] = Integer.parseInt(wv[0]);
                wvs[i][1] = Integer.parseInt(wv[1]);
            }
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) { 
                if (nums[i] == '0') { 
                    continue;
                }
                int W = 0;
                while (i < nums.length && nums[i] == '1') { 
                    W++;
                    i++;
                }
                list.add(W);
                i--;
            }
            int res = 0;
            for (Integer W : list) { 
                res += maxValue(W, wvs);
            }
            System.out.println(res);
        }
    
        public static int maxValue(int V, int[][] wv) { 
            int N = wv.length - 1;
            int[] dp = new int[V + 1];
            for (int i = 1; i <= N; i++) { 
                for (int j = 0; j <= V; j++) { 
                    if (j >= wv[i][0]) { 
                        dp[j] = Math.max(dp[j - wv[i][0]] + wv[i][1], dp[j]);
                    }
                }
            }
            return dp[V];
        }
    }

### Python版本 ###

n, l = [int(i) for i in input().split()]
    string = input()
    w = [0]
    v = [0]
    for i in range(l):
        key, val = [int(i) for i in input().split()]
        w.append(key)
        v.append(val)
    def maxsorce(string):
        start = 0
        res = 0
        n = len(string)
        while start < n:
            while start < n and string[start] == "0":
                start += 1
            if start == n:
                return res
            end = start
            while end < n and string[end] == "1":
                end += 1
            res += calc(end - start)
            start = end
        return res
    
    def calc(weight):
        global w, v
        n = len(w)-1
        dp = [[0] * (weight + 1) for i in range(n + 1)]
        for i in range(1, n + 1):
            # 0-1 背包的话从后往前进行计算， 因为每一个就会计算一次
            for j in range(weight + 1):
                if j < w[i]:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])
        return dp[n][weight]
    print(maxsorce(string))
    # 关注TechGuide！ 大厂笔经面经闪电速递！

### CPP版本 ###

#include<bits/stdc++.h>
    
    using namespace std;
    
    int main()
    { 
        int n, m;
        string s;
        cin >> n >> m;
        cin >> s;
    
        map<int, int> mp;
        int k, x;
        for (int i = 0; i < m; ++i)
        { 
            cin >> k >> x;
            mp[k] = max(mp[k], x);
        }
        int maxn = 0;
        for (auto it = mp.begin(); it != mp.end();)
        { 
            if (it->second <= maxn)
                mp.erase(it++);
            else
            { 
                maxn = it->second;
                ++it;
            }
        }
    
        vector<int> cnt;
        for (int i = 0; i < n; ++i)
        { 
            if (s[i] == '0')
                continue;
            int j = i + 1;
            while (j < n&& s[j] == '1')++j;
            cnt.emplace_back(j - i);
            i = j - 1;
        }
        if (0 == cnt.size())
        { 
            cout << 0 << endl;
            return 0;
        }
        sort(cnt.begin(), cnt.end(), [](const int a, const int b) { return a > b; });
        //int minLen=mp.begin()->first;
        int len = mp.size();
        vector<int> cost(len);
        vector<int> profit(len);
        int idx = 0;
        for (auto it = mp.begin(); it != mp.end(); ++it)
        { 
            int c = it->first;
            int p = it->second;
            cost[idx] = c;
            profit[idx] = p;
            ++idx;
        }
        int range = cnt[0];
        vector<vector<int>> dp(len, vector<int>(range + 1, 0));
        for (int i = 0; i < len; ++i)
            for (int j = 1; j <= range; ++j)
            { 
                if (i == 0)
                { 
                    dp[0][j] = j / cost[0] * profit[0];
                }
                else
                { 
                    dp[i][j] = dp[i - 1][j];
                    if (j - cost[i] >= 0)
                        dp[i][j] = max(dp[i][j], max(dp[i - 1][j - cost[i]], dp[i][j - cost[i]]) + profit[i]);
                }
            }
        int res = 0;
        for (int i = 0; i < cnt.size(); ++i)
        { 
            res += dp[len - 1][cnt[i]];
        }
        cout << res << endl;
        return 0;
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

> 关注TechGuide，大厂笔经面经闪电速递！

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAVGVjaEd1aWRl_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/557598408f994e588de36148538559a8.png