第一次习题课
阶乘和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int cal(int x){
int cal=1;
for(int i=2;i<=x;i++){
cal*=x;
}
return cal;
}
int fun(LinkList L){
LNode p=L->next;
int ans=0;
while(p){
ans+=cal(p->data);
p=p->next;
}
}
|
数组
在长度为N的数组arr中，将小于等于arr[0]的数放在数组的左半部分，大于arr[0]的放在右半部分， arr[0]介于中间，输出处理后的数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<iostream>
using namespace std;
const int N=100010;
int arr[N];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
int num=arr[0];
int i=0,j=n-1;
while(i<j){
while(arr[j]>=num&&i<j)j--;
while(arr[i]<=num&&i<j)i++;
swap(arr[i],arr[j]);
}
swap(arr[j],arr[0]);
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
return 0;
}
|
链表重排
有一个长度为n有序的带头结点单链表L={a1,a2…an}，设计一个空间复杂度O(1)，时间上尽可能高效的 算法，重新排列L中的结点，得到线性表L’={a1,an,a2,an-2….}，给出算法设计思想并实现，说明时间复杂度
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
| void fun(LinkList &L,int n){
LNode *p;
p=head->next;
LNode *q;
LNode *r;
int i=0;
while(i++<n/2)
p=p->next;
r=p->next;
q=NULL;
while(r){
p=r->next;
r->next=q;
q=r;
r=p;
}
p=head->next;
while(p->next&&q->next){
r=p->next;
s=q->next;
p->next=q;
q->next=r;
p=r;
q=s;
}
if(q->next==null)
p->next=q;
else
q->next=p;
}
|
链表合并
求两个递增有序带头结点链表LA和LB的并集，形成的新的链表，假设这两个链表都不含有重复的数字， 求并集指的是LA和LB共有的元素只保留一个
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
| LinkList fun(LinkList &LA,LinkList &LB){
LNode *p=LA->next;
LNode *q=LB->next;
LA->next=NULL;
LNode *r=LA;
int num=9999;
while(p!=NULL&&q!=NULL){
if(p->data<=q->data){
if(p->data!=num){
r->next=p;
r=r->next;
num=p->data;
}
p=p->next;
}else{
if(q->data!=num){
r->next=q;
r=r->next;
num=q->data;
}
q=q->next;
}
}
if(p!=NULL)r->next=p;
if(q!=NULL) r->next=q;
return LA;
}
|
火车站
有一列火车车厢进站，可以通过中转站改变出站顺序，现在的问题是，给定入站顺序和出栈顺序后，请问该站 的容纳量至少为多少节车厢？例如，进站顺序为ABCD，出站顺序为DCBA，则该站台的容纳量至少为4.保证出 站顺序合法 第一行输入n，表示总共有n节车厢 第二行输入n个字母表示进站的车厢序列 第三行输入n个字母表示出站的车厢序列 输出x表示站台的容纳量 输入： 5 ABCDE CBEDA 输出： 3
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<stack>
using namespace std;
const int N=100010;
int n;
char In[N];
char Out[N];
int main(){
stack<char> t;
cin>>n;
scanf("%s",In);
scanf("%s",Out);
int ans=0;
int i=0,j=0;
while(i<n){
if(t.empty()||t.top()!=Out[i]){
t.push(In[j]);
j++;
if(ans<t.size())
ans=t.size();
}else{
t.pop();
i++;
}
}
cout<<ans;
return 0;
}
|
画圈
输入n 表示有一个nxn的地图，地图由星组成，输入两个坐标（x1,y1），（x2,y2），由该两点形成一个 矩形，矩形由“1”组成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<iostream>
#include<stack>
using namespace std;
int arr[107][107];
int n;
int main(){
int x1,y1,x2,y2;
cin>>n>>x1>>y1>>x2>>y2;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(((i==x1||i==x2)&&j>=y1&&j<=y2)||((j==y1||j==y2)&&i>=x1&&i<=x2))
cout<<"1";
else
cout<<"*";
}
cout<<endl;
}
return 0;
}
|
QAQ
输入一行行由大写字母组成的字符串，数一数有多少个QAQ？QAQ三个字母任意一个位置不同，则总数+1，例如 QAQQ 位置123，算一个QAQ，而位置124也算一个QAQ，因此共有两个QAQ，答案为2 输入： QAQAQBCDEF 输出： 4 解释：123，125，145，345 (数字代表字母的位置)，以上共有4个QAQ
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
| #include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int fun(char arr[]){
int len=strlen(arr);
int cnt=0;
for(int i=0;i<len;i++){
if(arr[i]=='Q'){
for(int j=i+1;j<len;j++){
if(arr[j]=='A'){
for(int k=j+1;k<len;k++){
if(arr[k]=='Q')
cnt++;
}
}
}
}
}
return cnt;
}
int fun(char arr[]){
int len=strlen(arr);
int cnt=0;
int pre[N]={0};
for(int i=1;i<=len;i++){
if(arr[i-1]=='Q')
pre[i]=pre[i-1]+1;
else
pre[i]=pre[i-1];
}
for(int i=0;i<len;i++){
if(arr[i]=='A')
cnt+=pre[i]*(pre[len]-pre[i]);
}
return cnt;
}
int main(){
char arr[100];
scanf("%s",arr);
cout<<fun(arr);
return 0;
}
|
后缀表达式
编写函数，求后缀表达式的值，后缀表达式存在一个字符数组exp中，假设后缀式的数字都只有一位。
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
| #include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
double op(int a,char op,int b){
if(op=='+') return a+b;
if(op=='-') return a-b;
if(op=='*') return a*b;
if(op=='/') {
if(b==0){
return 0;
}
return (a*1.0)/(b*1.0);
}
}
double fun(char exp[]){
int len=strlen(exp);
double stack[N];
int top=-1;
for(int i=0;i<len;i++){
if(exp[i]>='0'&&exp[i]<='9')
stack[++top]=exp[i]-'0';
else{
double a,b,c;
b=stack[top--];
a=stack[top--];
c=op(a,exp[i],b);
stack[++top]=c;
}
}
return stack[top];
}
int main(){
char a[100];
scanf("%s",a);
cout<<fun(a);
return 0;
}
|
逆序无头结点单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void reserve(Linklist &L){
if(L==NULL&&L->next==NULL)
return;
LNode *p=L;
L=NULL;
LNode *q=NULL;
while(p){
q=p->next;
p->next=L;
L=p;
p=q;
}
}
|
区间反转
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。
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
| ListNode* reverseBetween(ListNode* head,int m,int n){
if(n-m==0) return head;
int cnt=1;
ListNode *p=head;
ListNode *last=nullptr;
while(cnt<m){
cnt++;
last=p;
p=p->next;
}
ListNode *left=p;
ListNode *nxt;
ListNode *pre=nullptr;
while(p!=NULL&&cnt<=n){
nxt=p->next;
p->next=pre;
pre=p;
p=nxt;
cnt++;
}
if(last!=NULL){
last->next=pre;
Left->next=p;
return head;
}else{
head->next=p;
return p;
}
}
|
判断是否有环
1
2
3
4
5
6
7
8
9
10
11
12
| bool hasCycle(Linklist head){
ListNode *p=head;
ListNode *q=head;
while(1){
if(p==NULL||p->next==NULL||p->next->next==NULL)
return false;
p=p->next->next;
if(p==q)
return true;
q=q->next;
}
}
|
微信
支付宝
