文档章节

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

o
 osc_w9s1w4o0
发布于 2019/04/02 22:41
字数 947
阅读 10
收藏 0

精选30+云产品,助力企业轻松上云!>>>

#数组标记法在算法题中的应用
什么?!你还不知道数组在算法题中不仅起储存数据的作用,还可以起链接标记的作用?哈哈不要紧,原来我也是不知道的,我是看了我好哥们的做题思路才知道这个方法的。。。
----
我们先声明一个长度为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中这个方法屡试不爽,希望大家都能够运用好此方法,为自己的算法刷题锦上添花。
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
LeetCode算法题-Count Primes(Java实现)

这是悦乐书的第190次更新,第193篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第49题(顺位题号是204)。计算小于非负数n的素数的数量。例如: 输入:10 输出:4 说明:有4...

小川94
2018/12/03
0
0
【算法】LeetCode算法题-Longest Common Prefix

这是悦乐书的第146次更新,第148篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第5题(顺位题号是14),给定一个随机的字符串数组,查找这些字符串元素的公共前缀字符串,如果...

小川94
2018/10/19
0
0
彻底理解回溯法的精要

给定一个没有重复数字的序列,返回其所有可能的全排列。示例: [TOC] 问题分析 使用什么方法? 全排列很明显使用回溯法来进行解答 什么是回溯法? 回溯法(探索与回溯法)是一种选优搜索法,又...

osc_i05nmotv
04/16
3
0
面试算法combine sum专题讲解一(回溯法)

combine sum是面试算法中最常考的一类题型,其主要思想是应用背包问题的延伸。 主要描述为:在一组数字中,寻找子数组,使子数组的元素和为target的所有组合,求罗列所有组合,或求解组合总数...

奋斗的小炎
03/31
0
0
【算法】LeetCode算法题-Longest Common Prefix

这是悦乐书的第146次更新,第148篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第5题(顺位题号是14),给定一个随机的字符串数组,查找这些字符串元素的公共前缀字符串,如果...

osc_8g11urw7
2018/10/19
2
0

没有更多内容

加载失败,请刷新页面

加载更多

科技人文丨玻璃心:承受阈值与表达

大家好,我是SKODE。 有趣的灵魂,聊科技人文。 本系列博客地址:传送门 本文转载自B站:安慰记传送门 玻璃心是网络用语,意思是: 对负面事件的接受度很低 还有对别人可能给出的负面评价非常...

osc_u9mt0sus
56分钟前
20
0
迅睿CMS 游客不允许上传附件

游客不允许上传附件 迅睿CMS系统:https://www.xunruicms.com/ 本文档原文地址:https://www.xunruicms.com/doc/752.html...

迅睿CMS-PHP开源CMS程序
56分钟前
12
0
代理,注解,接口和实现类的小测验

* retention : 保留* policy : 策略 ps : 简单测试了一下手写代理,jdk动态代理,和cglib动态代理,根据其不同的结果分析其原理 一:测试目的 主要想看一下不同的代理模式对于目标类中方法上注...

岁一
57分钟前
12
0
V-Ray 5 For 3ds Max 正式发布:超越渲染 - 知乎

15个新功能,V-Ray5助你时间更节省,渲染更出色! 作者:ChaosGroup VRay 5 For 3ds Max 已正式发布! 2分钟视频,抢先预览新功能↓ 知乎视频 www.zhihu.com V-Ray 5 for 3ds Max 新增功能 ...

osc_o9u1um45
57分钟前
0
0
毕业的笑容和悲伤永远是校园的回忆

校园的风轻轻的拂过我的脸庞,风儿显得更加凉爽, 开满火红的凤凰树,染遍了校园的每个角落, 晚上那枝头蝉儿的竞相鸣奏,唱满了令人不舍的毕业歌, 它们彷彿告诉了我们要毕业了。 毕业典礼那...

瑾123
58分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部