putchar

  1. int putchar(int c)
  2. 向标准输入写一个字符
  3. 返回写了几个字符,EOF(-1)表示写失败

getchar

  1. int getchar(void)
  2. 从标准输入读入一个字符
  3. 返回类型是int是为了返回EOF(-1)
  4. Windows下 Ctrl+Z表示读入EOF状态
  5. Unix下 Ctrl+D表示读入EOF状态
#include<stdio.h>
#include<stdlib.h>

int main(int argc ,char const *argv[])
{
    int ch;
    while((ch = getchar())!=EOF)
    {
        putchar(ch);
    }
    return 0;
}

 

怀念一起去金山报道的好吉,一个很厉害的女孩子,去金山居然是为了复习考研顺便实习,知道真相的我被惊呆了,很佩服很佩服。怀念半夜跑出来讨论人生的小房子,金山第一实习生能够周末在公司学习到4点半,祝你在百度一切顺利。怀念帮我分析情感问题的金山罗霸,真的是一个极好的人,希望你能够成功的进入香港的大学念研究生,直到现在都还一直在帮我,可能我再也无法带她去长春见你了吧。怀念我的舍友东东童鞋,周末晚上一起上分到4点,PDF部门是真的很强,祝你在腾讯一切顺利。怀念我的另一个舍友鹏哥,在生活上帮助我很多,半夜和我爬到顶楼一起看风景,希望你能追到你的不二,找到更好的工作。怀念母喵,一起下班一起吃鸡一起学喵叫,想起了我曾经给你直播金山生活,想起了你给我送的麦片是真的好吃(真香),还有那天晚上我们一起去屋顶谈论的很多很多事情,没有你和我一起春招我可能真的进不去金山,祝你以后在金山珠海一切顺利,认识你很开心呢,可惜你好像不再理我了。怀念小和子,从湖南大学逃课出来实习还没记处分的一个小伙伴,你好像一直觉得我很强,其实我很弱很弱的啊啊啊!祝你以后在金山武汉的工作一切顺利。怀念西安交大那个不会C++却来了金山C++岗的bihuchao,一个痴迷计算机世界的核动力专业学生,和你膜蛤谈笑风生的日子很开心,一直一直没有像你说的那样看不起你,我从心底里一直都很佩服你的,祝你在百度一切顺利,后会有期。怀念最后没有来金山去深信服实习的广大同学,我的blog找不回来啦,你让我认识了QQ邮箱日历这个神奇的功能,然后大家每天一起相约leetcode,bihuchao刷题速度太恐怖啦,也曾深夜一起谈论过自己喜欢的女孩子,都是悲伤的故事呢,但是你和我的不同是你很强,祝你在腾讯和东东同学一切顺利。怀念徐建华童鞋,一个很可爱很可爱的重庆妹子,春招同时认识了你和你男朋友,可惜你男朋友没有成功拿到金山的offer,最后秋招你们一起去了网易,祝你们以后的人生一帆风顺。

怀念金山的小伙伴,怀念金山的第一实习生梗,怀念金山的海风,怀念金山的华南第一食堂,怀念金山的一切。。。我想念你们啦!

问题描述
  体育老师小明要将自己班上的学生按顺序排队。他首先让学生按学号从小到大的顺序排成一排,学号小的排在前面,然后进行多次调整。一次调整小明可能让一位同学出队,向前或者向后移动一段距离后再插入队列。
例如,下面给出了一组移动的例子,例子中学生的人数为8人。
0)初始队列中学生的学号依次为1, 2, 3, 4, 5, 6, 7, 8;
1)第一次调整,命令为“3号同学向后移动2”,表示3号同学出队,向后移动2名同学的距离,再插入到队列中,新队列中学生的学号依次为1, 2, 4, 5, 3, 6, 7, 8;
2)第二次调整,命令为“8号同学向前移动3”,表示8号同学出队,向前移动3名同学的距离,再插入到队列中,新队列中学生的学号依次为1, 2, 4, 5, 8, 3, 6, 7;
3)第三次调整,命令为“3号同学向前移动2”,表示3号同学出队,向前移动2名同学的距离,再插入到队列中,新队列中学生的学号依次为1, 2, 4, 3, 5, 8, 6, 7。
小明记录了所有调整的过程,请问,最终从前向后所有学生的学号依次是多少?
请特别注意,上述移动过程中所涉及的号码指的是学号,而不是在队伍中的位置。在向后移动时,移动的距离不超过对应同学后面的人数,如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。在向前移动时,移动的距离不超过对应同学前面的人数,如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。
输入格式
  输入的第一行包含一个整数n,表示学生的数量,学生的学号由1到n编号。
第二行包含一个整数m,表示调整的次数。
接下来m行,每行两个整数p, q,如果q为正,表示学号为p的同学向后移动q,如果q为负,表示学号为p的同学向前移动-q。
输出格式
  输出一行,包含n个整数,相邻两个整数之间由一个空格分隔,表示最终从前向后所有学生的学号。
样例输入
8
3
3 2
8 -3
3 -2
样例输出
1 2 4 3 5 8 6 7
评测用例规模与约定
  对于所有评测用例,1 ≤ n ≤ 1000,1 ≤ m ≤ 1000,所有移动均合法。
AC代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int n,m;
    vector<int> a;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    a.push_back(i);
    for(int cas=0;cas<m;cas++)
    {
        int x,y;
        cin>>x>>y;
        vector<int>::iterator it;
        for(it=a.begin();it!=a.end();it++)
            if(*it==x)
            break;
        a.erase(it);
        a.insert(it+y,x);

    }
    for(int i=0;i<a.size();i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;

}

 

问题描述
  请实现一个铁路购票系统的简单座位分配算法,来处理一节车厢的座位分配。
假设一节车厢有20排、每一排5个座位。为方便起见,我们用1到100来给所有的座位编号,第一排是1到5号,第二排是6到10号,依次类推,第20排是96到100号。
购票时,一个人可能购一张或多张票,最多不超过5张。如果这几张票可以安排在同一排编号相邻的座位,则应该安排在编号最小的相邻座位。否则应该安排在编号最小的几个空座位中(不考虑是否相邻)。
假设初始时车票全部未被购买,现在给了一些购票指令,请你处理这些指令。
输入格式
  输入的第一行包含一个整数n,表示购票指令的数量。
第二行包含n个整数,每个整数p在1到5之间,表示要购入的票数,相邻的两个数之间使用一个空格分隔。
输出格式
  输出n行,每行对应一条指令的处理结果。
对于购票指令p,输出p张车票的编号,按从小到大排序。
样例输入
4
2 5 4 2
样例输出
1 2
6 7 8 9 10
11 12 13 14
3 4
样例说明
  1) 购2张票,得到座位1、2。
2) 购5张票,得到座位6至10。
3) 购4张票,得到座位11至14。
4) 购2张票,得到座位3、4。
评测用例规模与约定
  对于所有评测用例,1 ≤ n ≤ 100,所有购票数量之和不超过100。
AC代码
#include <iostream>
#include<list>
#include<math.h>
using namespace std;
  int main(){
  int n,m,temp,Count;
  int a[200];
  int b[30];

  for(int i=0;i<20;i++){
    b[i]=5;
  }
  for(int i=0;i<100;i++){
    a[i]=1;
  }

  cin>>n;
  while(n--){
    cin>>m;
    Count =m;
    for(int i=0;i<20;i++)
  {
      temp = i;
     if(b[i]>=m){
        break;
     }
     else temp++;
  }
   if(temp==20){
    for(int i=0;i<100;i++)
    if((a[i]==1)&&(Count!=0)){
        cout<<i+1<<" ";
        Count--;
        a[i]=0;
    }



   }
   else{
    for(int j=temp*5;j<temp*5+5;j++){
        if((a[j]==1)&&(Count!=0)){
            a[j]=0;
            cout<<j+1<<" ";
            Count--;
        }
    }
      b[temp] = b[temp] - m;
    cout<<endl;
   }
  }
  }

 

问题描述
  有一个学校的老师共用N个教室,按照规定,所有的钥匙都必须放在公共钥匙盒里,老师不能带钥匙回家。每次老师上课前,都从公共钥匙盒里找到自己上课的教室的钥匙去开门,上完课后,再将钥匙放回到钥匙盒中。
钥匙盒一共有N个挂钩,从左到右排成一排,用来挂N个教室的钥匙。一串钥匙没有固定的悬挂位置,但钥匙上有标识,所以老师们不会弄混钥匙。
每次取钥匙的时候,老师们都会找到自己所需要的钥匙将其取走,而不会移动其他钥匙。每次还钥匙的时候,还钥匙的老师会找到最左边的空的挂钩,将钥匙挂在这个挂钩上。如果有多位老师还钥匙,则他们按钥匙编号从小到大的顺序还。如果同一时刻既有老师还钥匙又有老师取钥匙,则老师们会先将钥匙全还回去再取出。
今天开始的时候钥匙是按编号从小到大的顺序放在钥匙盒里的。有K位老师要上课,给出每位老师所需要的钥匙、开始上课的时间和上课的时长,假设下课时间就是还钥匙时间,请问最终钥匙盒里面钥匙的顺序是怎样的?
输入格式
  输入的第一行包含两个整数NK
接下来K行,每行三个整数wsc,分别表示一位老师要使用的钥匙编号、开始上课的时间和上课的时长。可能有多位老师使用同一把钥匙,但是老师使用钥匙的时间不会重叠。
保证输入数据满足输入格式,你不用检查数据合法性。
输出格式
  输出一行,包含N个整数,相邻整数间用一个空格分隔,依次表示每个挂钩上挂的钥匙编号。
样例输入
5 2
4 3 3
2 2 7
样例输出
1 4 3 2 5
样例说明
  第一位老师从时刻3开始使用4号教室的钥匙,使用3单位时间,所以在时刻6还钥匙。第二位老师从时刻2开始使用钥匙,使用7单位时间,所以在时刻9还钥匙。
每个关键时刻后的钥匙状态如下(X表示空):
时刻2后为1X345;
时刻3后为1X3X5;
时刻6后为143X5;
时刻9后为14325。
样例输入
5 7
1 1 14
3 3 12
1 15 12
2 7 20
3 18 12
4 21 19
5 30 9
样例输出
1 2 3 5 4
评测用例规模与约定
  对于30%的评测用例,1 ≤ NK ≤ 10, 1 ≤ w ≤ N, 1 ≤ sc ≤ 30;
对于60%的评测用例,1 ≤ NK ≤ 50,1 ≤ w ≤ N,1 ≤ s ≤ 300,1 ≤ c ≤ 50;
对于所有评测用例,1 ≤ NK ≤ 1000,1 ≤ w ≤ N,1 ≤ s ≤ 10000,1 ≤ c ≤ 100。
AC代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, k, w, s, c, key[1001];


struct Teacher//定义教师结构体
{
    int key;//钥匙编号
    int time;//使用钥匙时间
    int flag;//设置标识符
};

bool cmp(Teacher t1,Teacher t2){
    if(t1.time !=t2.time){
        return t1.time<t2.time;
    }
    else if(t1.flag !=t2.flag){
        return t1.flag >t2.flag;
    }
    else{
        return t1.key < t2.key;
    }
}
int main(){
std::ios::sync_with_stdio(false);
 vector<Teacher> v;//定义结构体向量
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        key[i] = i;
    }
    for(int i=0;i<k;i++)
    {
        cin>>w>>s>>c;
        Teacher t;
        t.key = w;
        t.time = s;
        t.flag = 0;//借
        v.push_back(t);
        t.key = w;
        t.time = s+c;
        t.flag = 1;//归还
        v.push_back(t);
    }
   sort(v.begin(),v.end(),cmp);

   for(int i=0;i<v.size();i++){
    Teacher t = v[i];
    if(t.flag==0)//借钥匙
    {
       for(int j = 1;j<=n;j++){
        if(key[j]==t.key){
            key[j]=0;
            break;
        }
       }

    }
   else {//还钥匙
      for(int j=1;j<=n;j++){
        if(key[j]==0){
            key[j]=t.key;
            break;
        }
      }
   }
   }
   for (int i=1;i<=n;i++){
    cout<<key[i]<<" ";
   }
   cout<<endl;
   return 0;
}

 

问题描述
  在图像编码的算法中,需要将一个给定的方形矩阵进行Z字形扫描(Zigzag Scan)。给定一个n×n的矩阵,Z字形扫描的过程如下图所示:

对于下面的4×4的矩阵,
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3
对其进行Z字形扫描后得到长度为16的序列:
1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3
请实现一个Z字形扫描的程序,给定一个n×n的矩阵,输出对这个矩阵进行Z字形扫描的结果。
输入格式
  输入的第一行包含一个整数n,表示矩阵的大小。
输入的第二行到第n+1行每行包含n个正整数,由空格分隔,表示给定的矩阵。
输出格式
  输出一行,包含n×n个整数,由空格分隔,表示输入的矩阵经过Z字形扫描后的结果。
样例输入
4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3
样例输出
1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3
评测用例规模与约定
  1≤n≤500,矩阵元素为不超过1000的正整数。
AC代码
#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int a[600][600];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }

int m=n*2-1;
int i=0,j=0;//iÊÇÐУ¬jÊÇÁÐ
        int sum = 0;
     while(m--){
        if(sum%2==0){
                cout<<a[i][j]<<" ";
            while((j+1)<n&&(i-1)>=0){
                cout<<a[i-1][j+1]<<" ";
        j++;
        i--;
            }
            sum++;
            if(sum<n)
            {j++;
            }
            else {
                i++;
            }

        }
        else if(sum%2==1){
        cout<<a[i][j]<<" ";
            while((i+1)<n&&(j-1)>=0){
                 cout<<a[i+1][j-1]<<" ";
               // cout<<i+1<<":"<<j-1<<endl;
        i++;
        j--;

        }
           sum++;
           if(sum<n)
            {i++;
            }
            else {
                j++;
            }

     }
}
  return 0;
}

 

问题描述
  JSON (JavaScript Object Notation) 是一种轻量级的数据交换格式,可以用来描述半结构化的数据。JSON 格式中的基本单元是值 (value),出于简化的目的本题只涉及 2 种类型的值:
* 字符串 (string):字符串是由双引号 ” 括起来的一组字符(可以为空)。如果字符串的内容中出现双引号 “,在双引号前面加反斜杠,也就是用 \” 表示;如果出现反斜杠 \,则用两个反斜杠 \\ 表示。反斜杠后面不能出现 ” 和 \ 以外的字符。例如:””、”hello”、”\”\\”。
* 对象 (object):对象是一组键值对的无序集合(可以为空)。键值对表示对象的属性,键是属性名,值是属性的内容。对象以左花括号 { 开始,右花括号 } 结束,键值对之间以逗号 , 分隔。一个键值对的键和值之间以冒号 : 分隔。键必须是字符串,同一个对象所有键值对的键必须两两都不相同;值可以是字符串,也可以是另一个对象。例如:{}、{“foo”: “bar”}、{“Mon”: “weekday”, “Tue”: “weekday”, “Sun”: “weekend”}。
除了字符串内部的位置,其他位置都可以插入一个或多个空格使得 JSON 的呈现更加美观,也可以在一些地方换行,不会影响所表示的数据内容。例如,上面举例的最后一个 JSON 数据也可以写成如下形式。
{
“Mon”: “weekday”,
“Tue”: “weekday”,
“Sun”: “weekend”
}
给出一个 JSON 格式描述的数据,以及若干查询,编程返回这些查询的结果。
输入格式
  第一行是两个正整数 n 和 m,分别表示 JSON 数据的行数和查询的个数。
接下来 n 行,描述一个 JSON 数据,保证输入是一个合法的 JSON 对象。
接下来 m 行,每行描述一个查询。给出要查询的属性名,要求返回对应属性的内容。需要支持多层查询,各层的属性名之间用小数点 . 连接。保证查询的格式都是合法的。
输出格式
  对于输入的每一个查询,按顺序输出查询结果,每个结果占一行。
如果查询结果是一个字符串,则输出 STRING <string>,其中 <string> 是字符串的值,中间用一个空格分隔。
如果查询结果是一个对象,则输出 OBJECT,不需要输出对象的内容。
如果查询结果不存在,则输出 NOTEXIST。
样例输入
10 5
{
“firstName”: “John”,
“lastName”: “Smith”,
“address”: {
“streetAddress”: “2ndStreet”,
“city”: “NewYork”,
“state”: “NY”
},
“esc\\aped”: “\”hello\””
}
firstName
address
address.city
address.postal
esc\aped
样例输出
STRING John
OBJECT
STRING NewYork
NOTEXIST
STRING “hello”
评测用例规模与约定
n ≤ 100,每行不超过 80 个字符。
m ≤ 100,每个查询的长度不超过 80 个字符。
字符串中的字符均为 ASCII 码 33-126 的可打印字符,不会出现空格。所有字符串都不是空串。
所有作为键的字符串不会包含小数点 .。查询时键的大小写敏感。
50%的评测用例输入的对象只有 1 层结构,80%的评测用例输入的对象结构层数不超过 2 层。举例来说,{“a”: “b”} 是一层结构的对象,{“a”: {“b”: “c”}} 是二层结构的对象,以此类推。
AC代码
#include <iostream>
#include <string>
#include <map>
#include <cstdio>
using namespace std;

int n, m;
string s, str;
bool key;
map<string, string> json;

string handle(string str, string s)
{
    if (s.empty())
    {
        return str;
    }
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == ' ')
        {
            continue;
        }
        else if (s[i] == '{')
        {
            json[str] = "OBJECT";
            key = true;
        }
        else if (s[i] == '}')
        {
            int i;
            for (i = str.size() - 1; i >= 0; i--)
            {
                if (str[i] == '.')
                {
                    break;
                }
            }
            if (i < 0)
            {
                str = "";
            }
            else
            {
                str = str.substr(0, i);
            }
        }
        else if (s[i] == ':')
        {
            key = false;
        }
        else if (s[i] == ',')
        {
            key = true;
        }
        else if (s[i] == '"')
        {
            string temp;
            for (i = i + 1; i < s.size(); i++)
            {
                if (s[i] == '\\')
                {
                    i++;
                    temp += s[i];
                }
                else if (s[i] == '"')
                {
                    break;
                }
                else
                {
                    temp += s[i];
                }
            }
            if (key)
            {
                if (str == "")
                {
                    str = temp;
                }
                else
                {
                    str += '.' + temp;
                }
            }
            else
            {
                json[str] = "STRING " + temp;
                int i;
                for (i = str.size() - 1; i >= 0; i--)
                {
                    if (str[i] == '.')
                    {
                        break;
                    }
                }
                if (i < 0)
                {
                    str = "";
                }
                else
                {
                    str = str.substr(0, i);
                }
            }
        }
    }
    return str;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> m;
    cin.get();

    while (n--)
    {
        getline(cin, s);
        str = handle(str, s);
    }
    while (m--)
    {
        cin >> s;
        cout << (json[s] == "" ? "NOTEXIST" : json[s]) << endl;
    }
    return 0;
}

 

奇数回文串

定义奇数回文串是一个正读和反读都一样的,长度为奇数的字符串,比如“level”或者“non”就是奇数回文串。

请用不高于O(n^2)复杂度(以str.length()为准)的算法写出以下函数的实现代码。

int func(const std::string& str);

 

str中的字符只可能是小写的拉丁字母,该函数的返回值为str中最长的奇数回文子串的长度。 例如: str为“abba”,则函数的返回值为1。

str为“abcba”,则函数的返回值为5。

str为“eabcmcbad”,则函数的返回值为7。

str为“dddcbamabc”,则函数的返回值为7。

str为“cbamabcddd”,则函数的返回值为7。

我的代码

#include<iostream>
using namespace std;

int func(string str){
      int maxi = 0;
      int temp = 0;
      int count = 0;
      for(int i = 0; i < str.length()  ;i++){
            temp = i;
           int j = i;
           j -- ;
           i ++ ;
           while(j >= 0 && i <= str.length()-1 && str[i] == str[j]){
                count = count + 2;
                i++;
                j--;
           }
           if(count > maxi){
            maxi = count;
           }
           count = 0;
           i = temp;
      }
      return maxi+1;
}

int main(){
       string str1 = "abba";
       string str2 = "abcba";
       string str3 = "eabcmcbad";
       string str4 = "dddcbamabc";
       string str5 = "cbamabcddd";
       cout<<func(str1)<<endl;
       cout<<func(str2)<<endl;
       cout<<func(str3)<<endl;
       cout<<func(str4)<<endl;
       cout<<func(str5)<<endl;
}

排序题

实现如下函数:int GetNthCount(const int *a , int len , int n)

其中,a为无序的int数组,len为a的长度,1<= n <len。

返回第n大的值在数组中出现的次数。

举例:假设a为{5,7,9,0,2,7},len=6,n=2,第n大的值是7,在数组中出现的次数是2,结果返回2。

 

我的代码

#include<iostream>
#include<set>
#include<map>
using namespace std;

int GetNthCount(const int *a , int len ,int n){
         map < int ,int> mp;
         for(int i =0; i < len ;i++){
            map<int , int>::iterator it = mp.find(a[i]);
            if(it != mp.end()){
                it->second++;
            }
            else{
                mp[a[i]] = 1;
            }
         }
         map<int , int>::iterator it1 = mp.end();
         for(int i = 0; i < n;i++){
            it1--;
         }
        return it1->second;
}

int main(){
   int a[] = {5,7,9,0,2,7,7};
   cout<<GetNthCount(a, 7 ,2)<<endl;
}

 

Vector

实现vector中的insert方法

template<class T>

class vector

{

//从pos位置开始插入,elems为插入元素的指针地址,len为elems指向的长度

bool insert(size_t pos,T * elems,size_t len = 1);

private:

T* __begin;//容器开始地址

T* __end;//容器有效元素的结束地址

size_t  __cap;//容器的容量

};

 

void insert(const_iterator iter,const T& t )
        {  
            int index=iter-begin();
            if (index<size_)
            {
                if (size_==capacity_)
                {
                    int capa=calculateCapacity();
                    newCapacity(capa);
                }
                memmove(buf+index+1,buf+index,(size_-index)*sizeof(T)); 
                buf[index]=t;
                size_++;
            } 
        }