Python解力扣算法题（六）（详解+注释）

# 1.学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。
# 排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。
# 给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。
# 返回满足 heights[i] != expected[i] 的 下标数量 。

1. heightChecker函数
   • 解释：
     • 这个函数的目的是计算当前学生站位高度数组heights与按照非递减顺序排序后的高度数组中元素不相等的下标数量。
     • 首先，需要创建heights的副本pre_heights，因为直接使用pre_heights = heights只是创建了引用，对heights排序时pre_heights也会改变。这里使用切片pre_heights = heights[:]创建了副本。
     • 然后对heights进行排序，再通过遍历比较heights和pre_heights中相同下标的元素，如果不相等则将计数变量count加1。最后返回count。

def heightChecker(heights):# 创建heights的副本，这里使用切片操作pre_heights = heights[:]# 对heights进行排序heights.sort()count = 0for i in range(len(heights)):# 如果排序后的heights和原始的pre_heights在相同下标处元素不相等if heights[i]!= pre_heights[i]:count += 1return countprint(heightChecker([1, 1, 4, 2, 1, 3]))

# 2.复写0，列表长度不变

1. duplicateZeros函数
   • 解释：
     • 这个函数的目的是对输入的数组arr进行复写0的操作，即如果数组中的元素为0，则在该元素后面插入一个0，同时要保证数组长度不变。
     • 使用一个变量i来遍历数组arr，同时记录数组的长度length。在遍历过程中，如果i等于length，说明已经遍历到了原数组的末尾（因为插入操作可能会使数组变长），此时将数组截断为i个元素。如果当前元素为0，则在i + 1的位置插入一个0，并且将i加1（因为插入了一个元素），最后i加1继续下一轮遍历。最后返回处理后的数组arr。

def duplicateZeros(arr):i = 0length = len(arr)while i < len(arr):# 如果i等于数组长度，说明已经到了原数组末尾（考虑插入后的情况）if i == length:arr = arr[:i]break# 如果当前元素为0，则在i+1位置插入一个0if arr[i] == 0:arr.insert(i + 1, 0)i += 1i += 1return arrprint(duplicateZeros([1, 0, 2, 3, 0, 4, 5, 0]))

# 3.求第N个泰波那契数   Tn+3=Tn+Tn+1+Tn+2

1. tribonacci函数
   • 解释：
     • 这个函数用于计算第n个泰波那契数。泰波那契数的定义是Tn+3=Tn+Tn+1+Tn+2，初始值为[0, 1, 1]。
     • 首先创建一个包含初始值的数组arr = [0, 1, 1]，然后通过循环n - 2次，每次将前三个数的和添加到数组中，最后返回数组中第n个元素。

def tribonacci(n):arr = [0, 1, 1]# 循环计算泰波那契数，从第3个开始for i in range(0, n - 2):arr.append(arr[i]+arr[i + 1]+arr[i + 2])return arr[n]print(tribonacci(25))

# 4.给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。
# 输入为三个整数：day、month 和 year，分别表示日、月、年。
# 您返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。# 为了解决这个问题，我们可以使用蔡勒公式（Zeller's Congruence），这是一个用于计算格里高利历（公历）中任意日期是星期几的有效算法。
# 其中：# h是星期几（0 = Saturday, 1 = Sunday, 2 = Monday, ..., 6 = Friday）# q是月份中的日（1to31）# m是月（3 = March, 4 = April, ..., 12 = December；1 = March, 2 = April, ..., 10 = December, 11 = January, 12 = February）# K是年份中的最后两位数# J是年份中的前两位数
# 由于蔡勒公式中的月份是从3月开始的，所以如果输入的月份是1月或2月，需要将月份加上12，并将年份减1。
# 注意：蔡勒公式适用于1583年（格里高利历改革的那一年）以后的日期。对于更早的日期，需要使用其他公式或历史日历规则。

1. dayOfTheWeek函数
   • 解释：
     • 这个函数使用蔡勒公式（Zeller's Congruence）来计算给定日期（day、month、year）是星期几。
     • 由于蔡勒公式中的月份是从3月开始的，如果输入的月份是1月或2月，需要将月份加上12，并将年份减1。然后根据蔡勒公式计算出h（星期几的索引，0 = Saturday, 1 = Sunday, 2 = Monday,..., 6 = Friday），最后根据索引从星期的字符串数组days中返回对应的星期字符

def dayOfTheWeek(day, month, year):# 如果月份小于3，按照蔡勒公式的要求进行调整if month < 3:month += 12year -= 1q = daym = monthK = year % 100J = year // 100# 蔡勒公式计算星期几的索引hh = (q+(13*(m + 1))//5+K+K//4+J//4 - 2*J)%7days = ["Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"]return days[h]print(dayOfTheWeek(day = 31, month = 8, year = 2019))

# 5.给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 "balloon"（气球）。
# 字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 "balloon"。

1. maxNumberOfBalloons函数
   • 解释：
     • 这个函数用于计算给定字符串text中可以拼凑出单词“balloon”的最大数量。
     • 通过字典{'b': 1, 'a': 1, 'l': 2, 'o': 2, 'n': 1}定义了组成“balloon”每个字母的需求数量，然后使用字典推导式和min函数，计算每个字母在text中出现的次数除以需求数量的最小值，这个最小值就是可以拼凑出的最大单词数量。

def maxNumberOfBalloons(text):# 计算每个字母在text中的数量与组成balloon所需数量的比例的最小值return min(text.count(key)//val for key, val in {'b': 1, 'a': 1, 'l': 2, 'o': 2, 'n': 1}.items())print(maxNumberOfBalloons("loonbalxballpoon"))

# 6.给你个整数数组 arr，其中每个元素都 不相同。
# 请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
# 每对元素对 [a,b] 如下：
# a , b 均为数组 arr 中的元素
# a < b
# b - a 等于 arr 中任意两个元素的最小绝对差

1. minimumAbsDifference函数
   • 解释：
     • 这个函数的目的是在给定的整数数组arr中找到所有具有最小绝对差的元素对，并按升序返回。
     • 首先对数组arr进行排序，然后初始化最小差值min_diff为数组中最大元素与最小元素的差值。接着遍历数组，计算相邻元素的差值diff，如果diff小于min_diff，则更新min_diff并重新初始化pairs为包含当前元素对的列表；如果diff等于min_diff，则将当前元素对添加到pairs中。最后返回pairs。

def minimumAbsDifference(arr):arr.sort()# 先排序min_diff = arr[len(arr)-1]-arrpairs = []# 计算最小差值并找到对应的元素对for i in range(len(arr)-1):diff = arr[i + 1]-arr[i]if diff < min_diff:min_diff = diffpairs = [[arr[i], arr[i + 1]]]elif diff == min_diff:pairs.append([arr[i], arr[i + 1]])return pairsprint(minimumAbsDifference([4, 2, 1, 3]))

# 7.给你一个整数数组 arr，如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

1. uniqueOccurrences函数
   • 解释：
     • 这个函数用于判断整数数组arr中每个数的出现次数是否都是独一无二的。
     • 首先创建一个集合arr1，它包含数组arr中的所有不同元素。然后创建一个空列表list1，遍历arr1中的每个元素，计算其在arr中的出现次数并添加到list1中。对list1进行排序后，再遍历list1，如果有相邻元素相等，则返回False，否则返回True。

def uniqueOccurrences(arr):arr1 = set(arr)list1 = []for i in arr1:list1.append(arr.count(i))list1.sort()for i in range(len(list1)-1):if list1[i] == list1[i + 1]:return Falsereturn Trueprint(uniqueOccurrences([1, 2]))

# 8. n 个筹码。第 i 个筹码的位置是 position[i] 。
# 我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个筹码的位置从 position[i] 改变为:
# position[i] + 2 或 position[i] - 2 ，此时 cost = 0
# position[i] + 1 或 position[i] - 1 ，此时 cost = 1
# 返回将所有筹码移动到同一位置上所需要的 最小代价 。
# 因为我们的目标是最后将全部的「筹码」移动到同一个位置，那么最后的位置只有两种情况：
# 移动到某一个偶数位置，此时的开销最小值就是初始奇数位置「筹码」的数量。
# 移动到某一个奇数位置，此时的开销最小值就是初始偶数位置「筹码」的数量。
# 那么这两种情况中的最小值就是最后将所有筹码移动到同一位置上所需要的最小代价。

1. minCostToMoveChips函数
   • 解释：
     • 这个函数的目的是计算将所有筹码移动到同一位置上所需要的最小代价。
     • 由于移动到某一个偶数位置的开销最小值就是初始奇数位置筹码的数量，移动到某一个奇数位置的开销最小值就是初始偶数位置筹码的数量，所以使用Counter统计数组position中元素模2后的余数的个数，最后返回余数为0和余数为1的个数中的最小值。

from collections import Counterdef minCostToMoveChips(position):cnt = Counter(p % 2 for p in position)return min(cnt, cnt[1])print(minCostToMoveChips([1, 2, 2, 2, 2, 3, 3]))

# 9.平衡字符串 中，'L' 和 'R' 字符的数量是相同的。
# 给你一个平衡字符串 s，请你将它分割成尽可能多的子字符串，并满足：
# 每个子字符串都是平衡字符串。
# 返回可以通过分割得到的平衡字符串的 最大数量 。

1. balancedStringSplit函数
   • 解释：
     • 这个函数用于将平衡字符串s（其中'L'和'R'字符的数量是相同的）分割成尽可能多的子字符串，且每个子字符串都是平衡字符串，返回可以得到的平衡字符串的最大数量。
     • 使用变量count来记录'R'和'L'字符数量的差值，ans用于记录平衡字符串的数量。遍历字符串s，如果遇到'R'则count加1，如果遇到'L'则count减1，当count等于0时，说明找到了一个平衡字符串，ans加1。最后返回ans。

def balancedStringSplit(s):count = 0ans = 0for i in s:if i == "R":count += 1elif i == "L":count -= 1if count == 0:ans += 1return ansprint(balancedStringSplit("RLRRLLRLRL"))

# 10.数字的每一位相乘的积减去数字每一位相加的和的结果

1. subtractProductAndSum函数

• 解释：
  • 这个函数用于计算数字n的每一位相乘的积减去数字每一位相加的和的结果。
  • 首先将数字n转换为字符串，然后初始化两个变量sum1为1（用于乘积）和sum2为0（用于求和），遍历字符串中的每个字符，将其转换为整数后分别进行乘积和求和操作，最后返回sum1 - sum2。

def subtractProductAndSum(n):n = str(n)sum1 = 1sum2 = 0for i in range(len(n)):sum1 *= int(n[i])sum2 += int(n[i])return sum1 - sum2print(subtractProductAndSum(234))

# 11.给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
# 请你找到并返回这个整数

1. findSpecialInteger函数

• 解释：
  • 这个函数用于在非递减的有序整数数组arr中找到出现次数超过数组元素总数的25%的那个整数。
  • 首先创建一个集合arr1，它包含数组arr中的所有不同元素。然后遍历arr1中的每个元素，计算其在arr中的出现次数与数组长度的比例，如果大于0.25，则返回该元素。

def findSpecialInteger(arr):arr1 = set(arr)for i in arr1:if arr.count(i)/len(arr)>0.25:return iprint(findSpecialInteger([1, 2, 2, 6, 6, 6, 6, 7, 10]))

# 12.给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。

1. findNumbers函数

• 解释：
  • 这个函数用于返回整数数组nums中位数为偶数的数字的个数。
  • 遍历数组nums中的每个元素，将其转换为字符串，如果字符串的长度为偶数，则将计数变量double加1，最后返回double。

def findNumbers(nums):double = 0for i in nums:i = str(i)if len(i)%2 == 0:double += 1return doubleprint(findNumbers([555, 901, 482, 1771]))

# 13.给你一个以行程长度编码压缩的整数列表 nums 。
# 考虑每对相邻的两个元素 [freq, val] = [nums[2*i], nums[2*i+1]] （其中 i >= 0 ），
# 每一对都表示解压后子列表中有 freq 个值为 val 的元素，你需要从左到右连接所有子列表以生成解压后的列表。

• 解释：
  • 这个函数的目的是对以行程长度编码压缩的整数列表nums进行解压。行程长度编码的规则是每对相邻的两个元素[freq, val] = [nums[2*i], nums[2*i + 1]]（其中i >= 0）表示解压后子列表中有freq个值为val的元素，需要从左到右连接所有子列表以生成解压后的列表。
  • 通过遍历nums列表，当索引i为奇数时（因为行程长度编码是成对的，偶数位置是频率，奇数位置是值），根据前面偶数位置（i - 1）表示的频率，将当前奇数位置的值重复添加到结果列表list1中。最后返回list1。

def decompressRLElist(nums):list1 = []for i in range(len(nums)):if i % 2 == 1:# 根据前面偶数位置的频率，将当前奇数位置的值重复添加到结果列表for j in range(nums[i - 1]):list1.append(nums[i])return list1print(decompressRLElist([1, 2, 3, 4]))

# 14.给你一个仅由数字 6 和 9 组成的正整数 num。
# 你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。
# 请返回你可以得到的最大数字。

1. maximum69Number函数

• 解释：
  • 这个函数用于在仅由数字6和9组成的正整数num中，最多翻转一位数字（将6变成9，或者把9变成6）以得到最大数字。
  • 首先将数字num转换为字符串，再转换为列表，这样就可以修改其中的字符。然后从左到右遍历这个列表，如果遇到数字6，将其变为9后直接返回转换回整数后的结果（因为要得到最大数字，所以遇到6就变9后返回即可）。如果没有遇到6，说明数字本身就是最大的情况，直接将列表转换回整数并返回。

def maximum69Number (num):num = str(num)num = list(num)for i in range(len(num)):if num[i] == "6":num[i] = "9"return int(''.join(num))return int(''.join(num))print(maximum69Number(9996))

# 15.给你一个字符串 s，它仅由字母 'a' 和 'b' 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。
# 返回删除给定字符串中所有字符（字符串为空）的最小删除次数。
# 「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。
# 「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。

1. removePalindromeSub函数

• 解释：
  • 这个函数用于计算删除仅由字母'a'和'b'组成的字符串s中所有字符（使字符串为空）的最小删除次数。
  • 因为字符串只由'a'和'b'组成，并且每次可以删除一个回文子序列。如果字符串本身就是回文串，那么只需要删除一次就可以使字符串为空；如果字符串不是回文串，那么最多需要两次，一次删除所有的'a'（这是一个回文子序列），一次删除所有的'b'（这也是一个回文子序列）。通过判断字符串是否等于其逆序字符串来确定是否为回文串，然后返回相应的结果。

def removePalindromeSub(s):return 1 if s == s[::-1] else 2print(removePalindromeSub("aaabbb"))