题目
第一个只出现一次的字符
数组中的重复的数字
字符串流中第一个不重复的字符
数组中只出现一次的数字
调整数组顺序使奇数位于偶数前面
数组中出现次数超过一半的数字
把数组排成最小的数
顺时针打印矩阵
把字符串转换为整数
表示数值的字符串
左旋转字符串(矩阵翻转)
替换空格
正则表达式匹配
代码实现
第一个只出现一次的字符
题目描述：在一个字符串(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 < len_row and not walked[i+1][j]:
i += 1
else:
direction = 2
j -= 1
elif direction == 2: # left
if j > 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('0') or 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、搜索、推荐、数据挖掘算法和优化，提供面试辅导、专业知识入门到进阶辅导等定制化需求等服务，助力您顺利完成学习和求职之旅（有需要者可私信联系）
友友们，自己的知乎账号为“快乐星球”，定期更新技术文章，敬请关注！