欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数组标记法在算法题中的应用

程序员文章站 2022-04-09 14:03:26
#数组标记法在算法题中的应用 什么?!你还不知道数组在算法题中不仅起储存数据的作用,还可以起链接标记的作用?哈哈不要紧,原来我也是不知道的,我是看了我好哥们的做题思路才知道这个方法的。。。 我们先声明一个长度为5数组arr[5],再为arr[5]赋值arr[]={"q","w","e","r",“t ......
#数组标记法在算法题中的应用
什么?!你还不知道数组在算法题中不仅起储存数据的作用,还可以起链接标记的作用?哈哈不要紧,原来我也是不知道的,我是看了我好哥们的做题思路才知道这个方法的。。。
----
我们先声明一个长度为5数组arr[5],再为arr[5]赋值arr[]={"q","w","e","r",“t”}。这样我们访问arr[0]值为“q”,arr[1]值为w...你会发现通过数组arr[i]=某个字母,序号与字母形成了一种索引关系,即序号指向了数组中的某一个元素,这就好比python中的字典,c++中的map,数组的序号可以看做是键(key),对应的元素就可以看做是值(value),这样我们就可以解决很多问题,比如让编译器和我们都头疼的数组(或字符串去重问题),pta中有很多这样的例题,下面我们看一道。。。
---
1093 字符串a+b (20 分)
给定两个字符串 a 和 b,本题要求你输出 a+b,即两个字符串的并集。要求先输出 a,再输出 b,但重复的字符必须被剔除。

输入格式:
输入在两行中分别给出 a 和 b,均为长度不超过 10^6的、由可见 ascii 字符 (即码值为32~126)和空格组成的、由回车标识结束的非空字符串。

输出格式:
在一行中输出题面要求的 a 和 b 的和。

输入样例:
this is a sample test
to show you_how it works
输出样例:
this ampletowyu_hrk
---
字符串拼接可以说是基本操作,我们在这儿就不在赘述了(拼接后的的字符串我们声明为a吧),我们主要谈谈如何实现字符串去重,常规方法,也是最容易想到的方法就是,设立两层循环,复制a字符串(副本我们称之为b吧)外层循环遍历拼接后字符串的每个字母,内层循环用外层当前的字母i与副本b中的当前字符i以后的字符比较,如果在b中没有找到与当前字符相同的字符,我们就输出i;这样做的时间复杂度为o(n^2).
我们大可以换个思路。。。字符和是否重合的状态其实是一个索引的关系,即每个字符对应了一种状态(有或无),这样我们就可以使用我们之间提到的数组来维持两者的关系。当然你会说数组的序号是一个数字,怎么能把字符当序号呢?答案是字符都对应这唯一的ascii码啊,这就可以作为数组索引的目录。
(```)
#include<stdio.h>
#include<string.h>
int main()
{
     char a1[100000];
     char b1[100000];
     int c[128] = { 0 };//初始化这个数组的的所有元素都为0
     gets(a1);
     gets(b1);
     for (int i = 0; i <strlen(a1); i++)
     {
         if (c[a1[i]] == 0)
         {
             c[a1[i]] = 1;
             printf("%c",a1[i]);
         }
     }
     for (int i = 0; i < strlen(b1); i++)
     {
         if (c[b1[i]] == 0)
         {
             c[b1[i]] = 1;
/*每当出现一个新字符就讲b1[i]在c中对应的值改成1,当之后读取到c[b1[i]]==1时,程序就知道b1[i]在之前出现过了*/
             printf("%c",b1[i]);
         }
     }
     return 0;
}
(```)
 
这样我们就完成了对字符串的去重处理,时间复杂度o(n),在oj中更有优势。当然这只是数组标记法在本题中中的一个小小应用,至少在pta中这个方法屡试不爽,希望大家都能够运用好此方法,为自己的算法刷题锦上添花。