今天算是菜鸡这些天笔试以来做的最好的一次了，分享一下1、3题AC的代码，第二题不太明白，希望有大佬赐教，代码写的不太好，能给大家启发一下思路就行
第一题手撕adaboost，公式给你了，照着公式做即可，这边就把adaboost作为一个类实现了一下
class Adaboost{
int[][] train_data;
int[] true_result;
double[] weights;
int[] is_error;
double[] a;
int M;
int N;
public Adaboost(int[][] train_data_result, int[] true_result){
this.train_data = train_data_result;
M = train_data.length;
N = train_data[0].length;
this.true_result = true_result;
weights = new double[N];
is_error = new int[N];
a = new double[M];
Arrays.fill(weights, 1.0/N);
}
void train(){
for(int i=0; i<M; i++){
for(int j=0; j<N; j++){
if(train_data[i][j] == true_result[j]){
is_error[j] = 0;
}else{
is_error[j] = 1;
}
}
double ei = 0;
for(int k=0; k<N; k++){
ei += weights[k] * is_error[k];
}
if(ei==0){
a[i] = 1;
}else if(ei==1){
a[i] = 0;
}else{
a[i] = 0.5 * Math.log((1-ei)/ei);
}
double zm = 0;
for(int k=0; k<N; k++){
zm += weights[k] * Math.exp(-a[i] * true_result[k] * train_data[i][k]);
}
for(int k=0; k<N; k++){
weights[k] = weights[k] * Math.exp(-a[i] * true_result[k] * train_data[i][k]) / zm;
}
}
}
int check(int[] inputs){
double result = 0;
for(int i=0; i<M; i++){
result += a[i] * inputs[i];
}
return result>=0 ? 1 : -1;
}
} 第二题点技能，用回溯只能过40%，不知道大佬们有没有其他更巧妙的方法
第三题实现sql，sql的意思大致是给n组数据，遍历数据中的所有user_id，找出和该user_id购买相同道具的其他user_id的数量，并按user_id的大小排序
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[][] ids = new int[n][3];
HashMap<Integer, HashSet<Integer>> uid_to_iid = new HashMap(); //uid对应道具id
HashMap<Integer, HashSet<Integer>> iid_to_uid = new HashMap(); //道具id对应uid
for(int i=0; i<n; i++){
ids[i][0] = in.nextInt();
ids[i][1] = in.nextInt();
ids[i][2] = in.nextInt();
if(!uid_to_iid.containsKey(ids[i][1])){
uid_to_iid.put(ids[i][1], new HashSet<Integer>());
}
uid_to_iid.get(ids[i][1]).add(ids[i][2]);
if(!iid_to_uid.containsKey(ids[i][2])){
iid_to_uid.put(ids[i][2], new HashSet<Integer>());
}
iid_to_uid.get(ids[i][2]).add(ids[i][1]);
}
Arrays.sort(ids, new Comparator<int[]>() { @Override public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});
HashSet<Integer> username_has_visit = new HashSet<>();
for(int i=0; i<n; i++){
if(!username_has_visit.contains(ids[i][1])){
HashSet<Integer> set = uid_to_iid.get(ids[i][1]);
username_has_visit.add(ids[i][1]);
HashSet<Integer> ans = new HashSet<>();
for(Integer iid : set){
if(iid_to_uid.get(iid).size()>1){
for(Integer uid : iid_to_uid.get(iid)){
ans.add(uid);
}
}
}
if(ans.size()-1 > 0)
System.out.println(ids[i][1] + " " + (ans.size()-1));
}
}
}
} 
全部评论
(5) 回帖