0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

算法面试真题:完美走位

算法与数据结构 来源:吴师兄学算法 2023-06-15 11:24 次阅读

题目

在第一人称射击游戏中,玩家通过键盘的A、S、D、W四个按键控制游戏人物分别向左、向后、向右、向前进行移动,从而完成走位。

假设玩家每按动一次键盘,游戏人物会向某个方向移动一步,如果玩家在操作一定次数的键盘并且各个方向的步数相同时,此时游戏人物必定会回到原点,则称此次走位为完美走位。

现给定玩家的走位(例如:ASDA),请通过更换其中一段连续走位的方式使得原走位能够变成一个完美走位。其中待更换的连续走位可以是相同长度的任何走位。

请返回待更换的连续走位的最小可能长度。若果原走位本身是一个完美走位,则返回0。

输入

输入为由键盘字母表示的走位s,例如:ASDA

输出

输出为待更换的连续走位的最小可能长度

备注

走位长度1 ≤ s.length ≤ 10^5

s.length是4的倍数

s中只含有A,S,D,W四种字符

示例一

输入

ASDW

输出

0

说明

已经是完美走位了。

示例二

输入

AASW

输出

1

说明

需要把一个A更换成D,这样可以得到ADSW或者DASW。

示例三

输入

AAAA

输出

3

说明

可以替换后3个A,得到ASDW。

示例四

输入

AAAAADDD

输出

4

解题思路

注意,本题和LC76. 最小覆盖子串几乎完全一致。重点在于如何将原问题转化为覆盖子串的问题。

题目有两个重要条件:

完美走位字符串是指字符串中A、S、D、W四种字符出现次数相等的字符串

s.length是4的倍数

对于长度为len(s)的原字符串s来说,为了使其转变为一个完美走位字符串,其中A、S、D、W四种字符出现次数应该均为num = len(s) // 4。

原字符串s中各个字符出现的次数可以用哈希表cnt_s = Counter(s)进行统计,对于出现次数多于num = len(s) // 4的字符ch,应该修改cnt_s[ch] - len(s) // 4个字符为其他出现次数少于num = len(s) // 4的字符,才能够使得s变为一个完美走位字符串。

以示例四为例,s = "AAAAADDD",字符"A"出现的次数为5,字符"D"应该修改3,而num = len(s) // 4 = 2,需要修改3个"A"和1个"D"为剩余两种字符,才能使得s变为完美走位字符串。故我们需要找到包含3个"A"和1个"D"的最小子串。

因此这个问题就转变为了,找到覆盖cnt_s[ch] - len(s) // 4个的字符ch(ch满足条件cnt_s[ch] > len(s) // 4)的最短子串。需要覆盖的子串中所出现的字符以及次数,可以用另一个哈希表cnt_sub储存。

那么这个问题就和LC76. 最小覆盖子串完全一致了。上述逻辑整理为代码即

num=len(s)//4
cnt_s=Counter(s)
cnt_sub={k:v-numfork,vincnt_s.items()ifv>num}

代码

#题目:2023Q1A-完美走位
#分值:100
#作者:许老师&&吴师兄学算法
#算法:不定滑窗
#代码看不懂的地方,请直接在群上提问


fromcollectionsimportCounter
frommathimportinf


#定义辅助函数check()
#用于检查cnt_sub中的各个字符是否出现在cnt_win中,
#且cnt_win中的个数大于等于cnt_sub
defcheck(cnt_win,cnt_sub):
returnall(cnt_win[k]>=cnt_sub[k]forkincnt_sub)


s=input()
num=len(s)//4
#获得原字符串中所有字符的出现次数
cnt_s=Counter(s)
#获得需要覆盖的子串的字符以及出现次数
cnt_sub={k:v-numfork,vincnt_s.items()ifv>num}

#如果cnt_sub长度为0,说明每一种字符出现次数相等
#s已经是一个完美走位字符串,输出0
iflen(cnt_sub)==0:
print(0)
#否则要进行类似LC76.最小覆盖子串的不定滑窗过程
else:
#初始化滑窗对应的哈希表、最小覆盖的窗口长度
cnt_win=Counter()
ans=inf
left=0

forright,chinenumerate(s):
# Q1:对于每一个右指针right所指的元素ch,做什么操作?
# A1:将其加入哈希表cnt_win的计数中
cnt_win[ch]+=1
# Q2:什么时候要令左指针left右移?在什么条件下left停止右移?【循环不变量】
# A2:check(cnt_win, cnt_sub)为True,left可以右移以缩小窗口长度
whilecheck(cnt_win,cnt_sub):
# Q3:什么时候进行ans的更新?
# A3:check(cnt_win, cnt_sub)为True
ans=min(ans,right-left+1)
cnt_win[s[left]]-=1
left+=1

print(ans)

时空复杂度

时间复杂度:O(N)。仅需一次遍历整个字符串s。

空间复杂度:O(1)。只有4种字符,哈希表所占用空间为常数级别空间。

审核编辑:汤梓红

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 算法
    +关注

    关注

    23

    文章

    4608

    浏览量

    92844
  • 键盘
    +关注

    关注

    4

    文章

    859

    浏览量

    39647
  • 字符
    +关注

    关注

    0

    文章

    233

    浏览量

    25199
  • 函数
    +关注

    关注

    3

    文章

    4329

    浏览量

    62576

原文标题:算法面试真题:完美走位

文章出处:【微信号:TheAlgorithm,微信公众号:算法与数据结构】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    电子设计大赛

    电子设计大赛
    发表于 07-28 19:35

    视频教程:Java七大外企经典面试套路之基础篇

    多年来名企在各地的Java笔试面试经验,需要的朋友可以看看,作为参考!课程目录:第1节 String Stringbuffer Stringbuilder 深度解析第2节 完美
    发表于 06-14 15:47

    免费视频教程:java经典面试题深度解析

    简介:精选多年来名企在各地的Java笔试面试经验课程目录:第一节 String Stringbuffer Stringbuilder 深度解析第二节 完美回答
    发表于 06-15 15:13

    java经典面试题深度解析

    教程,需要的朋友可以看看,作为参考!课程简介:精选多年来名企在各地的Java笔试面试经验课程目录:第一节 String Stringbuffer Stringbuilder 深度解析第二节
    发表于 06-20 15:16

    硬件经典面试100 (附答案)

    学电人员必备;硬件经典面试100;面向电子行业的面试基础问题,提前进入职业的大门
    发表于 10-12 14:28

    蓝桥杯省赛赛代码总结

    蓝桥杯省赛赛代码总结,亲测有效!
    发表于 07-25 09:10

    大疆创新校园招聘笔试题-硬件

    名企面试笔试:大疆创新校园招聘笔试题-硬件,有需要的可以下载参考
    发表于 04-29 15:05

    硬件经典面试100分享

    学电人员必备;硬件经典面试100;面向电子行业的面试基础问题,提前进入职业的大门
    发表于 09-27 06:23

    程序员面试宝典下载(pdf电子书)

    程序员面试宝典取材于各大IT公司历年面试(笔试、口试、电话面试、英语面试,以及逻辑
    发表于 09-19 17:14 1818次下载
    程序员<b class='flag-5'>面试</b>宝典下载(pdf电子书)

    2011注电(供配电)基础(上午)

    2011注电(供配电)基础(上午)2011注电(供配电)基础(上午)2011注电(供配电)基础
    发表于 02-19 15:34 4次下载

    华为HCIE RS面试集锦

    华为HCIE RS面试集锦,华为认证必须
    发表于 05-11 11:16 0次下载

    微软面试100系列

    微软面试100系列
    发表于 01-08 14:14 0次下载

    Linux面试3道

    关键词:linux、面试 第一:下面的网络协议中,面向连接的的协议是( ) A 传输控制协议 B 用户数据报协议 C 网际协议 D 网际控制报文协议 第二:. Linux文件权限一共10
    发表于 09-23 11:03 486次阅读

    算法类型以及准备策略

    今天就和大家聊聊大公司的面试环节经常涉及的算法类型以及准备策略。 问题难度首先大家比较关心的就是面试时候出现的算法
    的头像 发表于 09-02 10:50 1483次阅读

    新疆大学信号与系统2002年

    新疆大学823信号与系统2002年-样板
    发表于 04-29 15:26 0次下载