大众点评2017校园招聘笔试（编程题）

• 圆桌边放了一圈红包形成一个环，每个红包的金额不同，围绕圆桌走一圈选择若干个红包，规则是不能拿相邻的红包，请问能拿到红包 最多的总金额是多少？（红包金额保存在一个数组中，认为数组第一个元素和最后一个元素相邻，形成闭合的环。）

输入包括多行：
第一行为整数N，N大于零小于等于20；
以下N行，每行为一个数组， 每个元素为一个红包的金额，如：
2
1，2
1，3，4
输出包括N行，每行一个数字，为拿到红包的总金额。如：
2
4

代码如下：

import java.util.ArrayList; 
import java.util.List; 
import java.util.Scanner; 
public class Hongbao { public static void main(String[] args) {

        Scanner in = new Scanner(System.in); int n = Integer.valueOf(in.nextLine());
        List<int[]> list = new ArrayList<int[]>(); for(int i = 0; i < n; i++){
            String[] temp = in.nextLine().split(","); int[] arr = new int[temp.length]; for(int j = 0; j < temp.length; j++){
                arr[j] = Integer.valueOf(temp[j]);
            }
            list.add(arr);
        } for(int[] l : list){ if(l.length%2 == 0){ int ou = 0; int qi = 0; for(int i = 0; i < l.length; i++){ if(i%2 == 0)
                        ou += l[i]; else qi += l[i];
                }
                System.out.println(ou >= qi ? ou : qi);
            }else{ int ou = 0; int qi = 0; for(int i = 0; i < l.length - 1; i++){ if(i == 0){
                        ou += (l[0] >= l[l.length - 1]) ? l[0] : l[l.length - 1];
                    }else{ if(i%2 == 0)
                            ou += l[i]; else qi += l[i];
                    }

                }
                System.out.println(ou >= qi ? ou : qi);
            }
        }
    }

}

• 给定一棵多叉树，每个节点保存一个int类型数字且节点数字不重复，要求从上到下按层次打印每个节点的数字，每个层次按从左到右的顺序。
  要求：
  （1）实现 一颗多叉树
  （2）根据自定义输入 ，构造多叉树
  （3）从左到右按层输出多叉树
  输入包含多行，每行有空格隔开的多个数字，第一个数字为某一个父节点的值，后面N个数字为父节点的所有子节点的值，按从左到右的顺序排序，所有节点的值为整数，取值范围[0，100]。
  如：
  5 2 3
  2 6 7 8
  （5为根节点，有两个子节点；2为5的第一个子节点，包含三个子节点）
  输出包含一行，用空格隔开：
  5 2 3 6 7 8

代码如下：

import java.util.ArrayList;
import java.util.List; 
import java.util.Scanner; 
public class Duoshu { public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String[] firstLine = in.nextLine().split(" ");
        TreeNode root = new TreeNode(Integer.parseInt(firstLine[0]));
        List<int[]> list = new ArrayList<int[]>(); while(in.hasNextLine()){
            String[] line = in.nextLine().split(" "); int[] temp = new int[line.length]; for (int i = 0; i < line.length; i++) {
                temp[i] = Integer.valueOf(line[i]);
            }
            list.add(temp);
        }
        TreeNode temp = null; for (int i = 1; i < firstLine.length; i++) { if(i == 1){
                root.firstChild = new TreeNode(Integer.valueOf(firstLine[i]));
                temp = root.firstChild;
                addChild(temp, list);
            } else{
                temp.nextBro = new TreeNode(Integer.valueOf(firstLine[i]));
                temp = temp.nextBro;
                addChild(temp, list);
            }
        }

        temp = root; while(temp != null){
            printBro(temp);
            temp = temp.firstChild;
        }

    } public static void printBro(TreeNode node){
        TreeNode temp = node;
        System.out.print(temp.value + " "); while(temp.nextBro != null){
            temp = temp.nextBro;
            System.out.print(temp.value + " ");
        }
    } public static void addChild(TreeNode node,List<int[]> list){ for (int[] l : list) { if(l[0] == node.value){
                TreeNode temp = null;
                TreeNode tempNode = null; for(int i = 1; i < l.length; i++){ if(i == 1){
                        node.firstChild = new TreeNode(Integer.valueOf(l[i]));
                        tempNode = node.firstChild;
                        addChild(tempNode, list); if(temp != null)
                            temp.nextBro = node.firstChild;
                    } else{
                        tempNode.nextBro = new TreeNode(Integer.valueOf(l[i]));
                        tempNode = tempNode.nextBro;
                        addChild(tempNode, list); if(i == l.length - 1)
                            temp = node.nextBro;
                    }
                }
            }

        }
    } static class TreeNode{ public int value; public TreeNode firstChild; public TreeNode nextBro; public TreeNode(){

        } public TreeNode(int value){ this.value = value;
        }
    }
}