文章目录
NC22 合并两个有序的数组
A: [4,5,6,0,0,0]，m=3
B: [1,2,3]，n=3
合并过后A为:
A: [1,2,3,4,5,6]
偷懒写法：
# @param A int整型一维数组
# @param B int整型一维数组
# @return void
#
class Solution:
def merge(self , A, m, B, n):
# write code here
A[m:] = B
A.sort()
return
标准写法：
class Solution:
def merge(self , A, m, B, n):
# write code here
while m>0 and n>0:
if A[m-1]>B[n-1]:
A[m+n-1] = A[m-1]
m-=1
else:
A[m+n-1] = B[n-1]
n-=1
if n >0:
A[:n] = B[:n]
return
NC3 链表中环的入口结点
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if pHead is None or pHead.next is None:
return None
tem = [] #遍历链表每一个节点
while pHead:
tem.append(pHead)
pHead = pHead.next
if pHead in tem: #若节点出现在tem中，此节点就是环的入口节点
return pHead
return None
WC137 单链表的排序
给定一个无序单链表，实现单链表的排序(按升序排序)。
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
#
# @param head ListNode类 the head node
# @return ListNode类
#
class Solution:
def sortInList(self , head ):
# write code here
p_head = head #保存链表的头
tem_val = [] #保存链表的值
while head: #读取链表的值
tem_val.append(head.val)
head = head.next
tem_val.sort()
new_head = p_head #保存链表的头
for i in tem_val:#将排序后的值，赋值给链表
p_head.val = i
p_head = p_head.next
return new_head
NC52 括号序列
给出一个仅包含字符’(’,’)’,’{’,’}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()“和”()[]{}“都是合法的括号序列，但”(]“和”([)]"不合法。
#
#
# @param s string字符串
# @return bool布尔型
#
class Solution:
def isValid(self , s ):
# write code here
dic = {'(':')','{' :"}",'[':']'}
first = []
for ss in s:
if ss in dic.keys(): #如果是左侧符号，就压入栈
first.append(ss)
if ss in dic.values(): #遇到右侧符号，弹出栈顶，并比对
if len(first) == 0:
return False
tem = first.pop()
if ss == dic[tem]:
continue
else:
return False
return True if len(first)==0 else False #若栈的长度为0返回True
NC53 删除链表的倒数第n个节点
思路：先求长度，再遍历到倒数n+1个节点处，删除它的下一个节点
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
#
# @param head ListNode类
# @param n int整型
# @return ListNode类
#
class Solution:
def removeNthFromEnd(self , head , n ):
# write code here
#防止head为空
if head is None or n ==0:
return head
#链表只有一个节点的情况
if head.next is None :
if n == 1:
return None
if n==0:
return head
#保存链表头
head_r = head
#计算列表长度
l = 0
while head:
l+=1
head = head.next
#重新开始遍历
head = head_r
#找到倒数n+1个节点，并删除它的下一个节点
if l==n:
return head_r.next
for i in range(l-n-1):
head = head.next
head.next = head.next.next
return head_r
NC1 大数加法
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 计算两个数之和
# @param s string字符串 表示第一个整数
# @param t string字符串 表示第二个整数
# @return string字符串
#
class Solution:
def solve(self , s , t ):
# write code here
full = 0 #保存进位
length_max = max(len(s),len(t))
#转化为列表
s = list(s)
t = list(t)
#保存结果
result = ''
for i in range(length_max):
if len(s)>0:
x1 = int(s.pop())
else:
x1 = 0
if len(t)>0:
x2 = int(t.pop())
else:
x2 = 0
tem = x1+x2+full
#判断进位
if tem >=10:
full =1
result += (str(tem-10))
else:
full = 0
result += (str(tem))
#p
if full == 1:
result += '1'
return result[::-1]
NC14 按之字形顺序打印二叉树
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
思路：采用层序遍历，并设置指示变量，每隔一层，反向
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Print(self, pRoot):
# write code here
if pRoot is None:
return []
if pRoot.left is None and pRoot.right is None:
return [[pRoot.val]]
result = [] #保存结果
tem = [pRoot] #保存每一层的节点
point = True#指示变量
while len(tem)>0:
if point:
tem_val = [x.val for x in tem]
result.append(tem_val)
tem2 = []
for node in tem:#从左向右读
if node.left:
tem2.append(node.left)
if node.right:
tem2.append(node.right)
point = False
tem = tem2
else:
tem_val = [x.val for x in tem[::-1]]
result.append(tem_val)
tem2 = []
for node in tem:
if node.left:
tem2.append(node.left)
if node.right:
tem2.append(node.right)
point = True
tem = tem2
return result
NC127 最长公共子串
输入：“1AB2345CD”,“12345EF”
输出：“2345”
思路：动态规划，在长字符串中，设置移动窗口，若遇到相同子串，最长长度+1，滑动窗口左边不动，右边长度+1，否则滑动窗口长度不变，同时向右移动1位
设置变量maxlen = 0 来记录当前最长子串的长度；用i来遍历较长字符串，i-maxlen表示滑动窗口左侧，i+1表示滑动窗口右侧
#
# longest common substring
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @return string字符串
#
class Solution:
def LCS(self,str1 , str2 ):
# write code here
if len(str1) < len(str2):
str1, str2 = str2, str1
res = ''
max_len = 0
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
NC38 螺旋矩阵
输入：
[[1,2,3],[4,5,6],[7,8,9]]返回值：
[1,2,3,6,9,8,7,4,5]
#
#
# @param matrix int整型二维数组
# @return int整型一维数组
#
class Solution:
def spiralOrder(self , matrix ):
# write code here
if len(matrix)==0:
return matrix
m = 0
n = len(matrix)-1 #行数
a = 0
b = len(matrix[0])-1 #列数
result = [] #保存结果
#保证输入矩阵行列数量都大于等于2
if n ==0 and b==0: #一行一列
return matrix[0]
elif n==0: #一行
return matrix[0]
elif b==0: #一列
return [x[0] for x in matrix]
while m<n and a < b:
result.extend(self.circle(matrix, m, n, a, b))
a+=1
m+=1
n-=1
b-=1
if m==n and a==b:#中间只剩一个值的情况（奇数方阵）
result.append(matrix[m][a])
return result
elif m>n and a>b:#中间没有值（偶数方阵）
pass
elif m==n:#中间还剩一行
result.extend(matrix[m][a:b+1])
elif a==b:#中加还有一列
result.extend([x[a] for x in matrix[m:n+1]])
return result
def circle(self,matrix,m,n,a,b):
'''
读取m,n行与a,b列交叉形成的矩形边的值
m<n,a<b
'''
tem = []
tem.extend(matrix[m][a:b+1]) # 向右
for i in range(m+1,n): #向下
tem.append(matrix[i][b])
tem.extend(reversed(matrix[n][a:b+1])) #向左
for j in range(n-1,m,-1): #向上
tem.append(matrix[j][a])
return tem
大佬解法：
zip实现行列变换，每次取完第一行，列变成行，然后逆序，就相当于长方形削掉最上面一层，然后向左旋转90度
class Solution:
def spiralOrder(self , matrix ):
res = []
while matrix:
res += matrix[0]
matrix = list(zip(*matrix[1:]))[::-1]
return res