IT校招全国统一模拟笔试(秋招三模)编程题参考代码

练习地址:https://www.nowcoder.com/test/5986669/summary

DNA片段

分析

挨着扫一遍,维护都是DNA碱基的连续序列的长度最大值即可。

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;

int main() {
    cin >> s;
    int cnt = 0, mx = 0;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') {
            cnt++;
            if(mx < cnt) {
                mx = cnt;
            }
        } else {
            cnt = 0;
        }
    }
    cout << mx << endl;
}

彩色瓷砖

分析

分析
因为有4种颜色可以轮转,所以我们直接两个两个的统计是否是相同颜色的个数即可。

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
    cin >> s;
    int cnt = 0;
    for(int i = 1; i < s.size(); i++) {
        if(s[i - 1] == s[i]) {
            cnt++;
            i++;
        }
    }
    cout << cnt << endl;
    return 0;
}

偶串

分析

枚举最后得到的偶串的长度,然后暴力去check是否是偶串。这里是倒着枚举的所以得到的第一个满足条件的即是所求答案。

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
    cin >> s;
    for (int slen = (s.size() - 1) / 2; slen >= 1; slen--) {
        bool is_even_str = true;
        for (int i = 0; i < slen; i++) {
            if (s[i] != s[slen + i]) {
                is_even_str = false;
                break;
            }
        }
        if (is_even_str) {
            cout << (slen * 2) << endl;
            return 0;
        }
    }
    return 0;
}

制造回文

分析

统计每种字符的数量,然后提取一个奇数个数的字符放在第一个回文串中心,对于每个剩下的字符,两个相同字符放在回文串左右,直接用每种字符的数量对2取余即可,如果还有剩下的单一字符都只能单独为一个回文串。

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
    cin >> s;
    vector<int> t(26);
    for(char c : s) {
        t[c - 'a']++;
    }
    int ans = 1;
    for(int i = 0; i < 26; i++) {
        if(t[i] & 1) {
            t[i]--;
            break;
        }
    }
    for(int i = 0; i < 26; i++) {
        t[i] %= 2;
    }
    for(int i = 0; i < 26; i++) {
        if(t[i]) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

猜数游戏

分析

仔细分析我们可以发现一个位置是Y还是N依赖于他的倍数。
考虑若干个素数p0,p1,p2...p3,当他们的乘积那个数确定为Y,那么它们一定也是Y。

例如:
如果27是Y,那么9一定是Y,3也一定是Y,但是81可以是Y或者N。

由于每个数都可以分解为若干素数的乘积。于是我们考虑范围内的素数及其k次幂的位置的情况,其他数字都可以由这些组合而来。
例如:n = 64 考虑2的次幂:
如果64是Y,那么32 16 8 4 2都要是Y;
如果64是N,32是Y,16 8 4 2都要是Y;
如果64 32是N,16是Y,8 4 2都要是Y;
...
依次类推一共有7种情况(因为64 = 2^6)
那么问题就变成计算每个素数p_i^(maxexp) <= n,然后情况数就是每个(maxexp + 1)的乘积

参考代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
int vis[maxn];

int main() {
    int n;
    scanf("%d", &n);
    long long ans = 1;
    for(int i = 2; i <= n; i++) {
        if(vis[i]) continue;
        for(int j = i + i; j <= n; j += i) vis[j] = 1;
        int tmp = n, cnt = 0;
        while(tmp >= i) tmp /= i, cnt++;
        ans = ans * (cnt + 1) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}
#Java工程师##C++工程师##iOS工程师##安卓工程师##运维工程师##前端工程师##算法工程师#
全部评论
猜数做了一个多小时,最后还是没有思路,看别人几行代码就搞定了,,,内心很受伤啊
点赞 回复
分享
发布于 2017-07-25 21:14
制造回文这道题题目不难,就是理解最少的回文串是啥意思,我理解了半个小时,然后想明白了,时间到了,可惜了。
点赞 回复
分享
发布于 2017-07-25 21:42
饿了么
校招火热招聘中
官网直投
又学到了! 制造回文那里统计每个字符个数之后,可以计算所有个数中的奇数个数,便是结果。 int cnt[26]{ 0 }; for (size_t i = 0; i < str.size(); ++i) { ++cnt[str[i] - 'a']; } int res = 0; for (int i = 0; i < 26; ++i) { res += cnt[i] & 0x01; } std::cout << res << std::endl;
点赞 回复
分享
发布于 2017-07-25 21:17
第3题猜数字,按照参考代码运行n=5时,结果和n=6的结果一样都是12 真正n=6的结果应该是16吧
点赞 回复
分享
发布于 2017-07-25 21:35
制造偶串的O(n)算法,应用KMP的next数组。 #include <bits/stdc++.h> using namespace std; int solve(string& s) { vector<int> next(s.size(), 0); int j = 0, i = 1; while (i < s.size()) { if (s[i] == s[j]) { next[i] = j+1; ++i; ++j; } else if (j != 0) { j = next[j-1]; } else { ++i; } } for (i = next.size() - 3; i >= 0; i -= 2) { if (next[i] * 2 == i + 1 || next[i] == i) { return i + 1; } } return 0; } int main() { freopen("in.txt", "r", stdin); string s; while (cin >> s) { cout << solve(s) << endl; } return 0; }
点赞 回复
分享
发布于 2017-07-25 21:55
制造回文,应该是最简单的解法了吧0.0 String tmp = new Scanner(System.in).next(); int[] map = new int[26]; for(int i=0;i<tmp.length();i++){ int c = tmp.charAt(i)-'a'; map[c]++; } int count1 = 0; for(int i=0;i<26;i++) if(map[i]!=0 && (map[i]&1) == 1) count1++; System.out.println(count1);
点赞 回复
分享
发布于 2017-07-25 23:49
求素数次幂可以优化为如下方式。 ans = ans * (int)(floor(log(n)/log(i)) + 1) % mod;
点赞 回复
分享
发布于 2017-07-26 15:05
猜数游戏可以用回溯法做吧
点赞 回复
分享
发布于 2017-07-25 21:04
//偶串 import java.util.Scanner; public class Main {     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         String in = scanner.nextLine();         for(int i = 2 ; i < in.length() ; i+=2){         int it = in.length() - i;         String st1 = in.substring(0, it / 2);         String st2 = in.substring(it / 2, it);         if(st1.equals(st2)){         System.out.println(it);         return;         }         }     } } //回文 import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Scanner; public class Main {     public static void main(String[] args) {     Map<Character, Integer> inMap = new HashMap<Character, Integer>();         Scanner scanner = new Scanner(System.in);         char[] in = scanner.nextLine().toCharArray();         for(char ct : in){         Integer tmp = inMap.get(ct);         if(tmp == null){         inMap.put(ct, 1);         }else{         inMap.put(ct, tmp + 1);         }         }         int out = 0;         Iterator it = inMap.keySet().iterator();         while(it.hasNext()){         if(inMap.get(it.next()) % 2 == 1){         out++;         }         }         System.out.println(out == 0 ? 1 : out);     } }
点赞 回复
分享
发布于 2017-07-25 21:16
制造回文,我的理解最少回文的个数就是个数为奇数的字符的个数总和,但是最后时间不够了,还没有验证,不知道对不对
点赞 回复
分享
发布于 2017-07-25 21:18
偶串 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.nextLine(); int maxLen = 0; for (int i = 1; i < s.length() - 2; i += 2) { int newLen = (i + 1) / 2; if (s.substring(0, newLen).equals(s.substring(newLen, i + 1))) { maxLen = Math.max(maxLen, newLen); } } System.out.println(maxLen*2); scanner.close(); } 回文 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.nextLine(); int[] flags = new int[26]; char[] chas = s.toCharArray(); int num = 0; for (int i = 0; i < chas.length; i++) { flags[chas[i] - 'a']++; } for (int i = 0; i < flags.length; i++) { if (flags[i] > 0 && flags[i] % 2 != 0) { num++; } } System.out.println(num); scanner.close(); }
点赞 回复
分享
发布于 2017-07-25 21:21
死鱼猜数。。我用递归做的,打屎只能20%。。。
点赞 回复
分享
发布于 2017-07-25 21:23
import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Scanner; //制造回文 public class MakePlalindrome { public static void main(String[] args) { int result = 0; Map<Character, Integer> dic = new HashMap<Character, Integer>(); Scanner input = new Scanner(System.in); String str = input.nextLine(); char[] chars = str.toCharArray(); for (char c : chars) { if(!dic.containsKey(c)){ dic.put(c, 1); }else{ dic.put(c, dic.get(c)+1); } } // System.out.println(dic.toString()); Iterator iter = dic.entrySet().iterator(); while (iter.hasNext()) { Map.Entry entry = (Map.Entry) iter.next(); int val = (int) entry.getValue(); if(val%2 == 1){ result++; } } System.out.println(result); } }
点赞 回复
分享
发布于 2017-07-25 21:25
import java.util.Scanner; // 偶串 public class EvenString { public static void main(String[] args) { Scanner input = new Scanner(System.in); String str = input.nextLine(); int len = str.length(); int result = 0; for(int i = 2;i<len;i+=2){ String substr = str.substring(0, len-i); if(isEvenString(substr)){ result = substr.length(); break; } } System.out.println(result); } public static boolean isEvenString(String str){ int len = str.length(); if(len%2==0){ int i=0,j=len/2; for(;i<len/2;i++){ if(str.charAt(i) == str.charAt(j)){ j++; }else{ return false; } } }else{ return false; } return true; } }
点赞 回复
分享
发布于 2017-07-25 21:26
http://blog.csdn.net/cchenliang/article/details/76098911 使用 javascript 解法的
点赞 回复
分享
发布于 2017-07-25 21:34
制造回文串这个题,其实只要统计出现此时为奇数的字符的个数就可以,出现次数为偶数的字符 可以直接放在出现次数为奇数的字符的两侧。如果统计结果中出现次数为奇数的字符个数为0, 则输出字符串的size,这种情况对应把所有字符拆分为单个字符的情况,否则输出统计结果。 #include <iostream> #include <vector> #include <string.h> using namespace std; int main(){ int i = 0; string s; while(cin >> s){ vector<int> count(256, 0); for(i = 0;i < s.size();i++){ count[s[i]]++; } int oddNum = 0; for(i = 0;i < count.size();i++){ if(count[i] % 2 == 1) oddNum++; } if(oddNum == 0) cout << s.size() << endl; else cout << oddNum << endl; } return 0; }
点赞 回复
分享
发布于 2017-07-29 12:09
小伙子,吊炸天啊
点赞 回复
分享
发布于 2017-07-25 21:04
有Java版吗
点赞 回复
分享
发布于 2017-07-25 21:07
卒于猜数。。。
点赞 回复
分享
发布于 2017-07-25 21:09
偶串: bool compare(string s1, string s2) { return s1.compare(s2) == 0; } int solve(string s) { int size = s.size(); if ((size % 2) != 0) size -= 1; else size -= 2; while (size) { if (compare(s.substr(0, size / 2), s.substr(size / 2, size / 2))) break; //重点是这里折半比较 else size -= 2; } return size; } 回文: int solve(string s) { map<char, int> m; int size = s.size(); int num = 0; for (int i = 0;i < size;i++) { m[s[i]]++; if (m[s[i]] == 2) { ++num; m[s[i]] = 0; } } return  size - num * 2;  }
点赞 回复
分享
发布于 2017-07-25 21:09

相关推荐

点赞 68 评论
分享
牛客网
牛客企业服务