9.14 去哪儿笔试(开发)(含个人解题思路代码)

如果有更好的思路欢迎在评论区讨论。 共勉~

第一题:如果一个数可以整除3,那么它每位数的和一定是3的倍数。
我们记录下来0-9每个数出现了多少次,并记录一下这些数的和 sum。
计算 sum % 3
0: 符合要求,直接输出就好。
1: 需要删除一个 %3 = 1 的数,如果没有就删除两个 %3 = 2的数。
2: 同1。
public String solution1(int[] d) {
    int[] cnt = new int[10];
    int[] modulo = new int[3];
    int sum = 0;
    for (int t : d) {
        ++cnt[t];
        ++modulo[t % 3];
        sum += t;
    }
    int l; // %3 == l的数 删除 r 个
    int r;
    int mod = sum % 3;
    if (mod == 0) {
        l = r = 0;
    } else {
        if (modulo[mod] >= 1) {
            l = mod;
            r = 1;
        } else {
            l = 2 * mod % 3;
            r = 2;
        }
    }
    StringBuffer buffer = new StringBuffer();
    for (int i = 0; i < 10; i++) {
        char ch = (char) (i + '0');
        for (int j = 0; j < cnt[i]; ++j) {
            if (r > 0 && i % 3 == l) {
                --r;
            } else {
                buffer.append(ch);
            }
        }
    }
    // 0000 的情况
    if (buffer.length() > 0 && buffer.charAt(buffer.length() - 1) == '0') {
        buffer = new StringBuffer("0");
    }
    return buffer.reverse().toString();
}



第二题:记录下来所有正数的和 sum。
负数扔到优先队列中(从大到小)从中依次取数,定义一个变量t 记录要选的所有负数的和。
那么选择一个负数带来的收益就是 sum + t(t是负的)。
只需判断 abs(t) 是否小于等于 sum 。
更好的思路:
一个sum记录选择的数的和。 每选一个数,带来的收益就是sum。
//笔试时写的
public int solution2(int[] arr) {
    int sum = 0;
    PriorityQueue<Integer> que = new PriorityQueue<>();
    PriorityQueue<Integer> fuQ = new PriorityQueue<>((o1, o2) -> o2 - o1);
    for (int t : arr) {
        if (t >= 0) {
            sum += t;
            que.add(t);
        } else {
            fuQ.add(t);
        }
    }
    int k = 1;
    int ans = 0;
    int t = 0;
    int last = 0;
    while (!fuQ.isEmpty()) {
        t += fuQ.remove();
        if (-t <= sum) {
            ans += t;
            k++;
        }
    }
    while (!que.isEmpty()) {
        t = que.remove();

        ans += t * k;
        k++;
    }
    return ans;
}
// 更好的思路
public static int solution2_2(int[] arr) {
    Arrays.sort(arr);
    int ans = 0;
    int sum = 0;
    for(int i = arr.length - 1; i >= 0 ;i--){
        sum+=arr[i];
        if(sum > 0) ans += sum;
        else break;
    }
    return ans;
}




第三题:我的算法最差应该是 O(n2) 的时间复杂度。
我发现一个规律,半回文串都是  1232123 、 1234321234 这种由两个回文串组成。第一个: 12321 和 32123 。第二个1234321、4321234。
但是长度为4的半回文串不符合上述规律,需单独处理。 if(s[i] == s[i+2] && s[i+1] == s[i+3])
然后利用马拉车算法 (O(n)) 求出 每个下标为中心 的回文串长度。去判断上述规律。 len[i] == len[j] && j - i == len[i]/2 - 2;  len[i] 表示以 s[i] 为中心的回文串的长度。
判断最差是O(n2)的算法。
public int solution3(String str) {
    if (str == null || str.length() < 4) return 0;
    StringBuilder sb = new StringBuilder();
    sb.append("$");
    char[] s = str.toCharArray();
    int ans = 0;
    for (int i = 0; i < str.length(); i++) {
        if (i + 3 < str.length())
            if (s[i] == s[i + 2] && s[i + 1] == s[i + 3]) ans++;
        sb.append('#');
        sb.append(s[i]);
    }

    sb.append("#@");
    int n = sb.length();
    int[] p = new int[n];
    int id = 0, mx = 0;
    int idex = 0;
    for (int j = 1; j < n - 1; j++) {
        p[j] = mx > j ? Math.min(p[2 * id - j], mx - j) : 1;
        while (sb.charAt(j + p[j]) == sb.charAt(j - p[j])) {
            p[j]++;
        }
        if (mx < p[j] + j) {
            mx = p[j] + j;
            id = j;
        }
    }
    for (int j = 2; j < n - 1; j += 2) {
        if (p[j] >= 6) {
            int tem = p[j];
            for (int i = j + p[j] - 2; i >= j + 4; i -= 2) {
                if (p[i] >= tem) ans++;
                tem-=2;
            }
        }
    }
    return ans;
}





#去哪儿##笔试题目#
全部评论
第三题,字符串长度为15时返回2,否则返回3,能骗60
4 回复 分享
发布于 2021-09-14 19:25
大佬,第二题怎么做
1 回复 分享
发布于 2021-09-14 19:26
第三个编程题,题目描述是多组输入,但是代码给的是单个输入, 我该了代码的输入样例全过了,改之前0% , 有人遇到这种情况吗?
1 回复 分享
发布于 2021-09-14 17:19
大家的招聘进度还是笔试吗
点赞 回复 分享
发布于 2021-09-19 14:14
第一题0.6思路和楼主一样,第二题先排降序,然后依次相加,直到总和小于0,记住该下标,从该下标开始往前公式计算相加,就是最大值了,用例全通过A1,第三题没做,return 2 A了0.4
点赞 回复 分享
发布于 2021-09-15 12:50
第一题暴力dfs+剪枝只过了80%😂
点赞 回复 分享
发布于 2021-09-15 11:25
笔试多久出结果呀😋
点赞 回复 分享
发布于 2021-09-14 19:23
第二题是只能选择三个元素吗,这题意绝了
点赞 回复 分享
发布于 2021-09-14 18:21
还有这种操作码????前两个我都没AC
点赞 回复 分享
发布于 2021-09-14 17:41

相关推荐

点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
怎么起名字:早知道就不读书了,害得我送外卖还得扶眼镜
点赞 评论 收藏
分享
评论
4
14
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务