携程在线测试题答案

时间：2024-06-29 01:24:19 公开教育我要投稿

相关推荐

携程在线测试题答案

　　试题一：

携程在线测试题答案

　　乘积最大：

　　尝试不同的拆分方法，dp求解或者找规律

　　示例代码：

　　#include

　　#define maxn 109

　　using namespace std;

　　long long dp[maxn][maxn];

　　int solve(int n){

　　long long ans = 0;

　　for(int i = 0; i <= n; i++)

　　ans = max(ans, dp[n][i]);

　　return ans;

　　}

　　int main(){

　　int n;

　　cin >> n;

　　for(int i = 0; i <= n; i++)

　　dp[0][i] = 1;

　　for(int i = 1; i <= n; i++){

　　for(int j = 1; j <= i; j++){

　　for(int k = 0 ; k < j; k++)

　　dp[i][j] = max(dp[i][j], dp[i - j][k] * j);

　　}

　　cout << solve(n) << endl;

　　return 0;

　　}

　　拼图：

　　经典问题，广度优先搜索

　　示例代码：

　　import java.io.*;

　　import java.util.*;

　　import java.text.*;

　　import java.math.*;

　　import java.util.regex.*;

　　import java.util.Scanner;

　　import java.util.Set;

　　import java.util.HashSet;

　　import java.util.ArrayList;

　　import java.lang.StringBuilder;

　　public class Main{

　　public static String destNumbers = "123456780";

　　public static Set set = new HashSet();

　　public static int[]moveTable = new int[]{12,14,10,13,15,11,5,7,3};

　　public static ArrayList getNextMoveList(Node pNode){

　　int position = pNode.numbers.indexOf("0");

　　int moveStatus = moveTable[position];

　　ArrayList cNodes = new ArrayList();

　　for(int status=1; status <=8; status=status<<1){

　　if((moveStatus & status) > 0){

　　char[] charNumbers = pNode.numbers.toCharArray();

　　int switchPosition = 0;

　　if(status == 1){

　　switchPosition = position - 3;

　　} else if(status == 2){

　　switchPosition = position - 1;

　　} else if(status == 4){

　　switchPosition = position + 1;

　　} else if(status == 8){

　　switchPosition = position + 3;

　　}

　　charNumbers[position] = charNumbers[switchPosition];

　　charNumbers[switchPosition] = '0';

　　String s = String.valueOf(charNumbers);

　　if(!set.contains(Integer.valueOf(s))){

　　set.add(Integer.valueOf(s));

　　Node n = new Node(pNode, s, charNumbers[position]);

　　cNodes.add(n);

　　}

　　return cNodes;

　　}

　　static int getResult(Node node){

　　String result = "";

　　while(node.parentNode != null){

　　result += node.currentNum;

　　node = node.parentNode;

　　}

　　return new StringBuffer(result).reverse().toString().length();

　　}

　　static int run(String numbers){

　　if(numbers.equals(destNumbers)){

　　return 0;

　　}

　　ArrayList numsList = new ArrayList();

　　numsList.add(new Node(null, numbers, ' '));

　　while(numsList.size() > 0){

　　ArrayList tmpList = new ArrayList();

　　for(Node pNode : numsList){

　　ArrayList cNodes = getNextMoveList(pNode);

　　for(Node cNode : cNodes){

　　if(cNode.numbers.equals(destNumbers)){

　　return getResult(cNode);

　　}

　　tmpList.add(cNode);

　　}

　　numsList = tmpList;

　　}

　　return -1;

　　}

　　public static void main(String[] args) {

　　Scanner scan = new Scanner(System.in);

　　String numbers = new String();

　　for(int rows=3; rows>0; rows--){

　　for(String n: scan.nextLine().split(" ")){

　　numbers += n;

　　}

　　int res = run(numbers);

　　System.out.println(String.valueOf(res));

　　}

　　class Node {

　　public Node(Node parentNode, String numbers, char currentNum){

　　this.numbers = numbers;

　　this.currentNum = currentNum;

　　this.parentNode = parentNode;

　　}

　　public char currentNum;

　　public String numbers;

　　public Node parentNode;

　　}

　　股票交易：

　　扫描序列，按照题意判断冷却时间，然后更新答案

　　示例代码：

　　#include

　　using namespace std;

　　int a[1000006],dp[1000006];

　　int main(){

　　int n,k;

　　scanf("%d",&n);

　　for(int i=1;i<=n;i++) scanf("%d",&a[i]);

　　scanf("%d",&k);

　　int cur=-1000000000, ans=0;

　　for(int i=1;i<=n;i++)

　　{

　　dp[i]=max(a[i]+cur, dp[i-1]);

　　if(i>=k)

　　cur=max(cur, dp[i-k]-a[i]);

　　else

　　cur=max(cur, -a[i]);

　　ans=max(ans, dp[i]);

　　}

　　printf("%d\n",ans);

　　}

　　试题二：

　　public class Base

　　{

　　private String baseName = "base";

　　public Base()

　　{

　　callName();

　　}

　　public void callName()

　　{

　　System. out. println(baseName);

　　}

　　static class Sub extends Base

　　{

　　private String baseName = "sub";

　　public void callName()

　　{

　　System. out. println (baseName) ;

　　}

　　public static void main(String[] args)

　　{

　　Base b = new Sub();

　　}

　　求这段程序的输出。

　　来自未老莫还乡的评论：

　　【不要在构造器里调用可能被重载的虚方法，这是极度危险的】。构造器的初始化顺序大概是父类静态块子类静态块父类初始化语句父类构造函器子类初始化语句子类构造器。父类构造器执行的时候，调用了子类的重载方法，然而子类的类字段还在刚初始化的阶段，刚完成内存布局，只能输出null。

　　来自 ihuning 的精华评论：

　　看我大师归来:

　　1. Base b = new Sub();

　　2. Base b = 直接忽略，从 new Sub();开始

　　3. 类加载器加载 Base，Sub 类到jvm;

　　4. 为Base，Sub 类中的两个属性baseName 分配存储空间，但是不初始化;

　　注意:属性的初始化时放在构造器中，按照代码顺序执行的。

　　5. new Sub会调用Sub的无参构造器，而在这个构造器中会隐式调用父类Base的无参构造器;

　　6. 父类Base的构造器中代码本质是

　　public Base()

　　{

　　baseName = "base";

　　callName();

　　}

　　即父类的属性baseName 的值为base。但为何输出null，骚年别急。

　　7. 因为父类构造器方法是在子类中调用的，即大环境是子类。此时，调用的方法callName()当然是指子类的方法。而这个方法打印的属性baseName当然也是子类的。那现在子类的属性baseName的值是多少呢?答案是null.因为此时子类Sub的构造器内代码本质是:

　　super();

　　baseName="sub";

　　此时baseName="sub"还没执行。

　　因此，左后的值当然是null.

【携程在线测试题答案】相关文章：