算法练习（九）

一、数星星 （线性结构）

题目描述

小明是一名天文爱好者，他喜欢晚上看星星。这天，他从淘宝上买下来了一个高级望远镜。他十分开心，于是他晚上去操场上看星星。
不同的星星发出不同的光，他的望远镜可以计算出观测到的星星发出的光的数值W。小明当然想尽可能地多看到星星，于是他每看到一颗星星，就要看看他之前有没有看过这颗星星。但是他看的星星太多了，他根本数不过来，于是他让你帮忙。

输入描述

共有两行，第一行只有一个整数，为小明观测到的星星的数量n。第二行有n个整数，每两个整数由一个空格隔开，分别为小明观测到每颗星星的光的数值W[1]-W[n]。

输出描述

只有一行，这一行共有n个数字0或1。0表示对应的星星之前没有观测到，1表示对应的星星之前已经看过了。注意：数字之间没有空格！

样例输入

5
1 5 5 4 1

样例输出

00101

题目链接

代码

//输入值需考虑范围
#include<stdio.h>

int main() {
	int n,i;
	scanf("%d",&n);
	int a[n],b[100] = {0};
	for (i = 0; i < n; i++) {
		scanf("%d",&a[i]);
	}
	for (i = 0; i < n; i++) {
		printf("%d",b[a[i]]);
		b[a[i]] = 1;
 	}
 	return 0;
}

---

#include<stdio.h>
#include<string.h>
#define mod 500009//大于50万的最小素数 
long long hash[mod*2];
int n,w[mod];
int i;
int flag;
int main()
{
    memset(hash,-128,sizeof(hash));//赋最小值 为 -2139062144 
    scanf("%d",&n);
    for( i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
        int k=abs(w[i])%mod;//字符下标非负 并缩小k的大小 
        flag=0;
        while(hash[k]>=-2000000000)
        {
            if(hash[k]==w[i])
               flag=1;//是否已经看过 
            k++;
        }
        hash[k]=w[i];//往后放到空位置 
        if(flag)
          printf("1");
        else 
          printf("0");
    }
    return 0;
}

解题思路

略

二、数的位置

题目描述

给一个数组，返回一个大小相同的数组。返回的数组的第i个位置的值应当是，对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素（如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上-1）。

例如：

input: 5,3,1,2,4
return: -1 3 1 1 -1

代码

#include<stdio.h>
int n;
int a[100];

int sum(int x) {
	int c;
	for (c = x;c < n; c++) {
		if (a[c] > a[x])
			return c-x;
	}
	return -1;
}


int main() {
	int i;
	for (i = 0; scanf("%d",&a[i]) != EOF; i++);
	n = i;
	
	for (i = 0; i < n; i++) {
		printf("%d ",sum(i));
	}
	
	return 0;
}

解题思路

略

附：明天开始改变自己！！！

以上