Part1 2/23

1有这样一道智力题:“某商店规定:三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶,她最多可以换多少瓶汽水喝?”答案是5瓶,方法如下:先用9个空瓶子换3瓶汽水,喝掉3瓶满的,喝完以后4个空瓶子,用3个再换一瓶,喝掉这瓶满的,这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水,喝掉这瓶满的,喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有n个空汽水瓶,最多可以换多少瓶汽水喝?

  • My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
int ans=0;
while(n>0)
{
if(n==1)
{
break;
}
else if(n==2)
{
n=n-2;
ans++;
break;
}
else//n>=3
{
int temp=n/3;
ans=ans+temp;
n=n%3+temp;;
}
}
if(ans>0) cout<<ans<<endl;
}
system("pause");
return 0;
}
  • 此解法过于复杂;
  • 通过数学分析,最后获得的饮料总数是总空瓶数整除2;
  • 则有下代码
1
2
3
4
5
6
7
#include<stdio.h>
int main ()
{
int m;
while(~scanf("%d",&m)&&m!=0) printf("%d\n",m/2);
return 0;
}

2明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤1000),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据,希望大家能正确处理)。

  • My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
int Arr[1010]={0};
int If[1010]={0};
for(int i=0;i<n;i++)
{
int x;
cin>>x;
if(If[x]) continue;
If[x]=1;
Arr[i]=x;
}
sort(Arr,Arr+n);
for(int i=0;i<n;i++)
{
if(Arr[i]==0) continue;
cout<<Arr[i]<<endl;
}
}
system("pause");
return 0;
}
  • 思路:输入n个数,重复时不输入,最后排序,按从小到大的顺序输出正数;
  • 题解思路:声明一个足够大的数组,当输入的数为i时,令数组第i为置1;for循环输出,当数组该位为1时,输出位数;
  • 代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int main() {
int N, n;
while (cin >> N) {
int a[1001] = { 0 };
while (N--) {
cin >> n;
a[n] = 1;
}
for (int i = 0; i < 1001; i++)
if (a[i])
cout << i << endl;
}
return 0;
}

3写出一个程序,接受一个十六进制的数,输出该数值的十进制表示。

  • My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int main()
{
char str[100];
while(cin>>str)
{
int ans=strtol(str,NULL,16);
cout<<ans<<endl;
}
system("pause");
return 0;
}
  • C++可以规定输入进制数,不需要调用strtol函数;
  • 代码如下
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin>>hex>>n)
{
cout<<n<<endl;
}
system("pause");
return 0;
}

Question From:HERE

Part2 2/24

输入一个链表,反转链表后,输出新链表的表头。

  • My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
ListNode* ReverseList(ListNode* pHead);
int main()
{
system("pause");
return 0;
}
ListNode* ReverseList(ListNode* pHead)
{
if(pHead==NULL)
{
return NULL;
}
ListNode *Pre=NULL;
ListNode *Next=NULL;
while(pHead!=NULL)
{
Next=pHead->next;
pHead->next=Pre;
Pre=pHead;
pHead=Next;
}
return Pre;
}
  • 思路1:从头到尾遍历,新建反转链表,不过会浪费一些空间;
  • 思路2(以上代码思路):将pHead指针逐个后移,再通过Pre以及Next指针将原指针反转,最后返回链表头指针;

Question From:HERE

给定一个数组,请你编写一个函数,返回该数组排序后的形式。

1
2
3
4
5
6
7
8
vector<int> MySort(vector<int>& arr) {
// write code here
//sort(arr.begin(),arr.end());
//sort(begin(arr),end(arr));
//sort(arr.begin(),arr.end(),less<int>());
sort(begin(arr),end(arr),less<int>());
return arr;
}
  • 通过begin和end函数找到数组的起始位置和结束位置;

Question From:HERE

Part3 2/25

1老师想知道从某某同学当中,分数最高的是多少,现在请你编程模拟老师的询问。当然,老师有时候需要更新某位同学的成绩.

  • My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std;
int main()
{
int n,m;
while(cin>>n>>m)
{
int Grade[30010]={0};
for(int i=1;i<=n;i++)
{
int temp;
cin>>temp;
Grade[i]=temp;
}
while(m--)
{
char c;
int a,b;
cin>>c>>a>>b;
if(c=='Q')
{
if(a>b)
{
int temp=b;
b=a;
a=temp;
}
int max=0;
for(int i=a;i<=b;i++)
{
if(Grade[i]>max) max=Grade[i];
}
cout<<max<<endl;
}
else if(c=='U')
{
Grade[a]=b;
}
}
}
system("pause");
return 0;
}
  • 这道题没什么难度,唯一需要注意的是当输入字符为Q时,可能会有a>b的情况

2开发一个简单错误记录功能小模块,能够记录出错的代码所在的文件名称和行号。
处理:
1.记录最多8条错误记录,对相同的错误记录(即文件名称和行号完全匹配)只记录一条,错误计数增加;(文件所在的目录不同,文件名和行号相同也要合并)
2.超过16个字符的文件名称,只记录文件的最后有效16个字符;(如果文件名不同,而只是文件名的后16个字符和行号相同,也不要合并)
3.输入的文件可能带路径,记录文件名称不能带路径

  • My Code
  • A Little Bit Hard

3扑克牌游戏大家应该都比较熟悉了,一副牌由54张组成,含3~A,2各4张,小王1张,大王1张。牌面从小到大用如下字符和字符串表示(其中,小写joker表示小王,大写JOKER表示大王)😃
3 4 5 6 7 8 9 10 J Q K A 2 joker JOKER
输入两手牌,两手牌之间用“-”连接,每手牌的每张牌以空格分隔,“-”两边没有空格,如:4 4 4 4-joker JOKER
请比较两手牌大小,输出较大的牌,如果不存在比较关系则输出ERROR

  • My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <string>
using namespace std;
int getType(string str,int l);
int main()
{
string str;
while(getline(cin,str))
{
int index=str.find('-');
string left=str.substr(0,index);
string right=str.substr(index+1,str.length());
string Card="12345678910JQKA2jokerJOKER";
//Type of left and right
//Type: 1Single; 2Pair; 3Trible; 4joker; 5JOKER;
// 6Sequence; 7bomb; 8KingBomb
int ll=left.length();
int rl=right.length();
int typeOfLeft=getType(left,ll),typeOfRight=getType(right,rl);
//Solve the Problem
if(typeOfLeft<=6&&typeOfRight<=6&&typeOfLeft!=typeOfRight) cout<<"ERROR"<<endl;
else if(typeOfLeft==8) cout<<left<<endl;
else if(typeOfRight==8) cout<<right<<endl;
else if(typeOfLeft==7&&typeOfRight==7)
{
int indexLeftSpace=left.find(' '),indexRightSpace=right.find(' ');
string tl=left.substr(0,indexLeftSpace),tr=right.substr(0,indexRightSpace);
//cout<<tl<<" "<<tr<<endl;
int indexl=Card.find(tl),indexr=Card.find(tr);
if(indexl>indexr) cout<<left<<endl;
else if(indexl<indexr) cout<<right<<endl;
else cout<<"ERROR"<<endl;
}
else if(typeOfLeft==7) cout<<left<<endl;
else if(typeOfRight==7) cout<<right<<endl;
else if(typeOfLeft==5) cout<<left<<endl;
else if(typeOfRight==5) cout<<right<<endl;
else if(typeOfLeft==4) cout<<left<<endl;
else if(typeOfRight==4) cout<<right<<endl;
else
{
int indexLeftSpace=left.find(' '),indexRightSpace=right.find(' ');
string tl=left.substr(0,indexLeftSpace),tr=right.substr(0,indexRightSpace);
int indexl=Card.find(tl),indexr=Card.find(tr);
if(indexl>indexr) cout<<left<<endl;
else if(indexl<indexr) cout<<right<<endl;
else cout<<"ERROR"<<endl;
}
}
system("pause");
return 0;
}
int getType(string str,int l)
{
int numOfSpace=0;
for(int i=0;i<l;i++)
{
if(str[i]==' ') numOfSpace++;
}
if(str=="joker") return 4;
else if(str=="JOKER") return 5;
else if(str=="joker JOKER"||str=="JOKER joker") return 8;
else if(l<=2) return 1;
else if(numOfSpace==1) return 2;
else if(numOfSpace==2) return 3;
else if(numOfSpace==3) return 7;
else return 6;
}
  • 思路
    1. 找到输入字符串‘-’的位置;
    2. 在该位置将字符串分成left,right两个字串;
    3. 分别判断出两个字串的类型;
    4. 比较大小;
    5. 问题的解。

Question From:HERE

Part4 2/27

1写出一个程序,接受一个字符串,然后输出该字符串反转后的字符串。(字符串长度不超过1000)

  • My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string Reverse(string str);
int main()
{
string s;
while(cin>>s)
{
cout<<Reverse(s)<<endl;
}
system("pause");
return 0;
}
string Reverse(string str)
{
reverse(str.begin(),str.end());
return str;
}
  • 函数:直接调用< algorithm>头文件中的reverse函数

Question From:HERE

2大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。

  • My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
int Fibonacci(int n);
int main()
{
int n;
while(cin>>n)
{
cout<<Fibonacci(n)<<endl;
}
system("pause");
return 0;
}
int Fibonacci(int n)
{
if(n==0) return 0;
else if(n==1) return 1;
else if(n==2) return 1;
else return Fibonacci(n-1)+Fibonacci(n-2);
}

Question From:HERE

3给定一个字符串,请编写一个函数判断该字符串是否回文。如果回文请返回true,否则返回false。

  • My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <string>
using namespace std;
bool judge(string str);
int main()
{
string s;
while(cin>>s)
{
if(judge(s)) cout<<"true"<<endl;
else cout<<"false"<<endl;
}
system("pause");
return 0;
}
bool judge(string str)
{
int l=str.length();
int mid=l/2;
if(l%2==0)//even
{
for(int i=0,j=l-1;i<=mid;i++,j--)
{
if(str[i]!=str[j]) return false;
else return true;
}
}
else//odd
{
for(int i=0,j=l-1;i<mid;i++,j--)
{
if(str[i]!=str[j]) return false;
}
return true;
}
}

Question From:HERE

4山峰元素是指其值大于或等于左右相邻值的元素。给定一个输入数组nums,任意两个相邻元素值不相等,数组可能包含多个山峰。找到索引最大的那个山峰元素并返回其索引。

  • My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int peak(int* a,int aLen);
int main()
{
system("pause");
return 0;
}
int peak(int* a,int aLen)
{
for(int i=aLen-1;i>=0;i--)
{
if(i==aLen-1)
{
if(a[i]>a[i-1]) return i;
}
else
{
if(a[i]>a[i-1]&&a[i]>a[i+1]) return i;
}
}
return 0;
}
  • 这道题很简单,不过以上代码还有可以简化的地方;
  • 将条件设为a[i]>a[i-1],好处为:如果循环到第i位,说明a[i+1]<a[i],所以下次不需要再次判断a[i+1]和a[i]的关系;
  • 答案代码如下
1
2
3
4
5
6
7
8
int solve(int* a, int aLen) {
// write code here
for(int i=aLen-1;i;i--)
{
if(a[i]>a[i-1])return i;
}
return 0;
}

Question From:HERE

Points

  • C++可以规定输入进制数

    1
    2
    3
    //Example 16
    int x;
    cin>>hex>>x;
  • 数组函数 begin end

    1
    2
    3
    4
    5
    6
    int Arr[]={1,2,3,......,n}//random number
    begin(Arr)->1;
    end(Arr)->n
    //convenient when needed to be sorted
    #include <algorithm>
    sort(begin(Arr),end(Arr));
  • C++中输入反斜杠’’

    1
    2
    3
    4
    5
    6
    7
    8
    /*
    在C++编程中有时候会遇到有些符号不能直接输入,像反斜杠'\',如果直接输入会出现:错误的终止了宏调用的错误,这时我们就需要把这些符号转义一下
    For Example
    */
    #include <string>
    string str='\';//Wrong!
    string str='\\';//Correct!
    //使用转义字符'\\',这样其实输入的还是'\'//
  • C++ Pair结构

  • C++ reverse函数

    1
    2
    3
    4
    #include <algorithm>
    #include <string>
    string str="abcd";
    reverse(str.begin(),str.end());
  • C++ vector结构