既然记下来就是一些十分基础的题目，肯定是要百分百的掌握的。
牛客网-找出所有三位数中质数的个数
方法一：
a = []
for i in range(100,1000):
for j in range(2,i):
if (i%j == 0):
break
else:
a.append(i) #在数组a原有的基础上加上元素i
print(len(a))
方法二：
n = 0
for i in range(100,1000):#对100~999的所有的三位数进行遍历
for j in range(2,i): #对从2~i的所有数进行遍历(排除了1和i本身的这两种情况)
if (i % j==0):
n = n +1
break
print(900-n)
前n项和的问题
看似简单，自己因为练习的比较少，觉得很好做，真正去调试的时候发现这些简单的题目也会出错。记录的原因就是不要让自己忘了最基本的东西也是最需要掌握的。
题目一：
输入一个整数n,计算 1+1/（1-3）+1/（1-3+5）+…+1/(1-3+5-…((-1)^(n-1))*(2n-1))
输出描述：输出一个浮点数，保留3位小数
代码如下：
n = int(input())
ai = 0
total = 0
#对n项数列的每一项进行遍历
#对其中一项的分母的各个子项进行遍历，这里j的范围很重要
for i in range(1,n+1):
for j in range(i,i+1):
ai += (-1)**(j-1)*(2*j-1) #对每一项值的分母进行记录
total += 1/ai #前i项数列的和
print("{:.3f}".format(total))
题目二：
计算 1+（1+2）+（1+2+3）+…+(1+2+3+…+n)
输出描述：输出一个整数
代码如下：
n = int(input())
sum = 0
ai = 0
aj = 0
for i in range(1,n+1):#对n项数列的每一项进行遍历
for j in range(i,i+1):#对其中一项的分母的各个子项进行遍历
aj =aj+j
ai += aj
sum +=ai
print(sum)
一行输入两个整数，输出两个整数最大公约数和最小公倍数的和
主要是掌握最小公倍数的求法，最小公倍数与最大公约数是相关联的
如果能够求出最大公约数，则最小的公倍数=a*b//最大公约数
方法一：辗转相除法
n,m = map(int,(input().split(' ')))
s=n*m
while n%m!=0:
n,m=m,(n%m)
else:
# print(m,'is the maximum common divisor')
# print(s//m,'is the least common multiple')
print(m+s//m)
更相减损法
n,m = map(int,(input().split(' ')))
s=n*m
while n!=m:
if n>m:
#n-=m #以后n的值为现在n的值减去m,也即n = n -m
n = n - m
elif n<m:
#m-=n
m = m - n
else:
print(m+s//m)
两者的区别：
（1）都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。更相减损术的时间复杂度约为O(N），辗转相除法的时间复杂度约为O(logN)。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。
BC133-回型矩阵
刚看到这题直到意思，但是也是不知道该如何处理，还得是去看题解才知道的，这里有两份题解，也是值得自己看一下的。首先有一个总起的思路：回型矩阵的特点：顺时针回型矩阵，按照一个回型为一层的情况来看，推导的前三条矩阵边上的**”结束值”-“起始值”=”矩阵边长”-1**，第四条矩阵边的”结束值”为该层的起始值
- 根据设定的矩阵边长，生成一个二维数组
- 按照矩阵边长生成该层的数据池
# 这种方式不太好理解，放弃
while size >0:
create pool()
layer +=1
size -=2
最终的代码如下：
def draw_matrix(begin,size,layer,arry,controlle_num):
# 以顺时针方向建立递增矩阵，按照层级
# 根据递增1的特点，建立当前层的上下左右，四个list,形成资源池
# 每个方向列表的长度都等于size的长度
top = range(begin,begin +size)
right = range(begin+size-1,begin+size*2-1)
bottom = range(begin+size*2-2,begin+size*3-2)
left = range(begin+size*3-3,begin+size*4-3)
# 顺时针的左list最后一个值改为起始值
left[size-1]=begin
# size相当于矩阵的边长，i既可以表示长，也可以表示宽
# 通过i步进来从本层的资源池里面取出各个值
for i in range(size):
arry[layer][layer+i] = top[i]
arry[layer+i][controlle_num-layer-1]=right[i]
arry[controlle_num-layer-1][controlle_num-layer-i-1] = bottom[i]
arry[controlle_num-1-layer-i][layer] = left[i]
return arry
def Matirx(size,begin=1,layer=0):
controlle_num = size
arry = []
for i in range(size):
arry.append(range(size))
while size >0:
arry = draw_matrix(begin,size,layer,arry,controlle_num)
begin = begin+(4*(size-1))
size = size -2
layer = layer +1
return arry
if __name__=='__main__':
dat = Matrix(5)
for i in range(5):
print(dat[i])
# 换第二种方式
n= int(input())
s = [[-1]*n for _ in range(n)]
cnt =0
directions=[[0,1],[1,-0],[0,-1],[-1,0]]
# 0 1 = right
# 1 0 = down
# 0 -1 = left
# -1 0 = up
x,y = 0,0
state=0
trace = []
# 总共有n**2个数
for i in range(n**2):
cnt+=1
s[y][x]=cnt
# 记录已经经过的路径,这里的想法很好，如果不记录的话就永远时外层的在变化
trace.append([y,x])
y+=directions[state%4][0]
x+=directions[state%4][1]
if ([y,x] in trace) or y>=n or y<0 or x>=n or x<0:
# 已经经过或者已经越界的话，回退坐标
y-=directions[state%4][0]
x-=directions[state%4][1]
# 更新状态
state +=1
# 更新坐标
y+=directions[state%4][0]
x+=directions[state%4][1]
#print(s)
# 按题目条件打印有两种方式
# 按照两次遍历元素的方式
# 按照下标索引的方式（这种更好理解）
'''
for i in s:
for j in i:
print(j,end=' ')
print()
'''
for i in range(n):
for j in range(n):
print(s[i][j],end=' ')
# 每次内循环结束后进行一次换行
print()
总结，要以这道题为原型来反思矩阵的计算、统计、输入与输出的问题。
BC145笨小猴（很重要）
做题链接：
https://www.nowcoder.com/practice/17865bc2a75c4944a872ef709958c56e?tpId=290&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Ftab%3D%25E8%25AF%25AD%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D290
使用python判断质数的简单方法：https://www.jb51.net/article/83616.htm
题目描述：找出一个输入的单词中出现频率最大的那个字母出现的次数与频率最小的那个字母出现的次数的差值，并判断该差值是否是一个质数，根据是否是质数，输出不同的结果。
解题思路：
- 用数组创建一个哈希表，下标0~25对应的是26个英文单词
- 统计字母出现的频率
- 遍历数组，寻找单词中频率最高和最低的字母出现的次数
- 判断一个数是否为质数（需要写一个对应的判断质数的函数）
#写一个判断是否为质数的函数
#定义一个判断质数的函数
def zhi(n):
if n<=1:
return False
for j in range(3,n):
if n%j==0:
return False
return True
a= input()
lt =[]
#在所给的单词中去遍历
for i in range(len(a)):
#用一个变量去储存每一个单词
b =a[i]
#用count函数去记录出现的次数
c=a.count(b)
#把每次遍历的元素出现的次数都累加到列表中
lt.append(c)
#对记录的次数进行排序，然后找到maxn和minn
lt.sort()
maxn=lt[-1]
minn=lt[0]
if zhi(maxn-minn):
print('Lucky Word')
print(maxn-minn)
else:
print('No Answer')
print(0)
调用相应的模块来解题：这种方法也值得自己去掌握清楚
#导入python内建模块的collections模块中的Counter类
from collections import Counter
#这里是以类似字典的方式存储起来的
#Counter({a:x ,b:y} , c:z})
c = Counter(input())
#用到most_common()函数,这里返回的是是一个列表，其中列表的每一个元素都是一个元组
#所以才会用c.most_common[0][1]来找到出现最多频率字母的次数
#most_common()是collections模块中Counter类的函数，使用的时候需要先导入collections模块
#返回的是元组列表，不是字典
maxn = c.most_common()[0][1]
minn = c.most_common()[-1][1]
# 检查质数
def isPrime(n):
if n in [0,1]:
#if n==0 or n==1:
#if n <=1:
return False
#运用到了质数的定义法：如果在2~√n中都不能被整除，那么在√n~n中也一定不能被整除
#并且由于开方之后是浮点数，需要向上取整，这里进行了+1后int取整，或者直接round(n**0.5)代替int(n**0.5)+1)
for i in range(2, int(n**0.5)+1):
if n%i==0:
return False
return True
if isPrime(maxn-minn):
print('Lucky Word')
print(maxn-minn)
else:
print('No Answer')
print(0)
BM44-有效括号
结合leetcoad上的一些思路：
自己第一遍做的时候，只能通过一部分的案例，题目要求最好是用栈来解决，虽然自己也用了但是也只是解决了一部分问题，以下是自己整理题解的时候发现的，希望自己能够好好掌握并且触类旁通。
思路如下：括号的匹配规则符合先进后出的规则，最外层的括号最早出现的左括号，也对应最晚出现的右括号（符合先进后出的规则，可以使用先进后出的栈），遇到左括号就将相应匹配的右括号加入栈中，后续如果是合法的，右括号来的顺序就是栈中弹出的顺序。
- 创建辅助栈，遍历字符串
- 每次遇到小括号的左，中括号的左，大括号的左，就将其对应的右括号加入栈中，期待在后续遇到。
- 如果没有遇到左括号但是栈为空，说明直接遇到了右括号，不合法
- 其他情况下，如果遇到右括号，刚好会与栈顶元素相同，弹出栈顶元素继续遍历
- 只要括号是匹配的，栈中元素最后是为空的，因此检查栈是否为空即可最后判读是否合法
下面的这两张图也可以用来辅助理解
注意事项：
- 这两条elif语句是不能颠倒的，首先在栈内有元素，才能查看当前元素是否等于栈顶元素，如果直接颠倒的话，直接碰到的是右括号就会报错，因为stack一直是空（没有加入元素），也就不可能弹出元素。
- 其次不要用if语句全部代替elif语句，会出现问题
- 而且上面利用栈的过程其实是很巧妙的，自己当时写的时候，老是有算例通不过去，根本原因在：
class Solution:
def isValid(self , s: str) -> bool:
# write code here
# 如果字符串为空，或者字符串的长度为奇数个， 直接返回
if len(s)==0 or len(s)%2!=0:
return False
stack=[]
for i in s:
# 如果发现元素是左括号，就将右括号加入栈中
if i=="(":
stack.append(")")
elif i=="[":
stack.append("]")
elif i=="{":
stack.append("}")
# 如果发现此时栈已经为空了，说明直接遇到了右括号
# 给一个对应的例子："]()]"
elif len(stack)==0:
return False
# 如果发现此时的数与栈顶元素相同，弹出栈顶元素继续遍历
elif i==stack[-1]:
stack.pop()
# 检查栈是否为空来看括号是否合法
if not stack:
return True
else:
# 这里给一个到这里仍然不能通过的例子："[()]{"，这个例子前面的几步都能执行，但是到了最后一步，这里加入了一个左括号，这里的栈是不为空的，需要返回False
return False
下面是换一种写法，本质上是一样的
class Solution:
def isValid(self, s: str) -> bool:
stack=[]
# 如果字符串的长度是奇数，直接返回False
if len(s)%2==1:
return False
# 对字符串进行遍历
for i in s:
# 如果发现是左括号,就将其加入进去
if i=="(" or i=='[' or i=='{':
stack.append(i)
# 遇到的不是左括号的情况
else:
# 如果是一个空栈，说明一开始就遇到右括号
if not stack:
return False
# 如果遇到的符合正好等于栈顶元素（说明匹配）
# 将栈顶元素进行弹出
elif i==')' and stack[-1]=='(' or i==']' and stack[-1]=='[' or i=='}' and stack[-1]=='{':
stack.pop()
# 如果没有找到相同的，说明也不符合要求
else:
return False
# 遍历完整个字符之后查看栈是否为空
if not stack:
return True
else:
return False
BM46-最小的K个数
BM47-寻找第K大
由于题目要求空间复杂度是O(1),所以用快速排序是允许的。以这题为基础，把几种排序的思想再好好的进行回顾（不是一件简单的事情）
BM49-表达式求值(在后面也有相应的解答)
好像完全没有一点思路呀，是不是栈的知识点还没有完全的弄懂
题目描述：写一个整数计算器，支持加减乘三种运算和括号，保证结果始终在整型范围内
难点：如何考虑使用栈和递归的方法，对于括号的处理在44题里面有了一定的了解了。
这题思路好像打不开，主要是不知道该如何处理运算符号和括号的问题
再看这道题，发现这道题一点也不简单，应该有点属于难题的范畴了，哎，还是自己太菜了，还得加把劲再看看里面的内容，还是不够深入。
先看看题解，打开一下思路，不然后面这几道3题目都是相同类型的，都在这上面翻车。
思路：
- 处理运算优先级的问题：遇到乘法就把前面一个数和后面一个数乘起来，遇到加法（减法同），最后乘法处理完了，就剩余加法，把之前存的数字进行相加。
- 处理括号的问题：将括号中的部分看成一个新的表达式，也就是一个子问题，因此可以将新的表达式进行递归的求解，得到一个数字，再运算
- 终止条件：每次遇到左括号意味着子问题进行计算，那么遇到右括号代表这个递归结束
- 返回值：将括号内部的计算结果值返回
- 本级任务：遍历括号里面的字符，进行计算
3.非个位数地运算数：在扫描字符串地时候，多扫描相邻地字符数字即可
具体做法如下：
- 使用辅助栈处理优先级，默认符号为加号
- 遍历字符串，遇到数字，则将连续的数字字符部分转化为int型数字
- 遇到左括号，则将括号后的部分送入递归，处理子问题；遇到右括号代表已经达到这个子问题的结尾，结束继续遍历字符串，将子问题的加法部分相加为一个数字，返回。
- 当遇到符号的时候，如果是+ 得到的数字正常入栈，如果是-，则将相反数入栈，如果是*，则将栈中的内容弹出后与元素相乘再入栈
- 最后将栈中剩余的所有元素，进行一次全部的相加
总说：采用栈的方式，从左往右阶段性的找到可以优先计算的部分，不断地缩短栈地数据深度，直到把所有地数据都扫描完，同时栈深度合并为1
可能需要补充逆波兰算法的原理（把这道题慕弄懂了再说）
# 贴一个带头文件形式的（可本地调试）
from typing import AnyStr
class Solution:
def solve(self , s: str) -> int:
# write code here
# 用于存储数字的栈
number=[]
# 用于存储运算操作的栈
operate=[]
# 存储数字的空字符串
pre=''
# 遍历每个字符
for i in s:
# 判断字符是否属于操作运算或者括号
if i=='(' or i==')' or i=='+' or i=='-' or i=='*':
# 判断运算符之前是否有数字
# 如果运算符之前的pre里面是有数字的
if pre!='':
# 把字符串数字转换为数字并添加进入number数组中（这里的理解：字符拼接好了，并且已经遇到了运算操作）
number.append(int(pre))
# 接下来就要进行相应的运算操作
# 先做乘法运算
if operate and operate[-1]=='*':
# 弹出运算符
op = operate.pop()
# 弹出操作数字
num2=number.pop()
num1=number.pop()
# 计算两数
num3=self.cal(num1,num2,op)
# 将结果添加到数组栈中
number.append(num3)
if operate and operate[-1]=='-':
operate[-1]='+'
number[-1]=(-1)*number[-1]
# 有数字，但是数字已经被操作或者加入了相应的栈中
# 对pre进行初始化
pre=''
# 添加操作数
operate.append(i)
#当前遍历的字符是数字
else:
# 对数字进行拼接
pre+=i
# 如果发现右括号，就需要运算括号内的内容
if operate and operate[-1]==')':
# 弹出右括号
operate.pop()
# 开始运算括号内的数字
# 只要运算栈存在，并且栈顶的元素不是左括号，就不停的对操作数和数组栈弹出
while operate and operate[-1]!='(':
# 用变量记录运算操作，因为后面的函数调用是需要的
# 依次弹出之前加入的两个数（数字是先进后出的，这里用num2和num1区分）
op=operate.pop()
num2=number.pop()
num1=number.pop()
num3=self.cal(num1,num2,op)
# 将计算好的值更新加入number栈中
number.append(num3)
# 此时发现栈顶元素已经是'('
# 弹出左括号
operate.pop()
# 将括号中的负号 数字都转化为相反数
if operate and operate[-1]=='-':
operate[-1]='+'
number[-1]=(-1)*number[-1]
# 整个for循环结束之后(括号里面的内容已经处理完成了)
# 剩下最后一步的运算
# 1.拼接最后一个数字
if pre!='':
number.append(int(pre))
if operate and operate[-1]=='-':
operate[-1]='+'
number[-1]=(-1)*number[-1]
# 2.进行最后一步的运算
while operate:
op=operate.pop()
num2=number.pop()
num1=number.pop()
num3=self.cal(num1,num2,op)
number.append(num3)
return number[0]
# 写出无括号，纯加减乘的函数
def cal(self,num1,num2,op):
if op=="+":
return num1+num2
if op=='*':
return num1*num2
# 剩下的运算
while operate:
op = operate.pop()
num2 = number.pop()
num1 = number.pop()
num3 = self.cal(num1, num2, op)
number.append(num3)
return number[0]
def cal(self, num1, num2, op):
if op == '+':
return num1 + num2
if op == '*':
return num1 * num2
# 头文件
if __name__ == '__main__':
# 输入一个特定的需要求解的数组
s= "(2*(3-4))*5"
res = Solution().solve(s)
#print(res)
print(" 输出 => " ,res)
当然这里引申一下关于eval()函数的用法：用来执行一个字符串表达式，并返回表达式的值
eval(expression[,globals[,locals]]).
BM65-最长公共子序列
题目的主要信息：
- 找到两个字符串的最长公共子序列
- 仅存在一个最长的公共子序列，不需要去重
- 没有找到的时候，返回-1，需要变换（这里是一个隐藏的坑）
思路：先得到最长公共子序列的长度（获取长度的思路已经知晓），然后根据这个长度来获取这个子序列（这里才是本道题有一个重点的部分，用到了栈的弹出的小知识，也是一个很关键的点，如果不是做题的话估计自己也很难想到这样的方法。需要对栈进行活学活用，而且要能够快速的反应过来，确实很考验代码和逻辑的思维能力！！！！！！）
在构造表的同时，用一个二维矩阵记录上面状态转移时选择的方向，用1表示来自左上方，用2表示来至左边，用3表示来自上边。
获取这个序列的时候，根据从最后一位开始，根据记录方向，不断地递归往前组装字符，只有来自左上的时候才添加本级字符（这种情况是动态规划中两个字符相等的情况，字符相等的时候才可以用）
这里看得到一个非常好的练习的线上的表格，帮自己完完全全的梳理了一下这个过程，一下子茅塞顿开。
链接如下：https://alchemist-al.com/algorithms/longest-common-subsequence
class Solution:
def LCS(self , s1: str, s2: str) -> str:
# write code here
# 首先采用二维dp来解题
# dp[i][j]表示s1中前i个字符和s2中前j个字符的最长公公共子序列
# 当两个字符串最后一个字符是相同的时候
# dp[i][j]=dp[i-1][j-1]+1
# 当两个字符串最后一个字符不是相同的时候，看到底是由s1延申过来，还是由s2延申过程
# dp[i][j-1]:表示s1中前i个字符与s2中前j-1个字符的最长公共给子序列
# dp[i-1][j]表示s1中的前i-1个字符与s2中前j个字符的最长公共子序列
m,n=len(s1),len(s2)
dp=[[0]*(n+1) for _ in range(m+1)]
# 初始条件
# 当s1或者s2为空字符串的时候,最长公共子串均为0
if m==0 or n==0:
return '-1'
for i in range(1,m+1):
for j in range(1,n+1):
# 判断当前遍历的最后一个字符是否相
if s1[i-1]==s2[j-1]:
dp[i][j]=dp[i-1][j-1]+1
# 当最后一个字符不相等的时候
else:
dp[i][j]=max(dp[i][j-1],dp[i-1][j])
# 找到最大长度之后，还要把对应的值给输出来
# return dp[m][n]
#print(dp)
# # 从动态规划数组的末尾开始
i,j=m,n
# 构建一个临时的栈，用来从后向前储存相同的字符
temp=[]
while dp[i][j] !=0:
# 来自左方向
if dp[i][j]==dp[i-1][j]:
i=i-1
# 来自上方向
elif dp[i][j]==dp[i][j-1]:
j= j-1
# 来自左上方
elif dp[i][j]>dp[i-1][j-1]:
i-=1
j-=1
# 只有左上方才是字符相等的情况，入栈，逆序使用
temp.append(s1[i])
# 循环结束之后，进行子序列的拼接
# print(temp)
res=''
while len(temp)!=0:
# 将temp中的元素不断地弹出并加入到res字符串中
res+=temp.pop()
#如果两个完全不同，返回字符串为空，需要改为-1
if res is None or res=='':
return '-1'
else:
return res
BM66- 最长公共子串
注意审题：最长的公共子串，不是最长的公共子序列，子序列可以不是连续的，但是子串一定是连续的。（这里的理解对于做题来说是十分的关键的，一道题能够读懂也十分重要的）
看到题解的时候有一个枚举的思路，对于自己的思维锻炼很有帮助，而且动态规划就是从枚举的思路上发展而来的，需要考验的是自己的能够有枚举的思路，而且还能由枚举来想到用动态规划的思路。（枚举是思维的核心所在！！！！）
参考链接：https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=295&tqId=991150&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
枚举所有的子串进行比较，不用完全枚举的形式，尝试做一点改良
- 遍历两个字符串的所有字符串作为起始
- 同时开始检查字符是否相等，相等的话就不断地后移，增加子串地长度，如果不说明以这两个为起点地子串截至了，不会再有了。(这里也是同动态规划地思想一致的)
- 后续比较长度维护最大值即可。
# 写代码的核心思维思维
class Solution:
def LCS(self , str1: str, str2: str) -> str:
#让str1为较长的字符串
if len(str1) < len(str2):
str1, str2 = str2, str1
res = ''
max_len = 0
#遍历str1的长度
for i in range(len(str1)):
#查找是否存在
if str1[i - max_len : i + 1] in str2:
res = str1[i - max_len : i + 1]
max_len += 1
return res
这题和最长的公共子序列也有一定的联系：比如构建dp数组的含义，dp数组的长度以及大小（这种题型要形成自己的思考定式下次碰到的时候就可以直接写了）
定义dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最长公共子串。如果要求dp[i][j]，也就是str1的第i个字符和str2的第j个字符为最后一个元素所构成的最长公共子串，我们首先需要判断这两个字符是否相等。(相当于是递推公式)
- 如果不相等，那么他们就不能构成公共子串，也就是dp[i][j]=0
- 如果相等的话，我们还需要计算前面相等字符的个数：即dp[i-1][j-1]
自己也要表格罗列了这样的一个过程，帮助自己去理解。
#很遗憾，采用动态规划的思路，用例并不能全盘的通过
class Solution:
def LCS(self , str1: str, str2: str) -> str:
# write code here
# 设置二维dp数组,dp[i][j]表示在str1的前i个字符，str2的前j个字符中最长公共子串的个数
# 当其中某个字符串长度为0的时候一定是空串
m,n=len(str1),len(str2)
maxlengh=0
dp=[[0]*(n+1) for _ in range(m+1)]
# 分别在两个字符串中进行遍历
# 目的是为了找到最长公共子串的长度
# 其中公共子串是需要连续的
# i在第一个字符串中进行遍历
for i in range(1,m+1):
# j在第二个字符串中进行遍历
for j in range(1,n+1):
# 如果两个字符串当前遍历的最后一个字符相等,就增加公共子串的长度
if str1[i-1]==str2[j-1]:
# 更新，找到它斜上角的值+1
dp[i][j]=dp[i-1][j-1]+1
# 如果不相等的话，需要将dp[i][j]置为0，一旦不等的时候就会断开
else:
dp[i][j]=0
# 判断结束之后，用一个数组来接受最大的长度
if dp[i][j]>maxlengh:
# 更新最大值
maxlengh=dp[i][j]
# 此时pos记录的就是正常字符串的下标（从0开始的）
pos=i-1
# 最后通过对任意一个字符串进行切分来返回最长的公共子串
return str1[pos-maxlengh+1:pos+1]
以下为整理的牛客网上华为的一些机试的题目，希望认认真真的准备，50道题全方位的掌握是必须的。
HJ6 质数因子
自己也是没有一点做题的思路，虽然理解质因数的概念，但是就是不能够用代码来实现，弱鸡实锤实锤。
这道题在之前的练习题目里面是有原型的，只是自己没有注意。
质因数：一个正整数的约数，并且该数还属于是质数的数字
附上思路：
# 理解好了之后，将代码附上去
n = int(input())
# 当n被所有不大于根号下n的质因数整除后，要么余下1，要么余下2，
for i in range(2, int(n**0.5 + 1)):
# 如果n能够整除i
while n % i == 0:
# 第一个能被整除的一定是最小的质因数
# 得到的每一个数都是n的质因数（重复的值也会被列出来）
print(i, end=" ")
# 把n的值更新,n的值n//i的整数部分，确保没有i这个质因数
n = n // i
# 如果发现n还是大于2，则说明在上一次分解的n中，while循环一次都没跑，直接输出n为素数
if n > 2:
print(n)
J8 合并表记录
没有比较好的做题思路，做了一半放着了（再做的时候，给自己一点时间再做一遍，先不慌看题解）
# 输入键值对的个数
n = int(input())
temp=[]
# 将所有的键值对按照数组的形式加入到temp列表中
for i in range(n):
a =list(map(int,input().split(" ")))
#print(a)
temp.append(a)
# 建立一个哈希表
hashmap = dict()
# 对数组进行遍历，找出索引相同的
for i in range(n):
# 如果列表的索引i的第一个值不在哈希表里面
if temp[i][0] not in hashmap:
# 把值添加进去
hashmap[temp[i][0]]=temp[i][1]
else:
hashmap[temp[i][0]] +=temp[i][1]
#print(hashmap)
# 对字典按照索引值进行排序
#hashmap.sort(key = lambda x:[x])
# 按照字典的键和值份行输出
for k in sorted(hashmap.keys()):
print(k,hashmap[k])
使用哈希表的时候可以做适当的简化操作
# 输入键值对的个数
n = int(input())
# 建立一个哈希表
hashmap = dict()
# 将所有的键值对按照数组的形式加入到temp列表中
for i in range(n):
key,value =list(map(int,input().split(" ")))
# 找出索引相同的
# 如果key值不在当前的字典中，key和value加进去
if key not in hashmap:
# 把值添加进去
hashmap[key]=value
else:
hashmap[key] +=value
#print(hashmap)
# 对字典按照索引值进行排序，并输出（这种方法是最简单的）
for k in sorted(hashmap.keys()):
print(k,hashmap[k])
对于排序后输出，可以将字典转换成列表再输出的话（这样的方法有点太繁琐了，上面的两行代码就可以解决掉）：
hashmap = {8: 46828, 24: 47153, 3: 93735, 13: 72600, 4: 44422}
dictlist=[]
for keys, value in hashmap.items():
temp = (keys,value)
dictlist.append(temp)
dictlist.sort(key = lambda x:x[0] )
for i in range(len(dictlist)):
# print(dictlist[i][0],end=" ")
# print(dictlist[i][1])
index =dictlist[i][0]
value =dictlist[i][1]
print(str(index)+ " " +str(value))
# 输出结果：
# 3 93735
# 4 44422
# 8 46828
# 13 72600
# 24 47153
转化为列表再排序的过程有一个简便的方法
hashmap = {8: 46828, 24: 47153, 3: 93735, 13: 72600, 4: 44422}
# 直接借助sorted()函数进行排序，排序后会转换成一个列表
# sorted(iterable, key=None,reverse=False)
lis1=sorted(hashmap.items(),key=lambda d:d[0]) #按键来排序
print(lis1)
for i in range(len(lis1)):
print(lis1[i][0], end=" ")
print(lis1[i][1])
# 输出结果：
# [(3, 93735), (4, 44422), (8, 46828), (13, 72600), (24, 47153)]
# 3 93735
# 4 44422
# 8 46828
# 13 72600
# 24 47153
HJ15 求int型正整数在内存中存储时1的个数
题目自己都没有读懂？？？，不好开展下去,回顾的时候再把题目好好的领悟一下，不懂的先记载在这里
- 先把数字转化为二进制
- 然后数二进制中1的个数
# 方法一：这种方法相对来说比较的粗暴
a = int(input())
b = bin(a)
print(b.count("1"))
# 方法二：采用位运算与：&
a = int(input())
count =0
while a !=0:
# n&(n-1)d的操作是将n的二进制中最低位的1变成0的过程
# 不断的进行这样的操作之后，就将a最低位的1不断地变为0，直到将所有的1都变为0，每次操作记录一次
a &=a-1
count =+1
print(count)
HJ16 购物单
需要用到动态规划的思路
把题目先读懂：（很关键！！！！），题解已经看了几遍了，还是不能够抓住其中的核心问题
- 要买附件，必须买附件所属的主件，每件物品只能购买一次
- 每个主件可以有0、1、2个附件
- 每件物品的价格是10的整数倍，并且只有N元预算
- 满意度的概念：物品价格*重要度再加和
- 最后的要求：要计算最大的满意度的问题
结合0-1背包问题，做详细的分析后用代码完成，这道题必须做3遍（3遍代码实现！！！！！）
对于给定例子：物品的个数N=3
考虑每个物品要考虑每种可能出现的情况：不一定每种情况都要考虑，只有当附件存在的时候才有对应的情况（重点和难点就是处理附件的地方） - 主件
- 主件 + 附件1
- 主件 + 附件2
- 主件 + 附件1 + 附件2
将所得的数据分为两个表：
- 单价价格表（相当于背包问题的重量，限制我们的总金额）
- 价值表(每个主、附件对应的价值，我们要求的是让他们和最大的值)
# 这种只是自己一开始就用别人的来理解，不一定是最好的
while True:
try:
# 最大金额total，物品数量k
total , k = list(map(int,input().split()))
# print(total,k)
# 单价
W={}
# 单价*重要程度=价值(满意度)
V={}
# 因为价格是10的倍数，为了方便运算，价格/10，可以减少循环的次数
total = int(total/10)
# print(total)
# 主件个数
main_key = []
# 构造字典
# 对于每一个物品都有价值和相应的满意度,做了一个初始化，之所以用1~k，只是为了表示k件物品与数字对应，方便调试，
# 同时也牵扯到一个编号的问题，必须要这样遍历然后创建
# 因为最多有两个附件，所以对于每一个物品编号来说，是三列
for i in range(1,k+1):
W[i] = [0,0,0]
V[i] = [0,0,0]
#print(W)
#print(V)
# 将物品对应的三个属性分别录入进去
for i in range(k):
# 单价，重要程度，类别
v,p,q= list(map(int,input().split()))
#print(v,p,q)
# 如果没有附件
if q ==0:
W[i+1][0] = int(v/10)
V[i+1][0] = int(v*p/10)
main_key.append(i+1)
#print(W)
#print(V)
#print(main_key)
# 存在附件的时候
else:
#
if W[q][1]==0:# 附件
W[q][1]=int(v/10) # 第一个附件
V[q][1]=int(v*p/10)
#print(W)
#print(V)
#
else:
W[q][2]= int(v/10) # 第二个附件
V[q][2]= int(v*p/10)
#print(W)
#print(V)
# 到这里输出结果，证明自己创建的两个表是正确的。
#print(W)
#print(V)
# 新建两个数组,用于存存放
W_lst = []
V_lst = []
# 在W字典中遍历键
for key in W.keys():
# key是在main_key里面的
if key in main_key:
W_lst.append(W[key])
V_lst.append(V[key])
#print(W_lst)
#print(V_lst)
m = len(W_lst)
# 构造一个二维数组
# 开始转化成为0-1背包问题
dp = [[0]*(total+1) for _ in range(m+1)]
for i in range(1,m+1): # 每几件物品
w1 = W_lst[i-1][0]
w2 = W_lst[i-1][1]
w3 = W_lst[i-1][2]
v1 = V_lst[i-1][0]
v2 = V_lst[i-1][1]
v3 = V_lst[i-1][2]
# 这里对j的遍历很关键
for j in range(total+1):
# 1.不放入的情况
# 当前价格j不能容下第i个主件时,价值为上一个物品的对应价格的价值
dp[i][j] = dp[i-1][j]
# 2. 放入一个主件
# 当前价格j可以容下第i个主件时,比较（上一个物品对应价格的价值）
if j -w1>=0:
dp[i][j] = max(dp[i][j],dp[i-1][j-w1] +v1)
# 1个主件+1附件
# 在确定主件可容纳，并做相应计算之后,判断附件的容纳情况，如果主件都没有办法容纳，则附件必定不可容纳
if j - w1-w2 >=0:
# 当可以容下第i个主件和此主件的第1个附件时，此时需要在比大小时加入当前最优，保证添加附件的结果不会反而更小
# 比较（当前价格对应上一物品的价值）与（主键价值+附件1价值+上一物品在价格（j-主键价格-附件1价格）时对应的价值）
dp[i][j] = max(dp[i][j],dp[i-1][j-w1-w2] +v1+v2)
# 一个主件+附件2
if j - w1 -w3 >=0:
# 可以容下第i个主件和此主件的第2个附件，此时也需要在比大小时加入当前最优，保证添加附件的结果不会反而更小
# 比较（当前价格对应上一物品的价值）与（主键价值+附件2价值+上一物品在价格（j-主键价格-附件2价格）时对应的价值）
dp[i][j] = max(dp[i][j],dp[i-1][j-w1-w3] + v1 + v3)
# 一个主件 + 附件1+ 附件2
# 根据3件物品价格之和必然大于等于2件物品的规则，只有在能容纳主件和附件2时，才有判断全部容纳可能性的必要
if j - w1 - w2 - w3 >=0:
# 当判断通过，则判断当前值与上物品计算当前价格价值与当前3物品情况价值中最大值，同时还要比较目前最优值
dp[i][j] = max(dp[i][j],dp[i-1][j-w1-w2-w3] + v1 + v2 +v3)
# 打印最后的结果
print(int(dp[m][total]*10))
except:
break
自己动手实操的时候就发现问题所在了
# 如果不对数据做先除以10的操作，会有一部分数据通不过，因为循环过大
# 输入总钱数N，物品的总数m
N,m=map(int,input().split())
# 新建价格和价值的二维数组,便于后期存放数据
# 对于每一个二维数组，总共有m行，对于每一行都有3列，分别表示主件，附件1、附件2
W=[[0]*3 for _ in range(m)]
V=[[0]*3 for _ in range(m)]
# 接下来将数据依次的存放入两个二维数组中
for i in range(m):
# 输入m行的基本数据,其中每一行包含三项数据：物品价格、物品的满意度，是主件/附件(如果是附件会注明所属主件所在的物品编号)
v,p,q=map(int,input().split())
# 如果发现q==0，则说明当前商品是一个存粹的主件没有附件
if q==0:
# 将价格放入表中
W[i][0] =v
# 将价值放入表中
V[i][0] =v*p
# 此时q!=0,说明存在附件的情况
else:
# 因为存入数据时候是一个个存放的,对于有附件的情况，这个时候需要再看相应所属的主件所在的物品编号
# 这里有一个坑，主件的编号是从1~m的范围，但是数组的索引是从0~m-1这个范围
# 也即q在1-m这个范围（含m）,数组的索引在0~m-1这个范围（含m-1）
# W[q-1][1]==0表明：这个附件是附件1，并且是从属于第q个物品编号
if W[q-1][1]==0:
# 存入数据
W[q-1][1]=v
V[q-1][1]=v*p
# 表明此时是：W[q-1][2]==0，是有第二个附件的情况
else:
# 存入第二个附件数据放入两张表中
W[q-1][2]=v
V[q-1][2]=v*p
# 检验数据存放是否正确
#print(W)
#print(V)
# 新建两个数组，用来存放剔除之后的数据
lst_W,lst_V=[],[]
# 把表中数据为0的给剔除掉：0的数据表示只有附件的的情况，不会单独存放的
for i in range(m):
if W[i] !=[0,0,0]:
lst_W.append(W[i])
lst_V.append(V[i])
#print(lst_W)
#print(lst_V)
# 接下就是转化为0-1背包的问题
# 在总钱数满足的情况下，所能够得到的最大的价值
# 由于上面已经对数据做了处理
# 处理之后数组的长度
# 然后用到动态规划的思路开始选商品
# 商品的件数为i，李强的总钱数为j
# dp[i][j]表示：在能够买前i件商品的时候所能获得的最大满意度
# 如果买不起第i件商品，则dp[i][j]=dp[i-1][j]
# 如果能够买得起商品的化，可以分两种情况就是讨论，然后取两者的最大值
# 情况一：不买第i件商品，此时dp[i][j]=dp[i-1][j]
# 情况二：买第i件商品，此时需要预留出买第i件商品的钱出来，用买完第i件物品之后的钱再去卖其他的物品
length=len(lst_W)
# 建立dp数组应该比较熟悉
dp=[[0]*(N+1) for _ in range(length)]
# print(dp)
# 这里提前对数据做一个预处理
for i in range(length):
# 这里对j的取值很讲究，j最大是可以取到N值的
for j in range(N+1):
# 边界条件的处理
# 如果只有0件物品，那么再多的钱也没用。
dp[0][1]=dp[1][0]=0
# 这里提前对数据做一个预处理,提取每种情况单独的价格和价值
w1=lst_W[i][0]
v1=lst_V[i][0]
w2=lst_W[i][1]
v2=lst_V[i][1]
w3=lst_W[i][2]
v3=lst_V[i][2]
# if j<w1:
# dp[i][j]=dp[i-1][j]
dp[i][j]=dp[i-1][j]
if j>=w1:
dp[i][j]=max(dp[i][j], dp[i-1][j-w1] +v1)
if j>=w1+w2:
dp[i][j]=max(dp[i][j], dp[i-1][j-w1-w2] +v1+v2)
if j>=w1+w3:
dp[i][j]=max(dp[i][j], dp[i-1][j-w1-w3] +v1+v3)
if j>=w1+w2+w3:
dp[i][j]=max(dp[i][j], dp[i-1][j-w1-w2-w3] +v1+v2+v3)
# 打印的时候，也是最大可以取到N值
print(dp[length-1][N])
```python
#当对输入的价格做除以10的操作后，最后提交能够通过了，但是要要注意在数据的处理上，因为N/10之后变成了一个浮点型，需要将其转换为整型
#同时对于给定的总的钱数也要做转换为整型的操作，这些都是很容易忽略的地方
# 以下为改进过之后的
# 输入总钱数N，物品的总数m
N,m=map(int,input().split())
# 新建价格和价值的二维数组,便于后期存放数据
N=int(N/10)
# 对于每一个二维数组，总共有m行，对于每一行都有3列，分别表示主件，附件1、附件2
W=[[0]*3 for _ in range(m)]
V=[[0]*3 for _ in range(m)]
# 接下来将数据依次的存放入两个二维数组中
for i in range(m):
v,p,q=map(int,input().split())
if q==0:
W[i][0] =int(v/10)
V[i][0] =int(v*p/10)
else:
if W[q-1][1]==0:
# 存入数据
W[q-1][1]=int(v/10)
V[q-1][1]=int(v*p/10)
else:
W[q-1][2]=int(v/10)
V[q-1][2]=int(v*p/10)
lst_W,lst_V=[],[]
for i in range(m):
if W[i] !=[0,0,0]:
lst_W.append(W[i])
lst_V.append(V[i])
length=len(lst_W)
dp=[[0]*(N+1) for _ in range(length)]
for i in range(length):
for j in range(N+1):
dp[0][1]=dp[1][0]=0
w1=lst_W[i][0]
v1=lst_V[i][0]
w2=lst_W[i][1]
v2=lst_V[i][1]
w3=lst_W[i][2]
v3=lst_V[i][2]
dp[i][j]=dp[i-1][j]
if j>=w1:
dp[i][j]=max(dp[i][j], dp[i-1][j-w1] +v1)
if j>=w1+w2:
dp[i][j]=max(dp[i][j], dp[i-1][j-w1-w2] +v1+v2)
if j>=w1+w3:
dp[i][j]=max(dp[i][j], dp[i-1][j-w1-w3] +v1+v3)
if j>=w1+w2+w3:
dp[i][j]=max(dp[i][j], dp[i-1][j-w1-w2-w3] +v1+v2+v3)
print(int(dp[length-1][N]*10))
HJ18 识别有效的IP地址和掩码并进行分类统计
（不会做就算了，不再浪费时间）
这道题，说实话就是直接没有看懂，题目的意思读了好久，可能是这里面的知识点太杂了，读了几遍都没有怎么领会。
什么是IP地址的分类：
子网掩码是什么：
私网IP和相应的范围：
HJ19 简单错误记录
做是做出来了，但是做的磕磕巴巴的，自己的问题也很大，有些操作不能立马在短时间里面就能领会，并且很好的实现出来。（也是知识的盲区，值得有时间再次进行回顾一遍，还不能做到特别熟练地地步）
# 附上做题的代码，如果有第二种方式，自己也贴上来，共同帮助解题
# 创建一个哈希表
hashmap=dict()
# 创建一个可以计数的数组
res =[]
while True:
try:
# 输入一行数据，将文件名和对应的行数转化为数组
# 按照\\进行分割，并提取最后的一个索引的元素
# 最后一个索引的元素为我呢见的路径和出现错误代码的行数，用空格进行连接
a = input().split('\\')[-1]
# 将a转化为2部分，放入数组b中，第一个为文件名，第二个为代码行数
b = a.split(' ')
if len(b[0])>16:
b[0]=b[0][-16:]
# 再次合并成一个新的字符串c
c = b[0] + " " + b[1]
if c not in hashmap:
hashmap[c] =1
else:
hashmap[c] +=1
except:
break
keys=[key for key in hashmap.keys()]
i=0
j= len(keys)-8
for key in keys:
if i>=j:
break
hashmap.pop(key)
i+=1
# print(hashmap)
for key,value in hashmap.items():
print(key+ " " +str(value))
HJ20 密码验证合格程序
第一遍看到的时候，说实话题目都没有看懂？？？这题也是一样需要花大力气弄懂
字串的定义：定义是弄清楚了，但是没有明白长度大于2的不含公共元素的子串是什么意思，如何用代码的语言来解释？？？这些都是之前刷题的时候并没有碰到过的问题。心累呀，刷题也太难受了。
思路一：判断当长度大于8的时候，四种情况中至少有三种（一次判断是否有四种情况，有一种k就增加1，当k大于等于3时满足），设置一个flag判断是否含有长度大于2的相同子串。在这里是否含有数字、大写字母、小写字母是通过找出字符串中的这些字符，存在res中，通过判断res长度来判断是否存在。
看看别人的思路：
题目分析：
- 题目给出我们若干条字符串，其含义是我们经常会注册登录所使用的密码
- 题目对密码格式进行要求
- 第一点：密码必须超过8位
- 第二点：必须有大写字母、小写字母、数字、符号四种中的三种
- 第三点：密码不能有重复的公共子串，公共子串长度判定为3个字符及以上
- 我们要输出其是否符合以上条件的判断结果，OK或者NG
思路： - 对于第一点在，只要判断是否长度合法就可以
- 对于第二点：准备要给列表分别表示四种情况的出现与否状态
- 如果出现了对应的情况，标记其值为1
- 最后查看是否标记为1的种类满足三种的要求
- 对于第三点是处理字符串的问题
while True:
try:
s = input()
if len(s) <= 8:
print('NG')
else:
l = [0, 0, 0, 0]
for i in s:
# 如果字符是a~z的小写字母
if 'a' <= i <= 'z':
l[0] = 1
# 如果字符是A~Z的大写字母
elif 'A' <= i <= 'Z':
l[1] = 1
# 如果字符是数字的话
elif i.isdigit():
l[2] = 1
else:
l[3] = 1
# 如果列表的总和小于3的话，直接打印NG
if sum(l) < 3:
print('NG')
# 当列表的总和大于等于3的时候
else:
# 对s中的数据进行遍历
for i in range(len(s)-2):
# 只取三位
x = s[i:i+3]
# 判断取的这三位是否在后面中出现了，如果出现了，直接打印NG,终止循环
if x in s[i+3:]:
print('NG')
break
# 这里用到了for else语句，当循环能够一直执行的时候，打印OK
else:
print('OK')
except:
break
HJ21 简单密码
这题看似好像能做，等真正来做的时候，又直接卡壳了，题目的意思并没有完全真正理解。导致做的时候就直接懵逼。在整理之后还要自己再用代码实现一遍(这道题要自己完完全全的实现至少两遍)
小写字母的处理：特定类型的字母转换成特定的数字（代码如何实现的问题）
大写字母的处理：大写变小写，然后往后移动一位（如何转换成代码语言）
主要思路：
参考链接：https://blog.csdn.net/weixin_40667448/article/details/108508386?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_baidulandingword~default-0.pc_relevant_paycolumn_v3&spm=1001.2101.3001.4242.1&utm_relevant_index=3
第一部分：给定字符串，将字符串中凡是小写字母。先将其变换成上诉规则中的数字，其余不变
第二部分：将第一部分获得的结果，作为第二部分的输入考虑，需要将大写字母部分，进行移位，以及移位之后将其变换成小写字母
# 直接按照题目的方式进行暴力的解法，思路上没有什么太大的问题，但是执行起来就是比较的慢
# 输入密码
a =input()
lst1=[]
# 将字符串分割后加入数组中
for i in a:
lst1.append(i)
# print(lst1)
# 转换其中的小写字母
# 在a中进行字符串的遍历
for i in range(len(lst1)):
# 如果i是a b c中的某个值
if lst1[i] in ["a","b","c"]:
# 把这个值直接变成2
lst1[i]="2"
elif lst1[i] in ["d","e","f"]:
# 把字母直接变成3
lst1[i]="3"
elif lst1[i] in ["g","h","i"]:
# 把字母直接变成4
lst1[i]="4"
elif lst1[i] in ["j","k","l"]:
# 把字母直接变成5
lst1[i]="5"
elif lst1[i] in ["m","n","o"]:
# 把字母直接变成6
lst1[i]="6"
elif a[i] in ["p","q","r","s"]:
# 把字母直接变成7
lst1[i]="7"
elif lst1[i] in ["t","u","v"]:
# 把字母直接变成8
lst1[i]="8"
elif lst1[i] in ["w","x","y","z"]:
# 把字母直接变成9
lst1[i]="9"
# 如果都不是，继续下一循环
else:
continue
# lst2表示第一步处理好的字符串
lst2=''.join(lst1)
# print(lst2)
# 如果在字符中出现大写字母，如何进行处理的问题
# 将大写字母后移一位，并且变成小写
lst3=[]
# 定义一个用于字符移位的函数
def fn(s):
# 创建一个空的字符串，用来装处理好的移位的大写字母对应的字符
new_str=''
# 移动的位数k
k = 1
for i in s :
if i >='A' and i <='Z':
# 把对应的ASCII移动k位，用移位后的ASCII和"a"的ASCII之差除以26的余数，然后加上"a"的ASCII得到最终的ASCII
i = ((ord(i) + k) - ord("A")) %26 + ord("A")
# 通过chr()函数，将ASCII值转换为单字符
i = chr(i)
# 把处理好地字符不断地加入到new_str中
new_str +=i
#print(new_str)
return new_str
# 对第一步处理后的进行操作
for i in range(len(lst2)):
# 对于发现有大写字母的情况，需要将大写字母进行移位操作，借助fn()将每次移位的值加入到目标数组中
if lst2[i] in ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']:
res = fn(lst2[i])
# print(res)
lst3.append(res.lower())
# 对于是其他字符的情况，直接添加就行
else:
lst3.append(lst2[i])
# 重新将第二步处理好的字符串数组用''.join()连成一个新的字符串
new_str = ''.join(lst3)
print(new_str)
这里再补充第二种方式，充分利用了ASCII的相关知识，但是这里还是不是太好理解
dic = ''
for i in range (26):
dic += chr(ord('a')+i)
# print(dic)
ciphertext = input()
password = ''
for i in ciphertext:
# 用issupper()用于检测字符串中所有的字母是否都为大写
if i.isupper():
# 如果包含该字符串的小写，返回相应的索引值
indx = dic.find(i.lower())
# 查看索引值是否小于等于24
if indx<=24:
res = dic[indx+1]
# 如果是最后一个索引，移位后的结果就是"A"
else:
res = dic[0]
# 如果所遍历的是由小写字母所组成的，将小写字母分别指向1~9的数字
elif i.islower():
# 返回小写对饮的索引值
indx = dic.find(i)
if 25>indx>=17:
indx -= 1
elif indx == 25:
indx -= 2
res = str(int(indx/3)+2)
#print(res)
# 如果字符既不是小写字母，也不是大写字母，直接进行相应的添加
else:
res = i
# 把经过处理之后的字符加入到预先准备好的空字符串中
password += res
print(password)
在第三次自己做的时候，发现这样做可能更加的快捷
# 方法如下：
# 1. 先将所有的小写字母变成对应的数字，组成一个新的中间字符串
# 2. 然后对得到的中间的字符串进行大写字母先变成小写再移位的操作
# 操作一：
a = list(input())
for i in range(len(a)):
if a[i] in ["a","b","c"]:
a[i] ="2"
elif a[i] in ["d","e","f"]:
a[i] ="3"
elif a[i] in ["g","h","i"]:
a[i] ="4"
elif a[i] in ["j","k","l"]:
a[i] ="5"
elif a[i] in ["m","n","o"]:
a[i] ="6"
elif a[i] in ["p","q","r","s"]:
a[i] ="7"
elif a[i] in ["t","u","v"]:
a[i] ="8"
elif a[i] in ["w","x","y","z"]:
a[i] =str(9)
# 第二步：将其中的大写先变成小写然后移位
# 补充知识点：A~Z的ASCII为65~90，a~z的ASCII为97~122
# ord()用于将单字符转化为ASCII, chr()用于将ACSII转化为单字符
# 对a中的字符进行遍历
for i in range(len(a)):
# 如果发现有大写字母
# 这里还是利用了内置的函数isupper()判断是否是大写字母
if a[i].isupper():
# 先将字符变为小写,然后进行向后移动一位
a[i]=(ord(a[i].lower())+ 1 -ord("a"))%26 +ord("a")
# 然后再将ASCII转化为单字符
a[i]=chr(a[i])
# 得到了一个变更好的数组
# 将数组中的每个元素合并输出来
res=""
for i in range(len(a)):
res+=a[i]
print(res)
HJ24合唱队
是最长递增子序列的变体：对原序列从左到右和从右到左分别求出到每个元素的最长递增子序列的长度
自己一开始根本没有想到这个层面上来，所以做的也是稀里糊涂的。
以下位正确的解题思路：
- 先要得到第一次从左到右计算升序即每个学生左边最多有多少人（包括最大的那个值）
- 将原数组进行逆序，然后计算每个人的右边最多可以有多少个人（包括它自己）
- 将两次列表的值相加，得到的就是每个人的左右最多有多少人（包括两次自己）
- 最大值-1就是最长的排队序列的人数了
看到还有的另外的一种解释：寻找峰值的过程，计算峰值左侧的数量以及峰值右侧的数量，并相加寻找最大值的过程，在一开始的过程中所有的值都是峰值，所以初始化为1
# 参照最长递增子序列的写法
# 先定义一个求最长子序列的函数,用来统计每个人的最左边出现的人数（善于把抽象的问题具体化）
def fn(nums):
n = len(nums)
# 设置一个dp数组，并将其中的值初始化为1，初始化的定义要明白：就是以本身结尾，左边没有比他小的数的情况
dp=[1]*n
# 设置一个数组来记录初始的长度
maxlength=1
# 设置一个结果数组，用来装到每个元素的最长递增子序列的长度
res=[]
# 对dp数组进行遍历
for i in range(n):
# 对原数组进行遍历，其中在遍历的时候不能超过dp中对应的位置
for j in range(i):
# 如果发现nums[i] > nums[j] 并且当前的dp[j]+1要比dp[i]的值要大，说明以最后的一个元素结尾组成的子序列要大一些（这里的比较的过程其实也是一个十分细节的过程，没有用到python的内置的max()来求解。）
if nums[i] >nums[j] and dp[i] <dp[j] +1:
dp[i] = dp[j]+1
# 在每次遍历完内层循环之后(更新dp[i]的过程中)，都需要比较一下此时dp[i]的值与初始化的1哪个更大
if maxlength < dp[i]:
# 把更长的子序列的长度赋予给maxlength
maxlength=dp[i]
res.append(dp[i])
# return maxlength
return res
N=int(input())
a = list(map(int,input().split()))
# 先求出从左向右的过程中的最长子序列长度的数组
lst1=fn(a)
#print(lst1)
# 再求从右向左的过程中的最长子序列长度的数组
b=list(num for num in a[-1::-1])
lst2=fn(b)
#print(lst2)
# 将lst1与lst2反序后合并
lst3=[]
for i in range(len(lst1)):
lst3.append(lst1[i]+lst2[::-1][i])
# 求出最后需要出列的人数
print(len(a)-max(lst3) +1)
# 这里拿题目中给定的例子来理解
# 题目给定的数，经过转换之后，a=[186, 186, 150, 200, 160, 130, 197, 200]
# 求从左到右数的到每个元素的最长递增子序列 lst1=[1, 1, 1, 2, 2, 1, 3, 4]
# 这里的lst1也可以理解为每个人左边可能出现最多的人
# 然后对lst1进行逆序b=[200, 197, 130, 160, 200, 150, 186, 186]
# 按照同样的方法求出从右向左到每一个元素的最长递增子序列
# lst2=[1, 1, 1, 2, 3, 2, 3, 3] 反序之后： lst2=[3,3,2,3,2,1,1,1]
# 这里的lst2理解为每个人右边可能出现的最多的人
# 现在需要将两个列表进行合并，注意合并的时候需要将lst2逆序之后再合并得到的最大值-1就得到最大的合唱队人数。（这个人左边的比他小的人数+右边的比他小的人数-多算的本身就是这个合唱队的最大的长度）这里的理解是看了好多的题解之后才慢慢的反应过来的。
# 需要出队的人数=原数组的总数人-维持合唱队需要的人
HJ25-数据的分类处理
描述
信息社会，有海量的数据需要分析处理，比如公安局分析身份证号码、 QQ 用户、手机号码、银行帐号等信息及活动记录。
采集输入大数据和分类规则，通过大数据分类处理程序，将大数据分类输出。
数据范围：1≤I,R≤100 ，输入的整数大小满足 0≤val≤2^31
输入描述：
一组输入整数序列I和一组规则整数序列R，I和R序列的第一个整数为序列的个数（个数不包含第一个整数）；整数范围为0~(2^31)-1，序列个数不限
输出描述：
从R依次中取出R，对I进行处理，找到满足条件的I：
I整数对应的数字需要连续包含R对应的数字。比如R为23，I为231，那么I包含了R，条件满足 。
按R从小到大的顺序:
(1)先输出R；
(2)再输出满足条件的I的个数；
(3)然后输出满足条件的I在I序列中的位置索引(从0开始)；
(4)最后再输出I。
附加条件：
(1)R需要从小到大排序。相同的R只需要输出索引小的以及满足条件的I，索引大的需要过滤掉
(2)如果没有满足条件的I，对应的R不用输出
(3)最后需要在输出序列的第一个整数位置记录后续整数序列的个数(不包含“个数”本身)
HJ26字符串的排序
这道题也是值得整理的，也是在不断熟悉函数的过程，同时更加熟悉如何处理字符串的问题
- 主要是这里处理的思想，前两个要求很好满足，只需将字符串转化成列表，然后按照将同时改为大写（或小写）来对原序列进行排序，用到了sort函数的高级用法。
- 合理的用到了for i ,v in enumerate的用法，是既可以返回索引又可以返回值的操作。
- 这里地第三点需要非英文字母保持在原味地写法很好，没有用到正则表达式地一些写法（自己暂时也还没有看那么多东西）
- 处理地时候先将非字母字符填充好，然后把带字母地排好序，然后按照顺序，从排好序地数组中弹出第一个元素，按照顺序加入到空缺位置。
a = list(input())
s=[]
res=[0]*len(a)
for i,v in enumerate(a):
# 如果v是字母的
if v.isalpha():
s.append(v)
# 如果v不是字母,把这个元素放在固定的位置不动
else:
res[i]=v
# 对s排序
s.sort(key=lambda x: x.upper())
#print(res)
#print(s)
for i,v in enumerate(res):
# 如果不是v(对于not v这样的写法，程序会自动地返回0)
# 所以这里地v==0和not v,虽然形式上不一样，但是结果都是返回地0地情况
# if v==0:
if not v:
# 将s的第一个元素作为此时的值
res[i]=s.pop(0)
# 然后把这两个连在一起
print(''.join(res))
HJ29-字符串的加解密
题目的描述还是比较的简单：
加密方法为：
当内容是英文字母时则用该英文字母的后一个字母替换，同时字母变换大小写,如字母a时则替换为B；字母Z时则替换为a；
当内容是数字时则把该数字加1，如0替换1，1替换2，9替换0；
其他字符不做变化。
解密方法为加密的逆过程。
数据范围：输入的两个字符串长度满足 1≤n≤1000，保证输入的字符串都是只由大小写字母或者数字组成
解题思路：
- 用到的不同的字符对应的ASCII的范围:48
57 6590 97~122 - 用到了几个重要的函数：ord() chr() isdigit() isupper() isalpha()
- 关于循环取模的用法：自己体会
# 解题思路：分别写一个加密的函数和一个解密的函数
# 定义一个加密的函数jiami
def jiami(s1):
res1=''
# 对字符串进行遍历
for c in s1:
# 如果发现是英文字母
# 小写的英文字母的ASCII码是65~90
# 大写的英文字母的ASCII是97~122
# 0~9的ASCII是48~57
if c.isalpha():
if 65<=ord(c)<=90:
# 先把字符转换为ASCII
temp=ord(c)
# print(temp)
# 然后将ASCII向后移动一位，变成小写字母，然后转换为单字符
c=chr((temp+1-65)%26+97)
elif 97<=ord(c)<=122:
# 先把字符转换为ASCII
temp=ord(c)
# print(temp)
# 然后将ASCII向后移动一位，变成大写字母，然后转换为单字符
c=chr((temp+1-97)%26+65)
# 说明是数字
else:
temp=ord(c)
c=chr((temp+1-48)%10+48)
res1+=c
return res1
# 定义一个解密的函数
def jiemi(s2):
res2=''
# 对字符串进行遍历
for c in s2:
# 如果发现是英文字母
# 小写的英文字母的ASCII码是65~90
# 大写的英文字母的ASCII是97~122
if c.isalpha():
# 是大写字母
if 65<=ord(c)<=90:
# 先把字符转换为ASCII
temp=ord(c)
# 然后将ASCII向后移动一位，并变成小写，然后转换为单字符
c=chr((temp-1-65)%26+97)
elif 97<=ord(c)<=122:
# 先把字符转换为ASCII
temp=ord(c)
# 然后将ASCII向后移动一位，并变成大写，然后转换为单字符
c=chr((temp-1-97)%26+65)
# 说明是数字
else:
temp=ord(c)
c=chr((temp-1-48)%10+48)
# print(c)
res2+=c
return res2
while True:
try:
s1=input()
s2=input()
print(jiami(s1))
print(jiemi(s2))
except:
break
HJ33整数与ip地址间的转换
这道题也是值得整理的，主要还是对字符串的处理上面，是两个过程：整数与IP地址之间的互换
值得自己再重新写一遍，而且有很多需要注意的细节的地方。
前置知识需要处理：
ip地址：是一个32位的二进制数，通常被分割为4个“8进制的数”，通常用”点分十进制”表示成（a.c.c.d）的形式，其中a b c d都是0~255之间的10进制的整数。
ip地址的组成重点：
- 网络部分(网络位)：直接决定了可以分配的网络计算方法：2^网络号位数-2
- 主机部分(主机位)：决定了网络中的最大主机数计算方法：2^主机号位数-2
- 网络地址：用来表示一个网络，主机位取值为0：例如192.168.1.0/24
- 广播地址：用于在一个网络内一对所有的通信。主机部分全部换成1。
- 子网掩码：用于区分IP地址中的网络部分和主机部分，子网掩码 在 网络位的 全部按 1
- 默认网关：就是一个网络连接到另一个网络的“关口”，一般情况下网关的IP就是所在网络的**路由器的IP **
while True:
try:
# 用.分隔字符串
s1=list(map(int,input().split('.')))
s2=input()
# print(s)
# 把每段数字转化为二进制数
# 10对应的二进制： 00001010
# 0对应的二进制： 00000000
# 3对应的二进制： 00000011
# 193对应的二进制：11000001
# 将ip地址转换为整数的过程
res1=''
for c1 in s1:
temp='{:08b}'.format(c1)
# print(temp)
res1+=temp
# print(res)
# 组成的二进制数整体转化为十进制
ans1=int(str(res1),2)
# print(ans1)
# 将整数转化为ip地址的过程
res2=[]
# 将10进制转为2进制
temp2=bin(int(s2,10))[2:]
# 如果长度小于32位，高位需要用0来填充
temp2 = '0'*(32-len(temp2)) + temp2 if len(temp2)<32 else temp2
# print(temp2)
for i in range(4):
temp=temp2[8*i:8*i+8]
temp=str(int(temp,2))
res2.append(temp)
# print(res2)
print('.'.join(res2))
except:
break
HJ35 蛇形矩阵
这道题做的时候咋一做的还真是把我难住了，并且还没有相应的思路，在短时间捏确实没有想出什么比较好的方法。以下都是提供的几种方式，我认为都是可以借鉴的，可以帮助自己打开自己的思路，遇到类似的题目的时候可以真正做到举一反三。
方式一是一比较巧的方式：
主要要找规律，主要找到第一行
第1行：相差是逐渐递增，相差2 3 4 5
第2行：第一行去掉第一个数，然后减1（这里的代码实现起来同样也是很巧妙的一种方式，利用上衣循环过程中生成的列表并且这里的列表都是采用的列表生成式的写法，包括在打印输出的时候，每一行矩阵的换行问题。里面的每一行代码都不能含糊）
后面的行数以此类推
# 观察到第一行的数相差的值是有规律的
# 后面的每一行都是在上一行的基础上除去第一个数之后再+1
# 有n行的矩阵
while True:
try:
n=int(input())
# 定义一个矩阵
res = []
for i in range(1,n+1):
# 先打印出第一行
if i==1:
res=[(1+i)*i//2 for i in range(1,n+1)]
# 然后再组装剩下的n-1行的数据
# 将上一行的数据剔除第一个数，然后把每一个数减1:res[1:]
else:
res=[num-1 for num in res[1:]]
# print(' '.join(map(str,res)))
# print(res)
for j in range(len(res)):
print(res[j],end=' ')
print('')
except:
break
方法二：直接硬找行与列之间的关系（参照别人的解答，确实是十分优秀的，尽管可能自己一时半会也想不出来，但是要有这样的思路）
第一行的规律符合累加求和：(1+n) *n//2
第二行的规律是第一行的((1+n) *n//2) -1
第三行的规律是第一行的((1+n) *n//2) -2
第四行的规律是第一行的((1+n) *n//2) -3
当i= 1的时候，j=1,2,3,4进入循环
当i=2的时候，j=2,3,4
当i=3的时候，j=3,4
当i=4的时候，j=4
while True:
try:
# 第一行：累加和的规律n+1)*n//2
# 第二行：在第一行的基础上(1+n) *n//2-1
# 第三行：在第一行的基础上-2
# 第四行：在第一行的基础上-3
n=int(input())
# i表示行数
for i in range(1,n+1):
# 表示当前行有多少列
for j in range(i,n+1):
print((1+j)*j//2-i+1,end=' ')
# 当一层循环完之后，需要换行，开始循环下一论打印下一行
print('')
except:
break
这里还有第三种解法
直接正向进行输出，我觉得这里的理解就更加的不好操作了，真的只有膜拜的份了。
n=5
# 计数器
count=0
# 先生成一个特定矩阵的容器
# 这个技巧必须要学会（是常规矩阵生成体的一种变式）
res=[[0]*(n-i) for i in range(n)]
# print(res)
# 下面来开始填入数据
# 我们通过找规律发现，如果是按照三角形塔的形式来输出的话
# 直接把这个矩阵逆时针旋转45度就可以得到目标矩阵
# 在旋转的过程中原来的行和列与现在的行和列有一定的关系
# 列前后不变，行有变换
# 这两个循环是冲着生成塔三角的形式去的
temp=[[0]*i for i in range(1,n+1)]
print(temp)
for i in range(n):
for j in range(i+1):
count+=1
temp[i][j]=count
print(temp)
# [1, 3, 6, 10, 15] [2, 5, 9, 14] [4, 8, 13] [7, 12] [11]
# 这样其实就已经将这个矩阵给求出来了
完整的代码如下：
n=int(in[put())
# 计数器
count=0
res=[[0]*(n-i) for i in range(n)]
# 在res中填充元素
for i in range(n):
for j in range(i+1):
count+=1
res[i-j][j]=count
# print(res)
# res=[[1, 3, 6, 10, 15], [2, 5, 9, 14], [4, 8, 13], [7, 12], [11]]
# 现在把结果矩阵的元素按照行输出来，元素与元素之间用空格隔开
for s in res:
for i in s:
print(i,end=' ')
print('')
# 这里也可以直接用map(srt,res)，可以一步到位，十分的方便(s本身也就是一个可以迭代的)
for s in res:
print(' '.join(map(str,s)))
HJ37-统计每个月兔子的总数
自己做了时候好像已经找了规律，但是写的时候还是有点摸不着头脑的样子（显然规律找错了）
用到动态规划和循环的解法（其实这里的解法很多很多，而且这道题已经快做烂了）
代码不再贴了，主要做了很多的次数了。
字符串加解密
直接写思路，题目估计在笔试前是没有时间做了。读懂题目
加密方法：
- 当内容是英文的时候，用英文字母的后一个字母替换（以26为一个轮换），同时字母变换大小写
- 当 内容是数字时，把数字+1（这肯定要做一个以9为一个循环的判断）
- 其他字符不做变化
解密方法：加密方法的逆过程
这题和21题总的来说是比较像的。
HJ43迷宫问题
第一次写这道题，想着是用深度优先搜索地，发现这里地模式是ACM模式，所以函数调用不成功，后面调试都进行不下去了。还是想总结出自己特有地思路，和之前听地视频课地内容能够很好地结合起来才会变成自己的东西。
借鉴别人的思路，把别人的代码先弄懂（找准一个点看下去就行）
N*M的一个矩阵，表示一个迷宫，其中1表示墙壁，0表示可以走的路，只能横或竖着走，不能斜着走，要求编程找出从左下角到右下角的最短路径。
在回顾这道题的时候，又把岛屿问题以及排列I和排列II的问题又回顾了一遍，代码还是不够完全熟练掌握。
废了好大的劲终于把这道题给弄懂了，剩下的就是不断地熟悉再熟悉地过程了（代码一定要滚瓜烂熟，烂熟于心才行，这题地代码也是多多多地跑几遍才行）
while True:
try:
# 先把dsf的模板搬上来，不会也要强行让自己掌握
def dfs(x,y,lst,mark,path):
# 循环遍历当前位置的上下左右四个方向
#定义方向向量
directions=[(-1,0),(1,0),(0,-1),(0,1)]
# 当遍历到最后一行最后一列是，递归结束，输出这条路径上的所有值
if x==len(mark)-1 and y==len(mark[0])-1:
for i, j in path:
print('(' + str(i) + ',' + str(j) + ')')
for dx,dy in directions:
# 定义新的行以及新的列
newX,newY=x+dx,y+dy
# 如果新的行与新的列超出数组的边界
if newX<0 or newX>=len(mark) or newY<0 or newY>=len(mark[0]):
#跳出当前的位置
continue
# 如果发现这个位置是0（表示可以走得通），并且这个位置又没有被标记过
if lst[newX][newY]==0 and mark[newX][newY]==0:
# 当前搜索在mark中标记为1，代表已经遍历过了
mark[newX][newY]=1
# 把该值添加到路径中去
path.append((newX,newY))
#print(path)
# 递归进行相应的搜素
dfs(newX,newY,lst,mark,path)
# 标记重新还原,表示没有被访问
mark[newX][newY]=0
path.pop()
# 输入行数和列数
n,m=map(int,input().split())
# 定义一个数组用来放输入的数据
lst=[]
path=[(0,0)]
# 定义一个mark数组，标记已经搜索的位置
mark=[[0]*m for _ in range(n)]
for i in range(n):
# a = list(map(int,input().split()))
# lst.append(a)
lst.append(list(map(int,input().split())))
#print(lst)
# 从坐标(0,0)开始进行搜索
dfs(0,0,lst,mark,path)
except:
break
在第二遍做的时候就发现，有的很小的东西出现错误，机会是完全靠的肌肉肌肉，把题目给背下来了，没有认真的去检查，但是相对来说已经有了很大的进步，总得来还算比较的合理。今天或者明天再做第三遍（不仅仅是代码的肌肉记忆，也是思路的肌肉记忆。）
出错的几个点：
这三行代码再写的时候打了一下蹬，说明在语法上面还是不够特别的熟悉。path是一个数组，数组里面的是元组，目的是取出元组。
这五行代码当时写的不是特别的笃定：- 一旦满足条件，就标记已访问
- 随后把符合条件的加入到路径数组中
- 然后在当前的基础上进行下一轮的搜索
- 下一轮搜索结束之后，将当前的标记改回来
- 将当前的元素弹出原本加入的路径
HJ48-从单向链表中删除指定值的节点
# 参考题解的一些做法
# 纯当学习记录
#方法一：逆向翻转链表
# 定义一个节点类
class ListNode(object):
def __init__(self, data=0):
self.data = data
self.next = None
while True:
try:
# 定义一个头节点
head = ListNode()
# 输入链表的结点个数
n = int(input())
a = list(map(int, input().split(" ")))
# print(a)
k = int(input())
# 经过一个循环之后，头节点指向倒数第k个节点
while k:
# 让head的next节点不断地指向从列表中弹出的元素
# 这里地定义很巧妙
head.next = ListNode(a.pop())
head = head.next
k -= 1
print(head.data)
except:
break
方法二（写的稍微多点，完全按照定义来）
# 定义一个节点类
class ListNode(object):
def __init__(self,data):
self.data=data
self.next=None
# 定义一个链表类
class SingleLinkList(object):
# 定义链表类的方法,并初始化方法
def __init__(self,node=None):
# 一个私有的head属性，指向None
self.__head=None
# 判断链表是否为空
def isempty(self):
return self.__head==None
# 在链表的尾部添加节点的方法（尾插法）
def append(self,item):
node=ListNode(item)
# 判断链表是否为空
if self.isempty():
# 直接让self.__head指向node
self.__head=node
# 链表不为空
else:
cur=self.__head
# 这个时候的循环判断条件发生变化
while cur.next!=None:
cur=cur.next
# 循环结束的时候cur.next指向为None
# 修改最后一个节点的指向，将cur.next指向node
cur.next=node
def pos_search(self,length,pos):
cur=self.__head
count=0
# 如果pos是负数的情况
if pos<=0:
return False
else:
while cur!=None:
# 计数+1
count+=1
if count==length-pos+1:
print(cur.data)
return True
else:
cur=cur.next
return False
while True:
try:
# 输入链表的结点个数
n=int(input())
a=list(map(int,input().split(' ')))
k=int(input())
sll=SingleLinkList()
# 把单向链表的值全部加进来
for i in range(n):
temp=a[i]
sll.append(temp)
# 接下来开始去查找倒数第K个指针对应的值
sll.pos_search(n,k)
except:
break
HJ50-四则运算
输入一个表达式（用字符串表示），求这个表达式的值。
保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。
数据范围：表达式计算结果和过程中满足 ∣val∣≤1000 ，字符串长度满足 1≤n≤1000
输入描述：
输入一个算术表达式
输出描述：
得到计算结果
做题分析：刚开始得到这道题也是一筹莫展，考点有字符串、基础数学、栈的相关知识
总的运算规则：
- 先算括号里面的，并且括号有一个优先级
- 在括号里面的数组，先算乘除，再算加减
- 在括号外面的同级的要按照从左到右的顺序来算
HJ51-输出单向链表中倒数第k个结点
这道题是务必要掌握的，没有任何的理由，必须拿下，原来这道题自己是做过的，但是这里更考验完整的代码能力，所以还是没有那么好做。
输入一个链表，输出倒数第k个结点，链表的倒数第一个结点为链表的尾指针
- 需要构建链表
- 构建后需要忘记链表长度
- 正常返回第k个节点指针，异常返回空指针
# 代码如下
# 利用列表的知识来求解（此份代码是引用别人的）
# 这种方式是在充分理解概念之后，用十分精简凝练的代码写出来的
# 需要自己写一个结点类
class Node(object):
def __init__(self, val=0):
self.val = val
self.next = None
while True:
try:
l, s, k, head = int(input()), list(map(int, input().split())), int(input()), Node()
while k:
head.next = Node(s.pop())
head = head.next
k -= 1
print(head.val)
except:
break
HJ53-杨辉三角的变形
发现规律，从第三行开始，2324的循环
while True:
try:
n=int(input())
if n<=2:
print(-1)
# 从第三行开始分别是 2 3 2 4 2 5
else:
temp=[2,3,2,4]
print(temp[(n-3)%4])
except:
break
HJ54-表达式求值/BM49
这道题和BM49题基本上一模一样的
描述
给定一个字符串描述的算术表达式，计算出结果值。
输入字符串长度不超过 100 ，合法的字符包括 ”+, -, *, /, (, )” ， ”0-9” 。
数据范围：运算过程中和最终结果均满足 ∣val∣≤231−1，即只进行整型运算，确保输入的表达式合法
输入描述：
输入算术表达式
输出描述：
计算出结果值
其实在做这道题的时候也发现一些比较好的思路，值得自己去学习：
# 待记录比较好的解法
HJ-完全数计算
也主要是思路
描述
完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。
它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。
例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。
输入n，请输出n以内(含n)完全数的个数。
数据范围： 1≤n≤5×105
可以尝试看看其他人的解法：
while True:
try:
# 首先需要明白完全数的定义：除自己以外的约束之和==它本身，即需要把相应的约数全部给枚举说出
# 然后给出一个判断，是否之和等于它本身
# 对于符合这个条件的数用count数组+1
n=int(input())
count=0
# 以下求的是某个具体的数的全部的约数
def fn(n):
res=[]
for i in range(1,n):
if n%i==0:
res.append(i)
return sum(res)
for i in range(1,n):
if fn(i)==i:
count+=1
print(count)
except:
break
HJ70-矩阵乘法计算量估算
这道题在利用栈的题目里面算相对简单的。这里需要注意的地方是计算的法则为一个字符串，它是由左右括号和大写字母组成的，这里就存在一个数字与ASCII的相互转换的问题，AZ对应的ASCII是6590，关键还是在处理矩阵以及矩阵的技巧上面，这个很考验基本功和思维能力；然后还有就是基本的矩阵相乘的数学知识的问题；还有对右括号的处理的问题（下面的两种写法一种处理了，一种并没有处理）；算完括号内的值之后在更新值的过程也是一大特点。（这里是自己不做题就根本想不到的地方）
这种用两种写法来写
- 用字典的形式来存储矩阵
- 直接用数组的形式来存储矩阵
# 用字典的形式来存储矩阵，其中key为对应的字母转化为ASCII之后的值
# 这里有一个好处是预先就将字典的key给出了，给每个矩阵都按顺序配了A~Zkey值
# 做了之后发现这样的方法不是特别的好，容易和输入的字母混淆
while True:
try:
n = int(input())
mdict = {}
for i in range(n):
mdict[chr(ord('A')+i)] = list(map(int, input().strip().split()))## 用strip()先去掉可能隐藏的末尾空格。再split(),防止map不过去
# s表示输入的矩阵表达式
# 注意这里s的表达式中非括号的数字是大写字母
# ((AB)C)
# (A(BC))
# (A(B(C(D(E(F(GH)))))))
s = input()
result = 0
temp = []
for i in s:
#不遇到')'就一直压栈
if i != ')':
temp.append(i)
#直接遇到')',把前两个弹出来计算乘法运算量
else:
C = temp.pop()
B = temp.pop()
# 弹掉前括号'('
temp.pop()
result+= mdict[B][0] * mdict[B][1] * mdict[C][1]
mdict[B] = [mdict[B][0], mdict[C][1]]#把当前乘积的结果存储起来
temp.append(B)#把当前乘积结果入栈
#因为有最外圈括号，弹完所有')'即完成整个算式的结果
print(result)
except:
break
# 直接用数组来存储矩阵，其实本质和上面的是差不多的，如果只是改动这一点，还上面没有什么差别
# 这里主要是改动了if的判断语句，作为一种选择放在这里
# 实际上是字符是左括号什么也不做；字符是右括号，出栈，字符是字母，入栈。
while True:
try:
n = int(input())
mdict = []
for i in range(n):
# 用strip()先去掉可能隐藏的末尾空格。再split(),防止map不过去
mdict.append(list(map(int, input().strip().split())))
# print(mdict)
# s表示输入的矩阵表达式
# 注意这里s的表达式中非括号的数字是
s = input()
result = 0
temp = []
for i in s:
# 如果发现是字母就加进去
# 相比上面的解法，这里排除了加入左括号的情况（默认题目给定的一定是一个有效的字符串）
if i.isalpha():
# temp.append(i)
# 把原先是字母的现在全部转换为数字，并且按照A~Z转化为0~25这样的形式来处理
temp.append(mdict[ord(i)-65])
#直接遇到')',把前两个弹出来计算乘法运算量
elif i==')' and len(temp)>=2:
# 第一次弹出的数
b=temp.pop()
#print(b)
# 第二次弹出来的数
a=temp.pop()
# print(a)
result +=a[0] * a[1] * b[1]
temp.append([a[0],b[1]])
#因为有最外圈括号，弹完所有')'即完成整个算式的结果
print(result)
except:
break
HJ87-密码强度等级
自己写的代码有点过于冗长了
while True:
try:
s=input()
# 初始化一个分数score，为0分
score=0
n=len(s)
# 分别从5个方面进行对分数的增加
# 1.对密码长度进行统计
# 2.对字母大小写的种类进行统计
# 3.对数字的个数进行统计
# 4.对符号的个数进行统计
# 5.对字母.数字以及符号的种类进行统计
# 对密码长度的判定，然后计算得分
if n<=4:
score+=5
elif 5<=n<=7:
score+=10
else:
score+=25
# 对密码中字母的判定
# 需要对大小写字母进行计数
count_daxie=0
count_xiaoxie=0
count_num=0
count_other=0
for c in s:
if c.isalpha():
if c.isupper():
count_daxie+=1
else:
count_xiaoxie+=1
# 如果发现c是数字统计数字的个数
elif c.isdigit():
count_num+=1
# 既不是字母，也不是数字，是其他的符号
else:
count_other+=1
# 循环结束之后对各项都有了一定的统计
if (count_daxie!=0 and count_xiaoxie==0) or (count_daxie==0 and count_xiaoxie!=0):
score+=10
elif count_daxie!=0 and count_xiaoxie!=0:
score+=20
if count_num==1:
score+=10
elif count_num>1:
score+=20
if count_other==1:
score+=10
elif count_other>1:
score+=25
# 怎么体现种类
count_alpha=count_daxie+count_xiaoxie
# 字母+数字
if count_alpha+count_num==n and count_num!=0:
score+=2
# 字母+数字+符号
elif count_alpha+count_num+count_other==n and count_daxie==0 or count_xiaoxie==0 and count_num!=0 and count_other!=0:
score+=3
elif count_daxie+count_xiaoxie+count_num+count_other==n and count_daxie!=0 and count_xiaoxie!=0 and count_num!=0 and count_other!=0:
score+=5
# print(score)
# 开始对密码进行强度的评定
if score >=90:
print('VERY_SECURE')
elif 80<=score<90:
print('SECURE')
elif 70<=score<80:
print('VERY_STRONG')
elif 60<=score<70:
print('STRONG')
elif 50<=score<60:
print('AVERAGE')
elif 25<=score<50:
print('WEAK')
elif 0<=score<25:
print('VERY_WEAK')
except:
break
HJ86- 求最大连续的bit数
主要是学习里面的思路，当然代码的实现也很重要
比如方法一里面采用0分隔的方法，然后找出最长的那个字符（就是出现最多1的情况）
方法一：
# split()一下之后用下set去掉多个分割出来的空值排个序就好了吧
while True:
try:
n=int(input())
temp=bin(n)[2:]
# print(temp)
# 按照0的位置进行相应的切分
temp=list(set(temp.split('0')))
# 然后按照长度进行排序
temp.sort(key=lambda x:len(x),reverse=True)
print(len(temp[0]))
except:
break
方法二：采用位运算的思路解题
要能想到这种方法以及里面的思想
while True:
try:
n=int(input())
temp=bin(n)[2:]
# print(temp)
nums=[int(c) for c in temp]
maxCount=count=0
length=len(nums)
# 对数进行遍历
for i in range(length):
if 1&nums[i]==1:
count+=1
# 每次更新最大的长度
maxCount=max(maxCount,count)
else:
count=0
print(maxCount)
except:
break
采用一次遍历的方法
这种方法应该才是最常规的方法了
while True:
try:
n=int(input())
temp=bin(n)[2:]
# 将位运算的字符转化为列表
# print(temp)
nums=[int(c) for c in temp]
# print(nums)
maxCount=count=0
for i,num in enumerate(nums):
if num==1:
count+=1
maxCount=max(maxCount,count)
else:
# 重置计数
count=0
print(maxCount)
except:
break
HJ96-表示数字
描述
将一个字符中所有的整数前后加上符号“”，其他字符保持不变。连续的数字视为一个整数。
数据范围：字符串长度满足 1≤n≤100 1 \le n \le 100 \ 1≤n≤100
输入描述：
输入一个字符串
输出描述：
字符中所有出现的数字前后加上符号“”，其他字符保持不变
示例1
输入：
Jkdi234klowe90a3
输出：
Jkdi234klowe90a3
这里自己参考别人的思路给了两种方法
while True:
try:
s=input()
n=len(s)
# 记录当前遍历的字符的前一个字符
char_pre=''
res=''
for c in s:
# 如果当前遇到的数字
if c.isdigit():
# 判断前面是否为数字，如果不是，说明这个数字就是开头的数字，加一个*
if char_pre.isdigit()==False:
res+='*'
# 如果当前遇到的不是数字，查看前面的数字是否是数字，如果是表示数字的结束，加入一个*
else:
if char_pre.isdigit():
res+='*'
# 把当前的字符带出来
res+=c
# 当前字符更新到前字符
char_pre=c
# 循环结束，查看最后一个字符是不是数字
if s[-1].isdigit():
res+='*'
print(res)
except:
break
while True:
try:
# 将所有出现数字的前后都加上*
# 循环完毕后将**用replace函数转换为''
s=input()
res=''
# 考虑到原本就有*的存在，先把*替换成一个不可能出现的字符
s=s.replace('*','熊锐')
for c in s:
if c.isdigit():
res+='*' + c + '*'
# print(res)
else:
res+=c
res=res.replace('**','')
# 在打印输出的阶段再把特殊字符更正回来
print(res.replace('熊锐','*'))
except:
break
HJ107-求解立方根
采用下面的几种方法：
采用二分法：
while True:
try:
a=float(input()) # 获取输入的实数a
e=0.0001 # 设定一个精度值
low=min(-1.0,a)
high=max(1.0,a)
ans=(low+high)/2
while abs(ans**3-a)>=e:
# 如果ans**3<a，说明此时的值偏小
if ans**3<a:
low=ans
else:
high=ans
ans=(low+high)/2
print('{:.1f}'.format(ans))
except:
break
#采用牛顿迭代法
while True:
try:
a=float(input()) # 获取输入的实数a
e=0.0001 # 设定一个精度值
# 用最初始的值作为初始值
last=a
# 用迭代公式求解下一个更接近的值
# 公式是通过泰勒展开式取前两项展开得来的
ans=last-((last**3-a)/(3*last**2))
# 当ans**3-last的精度值不满足要求的时候,进行循环迭代,使其满足相应的精度要求
while abs(ans-last)>=e:
last=ans
ans=last-((last**3-a)/(3*last**2))
print('{:.1f}'.format(ans))
except:
break
采用库函数
while True:
try:
a=float(input())
if a>=0:
res='{:.1f}'.format(pow(a,1/3))
else:
res='{:.1f}'.format(-pow(-a,1/3))
print(res)
except:
break
在用库函数的时候，看到别处的题解，觉得非常好，可以将代码进行一些相应的简化
while True:
try:
a=float(input())
s=-1 if a<0 else 1
res='{:.1f}'.format(s*pow(s*a,1/3))
print(res)
except:
break