1 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
#计算上下两个三角，然后相乘
length = len(A)
B = list(range(length)) #初始化链表
if length: #不要写成while
B[0] = 1
for i in range(1,length): #下三角
B[i] = B[i - 1] * A[i -1]
temp = 1
for j in range(length-2,-1,-1): #range的用法很重要
temp = temp * A[j+1] #上三角
B[j] = temp * B[j] #上下三角相乘
return B 注意注释
2 请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
# -*- coding:utf-8 -*-
'''
题目：请实现一个函数用来匹配包括'.'和'*'的正则表达式。
模式中的字符'.'表示任意一个字符（不包括空字符！），而'*'表示它前面的字符可以出现任意次（包含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
'''
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:]) 主要考察分类讨论
3 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+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
#标记小数点，符号，E是否出现过
sign = False
decimal = False
hasE = False
for i in range(len(s)): #遍历字符串
if s[i] =='e' or s[i] == 'E': #遇到E的情况
if i == len(s) - 1: return False #E不能在最后一位
if hasE: return False#E不能有第二次
hasE = True #将E的标志改变
elif s[i] =='+' or s[i] =='-': #出现符号的情况
if sign and s[i-1] != 'e' and s[i-1] !='E': return False #存在第二个符号而且前面不是E
if not sign and i > 0 and s[i-1] != 'e' and s[i-1] !='E' :#不在第一位出现符号且前面不是E
return False
sign = True
elif s[i] =='.': #点只能一次且不能在E之后
if hasE or decimal:
return False
decimal = True
elif s[i] < '0' or s[i] > '9': #判断有无特殊字符
return False
return True
分类讨论，也可以用正则表达式。
4 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
# -*- coding:utf-8 -*-
from collections import Counter
class Solution:
def __init__(self):
self.word = [] #要有self
def FirstAppearingOnce(self):
res = Counter(self.word) #counter是计数函数
for char in self.word: #self
if res[char] ==1:
return char
return '#'
def Insert(self,char):
self.word.append(char)
# -*- coding:utf-8 -*-
链接：https://www.nowcoder.com/questionTerminal/00de97733b8e4f97a3fb5c680ee10720
来源：牛客网
# -*- coding:utf-8 -*-
'''
题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。
例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。
当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
'''
class Solution:
def __init__(self):
self.char_list = [-1 for i in range(256)]
self.index = 0 # 记录当前字符的个数，可以理解为输入的字符串中的下标
'''
解法：利用一个int型数组表示256个字符，这个数组初值置为-1.
每读出一个字符，将该字符的位置存入字符对应数组下标中。
若值为-1标识第一次读入，不为-1且>0表示不是第一次读入，将值改为-2.
之后在数组中找到>0的最小值，该数组下标对应的字符为所求。
在python中，ord(char)是得到char对应的ASCII码；chr(idx)是得到ASCII位idx的字符
'''
def FirstAppearingOnce(self):
# write code here
min_value = 500
min_idx = -1
for i in range(256):
if self.char_list[i] > -1:
if self.char_list[i] < min_value:
min_value = self.char_list[i]
min_idx = i
if min_idx > -1:
return chr(min_idx)
else:
return '#'
def Insert(self, char):
# 如果是第一出现，则将对应元素的值改为下边
if self.char_list[ord(char)] == -1:
self.char_list[ord(char)] = self.index
# 如果已经出现过两次了，则不修改
elif self.char_list[ord(char)] == -2:
pass
# 如果出现过一次，则进行修改，修改为-2
else:
self.char_list[ord(char)] = -2
self.index += 1
注意面向对象编程的格式，尤其是Init,self等。参考：https://blog.csdn.net/fuxuemingzhu/article/details/79734715
5 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#利用一个List来记录是否已经遍历过这个节点
#追求时间复杂度可以用快慢节点法
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if not pHead:
return None
p1 = pHead
res = []
while p1.next:
if p1 not in res:
res.append(p1)
p1 = p1.next
else: #注意符号一定要是英文！！
return p1
return None 也可以利用一快一慢的双指针法。
6 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
class Solution:
def maxInWindows(self, num, size):
# write code here
if not num or not size or size > len(num):
return []
if size == len(num):
MAXWIN = [max(num)]
return MAXWIN
res = []
for i in range(len(num)-size+1):
maxwin = max(num[i:i+size])
res.append(maxwin)
return res
可以利用双端树来减小时间复杂度。一定要注意返回的格式，要不然汇报len的错误。
7 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
if not matrix:
return False #不是None
if not path:
return True
board = [list(matrix[cols*i:cols*i+cols]) for i in range(rows)] #注意转换成二维列表的方式
for i in range(rows):
for j in range(cols):
if self.pathCharge(board, i, j, path):
return True
return False
def pathCharge(self,board,i,j,path):
if board[i][j] == path[0]:
if not path[1:]:
return True
board[i][j] = ''
if i > 0 and self.pathCharge(board,i-1,j,path[1:]):
return True
if i < len(board) -1 and self.pathCharge(board,i+1,j,path[1:]):
return True
if j > 0 and self.pathCharge(board,i,j-1,path[1:]):
return True
if j < len(board[0]) -1 and self.pathCharge(board,i,j+1,path[1:]):
return True
board[i][j] = path[0] # ？？？
return False
else:
return False 将matrix转变为二维列表的方法，回溯的思想
8 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
# -*- coding:utf-8 -*-
class Solution:
def __init__(self): #开始必备，注意self
self.count = 0 #注意加self
def movingCount(self,threshold,rows,cols):
arr = [[1 for i in range(cols)] for j in range(rows)] #注意中括号
self.findblocks(arr,0,0,threshold) #里面不加self，传入的顺序
return self.count #self
def findblocks(self,arr,i,j,k): #ijk对应的值
if i < 0 or j < 0 or i >= len(arr) or j >= len(arr[0]):
return
sumi = list(map(int,str(i))) #将数字转换为字符串再转换为列表进而用sum
sumj = list(map(int,str(j)))
if sum(sumi) + sum(sumj) > k or arr[i][j] != 1: #b不等于里面不能有空格
return
self.count = self.count + 1 #要加self
arr[i][j] = 0
self.findblocks(arr,i,j-1,k)
self.findblocks(arr,i,j+1,k)
self.findblocks(arr,i-1,j,k)
self.findblocks(arr,i+1,j,k)
#注意，一定要连通
#回溯，深度优先 回溯法，深度优先，注意注释。
补充：
pop() 函数用于移除列表中的一个元素（默认最后一个元素），并且返回该元素的值。pop(0)则是删除第一个。
https://blog.csdn.net/u010429424/article/details/73692248 滑动窗口的双端队列
https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4 快慢指针法解答环链表
Counter是对字典类型的补充，用于追踪值的出现次数。
具备字典的所有功能 + 自己的功能。
1 import collections
2 aa = collections.Counter("sdfdsgsdf;sdfssfd") #把所有元素出现的次数统计下来了
3 print(aa)
4
5 输出结果：
6 Counter({'s': 6, 'd': 5, 'f': 4, ';': 1, 'g': 1})
Counter 是实现的 dict 的一个子类，可以用来方便地计数。
对init的解释，写的不错https://blog.csdn.net/m0_37693335/article/details/82972925 https://www.crifan.com/summary_the_meaning_of_self_and___init___in_python_and_why_need_them/
collections 模块总结 https://www.cnblogs.com/George1994/p/7204880.html
正则表达式入门 写的很好，工大学长 https://www.cnblogs.com/chuxiuhong/p/5885073.html
京公网安备 11010502036488号