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

## 6 排序和搜索

### 6.1 合并两个有序数组

class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
# 两个中存在空数组的时，直接返回
if m == 0:
nums1[:] = nums2[:]
return
if n == 0:
return

index1,index2 = 0,0
t = []
while index1<m and index2<n:
if nums1[index1] <= nums2[index2]:
t.append(nums1[index1])
index1 += 1
else:
t.append(nums2[index2])
index2 += 1

if index1 < m:
t += nums1[index1:m]
else:
t += nums2[index2:n]

nums1[:] = t[:]

### 6.2 第一个错误的版本

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer

class Solution:
"""
:type n: int
:rtype: int
"""
mid = n//2
left = 0
right = n
right = mid-1
else:
left = mid+1
mid = (left+right)//2
return mid

return True
else:
return False

## 7 动态规划

### 7.1爬楼梯

class Solution:
def climbStairs(self, n: int) -> int:
if n == 1 or n == 2:
return n
ans = [0,1,2]
i = 3
while i <= n:
ans.append(ans[i-1]+ans[i-2])
i +=1

return ans[n]

### 7.2 买卖股票的最佳时机

class Solution:
def maxProfit(self, prices: List[int]) -> int:
r = 0
min_price = float('inf')  # float('inf')表示正无穷
for price in prices:
min_price = min(min_price, price)  # 截止到当前的最低价（买入价）
r = max(r, price - min_price)  # 截止到目前的最高利润
return r

### 7.3 最大子序和

@yichendai

dp[i] 表示终点在i的子序列的最佳子序和，这样就可以建立其dp[i]和dp[i-1]的关系。

dp[i] = max(dp[i - 1], 0) + nums[i]

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
length = len(nums)
dp = [0 for i in range(length)]
max_r = nums[0]
for i in range(length):
dp[i] = max(dp[i - 1], 0) + nums[i]
max_r = max(max_r,dp[i])

return max_r

### 7.4 打家劫舍

class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) <=0 :
return 0
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0],nums[1])
dp = [0 for i in nums]
dp[0] = nums[0]
dp[1] = max(nums[1],dp[0])
i = 2
while i < len(nums) :
dp[i] = max(dp[i-2]+nums[i],dp[i-1])
i += 1
length = len(nums)
return dp[length-1]

@NeilJi

class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) <=0 :
return 0
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0],nums[1])
pre1 = nums[0]
pre2 = max(nums[0],nums[1])
max_r = 0
i = 2
while i < len(nums) :
max_r = max(pre1+nums[i],pre2)
(pre1,pre2) = (pre2,max_r)
i += 1
return  max_r

## 8 设计问题

### 8.1 打乱数

import random
class Solution:

def __init__(self, nums: List[int]):
self.length = len(nums)
self.reset_nums = nums[:]
self.shuffle_nums  = nums[:]

def reset(self) -> List[int]:
return self.reset_nums

def shuffle(self) -> List[int]:
i = 0
while i < self.length:
t = random.randint(1,self.length-1)
self.shuffle_nums[i],self.shuffle_nums[t] = self.shuffle_nums[t],self.shuffle_nums[i]
i += 1
return self.shuffle_nums

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

### 8.2 最小栈

class MinStack:

def __init__(self):
self.min_v = []
self.stack = []

def push(self, val: int) -> None:
self.stack.append(val)
if len(self.min_v) == 0 or  val <= self.min_v[len(self.min_v)-1]:
self.min_v.append(val)

def pop(self) -> None:
t = self.stack.pop()
if t ==  self.min_v[len(self.min_v)-1]:
self.min_v.pop()

def top(self) -> int:
return self.stack[len(self.stack)-1]

def getMin(self) -> int:
return self.min_v[len(self.min_v)-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

## 9 数学

### 9.1 Fizz Buzz

if else练习

class Solution:
def fizzBuzz(self, n: int) -> List[str]:
list = []
for i in range(1,n+1):
if i % 3 == 0 and i % 5 == 0:
list.append("FizzBuzz")
elif i % 3 == 0:
list.append("Fizz")
elif i % 5 == 0:
list.append("Buzz")
else:
list.append(str(i))
return list

### 9.2 计数质数

class Solution:
def countPrimes(self, n: int) -> int:
isPrimes = [True for _ in range(n)]
count = 0
for i in range(2,n):
if isPrimes[i]:
count += 1
#埃氏筛，i的倍数不是素数
for j in range(2*i,n,i):
isPrimes[j] = False

return count

### 9.3 3的幂

class Solution:
def isPowerOfThree(self, n: int) -> bool:
t = 1
while  t < n :
t *= 3
return True if t == n else False

### 9.4 罗马数字转整数

class Solution:
def romanToInt(self, s: str) -> int:
store = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
strs = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
maps = dict(zip(strs,store))
result = 0
i = 0
while i < len(s):
if i+1 < len(s) and s[i:i+2] in maps:
result += maps.get(s[i:i+2])
i += 2
else:
result += maps.get(s[i:i+1])
i += 1
return result

## 10 其它

### 10.1 位1的个数

class Solution:
def hammingWeight(self, n: int) -> int:
# 第一种解法 使用python特性 bin(3) = ob11
#return bin(n).count("1")

# 第二种使用 位运算 特性 & 与预算符号，  >> 右进位预算符号
res = 0
while n:
res += n & 1  # res +=  （n & 1） 11&1 =1 , 10&1=0 比较最后一位相同1，不同0
n >>= 1 # 右滑动进位
return res

### 10.2 汉明距离

class Solution:
def hammingDistance(self, x: int, y: int) -> int:
#return bin(x^y).count("1")

cnt = 0
z = x^y
while z:
cnt += z & 1
z >>= 1

return cnt

### 10.3 颠倒二进制位

class Solution:
def reverseBits(self, n: int) -> int:
res = 0
for i in range(32):
res <<= 1
res += (n & 1)
n >>= 1

return res

### 10.4 杨辉三角

class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = [[]for _ in range(numRows)]
res[0] = [1]
for i in range(1,numRows):
res[i].append(1)
for j in range(0,len(res[i-1])-1):
res[i].append(res[i-1][j] + res[i-1][j+1])
res[i].append(1)

return res

### 10.5 有效的括号

class Solution:
def isValid(self, s: str) -> bool:
stack = []
for i in range(0,len(s)):
c = s[i]
if c == '(' or c =='[' or c =='{':
stack.append(c)
else:
if len(stack) == 0:
return False
left = stack.pop()
if (c == ')' and left == '(') :
continue
elif (c == ']' and left == '['):
continue
elif (c == '}' and left == '{'):
continue
else:
return False

if len(stack) == 0:
return True
else:
return False

### 10.6 缺失数字

class Solution:
def missingNumber(self, nums: List[int]) -> int:

length = len(nums)
jg = [False for _ in range(length+1)]
for num in nums:
jg[num] = True
return jg.index(False)


class Solution:
def missingNumber(self, nums: List[int]) -> int:

length = len(nums)
sum_n = (length+1)*length//2
sum_nums = sum(nums)
return sum_n - sum_nums

a^b^a = a^a^b = b,  b和a异或两次还等于b。

class Solution:
def missingNumber(self, nums: List[int]) -> int:
length = len(nums)
xor = 0
for i in range(length):
xor  ^= nums[i] ^ (i+1)

return xor

|
1天前
|

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

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

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

12 3
|
1天前
|

Python基于深度学习算法实现图书推荐系统项目实战
Python基于深度学习算法实现图书推荐系统项目实战
18 3
|
1天前
|

Python实现PCA降维和KNN人脸识别模型(PCA和KNeighborsClassifier算法)项目实战
Python实现PCA降维和KNN人脸识别模型(PCA和KNeighborsClassifier算法)项目实战
14 3
|
1天前
|

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

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

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

Python实现GWO智能灰狼优化算法优化支持向量机回归模型(svr算法)项目实战
Python实现GWO智能灰狼优化算法优化支持向量机回归模型(svr算法)项目实战
13 1