# 力扣初级算法（Python）（一）

## 2数组

### 2.1 删除排序数组中的重复项

class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
length = 0;
for i in nums:
if i != nums[length]:
length+=1
nums[length] = i
return length+1

### 2.2  买卖股票的最佳时机 II

class Solution:
def maxProfit(self, prices: List[int]) -> int:
if (prices == None or len(prices)<2):
return 0
profit = 0
index = 0
length = len(prices)
while(index<length):
while (index<length-1 and prices[index]>= prices[index+1]):
index+=1
min = prices[index]
while (index<length-1 and prices[index]<= prices[index+1]):
index+=1
profit += prices[index]-min
index +=1
return profit



### 2.3 轮转数组

class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k = k % n
nums[:] = nums[n - k:] + nums[:n - k]

### 2.4 存在重复元素

class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
nums.sort()
length = len(nums)
for i in range(length-1):
if nums[i] == nums[i+1]:
return True
return False

### 2.5 只出现一次的数字

class Solution:
def singleNumber(self, nums: List[int]) -> int:
nums.sort()
length = len(nums)
i = 0
while i < (length-1):
if nums[i] == nums[i+1]:
i+=2
else:
return nums[i]
return nums[length-1]

### 2.6 两个数组的交集||

class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
i = 0
j = 0
result = []
while i<len(nums1) and j<len(nums2):
if(nums1[i]<nums2[j]):
i+=1
elif(nums1[i]>nums2[j]):
j+=1
else:
result.append(nums1[i])
i+=1
j+=1

return  result

### 2.7 加一

class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
length = len(digits)
i = 0
sum = 0
while i<length:
sum = sum*10+digits[i]
i +=1

sum +=1
result = []
while sum > 0:
t = sum%10
sum //=10
result.insert(0,t)
return result

### 2.8 移动零

class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
i = 0
num_zeros = 0
while i < len(nums):
if nums[i] == 0:
nums.pop(i)
num_zeros += 1
else:
i+=1

for i in range(num_zeros):
nums.append(0)            

### 2.9 两数之和

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
length = len(nums)
first = 0
while(first<length):
second = first+1
while(second<length):
if(nums[first]+nums[second] == target):
return [first,second]
second += 1
first +=1
return [first,second]

### 2.10 有效的数独

3行2列：3个列表，每个列表的长度是2
w, h = 2, 3
A = [[None] * w for i in range(h)]

class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
n = len(board)
m = len(board[0])
row = [[]  for _ in range(9)]
col = [[]  for _ in range(9)]
nine = [[]  for _ in range(9)]
for i in range(n):
for j in range(m):
tmp = board[i][j]
if not tmp.isdigit():
continue
if tmp in row[i]:
return False
if tmp in col[j]:
return False
if tmp in nine[(j // 3) * 3 + (i // 3)]:
return False
row[i].append(tmp)
col[j].append(tmp)
nine[(j // 3) * 3 + (i // 3)].append(tmp)
return True

### 2.11旋转图像

class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
length = len(matrix);
#先上下交换
for  i in range(length // 2):
temp = matrix[i]
matrix[i] = matrix[length - i - 1]
matrix[length - i - 1] = temp
#在按照对角线交换
for i in range(length):
for  j in range(i + 1, length):
temp = matrix[i][j]
matrix[i][j] = matrix[j][i]
matrix[j][i] = temp

## 3 字符串

### 3.1 反转字符串

class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
#s.reverse()-_-
length = len(s)
for i in range(length//2):
t = s[i]
s[i] = s[length-1-i]
s[length-1-i] = t

### 3.2   整数反转

class Solution:
def reverse(self, x: int) -> int:
s = str(x)
if s[0] == '-':
s_rev = s[0] + s[-1:-len(s):-1]
else:
s_rev = s[::-1]
x_rev = int(s_rev)
if -2 ** 31 <= x_rev <= 2 ** 31 - 1:
return x_rev
return 0

### 3.3 字符串中第一个唯一字符

class Solution:
def firstUniqChar(self, s: str) -> int:
for x in s:
if s.find(x) == s.rfind(x):
return s.index(x)
return -1

class Solution:
def firstUniqChar(self, s: str) -> int:
for x in s:
if s.count(x) == 1:
return s.index(x)
return -1

### 3.4 有效的字母异位词

class Solution:
def isAnagram(self, s: str, t: str) -> bool:
list_s = list(s)
list_s.sort()
list_t = list(t)
list_t.sort()
length = len(list_s)
if length != len(list_t):
return False
for i in range(len(list_s)):
if list_s[i] != list_t[i]:
return False

return True

### 3.5 验证回文串

1.双指针

class Solution:
def isPalindrome(self, s: str) -> bool:
s = s.lower()
tail = len(s)-1
continue
if not (s[tail].isalpha() or s[tail].isdigit()):
tail -=1
continue
else:
return False
else:
tail -=1
return True

2.去掉字母数字后，遍历一半元素

class Solution:
def isPalindrome(self, s: str) -> bool:
list_s = []
s = s.lower()
length_s = len(s)
for i in  range(length_s):
if s[i].isalpha() or s[i].isdigit():
list_s.append(s[i])
print(list_s)
length_list = len(list_s)
for i in range(length_list//2):
if list_s[i] != list_s[length_list-1-i]:
return  False
return True

### 3.6 字符串转整数

class Solution:
def myAtoi(self, s: str) -> int:
res = 0
i = 0
flag = 1
length = len(s)
#处理空格
while i < length and s[i] == ' ':
i += 1
#处理符号
if i < length and s[i] == '-':
flag = -1
i += 1
elif i < length and s[i] == '+':
flag = 1
i += 1

#读取数字
while i < length and s[i].isdigit():
r = int(s[i])
res = res*10 + r
i += 1
res *= flag
#截断超过范围的结果
if res>= -2**31 and res <= 2**31-1 :
return res
else:
return -2**31 if res<-2**31 else 2**31-1

### 3.7 实现 strStr()

class Solution:
def strStr(self, haystack: str, needle: str) -> int:
n = len(haystack)
left = 0
right = len(needle)
if right == 0:
return 0
while right <= n:
if haystack[left: right] == needle:
return left
left += 1
right += 1
return -1

### 3.8  外观数列

• countAndSay(1) = "1"
• countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
class Solution:
def countAndSay(self, n: int) -> str:
if n == 1:
return '1'
s = self.countAndSay(n - 1)
ans = ''
start, end = 0, 0
while end < len(s):
while end < len(s) and s[start] == s[end]:
end += 1
ans += str(end - start) + s[start]
start = end

return ans

### 3.9  最长公共前缀

class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if strs is None or len(strs) == 0:
return ""
result = ""
minLength = len(strs[0])
for s in strs:
if len(s) < minLength:
minLength = len(s)
for i in range(minLength):
c = strs[0][i]
for s in strs:
if s[i] != c:
return result
result += c
return result

## 4 链表

### 4.1  删除链表中的节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next

### 4.2 删除链表的倒数第N个节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:

fast = dummy
slow = dummy
#fast先走n步
for i in range(n):
fast = fast.next
while fast.next != None:
fast = fast.next
slow = slow.next

slow.next = slow.next.next
return dummy.next

### 4.3 反转列表

#Python中类内函数的递归用self调用：self.f(...)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:

t = res
while  t.next != None:
t = t.next
return  res

### 4.4 合并两个有序链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
if  list2 is None:
return list1
elif list1 is None:
return list2

cur = dummy

while list1 is not None and list2 is not None:
if (list1.val <= list2.val):
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next

if list1 is not None:
cur.next = list1
elif list2 is not None:
cur.next = list2

return dummy.next

### 4.5 回文链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
while fast != None and fast.next !=None:
slow = slow.next
fast = fast.next.next
#链表节点个数为奇数
if fast != None:
slow = slow.next
second = self.reverseList(slow)
while second!=None and head != None:
return False
second = second.next
return True

def reverseList(self, head: ListNode) -> ListNode:
prev = None
return prev

### 4.6 环形链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def hasCycle(self, head: ListNode) -> bool:
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False

## 5 树

### 5.1 二叉树的最大深度

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root == None:
return 0
else:
return 1+max(self.maxDepth(root.left), self.maxDepth(root.right))

### 5.2 验证二叉搜索树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
inorder_list = []
self.inorder(root,inorder_list)
for i in range(len(inorder_list)-1):
if inorder_list[i].val >=inorder_list[i+1].val:
return False
return True

def inorder(self,root,list_m):
if root == None:
return
self.inorder(root.left,list_m)
list_m.append(root)
self.inorder(root.right, list_m)
return list_m

### 5.3 对称二叉树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root == None:
return True
else:
return self.isSymmetricHelper(root.left,root.right)
def isSymmetricHelper(self, left:TreeNode, right:TreeNode) -> bool:
#如果左右子节点都为空，说明当前节点是叶子节点，返回true
if left == None and right == None:
return True
#如果当前节点有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
if (left == None or right == None or left.val != right.val):
return False
#然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
return self.isSymmetricHelper(left.left, right.right) and self.isSymmetricHelper(left.right, right.left)

### 5.4 二叉树的层序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
queue = [root]
res = []
while queue:
sub_list = []
for i in range(len(queue)):
t = queue.pop(0)
sub_list.append(t.val)
if t.left:
queue.append(t.left)
if t.right:
queue.append(t.right)
res.append(sub_list)
return res

### 5.5 将有序数组转换为二叉搜索树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if len(nums) == 0:
return None
mid = len(nums)//2
root = TreeNode(nums[mid])
root.left = Solution.sortedArrayToBST(self,nums[:mid])
root.right =  Solution.sortedArrayToBST(self,nums[mid+1:])
return root

|
7天前
|

Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
26 9
|
5天前
|

Python排序算法大PK：归并VS快速，谁才是你的效率之选？
【7月更文挑战第13天】归并排序** 使用分治法，稳定且平均时间复杂度O(n log n)，适合保持元素顺序和并行处理。
13 5
|
6天前
|

【7月更文挑战第12天】归并排序是高效稳定的排序算法，采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 [12, 11, 13, 5, 6] 分割并归并成有序数组 [5, 6, 11, 12, 13]。虽然 $O(n log n)$ 时间复杂度优秀，但需额外空间，适合大规模数据排序。对于小规模数据，可考虑其他算法。**
26 4
|
7天前
|

Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
53 4
|
5天前
|

“解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系，通过节点和边连接。常见的表示方法是邻接矩阵（适合稠密图）和邻接表（适合稀疏图）。图遍历包括DFS（深度优先搜索）和BFS（广度优先搜索）：DFS深入探索分支，BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
10 1
|
7天前
|

Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
15 3
|
7天前
|

22 3
|
7天前
|

Python实现WOA智能鲸鱼优化算法优化支持向量机回归模型(LinearSVR算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机回归模型(LinearSVR算法)项目实战
21 2
|
7天前
|

Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
43 1
|
7天前
|

Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
23 1