编程算法题集与解析大全.docxVIP

第PAGE页共NUMPAGES页

编程算法题集与解析大全

字符串处理题集与解析（共5题，每题10分）

题目1（10分）

题目：给定一个字符串`s`，其中包含数字和字母，请编写一个函数，统计并返回字符串中数字和字母的数量。数字和字母分别用两个独立的变量返回。例如，输入`s=a1b2c3`，输出应为数字数量为3，字母数量为3。

答案：

python

defcount_digits_letters(s):

digit_count=0

letter_count=0

forcharins:

ifchar.isdigit():

digit_count+=1

elifchar.isalpha():

letter_count+=1

returndigit_count,letter_count

测试

s=a1b2c3

print(count_digits_letters(s))#输出：(3,3)

解析：

通过遍历字符串中的每个字符，使用`isdigit()`和`isalpha()`方法判断字符是否为数字或字母，分别计数。时间复杂度为O(n)，n为字符串长度。此题考察基础字符串操作和条件判断能力。

题目2（10分）

题目：实现一个函数`compress_string`，对输入字符串中的连续重复字符进行压缩。例如，输入`aaabbbccccc`，输出应为`a3b3c5`。

答案：

python

defcompress_string(s):

ifnots:

return

result=[]

count=1

foriinrange(1,len(s)):

ifs[i]==s[i-1]:

count+=1

else:

result.append(s[i-1]+str(count))

count=1

result.append(s[-1]+str(count))

return.join(result)

测试

s=aaabbbccccc

print(compress_string(s))#输出：a3b3c5

解析：

通过遍历字符串，统计连续相同字符的数量，并在遇到不同字符时将字符和数量追加到结果列表中。最后将列表转换为字符串返回。时间复杂度为O(n)，空间复杂度为O(n)。

题目3（10分）

题目：给定一个字符串`s`，请编写一个函数，检查该字符串是否为回文串（忽略大小写和非字母字符）。例如，输入`s=Aman,aplan,acanal:Panama`，输出应为`True`。

答案：

python

defis_palindrome(s):

s=.join(c.lower()forcinsifc.isalnum())

returns==s[::-1]

测试

s=Aman,aplan,acanal:Panama

print(is_palindrome(s))#输出：True

解析：

首先将字符串转换为小写，并过滤掉非字母数字字符，然后检查处理后的字符串是否为回文。回文判断通过比较字符串与其反转是否相等实现。时间复杂度为O(n)，空间复杂度为O(n)。

题目4（10分）

题目：实现一个函数`find_substring`，在字符串`s`中查找子串`sub`的所有出现位置（从0开始计数），返回一个列表。如果未找到，返回空列表。例如，输入`s=ababa`，`sub=aba`，输出应为`[0,2]`。

答案：

python

deffind_substring(s,sub):

positions=[]

sub_len=len(sub)

foriinrange(len(s)-sub_len+1):

ifs[i:i+sub_len]==sub:

positions.append(i)

returnpositions

测试

s=ababa

sub=aba

print(find_substring(s,sub))#输出：[0,2]

解析：

通过遍历字符串`s`，每次检查从当前位置开始的子串是否与`sub`匹配。如果匹配，记录位置。时间复杂度为O(nm)，n为`s`长度，m为`sub`长度。可优化为O(n+m)的KMP算法，但此处使用简单暴力匹配。

题目5（10分）

题目：给定一个字符串`s`，请编写一个函数，将字符串中的所有单词按字典序排序，但保持每个单词内部字符顺序不变。例如，输入`s=applebananacherry`，输出应为`applebananacherry`（原已排序）。

答案：

python

defso