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

code

4 年前

时间： 1ms 内存：1000M

描述：

题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。
例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。

输入：

输入：

12

输出：

输出：

5

示例输入：

示例输出：

提示：

参考答案（内存最优[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;
}

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