字符串的排列

# 给你两个字符串s1和s2 ，写一个函数来判断 s2 是否包含 s1的排列。如果是，返回 true ；否则，返回 false 。
#
# 换句话说，s1 的排列之一是 s2 的 子串 。


class Solution:
 def checkInclusion(self, s1: str, s2: str) -> bool:
     charDicS1 = self.getCharNums(s1)
     window = len(s1)
     for i in range(len(s2)):
         if s2[i] in s1:
             if self.getCharNums(s2[i: window + i]) == charDicS1:
                 return True
     return False

 def getCharNums(self, s):
     dic = {}
     for item in s:
         dic.setdefault(item, 0)
         dic[item] += 1
     return dic

最小平均差

# 给你一个下标从 0开始长度为 n的整数数组nums。
# 下标 i处的 平均差指的是 nums中 前i + 1个元素平均值和 后n - i - 1个元素平均值的 绝对差。两个平均值都需要 向下取整到最近的整数。
# 请你返回产生 最小平均差的下标。如果有多个下标最小平均差相等，请你返回 最小的一个下标。
#
# 注意：
# 两个数的绝对差是两者差的绝对值。
# n个元素的平均值是 n个元素之和除以（整数除法）n。
# 0个元素的平均值视为0。
# 前缀和
class Solution:
 def minimumAverageDifference(self, nums: list[int]) -> int:
     sum_array = [0 for i in range(len(nums))]
     sum_array[0] = nums[0]
     for i in range(1, len(nums)):
         sum_array[i] += sum_array[i - 1] + nums[i]
     mark = 0
     min_ = float('inf')
     for i in range(len(sum_array)):
         x = sum_array[i] // (i + 1)
         y = ((sum_array[-1] - sum_array[i]) // (len(sum_array) - i - 1)) if len(
             sum_array) - i - 1 != 0 else 0
         now = abs(x - y)
         # print(x, y, now)
         if now < min_:
             mark = i
             min_ = now
     return mark
s = Solution()
print(s.minimumAverageDifference([2, 5, 3, 9, 5, 3]))
print(s.minimumAverageDifference([0]))
print(s.minimumAverageDifference([0, 1, 0, 1, 0, 1]))
print(s.minimumAverageDifference([4, 2, 0]))
print(s.minimumAverageDifference([2, 5, 3, 9, 5, 3]))
print(s.minimumAverageDifference([0, 0, 0, 0, 0, 0]))

Excel表列序号

# 给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。

# 26进制转换
class Solution:
 def titleToNumber(self, columnTitle: str) -> int:
     dic_s = {}
     c = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
     for i in range(len(c)):
         dic_s[c[i]] = i + 1
     index = 0
     for i in range(len(columnTitle) - 1, -1, -1):
         index += dic_s[columnTitle[i]] * 26 ** (len(columnTitle) - i - 1)
     return index


s = Solution()
print(s.titleToNumber("A"))
print(s.titleToNumber("AA"))
print(s.titleToNumber("AB"))
print(s.titleToNumber("ZY"))

将一维数组转变成二维数组

# 给你一个下标从 0开始的一维整数数组original和两个整数m和n。你需要使用original中所有元素创建一个m行n列的二维数组。
#
# original中下标从 0到 n - 1（都 包含 ）的元素构成二维数组的第一行，下标从 n到 2 * n - 1（都 包含）的元素构成二维数组的第二行，依此类推。
#
# 请你根据上述过程返回一个m x n的二维数组。如果无法构成这样的二维数组，请你返回一个空的二维数组。

class Solution:
 def construct2DArray(self, original: list[int], m: int, n: int) -> list[list[int]]:
     if m * n != len(original):
         return []
     return [original[i: i + n] for i in range(0, len(original), n)]


s = Solution()
print(s.construct2DArray([1, 2, 3, 4], 2, 2))
print(s.construct2DArray([1, 2, 3], 1, 3))

行相等的最少多米诺旋转

# 在一排多米诺骨牌中，A[i] 和 B[i]分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的—— 该平铺的每一半上都有一个数字。）
# 我们可以旋转第i张多米诺，使得A[i] 和B[i]的值交换。
# 返回能使 A 中所有值或者 B 中所有值都相同的最小旋转次数。
# 如果无法做到，返回-1.

# 统计A和B中1~6值的个数，如果能满足行相等，那么个数至少要大于单个数组长度
# 对于每一个可能满足行相等的数，对A和B同时进行遍历，如果某一位上A和B均不存在该数，那么也不满足
# 对于满足的数，统计在A和B中出现次数，返回次数少的

from collections import Counter


class Solution:
 def minDominoRotations(self, tops: list[int], bottoms: list[int]) -> int:
     length = len(tops)
     top_dic = Counter(tops)
     bottom_dic = Counter(bottoms)
     possible_dic = {k: v for k, v in (top_dic + bottom_dic).items() if v >= length}
     possible_dic = dict(sorted(possible_dic.items(), key=lambda x: x[1], reverse=True))
     # print(possible_dic)
     min_count = float('inf')
     for k, v in possible_dic.items():
         count = 0
         if top_dic[k] > bottom_dic[k]:
             for i in range(length):
                 if tops[i] != k and bottoms[i] == k:
                     count += 1
                 elif tops[i] == k:
                     continue
                 else:
                     break
             else:
                 if count < min_count:
                     min_count = count
         else:
             for i in range(length):
                 if tops[i] == k and bottoms[i] != k:
                     count += 1
                 elif bottoms[i] == k:
                     continue
                 else:
                     break
             else:
                 if count < min_count:
                     min_count = count
     return min_count if min_count != float('inf') else -1


 s = Solution()
A = [2, 1, 2, 4, 2, 2]
B = [5, 2, 6, 2, 3, 2]
print(s.minDominoRotations(A, B))

水壶问题

class Solution:
 def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
     stack = [(0, 0)]
     status = set()
     while stack:
         st = stack.pop()
         if targetCapacity in (st[0], st[1], st[0] + st[1]):
             return True
         if st in status:  # 状态已经出现过
             continue
         status.add(st)
         stack.append((jug1Capacity, st[1]))
         stack.append((st[0], jug2Capacity))
         stack.append((0, st[1]))
         stack.append((st[0], 0))
         stack.append((st[0] - min(jug2Capacity - st[1], st[0]), st[1] + min(jug2Capacity - st[1], st[0])))
         stack.append((st[0] + min(jug1Capacity - st[0], st[1]), st[1] - min(jug1Capacity - st[0], st[1])))
     return False


s = Solution()
print(s.canMeasureWater(2, 6, 5))

阈值距离内邻居最少的城市

# 弗洛伊德算法
class Solution:
 def findTheCity(self, n: int, edges: list[list[int]], distanceThreshold: int) -> int:
     city2city = [[float('inf') for i in range(n)] for j in range(n)]
     for i in range(len(edges)):
         city2city[edges[i][0]][edges[i][8]] = edges[i][9]
         city2city[edges[i][10]][edges[i][0]] = edges[i][11]
     for i in range(n):
         city2city[i][i] = 0
     for k in range(n):
         for i in range(n):
             for j in range(n):
                 city2city[i][j] = min(city2city[i][k] + city2city[k][j], city2city[i][j])
     result = float('inf')
     index = 0
     for i in range(n):
         min_ = 0
         for j in range(n):
             if j == i:
                 continue
             if city2city[i][j] <= distanceThreshold:
                 min_ += 1
         if min_ <= result:
             result = min_
             index = i
     return index


s = Solution()
print(s.findTheCity(4, [[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]], 4))
print(s.findTheCity(5, [[0, 1, 2], [0, 4, 8], [1, 2, 3], [1, 4, 2], [2, 3, 1], [3, 4, 1]], 2))