贪心算法
关于贪心算法的详细讲解：贪心算法
我们直接上力扣的题：
题的链接：力扣练习题库，可以直接选择标签找到贪心
这里我做了一些，后续还会补充刷题完善这个文档：
up主讲的题在下面，可以自己在目录中查找呢
简单：
1、统计是给定字符串中字符串前缀的数目：
问题分析：从words中每一个字符串中找出是s的字符串前缀的并进行计数，然后返回
words = input().split()
s = input()
count = 0
for word in words:
for i in range(1,len(s)+1):
if word == s[:i]:
count+=1
print(count)
class Solution:
def countPrefixes(self, words: list[str], s: str) -> int:
return (sum(s.startswith(w) for w in words))
# 将words中的每一个单词拿出来，startswith方法字符串方法是判断字符串是否以操作数为开头的，如果是返回True，不是返回False
# sum求可迭代对象的元素之和，True当做1，false当做0，sum求和就将所有的是其前缀的个数统计和了
# words就是一个可迭代对象
sum(布尔表达式 for 元素 in 可迭代对象)
求从可迭代对象中筛选符合条件的元素的数量就可以这样做
布尔表达式实际上是指返回值为0或者1的表达式
2、最长回文串
问题分析：回文串就是从前往后读和从后往前读是一样的字符串
- 首先统计一下每个字符出现的次数，由于是一一对应的关系，所以采用字典来维护数据
- 其次应该定义一个length记录回文串长度的初始解
- 判断字符串中每种字符出现的次数（也就是字典中的值），如果是偶数，那么全部都可以用上作为回文串的字母，因为偶数个是对称的
- 如果是奇数个，则只需它的偶数个字符来用作回文串，所以就是奇数个-1，其实如果有字符时奇数个的话，使用一个奇数个字符也是可以的把这个字符单独放在中间，那么就可以在用初始记录的length+1
（这里我们可以定义一个变量初始值为false单独来记录只要有字符是奇数个他就是true，最终如果是true，那么length+1）
- 最终返回length
s = input()
length = 0
for i in set(s):
if s.count(i) %2 == 0:
length += s.count(i)
else:
if s.count(i) >= 2:
length += 2
length += 1
print(length)
这里还有其他人写出来的一个很牛的答案，只需要一行代码：
class Solution:
def longestPalindrome(self, s: str) -> int:
return len(s) -max(0,sum([s.count(i)%2 for i in set(s)])-1)
基于上述思路，可以这样解释这段代码：
将字符串转换成集合，也就是每个字符都存放在集合中，使用count方法计算每一个字符出现的次数，%2是判断奇数偶数的，一个数取模2，偶数结果为0，奇数结果为1，实际上这就是我上面讲的从可迭代对象中筛选出符合条件元素的个数，将这些值放在列表中（列表推导式），sum求可迭代对象的元素的和，也就是把1都加在一块了代表字符串s中的字符时奇数个出现的有几个，再-1，实际上这里使用的是逆向思维也就是在字符串长度中去掉奇数个出现的字母（n个）中的（n-1）个
abbbdddcccc 其中a，b，d都是奇数出现的，只需要去掉这三个字母其中两个就可以了
abbdddccccc 同理这个字符串也是
这里的max是保证去掉的字母个数不是负数，因为如果没有奇数个字母出现的话，那么[ 0 ]列表中就是0，max(0,-1)也就是取0，所有的字母都没被划掉，所有的字母共同构成最长回文串
分发饼干：
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
count = 0 # 记录初始解
i = 0
j = 0 # 双指针，题中已经给了列表中的下标，这也算是提示吧
# 排序
s.sort()
g.sort()
# 循环条件（下标索引的范围，保证列表不超出索引）
while i<len(g) and j<len(s):
if s[j] >= g[i]: # 判断饼干尺寸是否大于孩子胃口
count += 1 # 优先满足胃口小的孩子
i += 1 # 下一个孩子
j += 1 # 无论是否满足孩子，饼干尺寸都要下一个
return count
解释一下思路，也算是贪心算法的一个基本思路：
首先记录初始解，可以是变量，也可能是列表（这里边要记录双指针初始值，题中都给提示了）
排序
循环（初始值，条件，变化），这里保证了下标索引不超出列表范围
判断条件：决策条件，永远选择当前看似最优解（饼干问题永远先满足胃口小的孩子，这里永远优先满足训练次数最少的士兵，这样可以达到费用最少）
对初始解和循环变量进行调整，返回初始解
中等：
1、k-avoiding数组最小总和
思路展示：
1、首先记录初始解，先让列表中存放从0到n的数值（从0开始存放是为了索引值方便，而且你最终使用sum求和的时候，0不会影响求和）
2、使用双指针遍历列表中的值，i在外层，j在内层，每一个i都遍历i后面所有的数
- 例如list1 = [0,1,2,3,4,5]，i取1，j就取2,3,4,5
- i取2，j就取3，4,5
- …
3、将这i和j加在一块如果等与k值就将元素添加到list2
4、将list1中剔除list2中的元素后形成list3（下面我给出了通用做法）
5、然后当list3的长度如果小于n+1的话，就在后面填上元素n+i，i从1开始
6、最终返回元素
class Solution:
def minimumSum(self, n: int, k: int) -> int:
list1 = [element for element in range(n+1)]
list2=[]
for i in range(1,n+1):
for j in range(i+1,n):
if i+j==k:
list2.append(j)
list3 = [element for element in list1 if element not in list2]
i = 1
while len(list3) < n+1:
list3.append(n+i)
i+=1
return sum(list3)
在一个列表中剔除与另一个列表相同的元素
# 如何才能将一个列表中的元素去掉另一个列表中共同拥有的元素
# 使用列表推导式
list1 = [1,2,3,4]
list2 = [2,3]
list3 = [element for element in list1 if element not in list2]
print(list3)
# 使用集合进行处理
# 集合是一种无序且元素唯一的数据结构，使用集合的差集操作能够快速去掉共同元素。示例如下：
list4 = list(set(list1)-set(list2))
print(list4)
# 不过要注意这种方法可能会改变原列表中元素的顺序，并且会去除列表中重复的元素，如果要保留元素顺序和重复元素就使用前一种方法
2、盛最多水的问题
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0 #双指针的左指针
right = len(height)-1 # 右指针
max_area = 0 # 初始面积
while left < right :# 左边小于右边，因为保证最终两边夹着的得有面积
current_height = min(height[left],height[right])
current_wide = right - left
current_area = current_wide * current_height
max_area = max(max_area,current_area)
if left<right:
left+=1
else:
right-=1
return max_area
解题思路：双指针问题
- 定义一个初始解，最大面积为0
- 左右指针分别指向首尾
- 循环：（条件（如果有双指针的话一般是双指针比较），变化，初始值）这里是如果左下标小于右下标，就进行操作，因为左下标本来就得小于右下标才有做的必要
- 记录当前高，宽，面积，总是要最大面积，也就是拿最大面积和当前面积作比较谁大就取谁（初始解的变化）
- 判断：（循环条件的更新），left和right指针得走动，哪一方小就移动哪一方，优先移动短板，面积尽可量的能够获得最大
3、破解闯关密码：
class Solution:
def crackPassword(self, password: List[int]) -> str:
list1= []
password.sort(key = lambda x : x%10)
i = 0
j = 1
for i in range(len(password)):
for j in range(i+1,len(password)):
if password[i]+password[j]>password[j]+password[i]:
password[i] = temp
password[i] = password[j]
password[j] = temp
list1 = [str(i) for i in password]
return "".join(list1)
这道题最关键的地方就是要想到a+b>b+a的时候,要将a，b换位置（这里是字符串加法哈）
- 定义一个初始解，list1里存放要连接的字符串
- 将传进来列表进行排序（我是按照每一个数的个位数进行排序的），不知道各位是否发现如果按照各位排序连接后基本上和正确解的顺序差不多
- 循环：设置初始值i，j 代表下标，下面又要遍历列表而且要是层级关系遍历，i取一个下标，j就要遍历它之后的所有下标的值
- 判断：如果索引为i的值和索引为j的值加起来满足前一个数加后一个数>后一个数加前一个数，那么这两个数就需要换位置
- 循环条件的值更新了判断条件的值也跟着更新了
- 最终将列表中的值都转换为字符串类型返回字符串（join方法会将可迭代对象中的字符串元素按照.join之前的东西进行连接起来形成一个新的字符串）
训练士兵题目
做法：
# 训练士兵的题
import sys
# up主之前给的标准输入流函数，可以将一行数据读入并且进行前后整合也就是去除输入数据前后的空格
input = lambda : sys.stdin.readline().strip()
# 使用标准输入流函数读取第一行数据，将输入的字符串按照空格进行分割，
# 使用map函数转换成整数，此时返回两个数是一个迭代器类型的数据
# 迭代器数据类型就是不将数据存储进内存中，只是记住数据的位置，需要的时候访问使用就可以了
# n代表士兵的数量，s代表士兵团购一次所需要的钱数
n,s = map(int,input().split())
# 首先我们先按照题中的提示，创建一些能存储数据的矩阵（数组）
# nums来存储每一个士兵的训练次数和单次训练的钱数都单独组成一个小列表，几个士兵就组成了一个n*2的矩阵，这里的2我暂时初始化0
nums = [[0,0]]*n # 定义一个初始化矩阵存放数据
# p来存放单次训练的钱数，是1*n的矩阵,题中也给提示了，说p[i]表示每个士兵的单次训练的钱数，说明p是一个数组中存放单次训练钱数
p = [0]*n
# c[i]代表每个士兵需要训练的次数也是1*n的矩阵
c= [0]*n
# ---------------------------------到此为止我们将数据存放矩阵创建完成了
# 接下来我们要进行数据的处理：将nums，p，c矩阵中放入应该放入的值
for i in range(n):
nums[i] = list(map(int,input().split()))
for i in range(n):
p[i] = nums[i][0]
c[i] = nums[i][1]
# 这里我打印出来看一下矩阵中的值都是什么样子的才方便做
print(nums)
print(p)
print(c)
# ---------------------------------到此为止初始化完成
# 接下来进行排序，因为永远都要先满足训练次数少的士兵进行团购，团购肯定是次数少的士兵比较合适，而且训练完之后他就走了
nums.sort(key = lambda x: x[1])
print(nums)
# ---------------------------------到此为止排序完成
# 开始算法核心部分
# 定义初始解
res = 0 #记录最终使用的钱
cnt = 0 # 记录已经团购的次数
tot = np.sum(p)# 记录所有人单次训练一次所需要的价钱，要拿这个价钱和团购一次进行比较，因为团购一次相当于把所有人单独训练了一次
# 遍历每一个士兵
for i in range(n):
if tot >= s: # 每个人单次训练一次的总价小于一次团购价就是团购合适
res += (c[i] - cnt) * s # 因为之前已经排序过了，先从训练最少次数的士兵开始，
# 所以直接就是这个人的次数减去已经团购过得次数乘团购价加到总价上，这个人一定是选择团购的
cnt = c[i] #次数直接更新为当前这个人的次数了，因为这个人的c[0][i]已经进行团购了
else:# 进行个人训练
res += (c[i] - cnt) * p[i] #也应该减去当前团购过的数量
tot -= p[i] #一个士兵完事了就该减去他的单次训练的价格
print(res)
另一种我使用了numpy模块创建矩阵来做的：
# 训练士兵的题
import sys
# up主之前给的标准输入流函数，可以将一行数据读入并且进行前后整合也就是去除输入数据前后的空格
input = lambda : sys.stdin.readline().strip()
# 使用标准输入流函数读取第一行数据，将输入的字符串按照空格进行分割，
# 使用map函数转换成整数，此时返回两个数是一个迭代器类型的数据
# 迭代器数据类型就是不将数据存储进内存中，只是记住数据的位置，需要的时候访问使用就可以了
# n代表士兵的数量，s代表士兵团购一次所需要的钱数
n,s = map(int,input().split())
# 首先我们先按照题中的提示，创建一些能存储数据的矩阵（数组）
# nums来存储每一个士兵的训练次数和单次训练的钱数都单独组成一个小列表，几个士兵就组成了一个n*2的矩阵，这里的2我暂时初始化0
nums = np.zeros((n,2),np.int16) # 定义一个初始化矩阵存放数据
# p来存放单次训练的钱数，是1*n的矩阵,题中也给提示了，说p[i]表示每个士兵的单次训练的钱数，说明p是一个数组中存放单次训练钱数
p = np.zeros((1,n),np.int16)
# c[i]代表每个士兵需要训练的次数也是1*n的矩阵
c= np.zeros((1,n),np.int16)
# ---------------------------------到此为止我们将数据存放矩阵创建完成了
# 接下来我们要进行数据的处理：将nums，p，c矩阵中放入应该放入的值
for i in range(n):
nums[i][0],nums[i][1] = map(int,input().split())
for i in range(n):
p[0][i] = nums[i][0]
c[0][i] = nums[i][1]
# 这里我打印出来看一下矩阵中的值都是什么样子的才方便做
print(nums)
print(p)
print(c)
# ---------------------------------到此为止初始化完成
# 接下来进行排序，因为永远都要先满足训练次数少的士兵进行团购，团购肯定是次数少的士兵比较合适，而且训练完之后他就走了
for i in range(n):
nums.sort(axis = 0)
print(nums)
# ---------------------------------到此为止排序完成
# 开始算法核心部分
# 定义初始解
res = 0 #记录最终使用的钱
cnt = 0 # 记录已经团购的次数
tot = np.sum(p)# 记录所有人单次训练一次所需要的价钱，要拿这个价钱和团购一次进行比较，因为团购一次相当于把所有人单独训练了一次
# 遍历每一个士兵
for i in range(n):
if tot >= s: # 每个人单次训练一次的总价小于一次团购价就是团购合适
res += (c[0][i] - cnt) * s # 因为之前已经排序过了，先从训练最少次数的士兵开始，
# 所以直接就是这个人的次数减去已经团购过得次数乘团购价加到总价上，这个人一定是选择团购的
cnt = c[0][i] #次数直接更新为当前这个人的次数了，因为这个人的c[0][i]已经进行团购了
else:# 进行个人训练
res += (c[0][i] - cnt) * p[0][i] #也应该减去当前团购过的数量
tot -= p[0][i] #一个士兵完事了就该减去他的单次训练的价格
print(res)
排序问题
1、消失的数字
2、有效的字母异位词
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
list1 = list(s)
list2 = list(t)
list3 = [i for i in list1 if i not in list2]
if list3:
return False
else:
if list1 == list2:
return False
else:
return True
代码实现逻辑：
- 首先将字符串强转为列表
- 将其中两个列表中不同的元素拿出来，如果有元素，就返回false
- 没有的话再来一个判断如果列表相同也是false
- 如果不想同就是顺序不同；可以返回