python第八周小测试_《数据结构与算法分析python版》第八周编程作业

不念不忘少年蓝@ 2023-01-09 01:11 171阅读 0赞

《数据结构与算法分析python版》第八周编程作业

1、字符串中所有重排

题目内容：

给定一个字符串s与待查找字符串p，请给出使得s\[i:i+len§\]是p的一个字母重排的所有下标i

输入格式:

两行字符串，第一行为s，第二行为p

输出格式：

所有满足条件的下标从小到大排列，以空格分隔输出

若无对应下标，则输出"none"

输入样例

cbaebabacd

abc

输出样例：

0 6

脚本

\# -\*- coding: utf-8 -\*-

"""

Created on Fri May 1 12:11:20 2020

@author: dulow

"""

def findAnagrams(s,p):

p\_lst = list(p)

p\_lst.sort()

s\_lst = list(s)

L\_p = len(p\_lst)

L\_s = len(s\_lst)

result\_lst = \[\]

for i in range(0,L\_s-L\_p+1):

s\_picked = s\_lst\[i:i+L\_p\]

s\_picked.sort()

if p\_lst == s\_picked:

result\_lst.append(i)

if len(result\_lst) == 0:

print("none")

else:

result\_lst = \[str(i) for i in result\_lst\]

print(" ".join(result\_lst))

s = input()

p = input()

findAnagrams(s,p)

2、列表出现最频繁的元素

题目内容：

给定一个列表与数字K，按出现次数倒序输出列表中前K个出现最频繁的元素；若少于K个元素则返回所有元素

输入格式:

输入为两行

第一行为给定列表，以合法的Python表达式给出

第二行为数字K

输出格式：

不多于K个数字，以空格分隔

输入样例

\[1,1,1,2,2,3\]

输出样例：

1 2

脚本

def topKFrequent(nums, k):

finallst=\[\]

nums\_dict = \{\}.fromkeys(nums,0)

for i in nums:

if i in nums\_dict.keys():

nums\_dict\[i\] += 1

rlst = list(nums\_dict.values())

rlst.sort(reverse=True)

for j in range(0,len(rlst)):

if j < k:

for key in nums\_dict.keys():

if nums\_dict\[key\] == rlst\[j\]:

finallst.append(key)

nums\_dict\[key\] = None

break

else:

break

finallst = \[str(i) for i in finallst\]

result\_str = " ".join(finallst)

print(result\_str)

lst = eval(input())

k = int(input())

topKFrequent(lst, k)

很难受啊，明明各种也测试过了，不晓得为啥用例2没通过。希望有同道中人能认真看一下指点指点。

这里放一下别人家的代码吧，这个sorted函数没有搞懂，其实用字典来解这道题是比较简单的，但是由于排序问题搞的复杂了。来学习一些别人是怎么用sorted函数的。

def topKFrequent(nums, k):

dct = \{\}

for x in nums:

dct\[x\] = dct.get(x, 0) + 1

result = sorted(dct.items(), key=lambda x: (-x\[1\],x\[0\]))

result = \[x\[0\] for x in result\[:k\]\]

print(\*result)

lst = eval(input())

k = int(input())

topKFrequent(lst, k)

3、散列表

题目内容：

给定一个指定大小N的散列表，并输入一系列数字：若找到空槽，则插入该数字，并返回槽位置；若该数字在散列表中存在，则直接输出其位置。

注：使用下标增加的二次探测法解决散列冲突

注2：散列表实际大小应确定为不小于用户输入N的最小质数

输入格式:

两行

第一行为用户指定散列表大小N

第二行为一系列数字，以空格分隔

输出格式：

逐个输出对应数字在散列表中位置，以空格分隔

若该数字无法插入，则输出“-”

输入样例：

10 6 4 10 15

输出样例：

0 1 4 0 -

脚本

这道题空了好几天，最近又要改论文还有组会，难受啊

def createHashTable(n):

NotFound = True

while NotFound:

temp = int(pow(n,0.5))

for i in range(2,temp+1):

if n % i == 0:

NotFound = True

break

else:

NotFound = False

n += 1

table = \[None\] \* (n -1)

return table

def insertNumbers(table, nums):

indexlst = \[\]

size = len(table)

for i in range(0,len(nums)):

slot\_i = nums\[i\] % size

if slot\_i not in indexlst:

indexlst.append(slot\_i)

else:

if nums\[i\] in nums\[:i\]:

for x in range(i):

if nums\[x\] == nums\[i\]:

indexlst.append(indexlst\[x\])

else:

for m in range(1,size):

n = (slot\_i+m\*\*2) % size

if n not in indexlst:

indexlst.append(n)

break

elif m\*\*2 >= size \* 2:

indexlst.append("-")

break

return indexlst

n = int(input())

nums = list(map(int, input().split()))

table = createHashTable(n)

print(\*insertNumbers(table, nums))

python第八周小测试_《数据结构与算法分析python版》第八周编程作业

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关第八周习题

相关 python第八周小测试_《数据结构与算法分析python版》第八周编程作业

相关第八周作业

相关第八周作业

相关第八周作业

相关 2019春第八周作业

相关 2019春第八周作业

相关第八周

相关 Python打卡第八周

相关 20189307《网络攻防》第八周作业