0814笔试回忆

1、二进制中的"101"

输入一个整数,求其二进制序列中用多少个'101',以及第一个'101'出现的位置,二进制序列右端为起始位置。

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;
string Base2Bin(string n){
    char a[32];
    int len_n = n.size()*4;
    int m;
    stringstream ss;
    ss<<n;
    ss>>m;
    for (int i=0; i<32; i++){
        a[i] = '0';
    }
    int j = 0;
    while(m){
        a[j] = m%2 + '0';
        m /= 2;
        j = j+1;
    }
    //cout<<endl;
    string str = "";
    for (int i=len_n-1; i>=0; i--){
        str += a[i];
    }
    return str;
}

int main(){
    string n;
    int num = 0;
    int begin = -1;
    int last_begin = 0;
    cin>>n;
    string str = Base2Bin(n);
    string p = "101";
    while((begin = str.find(p, begin+1)) != string::npos){
        if (begin != -1){
            last_begin = begin;
            num++;
            begin = begin+1;
        }
    }
    if (num == 0){
        cout<<num<<" "<<-1<<endl;
    }else{
        cout<<num<<" "<<str.size()-3-last_begin<<endl;
    }
    return 0;
}

2、 自定义数据存储格式

题目太长,待补充。。。

/*

测试用例: 
,"abc",1,"b,","a,""","6""",bk,,op,"fa","cd
*/ 

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    string cnt[100];
    freopen("in.txt", "r", stdin);
    getline(cin, s);
    int count = 0, flag = 0, len = s.size(), error = 0;
    for (int i=0; i<len; i++){
        if (s[i] == '"'){
            if (flag == 0) {
                if (cnt[count].size() > 0) error = 1; //如果"出现在字段中间 ,字段头却没有 
                else flag = 1;
            }
            else if (flag == 1){
                if (i < len-1 && s[i+1] != ','){
                    if (s[i+1] == '"') {//如果下一个还是" 
                        cnt[count] += '"';
                        i += 1;
                    }else{//如果不是", error 
                        error = 1;
                    }
                }
                else {
                    flag = 0;
                    if (i != len-1){//如果没结束 
                        count++;
                        i++;
                    }
                }
            }
        }
        else if (s[i] == ','){
            if (flag == 0) count++;
            else{
                cnt[count] += s[i];
            }
        }
        else {
            cnt[count] += s[i];
        }
    }
    if (flag || error){
        cout<<"ERROR"<<endl;
    }else{
        cout<<count + 1<<endl;
        for (int i=0; i<=count; i++){
            if (cnt[i] == "") cout<<"--"<<endl;
            else cout<<cnt[i]<<endl;
        }
    }
    return 0;
}

//个人理解,题目中的不明确信息太多,很难全A

3、 好友推荐

有一款社交软件APP,假设注册用户m人(0<m<50), 用户编号为0~m-1,
用r[i][j]表示用户i和用户j之间的好友关系
(r[i][j]=0代表i和j不是好友,r[i][j]=1~9代表是好友且数值代表熟悉程度,其中r[i][j] = r[j][i]),
编制程序,输出特定用户i的n度好友(1<=n<=10, 1表示直接好友,2表示好友的好友),
并按推荐值降序输出好友列表(若推荐值相同,则按好友编号升序, 推荐值是指关系熟悉度之和),
若此用户没有n度好友输出-1.

输入:
输入一个整数T,表示有T组数据(0<T<100)
对于每组数据,输入两行:
第一行, 输入3个整数m, i, n, m表示用户数, 某个特定的用户编号i, n度好友,
即表示本组数据需要输出用户i的n度好友
第二行, 输入一个整型k, 接下来输入3*k个整数, 每三个组成一个关系对,
每个关系有3个整数i, j, w, 表示i和j的好友熟悉程度, 没有输入的关系默认为非好友

输出:
输出T行, 每行对应每组测试数据的用户i的n度好友, 按推荐值降序输出,
若推荐值相同, 则按好友编号升序, 没有n度好友输出-1

测试用例:
输入:
2
10 5 2
13 0 3 5 0 4 9 0 6 8 0 7 5 1 2 6 1 6 3 2 9 7 3 4 3 3 5 3 3 8 3 3 9 3 5 8 9 7 8 9
10 0 2
13 0 3 5 0 4 9 0 6 8 0 7 5 1 2 6 1 6 3 2 9 7 3 4 3 3 5 3 3 8 3 3 9 3 5 8 9 7 8 9
输出:
7 0 4 9
1 5 8 9

/*
思路:
BFS至第n层, 中间可达的需标记 
*/

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>

using namespace std;
int r[55][55];
int vis[55];

typedef struct ND_Friend{
    int x, sum, degree;
}NDF;
bool compare (NDF left, NDF right) 
{
    if (left.sum != right.sum) {
        return left.sum > right.sum;
    }
    else return left.x < right.x;
}
queue<NDF> cq;

void BFS(int m, NDF index){
    vis[index.x] = 1;
    for (int i=0; i < m; i++){
        if (r[index.x][i] != 0 && vis[i] != 1){
            //cout<<i<<" "<<index.degree<<"degree"<<endl;
            NDF nd;
            nd.x = i;
            nd.sum = index.sum + r[index.x][i];
            nd.degree = index.degree - 1;
            cq.push(nd);
            vis[i] = 1;
        }
    }
}

int main(){
    int T;
    freopen("in.txt", "r", stdin);
    cin>>T;
    while(T--){
        int m, index, n;
        cin>>m>>index>>n;
        memset(r, 0, sizeof(r));
        memset(vis, 0, sizeof(vis));
        int k, i, j, w;
        cin>>k;
        for (int p=0; p<k; p++){
            cin>>i>>j>>w;
            r[i][j] = w;
            r[j][i] = w;
        }
        NDF root;
        root.x = index;
        root.sum = 0;
        root.degree = n;
        cq.push(root);
        while(!cq.empty()){
            NDF ndf = cq.front();
            if (ndf.degree == 0){
                break;
            }
            cq.pop();
            BFS(m, ndf);
        }
        if (cq.empty()){
            cout<<"-1"<<endl;
            break;
        }
        int p = 0;
        NDF nd_friend[55];
        while(!cq.empty()){
            NDF ndf = cq.front();
            cq.pop();
            nd_friend[p++] = ndf;
            //cout<<ndf.x<<" "<<ndf.sum<<endl;
        }
        sort(nd_friend, nd_friend+p, compare);
        for (int pp=0; pp<p; pp++){
            cout<<nd_friend[pp].x<<" ";
        }
        cout<<endl;
    }
    return 0;
}

/*
//遗留问题:
第二个测试用例:
0->3->8 推荐值8
0->7->8 推荐值14
都可达,推荐值不同,测试用例取了第一种,没有给出解释

*/
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,784评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,745评论 2 378
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,702评论 0 335
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,229评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,245评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,376评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,798评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,471评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,655评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,485评论 2 318
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,535评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,235评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,793评论 3 304
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,863评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,096评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,654评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,233评论 2 341

推荐阅读更多精彩内容