去哪儿笔试0906（真难受）
三道算法
80 16.6 6
9.6去哪儿笔试（去哪儿笔试，难度适中（0906秋招笔试真题解析））
第一题
牛牛有一个由n个整数组成的数组[a1，a2，.,an]，他想将这n个数打乱后依次拼接，使得拼接得到的字符串字典序是所有拼接字符串中最小的。直接输出这个打乱过后的数组。
输入描述
第一行输入一个整数n(1≤n≤10^5)代表数组中的元素数量。第二行输入n个整数a1，a2，...,an(0≤ai≤10^9)代表数组元素
输出描述
在第一行上输出n个整数，代表重新排列后的数组
示例1：
输入
32 1 -1
输出
-1 1 2
首先观察到一个性质：给定字符串a和b，如果a + b < b + a，那么在最终的数组中，a一定在b的前面（否则我们调换a和b的位置字典序一定会变得更小）。因此，我们根据a + b < b + a进行排序即可。
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();
String[] ans=in.nextLine().split(" ");
Arrays.sort(ans,(s1, s2)->(s1+s2).compareTo(s2+s1));
for (String s:ans){
System.out.printf("%s ",s);
}
}
第二题
去哪儿会员体系分为大众、白银、黄金、铂金和钻石会员五个等级，等级由成长值决定，成长值越高，等级也就越高，也能够享受更多的会员权益。这天，牛牛发现可以通过完成每日任务的方式快速获得成长值提升等级！一共有n个任务，每天都会解锁一个新的任务，第i个任务达成后可以获得ai点成长值奖励。为了鼓励用户参与任务，在开始任务之前，还可以进入“挑战”模式，即预先设置自己能够坚持的天数x，在完成挑战后，可以得到前张奖励翻倍卡，你可以自由选择翻倍卡的使用顺序，使得每一天的成长值奖励翻倍，第i张翻倍卡可以将任务完成后的成长值奖励乘以bi倍，例如：第一天任务奖励1点成长值，第二天任务奖励2点成长值，奖励一张四倍翻倍卡和一张两倍翻倍卡，那么最少可以得到8点成长值，最多可以得到10点成长值。牛牛比较偷懒，他想要找到最少需要坚持的天数，使得自己能够获得至少m点成长值。
输入描述
第一行输入两个整数n和m(1≤n≤10^5；1≤m≤10^12)代表任务总数量和需要的成长值数量。第二行n个整数 a1,a2，..,an(0≤ai≤10^3)代表每一个任务奖励的成长值点 第三行n个整数b1,b2，..,bn(1≤bi≤10^3)代表按顺字摆放的翻倍卡的面值。
输出描述
在一行输出一个整数，代表最少坚持的天数；若永远无法达到目标，则直接输出-1
示例1：
输入：
5 20
1 2 3 4 5
4 2 3 5 10
输出：
3
容易观察到如果牛牛n天可以完成挑战，那么n+1天,n+2天....都可以完成挑战，因此我们二分天数，然后将前mid个任务根据成长值排序，将前mid个翻倍卡根据倍数进行排序，最后小的成长值乘小的翻倍卡即可。
public class Mian22 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] input = in.nextLine().split(" ");
int n=Integer.parseInt(input[0]);
long m=Integer.parseInt(input[1]);
int[] res1=new int[n];
String[] ans1=in.nextLine().split(" ");
for (int i=0; i<n; i++) {
res1[i]=Integer.parseInt(ans1[i]);
}
int[] res2=new int[n];
String[] ans2=in.nextLine().split(" ");
for (int i=0; i<n; i++) {
res2[i]=Integer.parseInt(ans2[i]);
}
int l=0,r=n-1;
while (l<=r){
int mid=(r-l)/2+l;
if(checkTrue(res1,res2,mid,m)){
r=mid-1;
}else {
l=mid+1;
}
}
System.out.println(l>=n?-1:(l+1));
}
public static boolean checkTrue(int[] res1,int[] res2,int mid,long m){
int[] Ans1Copy= Arrays.copyOfRange(res1,0,mid+1);
Arrays.sort(Ans1Copy);
int[] Ans2Copy= Arrays.copyOfRange(res2,0,mid+1);
Arrays.sort(Ans2Copy);
long res=0l;
for(int i=mid;i>=0;i--){
res+=(long)Ans1Copy[i]*Ans2Copy[i];
if(res>=m){
return true;
}
}
return false;
}
}
第三题
如果一个字符串s可以由某个字符串t重复x(x>1)次得到，就称字符串s为一个真周期串。例如：s=01230123,t=0123,x=2。对于一个只包含数字0~9的字符串S，可以执行任意次（也可以不执行）操作，选择任意两个下标，交换两个下标的字符。更正式地说，选择i,j(i≠j)交换Si和Sj。如果字符串S经过操作后可以变成真周期串，那么称S为伪周期串。现在给定一个只包含数字0~9的字符串T，问：最多可以将字符串T划分成几个伪周期串？更正式地说，找出一个大小为k的伪周期串集合P，使得T=P1+P2+…+Pk输出最大的k。
输入描述
第一行输入一个整数n(1≤n≤2×10^3)，表示字符串长度。第二行输入一个长度为n，且只包含数字字符的字符串T。
输出描述
在一行输入一个长度为n，且只包含数字字符的字符串T
示例：
输入：
801102222
输出
定义dp[i]为长度为i的前缀最多可以分为多少个，特别的，如果dp[i]为-1的话就代表这个前缀不可分。在过渡的时候，枚举以i为右端点的子字符串，判断子字符串是否是伪周期串并且前缀不能等于-1，然后更新答案。特别的，判断是否为伪周期串可以根据所有字符出现次数的最大公约数来判断，如果大于1，则是伪周期串。
package com.面试中的算法.去哪儿.去哪儿9_6秋招;
import java.util.Scanner;
/**
* @author xing'chen
* @version 1.0
* @description: TODO
* @date 2024/9/6 21:23
*/
public class Main33 {
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String t = scanner.next();
int[] dp = new int[n + 1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int[] cnt = new int[10];
for (int len = 1; len <= i; len++) {
int id = t.charAt(i - len) - '0';
cnt[id]++;
int g = 0;
for (int j = 0; j < 10; j++) {
g = gcd(g, cnt[j]);
}
if (g > 1 && dp[i - len] != -1) {
dp[i] =Math.max(dp[i], 1 + dp[i - len]);
}
}
}
System.out.println(dp[n]);
}
}
麻了能不能给个面试我以后只在去哪儿订酒店
#去哪儿求职进展汇总##秋招##投票##去哪儿旅行秋招#秋招中的笔试以及面记录
