网站导航
> 技术文档 > 《剑指offer》-数据结构篇-哈希表/数组/矩阵/字符串

《剑指offer》-数据结构篇-哈希表/数组/矩阵/字符串

网友: 技术文档 2025-07-30 14:12:20

题目

  1. 第一个只出现一次的字符

  2. 数组中的重复的数字

  3. 字符串流中第一个不重复的字符

  4. 数组中只出现一次的数字

  5. 调整数组顺序使奇数位于偶数前面

  6. 数组中出现次数超过一半的数字

  7. 把数组排成最小的数

  8. 顺时针打印矩阵

  9. 把字符串转换为整数

  10. 表示数值的字符串

  11. 左旋转字符串(矩阵翻转)

  12. 替换空格

  13. 正则表达式匹配

代码实现

第一个只出现一次的字符

题目描述：在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）。

思路：遍历字符串的所有字符，将字符和对应的出现次数构成“键值对”。再次遍历，找到第一个值为1的键，即为所求的字符。

# -*- coding:utf-8 -*-class Solution: def FirstNotRepeatingChar(self, s): # write code here #采用字典的方式 map = {} for i in range(len(s)): #字典的.get(key，value)方法对字典中没有的key赋一个value值，因而这里需要指定value值； #如果不指定，使用.get(key)得到字典中已有的的对应于key的value值 map[s[i]] = map.get(s[i], 0) + 1 for i in range(len(s)): if map[s[i]] == 1: return i return -1

数组中的重复的数字

题目描述：

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

思路：和第1题类似，这里使用列表存储数字出现的次数。

# -*- coding:utf-8 -*-class Solution: # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0] # 函数返回True/False def duplicate(self, numbers, duplication): # write code here map = [0] * 1000 for n in numbers: if map[n] == 1: duplication[0] = n return True else: map[n] = 1 return False

字符串流中第一个不重复的字符

题目描述：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符\"go\"时，第一个只出现一次的字符是\"g\"。当从该字符流中读出前六个字符“google\"时，第一个只出现一次的字符是\"l\"。如果当前字符流没有存在出现一次的字符，返回#字符。

思路：用列表来实现栈，栈中只保留连续字符中不重复的字符。

# -*- coding:utf-8 -*-class Solution: # 返回对应char def __init__(self): self.data = [] def FirstAppearingOnce(self): # write code here return self.data[0] if self.data else \'#\' def Insert(self, char): # write code here n = len(self.data) for i in range(n-1, -1, -1): if self.data[i] == char: self.data.pop(i) return self.data.append(char)

数组中只出现一次的数字

题目描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路：和第1题类似。

# -*- coding:utf-8 -*-class Solution: # 返回[a,b] 其中ab是出现一次的两个数字 def FindNumsAppearOnce(self, array): # write code here map = {} res = [] for n in array: map[n] = map.get(n, 0) + 1 for n in array: if map[n] == 1: res.append(n) return res

调整数组顺序使奇数位于偶数前面

题目描述：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路：统计得到数组的长度，然后将奇数依次放在前半部分，偶数也类似。

# -*- coding:utf-8 -*-class Solution: def reOrderArray(self, array): # write code here odd_cnt = 0 res = [0] * len(array) # 统计个数 for n in array:  if n % 2 != 0: odd_cnt += 1 # 填坑 odd_i = 0 even_i = odd_cnt for i in range(len(array)): if array[i] % 2 != 0:  res[odd_i] = array[i] odd_i += 1 else: res[even_i] = array[i] even_i += 1 return res

数组中出现次数超过一半的数字

题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路：找到出现次数最多的那个数字，然后判断其出现的次数是否超过数组长度的一半。

# -*- coding:utf-8 -*-class Solution: def MoreThanHalfNum_Solution(self, numbers): # write code here res = None cnt = 0 # 留下数组中出现次数最高的数 for i in numbers:  if not res: res = i cnt = 1 else: if i == res:  cnt += 1 else:  cnt -= 1  if cnt == 0: res = None # 判断次数是否大于一半 cnt = 0 for i in numbers: if i == res: cnt += 1 if cnt > len(numbers) / 2: return res else: return 0

把数组排成最小的数

题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

思路：首先，找到数组中元素的最大长度n。然后，将数组中的其它元素按照元素+元素最后一位（补至第n-1位）+元素在数组中的序号的形式改写。最后，对补齐后的结果进行排序，找到最小的元素，并找到其所对应的原数组的元素值，把它作为所能组成的数字的最高几位，依次按照这种方式将数组中的数字排列在一起构成最小的数字。本人觉得本题较难！

# -*- coding:utf-8 -*-#计算数组中的数字的长度def number_len(n): res = 0 while n: n //= 10 res += 1 return res class Solution: def PrintMinNumber(self, numbers): # write code here #考虑特殊情况 if not numbers: return \"\" if len(numbers) == 1: return numbers[0] #补齐数字的长度 #例如：{3, 32, 321}补齐成{3331, 3222, 3213}，{1, 11, 111}补齐成{1111, 1112, 1113} max_len = number_len(max(numbers)) map = {} for i in range(len(numbers)): n = numbers[i] pad = n % 10 n_len = number_len(n) for j in range(max_len-n_len): n = n*10+pad map[n*10+n_len] = i #对补齐后的结果进行排序，找到最小的元素，然后根据原每个数组中的数字的长度乘以10的指数次方 keys = sorted(map.keys()) res = numbers[map[keys[0]]] for i in range(1, len(keys)): n = numbers[map[keys[i]]] res = res * 10 ** number_len(n) + n return res

顺时针打印矩阵

题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10。

思路：依次打印，注意停止条件。

# -*- coding:utf-8 -*-class Solution: # matrix类型为二维列表，需要返回列表 def printMatrix(self, matrix): # write code here # write code here walked = [[False] * (len(matrix[0])+1) for _ in range(len(matrix)+1)] for j in range(len(walked[-1])): walked[-1][j] = True for i in range(len(walked)): walked[i][-1] = True len_row = len(matrix) - 1 len_col = len(matrix[0]) - 1 res = [] i = 0 j = 0 direction = 0 # 0向右，1向下，2向左，3向上 while not walked[i][j]: res.append(matrix[i][j]) walked[i][j] = True if direction == 0: # right if j < len_col and not walked[i][j+1]:  j += 1 else:  direction = 1  i += 1 elif direction == 1: # down if i  0 and not walked[i][j-1]:  j -= 1 else:  direction = 3  i -= 1 elif direction == 3: # up if i > 0 and not walked[i-1][j]:  i -= 1 else:  direction = 0  j += 1 return res

把字符串转换为整数

题目描述：将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。输入一个字符串,包括数字字母符号,可以为空。如果是合法的数值表达则返回该数字，否则返回0。 思路：判断首字符是“+”/\"-\"。然后，判断其它字符的ASCII/Unicode码是否在“0”和“9”所对应的数值的大小范围之内，如果是的话说明是数字，进行转变后加到整数的对应位上。

# -*- coding:utf-8 -*-class Solution: def StrToInt(self, s): # write code here res = 0 flag = 1 for i in range(len(s)): #判断数值是正是负 if i == 0 and s[i] == \'+\': continue elif i == 0 and s[i] == \'-\': flag = -1 continue #将每个字符转换为i“二进制”的表示结果 #返回对应的ASCII数值，或者Unicode数值，如果所给的Unicode #字符超出了你的Python定义范围，则会引发一个TypeError的异常。 n = ord(s[i]) - ord(\'0\') if n>=0 and n<=9: res = 10 * res + n else: return False return res * flag

表示数值的字符串

题目描述：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串\"+100\",\"5e2\",\"-123\",\"3.1416\"和\"-1E-16\"都表示数值。 但是\"12e\",\"1a3.14\",\"1.2.3\",\"+-5\"和\"12e+4.3\"都不是。

思考：考虑不表示数值的字符串的情况，然后逐个进行判断。

# -*- coding:utf-8 -*-class Solution: # s字符串 def isNumeric(self, s): # write code here sign, point, hasE = False, False, False for i in range(len(s)): if s[i].lower() == \'e\': #不出现两个\'e\' if hasE: return False #不能使得字符串的最后一个字符是\'e\' if i == len(s)-1: return False hasE = True elif s[i] == \'+\' or s[i] == \'-\': #不能同时出现\'e\'和\'+\'或\'-\' if sign and s[i-1].lower() != \'e\': return False if not sign and i > 0 and s[i-1].lower() != \'e\': return False sign = True elif s[i] == \'.\': #不出现连续的\'.\' #不能既有\'.\',又有\'e\' if hasE or point: return False point = True #不出现0~9之外的其它字符 elif ord(s[i])  ord(\'9\'): return False return True

左旋转字符串(矩阵翻转)

题目描述：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

思路：对于一个字符串XY，在X与Y的交界处循环左移，使得结果为YX。可以先得到YTXT(T表示翻转，XT表示对X进行翻转)，再得到YTX，最后得到YX。

# -*- coding:utf-8 -*-def reverse(str, s, e): e -= 1 while s < e: str[s], str[e] = str[e], str[s] s += 1 e -= 1 class Solution: def LeftRotateString(self, s, n): # write code here if len(s) == 0 or n == 0: return s s = list(s) #对于一个字符串XY，在X与Y的交界处循环左移，使得结果为YX #可以先得到YTXT(T表示翻转，XT表示对X进行翻转)，再得到YTX，最后得到YX reverse(s, 0, n) reverse(s, n, len(s)) reverse(s, 0, len(s)) return \'\'.join(s)

替换空格

题目描述：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思考：找到“”并进行替换，利用列表的特性。

# -*- coding:utf-8 -*-class Solution: # s 源字符串 def replaceSpace(self, s): # write code here s = list(s) count=len(s) for i in range(0,count): if s[i]==\' \': s[i]=\'%20\' return \'\'.join(s)

正则表达式匹配

题目描述：请实现一个函数用来匹配包括\'.\'和\'*\'的正则表达式。模式中的字符\'.\'表示任意一个字符，而\'*\'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串\"aaa\"与模式\"a.a\"和\"ab*ac*a\"匹配，但是与\"aa.a\"和\"ab*a\"均不匹配。

思路：分不同的情况进行罗列。本人觉得题目较难。

# -*- coding:utf-8 -*-class Solution: # s, pattern都是字符串 def match(self, s, pattern): # 如果s与pattern都为空，则True if len(s) == 0 and len(pattern) == 0: return True # 如果s不为空，而pattern为空，则False elif len(s) != 0 and len(pattern) == 0: return False # 如果s为空，而pattern不为空，则需要判断 elif len(s) == 0 and len(pattern) != 0: # pattern中的第二个字符为*，则pattern后移两位继续比较 if len(pattern) > 1 and pattern[1] == \'*\': return self.match(s, pattern[2:]) else: return False # s与pattern都不为空的情况 else: # pattern的第二个字符为*的情况 if len(pattern) > 1 and pattern[1] == \'*\': # s与pattern的第一个元素不同，则s不变，pattern后移两位，相当于pattern前两位当成空 if s[0] != pattern[0] and pattern[0] != \'.\':  return self.match(s, pattern[2:]) else:  # 如果s[0]与pattern[0]相同，且pattern[1]为*，这个时候有三种情况  # pattern后移2个，s不变；相当于把pattern前两位当成空，匹配后面的  # pattern后移2个，s后移1个；相当于pattern前两位与s[0]匹配  # pattern不变，s后移1个；相当于pattern前两位，与s中的多位进行匹配，因为*可以匹配多位  return self.match(s, pattern[2:]) or self.match(s[1:], pattern[2:]) or self.match(s[1:], pattern) # pattern第二个字符不为*的情况 else: if s[0] == pattern[0] or pattern[0] == \'.\':  return self.match(s[1:], pattern[1:]) else:  return False

结尾

亲爱的读者朋友：感谢您在繁忙中驻足阅读本期内容！您的到来是对我们最大的支持❤️

正如古语所言：\"当局者迷，旁观者清\"。您独到的见解与客观评价，恰似一盏明灯💡，能帮助我们照亮内容盲区，让未来的创作更加贴近您的需求。

若此文给您带来启发或收获，不妨通过以下方式为彼此搭建一座桥梁： ✨ 点击右上角【点赞】图标，让好内容被更多人看见 ✨ 滑动屏幕【收藏】本篇，便于随时查阅回味 ✨ 在评论区留下您的真知灼见，让我们共同碰撞思维的火花

我始终秉持匠心精神，以键盘为犁铧深耕知识沃土💻，用每一次敲击传递专业价值，不断优化内容呈现形式，力求为您打造沉浸式的阅读盛宴📚。

有任何疑问或建议？评论区就是我们的连心桥！您的每一条留言我都将认真研读，并在24小时内回复解答📝。

愿我们携手同行，在知识的雨林中茁壮成长🌳，共享思想绽放的甘甜果实。下期相遇时，期待看到您智慧的评论与闪亮的点赞身影✨！

万分感谢🙏🙏您的点赞👍👍、收藏⭐🌟、评论💬🗯️、关注❤️💚～

自我介绍：一线互联网大厂资深算法研发（工作6年+），4年以上招聘面试官经验（一二面面试官，面试候选人400+），深谙岗位专业知识、技能雷达图，已累计辅导15+求职者顺利入职大中型互联网公司。熟练掌握大模型、NLP、搜索、推荐、数据挖掘算法和优化，提供面试辅导、专业知识入门到进阶辅导等定制化需求等服务，助力您顺利完成学习和求职之旅（有需要者可私信联系） 

友友们，自己的知乎账号为“快乐星球”，定期更新技术文章，敬请关注！      

网络标签：

相关问题