在从1到n的正数中1出现的次数(栈和队列)

在从1到n的正数中1出现的次数(栈和队列)

时间: 1ms        内存:1000M

描述:

题目:输入一个整数n,求从1nn个整数的十进制表示中1出现的次数。
例如输入12,从112这些整数中包含1 的数字有11011121一共出现了5次。

输入:

输入:

12

输出:

输出:

5

示例输入:

21

示例输出:

13

提示:

参考答案(内存最优[752]):

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node
{
	char  data[100];     
	struct  node  *next;
}node;
typedef  struct
{
	node  *front,*rear;
}queue; 
void InQueue(queue *s,char x[])
{                           
	node *p;
	p=(node*)malloc(sizeof(node));
	strcpy(p->data,x);                         
	p->next=NULL;                       
	if (s->front==NULL)                   
		s->front=p;
	else
		s->rear->next=p;
	s->rear=p;
}
int OutQueue(queue *s,char *x)
{
	node *p;
	if (s->front==NULL)                
		return 0;
	else
	{
		p=s->front;                      
		s->front=p->next;
		strcpy(x,p->data);
		if(s->front==NULL)
			s->rear=NULL;
		free(p);                  
		return 1;
	}
}
queue *InitQueue()
{
	queue *q;
	q=(queue*)malloc(sizeof(queue));
	q->front=q->rear=NULL;          
	return q;
}
int main()
{
	queue *p;
	int n,i,s=0;
	char c[100],x[100];
	p=InitQueue();
	scanf("%d",&n);
	i=1;
	while(i<=n)
	{
		sprintf(c,"%d",i);
		InQueue(p,c);
		i++;
	}
	while(p->front!=p->rear)
	{
		OutQueue(p,x);
		for(i=0;x[i]!='\0';i++)
			if(x[i]=='1')
				s++;
	}
	printf("%d\n",s+1);
	return 0;
}

参考答案(时间最优[0]):

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node
{
	char  data[100];     
	struct  node  *next;
}node;
typedef  struct
{
	node  *front,*rear;
}queue; 
void InQueue(queue *s,char x[])
{                           
	node *p;
	p=(node*)malloc(sizeof(node));
	strcpy(p->data,x);                         
	p->next=NULL;                       
	if (s->front==NULL)                   
		s->front=p;
	else
		s->rear->next=p;
	s->rear=p;
}
int OutQueue(queue *s,char *x)
{
	node *p;
	if (s->front==NULL)                
		return 0;
	else
	{
		p=s->front;                      
		s->front=p->next;
		strcpy(x,p->data);
		if(s->front==NULL)
			s->rear=NULL;
		free(p);                  
		return 1;
	}
}
queue *InitQueue()
{
	queue *q;
	q=(queue*)malloc(sizeof(queue));
	q->front=q->rear=NULL;          
	return q;
}
int main()
{
	queue *p;
	int n,i,s=0;
	char c[100],x[100];
	p=InitQueue();
	scanf("%d",&n);
	i=1;
	while(i<=n)
	{
		sprintf(c,"%d",i);
		InQueue(p,c);
		i++;
	}
	while(p->front!=p->rear)
	{
		OutQueue(p,x);
		for(i=0;x[i]!='\0';i++)
			if(x[i]=='1')
				s++;
	}
	printf("%d\n",s+1);
	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注