奇虎360研发工程师内推笔试编程题-2016年

编程题

1、正在挑战一个CrackMe的你，把需要填写的前面几位密码都正确猜出了，可是这最后一位密码，好像藏得有点深。CrackMe的作者还挑衅般的在里面藏了个.tar.gz文件，解压缩出来，里面写道
你要的最后一个字符就在下面这个字符串里，这个字符是下面整个字符串中第一个只出现一次的字符。（比如，串是abaccdeff，那么正确字符就是b了） 然而下面给出来的字符串好像太长太长了，单靠人力完全无法找出来。
于是，你需要写一个程序代劳了。输入文件体积较大，请使用一些快速的输入输出手段，不推荐使用cin/cout，对Java并不推荐使用Scanner直接读写。

输入描述:

第一行，一个正整数T(T≤20)  ，表示输入数据组数。
之后T行，每行一个字符串S。( 1≤S  的长度≤1000000   ，保证字符串中出现的字符的ASCII码在[0x21,0x7F)范围内，即均为可显示的非空白符，同时保证一定有解)

输出描述:

一共T 行，每行一个字符C ，表示所给的相应字符串中第一个只出现一次的字符。

输入例子:

2
abaccdeff
testonline

输出例子:

b
s

2、360员工桂最近申请了一个长假，一个人背着包出去自助游了。
　　路上，他经过了一个小镇，发现小镇的人们都围在一棵树下争吵。桂上前询问情况，得知小镇的人们正缺一个镇长，他们希望能选一个知名又公正的镇长，即，大家希望能选出一个人，所有人都认识他，但同时他不认识镇上除自己以外的其他人（在此，我们默认每个人自己认识自己）。可是小镇里的人太多了，一下子大家谁也说服不了谁。
　　“这简单啊。”桂表示。于是他一下子统计出来了镇上人们相互之间的认识关系，并且一下子找到了合适的镇长人选。
　　现在你手上也拿到了这样一份认识关系的清单。其中上面给出的认识关系是单向的，即，A认识B与B认识A是相互独立的，只给出A认识B就不能认为B认识A，例如，我认识你，你不一定认识我。而且，这里的认识关系也不具有传递性，即，A认识B，B认识C，但这不代表A认识C。同时，为了方便处理，这份清单中，镇上的N个人依次编号为1到N。你能否像桂一样快速找到合适的镇长人选呢？

输入描述:

首先一个正整数T（T≤20），表示数据组数。
之后每组数据的第一行有2个整数n  和m  (1≤n≤105 ,0≤m≤3×105 )，依次表示镇上的人数和相互之间的认识关系数。
之后m行，第 i 行每行两个数Ai和Bi   (1≤Ai ,Bi ≤n  )，表示Ai认识Bi。（保证没有重复的认识关系，但可能存在自己认识自己的认识关系）
保证所有数据中80%的数据满足n≤1000,m≤10000

输出描述:

一共2T 行，每组数据对应2行。
第一行，一个整数，表示你所找出来的合适的镇长人选人数num i   。
第二行，num i 个整数，每两个数中间用空格隔开，表示你所选的合适的镇长的编号。
特别的，如果并没有找到合适的镇长，第一行输出一个数0，第二行留空即可（参见样例）。

输入例子:

3
2 0
3 2
1 2
3 2
4 5
1 1
2 1
3 1
4 1
3 3

输出例子:

0

1
2
1
1

参考答案

1、

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
typedef long long ll;
 
const int MAXN=1000000;
 
int idx[256];
int T;
char str[MAXN+5];
 
int main(){
    for(scanf("%d",&T);T--;){
        scanf("%s",str+1);
        memset(idx,0,sizeof(idx));
        for(int i=1;str[i];i++){
            if(idx[str[i]]==0){
                idx[str[i]]=i;
            }else{
                idx[str[i]]=-1;
            }
        }
        char ans='\0';
        for(int i=0x21;i<0x7F;i++){
            if(idx[i]>0){
                if(ans==0||idx[ans]>idx[i]) ans=i;
            }
        }
        printf("%c\n",ans);
    }
    return 0;
}

2、

#include <iostream>
#include <vector>
using namespace  std;
int main()
{
    int T;
    cin >> T;
    int n, m;
    vector<int> *mayor = new vector<int>[T];
    int k = 0;
    while (k < T && cin >> n >> m) {
        unsigned int* elected = new unsigned int [n+1]; // 被投票的次数
        unsigned int* elect = new unsigned int [n+1]; // 投票的次数
        for (int i = 0; i < n+1; i++) {
            elected[i] = 0;
            elect[i] = 0;
        }
        int A, B;
        // 输入 m 组关系数
        for (int i = 0; i < m; i++) {
            cin >> A >> B;
            if (A != B) {
                elected[B]++; // A 认识 B，B被投一票
                elect[A]++; // A 投出一票
            }
        }
        for (int i = 1; i < n+1; i++) {
            if (elected[i] == n-1 && elect[i] == 0)
                mayor[k].push_back(i); // 得到 n-1 个选票，投出 0 票的人是镇长人选
        }
        delete []elected;
        delete []elect;
        k++;
    }

    for (int i = 0; i < T; i++) {
        cout << mayor[i].size() << endl;
        for (int j = 0; j < mayor[i].size(); j++) {
            if (j > 0)
                cout << " ";
            cout << mayor[i][j];
        }
        cout << endl;
    }
    delete []mayor;
}