# -*- coding: utf-8 -*-
# 086: 面试题 01.07. 旋转矩阵
# 给你一幅由 N × N矩阵表示的图像，其中每个像素的大小为4字节。请你设计一种算法，将图像旋转90度。
# 示例 1:
# 给定 matrix =
# [
# [1,2,3],
# [4,5,6],
# [7,8,9]
# ],
#
# 原地旋转输入矩阵，使其变为:
# [
# [7,4,1],
# [8,5,2],
# [9,6,3]
# ]
class Solution086:
def rotate(self, matrix: list[list[int]]) -> None:
all = [j for i in matrix for j in i]
lend = len(matrix[0])
a = []
for i in range(lend):
init_a = all[i::lend][::-1]
a.append(init_a)
matrix[:] = a
s086 = Solution086()
matrix = [
[5, 1, 9, 11],
[2, 4, 8, 10],
[13, 3, 6, 7],
[15, 14, 12, 16]
]
s086.rotate(matrix)
print(matrix) # [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]
# 087: 实现 strStr()
# 实现 strStr() 函数。给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个
# 位置（下标从 0 开始）。如果不存在，则返回-1 。
# 示例 1：
# 输入：haystack = "hello", needle = "ll"
# 输出：2
#
# 示例 2：
# 输入：haystack = "aaaaa", needle = "bba"
# 输出：-1
#
# 示例 3：
# 输入：haystack = "", needle = ""
# 输出：0
class Solution087:
def strStr(self, haystack: str, needle: str) -> int:
return haystack.find(needle) if needle in haystack else -1
s087 = Solution087()
r087 = s087.strStr("hello", "he")
print(r087) # 0
# 088: 翻转字符串里的单词
# 给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
# 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
# 请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
# 示例 1：
# 输入：s = "the sky is blue"
# 输出："blue is sky the"
#
# 示例 2：
# 输入：s = " hello world "
# 输出："world hello"
# 解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
class Solution088:
def reverseWords(self, s: str) -> str:
words = s.split(" ")
words = [i for i in words[::-1] if i]
return " ".join(words)
s088 = Solution088()
r088 = s088.reverseWords("hello world")
print(r088) # world hello
# 089: 最大连续 1 的个数
# 给定一个二进制数组， 计算其中最大连续 1 的个数。
# 示例：
# 输入：[1,1,0,1,1,1]
# 输出：3
# 解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
class Solution089:
def findMaxConsecutiveOnes(self, nums: list[int]) -> int:
s = "".join([str(i) for i in nums])
words = s.split("0")
words.sort()
return len(words[-1])
s089 = Solution089()
r089 = s089.findMaxConsecutiveOnes([1, 0, 1, 1, 0, 1, 1, 1, 0])
print(r089) # 3
# 090: 各位相加
# 给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
# 示例:
# 输入: 38
# 输出: 2
# 解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
class Solution090:
def addDigits(self, num: int) -> int:
while True:
num = sum([int(i) for i in str(num)])
if num < 10:
break
return num
s090 = Solution090()
r090 = s090.addDigits(88)
print(r090) # 7： 8+8 > 16 > 1+6 > 7
# 091: 多数元素
# 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
# 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
# 示例 1：
# 输入：[3,2,3]
# 输出：3
#
# 示例 2：
# 输入：[2,2,1,1,1,2,2]
# 输出：2
class Solution091:
def majorityElement(self, nums: list[int]) -> int:
nums.sort()
return nums[len(nums) // 2]
s091 = Solution091()
r091 = s091.majorityElement([1, 2, 2, 3, 3, 2, 1])
print(r091) # 2
# 092: 十-二进制数的最少数目
# 如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1 ，那么该数字就是一个 十-二进制数 。
# 例如，101 和 1100 都是 十-二进制数，而 112 和 3001 不是。
# 给你一个表示十进制整数的字符串 n ，返回和为 n 的 十-二进制数 的最少数目。
# 示例 1：
# 输入：n = "32"
# 输出：3
# 解释：10 + 11 + 11 = 32
#
# 示例 2：
# 输入：n = "82734"
# 输出：8
#
# 示例 3：
# 输入：n = "27346209830709182346"
# 输出：9
class Solution092:
def minPartitions(self, n: str) -> int:
# 本质是求各位位上出现的最大数值。
return int(max(n))
s092 = Solution092()
r092 = s092.minPartitions("3141592653")
print(r092) # 9
# 093: 反转字符串中的单词 III
# 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
# 示例：
# 输入："Let's take LeetCode contest"
# 输出："s'teL ekat edoCteeL tsetnoc"
class Solution093:
def reverseWords(self, s: str) -> str:
words = s.split(" ")
words = [i[::-1] for i in words]
return " ".join(words)
s093 = Solution093()
r093 = s093.reverseWords("s'tI a .tac")
print(r093) # It's a cat.
# 094: 合并两个有序数组
# 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
# 示例 1：
# 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
# 输出：[1,2,2,3,5,6]
# 解释：需要合并 [1,2,3] 和 [2,5,6] 。
# 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
#
# 示例 2：
# 输入：nums1 = [1], m = 1, nums2 = [], n = 0
# 输出：[1]
# 解释：需要合并 [1] 和 [] 。
# 合并结果是 [1] 。
#
# 示例 3：
# 输入：nums1 = [0], m = 0, nums2 = [1], n = 1
# 输出：[1]
# 解释：需要合并的数组是 [] 和 [1] 。
# 合并结果是 [1] 。
# 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
class Solution094:
def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
nums1[:] = nums1[:m] + nums2[:n]
nums1.sort()
s094 = Solution094()
nums094 = [1, 1, 2, 3, 4, 5, 5, 6]
s094.merge(nums1=nums094, m=3, nums2=[2, 3, 3, 4, 5], n=3)
print(nums094) # [1, 1, 2, 2, 3, 3]
# 095: 2 的幂
# 给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
# 如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
# 示例 1：
# 输入：n = 1
# 输出：true
# 解释：20 = 1
#
# 示例 2：
# 输入：n = 16
# 输出：true
# 解释：24 = 16
#
# 示例 3：
# 输入：n = 3
# 输出：false
class Solution095:
def isPowerOfTwo(self, n: int) -> bool:
if n == 0:
return False
if n in (1, 2):
return True
while True:
n = n / 2
if n == 2:
r = True
break
if n != int(n):
r = False
break
return r
s095 = Solution095()
r095 = s095.isPowerOfTwo(36)
print(r095) # False
# 096: 数组中的第K个最大元素
# 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
# 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
# 示例 1:
# 输入: [3,2,1,5,6,4] 和 k = 2
# 输出: 5
#
# 示例 2:
# 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
# 输出: 4
class Solution096:
def findKthLargest(self, nums: list[int], k: int) -> int:
nums.sort()
return nums[-k]
s096 = Solution096()
r096 = s096.findKthLargest([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9], 3)
print(r096) # 8
# 097: 整数反转
# 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
# 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
# 假设环境不允许存储 64 位整数（有符号或无符号）。
# 示例 1：
# 输入：x = 123
# 输出：321
#
# 示例 2：
# 输入：x = -123
# 输出：-321
#
# 示例 3：
# 输入：x = 120
# 输出：21
#
# 示例 4：
# 输入：x = 0
# 输出：0
class Solution097:
def reverse(self, x: int) -> int:
if abs(x) < 10:
return x
list1 = [i for i in str(x)]
s = "+"
if list1[0] == "-":
s = list1[0]
list1[:] = list1[1:]
while True:
if list1[-1] == "0":
list1[:] = list1[:-1]
else:
break
r = int(s + "".join(list1[::-1]))
if abs(r) > (2 ** 31 - 1):
return 0
return int(s + "".join(list1[::-1]))
s097 = Solution097()
r097 = s097.reverse(-314159)
print(r097) # -951413
# 098: 阶乘后的零
# 给定一个整数 n ，返回 n! 结果中尾随零的数量。
# 提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
# 示例 1：
# 输入：n = 3
# 输出：0
# 解释：3! = 6 ，不含尾随 0
#
# 示例 2：
# 输入：n = 5
# 输出：1
# 解释：5! = 120 ，有一个尾随 0
#
# 示例 3：
# 输入：n = 0
# 输出：0
class Solution098:
def trailingZeroes(self, n: int) -> int:
if n in (0, 1):
return 0
s = 1
while True:
s *= n
n -= 1
if n == 1:
break
return len(str(s)) - len(str(int(str(s)[::-1])))
s098 = Solution098()
r098 = s098.trailingZeroes(68)
print(r098) # 15
# 099: 寻找重复数
# 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
# 假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
# 示例 1：
# 输入：nums = [1,3,4,2,2]
# 输出：2
# 示例 2：
# 输入：nums = [3,1,3,4,2]
# 输出：3
#
# 示例 3：
# 输入：nums = [1,1]
# 输出：1
#
# 示例 4：
# 输入：nums = [1,1,2]
# 输出：1
class Solution099:
def findDuplicate(self, nums: list[int]) -> int:
set1 = set()
# 不在集合内则加入集合
for num in nums:
if num not in set1:
set1.add(num)
else:
return num
s099 = Solution099()
r099 = s099.findDuplicate([3, 1, 4, 1, 5, 9, 2, 6, 5])
print(r099) # 1
# 100: 字典序排数
# 给你一个整数
# n ，按字典序返回范围[1, n]
# 内所有整数。
# 你必须设计一个时间复杂度为
# O(n)
# 且使用
# O(1)
# 额外空间的算法。
# 示例
# 1：
# 输入：n = 13
# 输出：[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
#
# 示例
# 2：
# 输入：n = 2
# 输出：[1, 2]
class Solution100:
def lexicalOrder(self, n: int) -> list[int]:
return [int(i) for i in sorted({str(i): 1 for i in range(1, n + 1)}.keys())]
s100 = Solution100()
r100 = s100.lexicalOrder(22)
print(r100) # [1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 3, 4, 5, 6, 7, 8, 9]
微信公众号：玩转测试开发
欢迎关注，共同进步，谢谢！
