携程大数据编程题AK
第一题：信息墒（100%）
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class XC1 {
public static void solve(int[] x, int[] y) {
double sum = 0;
int n = x.length;
Set<Integer> set = new HashSet<>();
for (int i : x) set.add(i);
Map<Integer, Integer> pos = new HashMap<>();
Map<Integer, Integer> neg = new HashMap<>();
Map<Integer, Integer> all = new HashMap<>();
for (int i : set) {
pos.put(i, 0);
neg.put(i, 0);
all.put(i, 0);
}
int pos_ = 0;
int neg_ = 0;
for (int i = 0; i < n; ++i) {
if (y[i] == 1) pos_ += 1;
else neg_ += 1;
}
double p3 = pos_ * 1.0 / n;
double p4 = neg_ * 1.0 / n;
double sub = - p3 * Math.log(p3) / Math.log(2) - p4 * Math.log(p4) / Math.log(2);
for (int i = 0; i < n; ++i) {
int key = x[i];
if (y[i] == 1) {
pos.put(key, pos.get(key) + 1);
}
else {
neg.put(key, neg.get(key) + 1);
}
all.put(key, all.get(key) + 1);
}
for (int key : set) {
int cnt = all.get(key);
double factor = cnt * 1.0 / n;
double p1 = pos.get(key) * 1.0 / cnt;
double p2 = neg.get(key) * 1.0 / cnt;
if (pos.get(key) == cnt || pos.get(key) == 0) {
sum += factor * 0;
}
else {
double gain = - p1 * Math.log(p1) - p2 * Math.log(p2);
sum += factor * gain;
}
}
String f = String.format("%.2f", sub - sum);
System.out.println(f);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String num = in.nextLine().trim();
int n = Integer.parseInt(num);
int[] x = new int[n];
int[] y = new int[n];
for (int i = 0; i < n; ++i) {
String[] line = in.nextLine().trim().split(",");
int x_ = Integer.parseInt(line[0].trim());
int y_ = Integer.parseInt(line[1].trim());
x[i] = x_;
y[i] = y_;
}
solve(x, y);
in.close();
}
} 第二题：KL距离（100%）
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class XC2 {
public static void solve(String[] as, String[] bs) {
Map<String, Double> a_prob = getRatio(as);
Map<String, Double> b_prob = getRatio(bs);
double sum = 0;
for (String v : a_prob.keySet()) {
double px = a_prob.getOrDefault(v, 0.0);
double qx = b_prob.getOrDefault(v, 0.0);
sum += px * Math.log(px / qx) / Math.log(2);
}
String f = String.format("%.2f", sum);
System.out.println(f);
}
public static Map<String, Double> getRatio(String[] as){
int as_len = as.length;
Map<String, Integer> mem = new HashMap<>();
for (String a : as) {
mem.put(a, mem.getOrDefault(a, 0) + 1);
}
Map<String, Double> a_prob = new HashMap<>();
for (String a : mem.keySet()) {
a_prob.put(a, mem.get(a) * 1.0 / as_len);
}
return a_prob;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String a = in.nextLine().trim();
String b = in.nextLine().trim();
String[] as = a.split("\\s+");
String[] bs = b.split("\\s+");
solve(as, bs);
in.close();
}
} 第三题：朴素贝叶斯（100%）
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class XC3 {
static String[] goods = { "high cost performance", "Great place", "Have a good time", "quite special", "good place",
"easy of access", "Very worth a visit", "tickets are cheap", "convenient traffic", "overall feels good",
"worth to see", "very convenient traffic", "very fun", "a good place", "The ticket is cost-effective",
"the overall feeling is good", "the place worth going", "the view is good", "the overall is not bad",
"feel good", "the scenery is very good", "the scenery is not bad", "I like it very much", "Really good",
"It's worth seeing", "The ticket is not expensive", "The ticket is very cheap", "The scenery is not bad",
"The price is very good", "It's still very good", "The scenery is very good", "The environment is great",
"The scenery is OK", "The air is very fresh", "Very worth seeing", "Very worth going", "Good view",
"Good traffic", " Value this price", "good value for money" };
static String[] bads = { "low cost performance", "I don't prefer it", "Nothing fun", "Nothing special",
"Nothing good-looking", "Traffic is not very convenient", "Nothing special", "Tickets are too expensive",
"Traffic inconvenient", "The overall feeling is bad", "Nothing to play", "Never come again",
"Nothing to see", "Feeling bad", "Tickets are a bit expensive", "very bad", "The scenery is bad",
"There is nothing to watch", "I don't like it", "The price is a bit expensive",
"cost performance is too low", "I feel not good", "not high cost performance", "Not very fun",
"Tickets are not cheap ", "traffic is not convenient", "the scenery is not good", "nothing to play",
"too commercial", "tickets are expensive", "fare is a bit expensive", "nothing to see", "price not cheap",
"price is very high", "ticket too expensive", "The traffic is not good", "The ticket is too expensive",
"The scenery is very poor", "Not worth the price", "The traffic is bad" };
static double pos = goods.length * 1.0 / (goods.length + bads.length);
static double neg = bads.length * 1.0 / (goods.length + bads.length);
static Map<String, Double> total(String[] data){
Map<String, Integer> mem = new HashMap<>();
int cnt = 0;
for (String da : data) {
String[] sp = da.split("\\s+");
for (String key : sp) {
key = key.toLowerCase();
mem.put(key, mem.getOrDefault(key, 0) + 1);
cnt ++;
}
}
Map<String, Double> ratio = new HashMap<>();
for (String key : mem.keySet()) {
int val = mem.get(key);
ratio.put(key, val * 1.0 / cnt);
}
return ratio;
}
static double cmp(String line, Map<String, Double> ratio) {
double cmp = 1;
for (String key : line.split("\\s+")) {
double p1 = ratio.getOrDefault(key, 1.0);
cmp *= p1;
}
return cmp;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String line = in.nextLine().trim();
Map<String, Double> go = total(goods);
Map<String, Double> ba = total(bads);
double cmp1 = pos * cmp(line, go);
double cmp2 = neg * cmp(line, ba);
System.out.println(cmp1 >= cmp2 ? 1 : 0);
in.close();
}
}#携程##笔试题目##题解#
