python：基础入门练习076 - 085

# -*- coding: utf-8 -*-
# 076: Fizz Buzz
# 写一个程序，输出从 1 到 n 数字的字符串表示。
# 1. 如果 n 是3的倍数，输出“Fizz”；
# 2. 如果 n 是5的倍数，输出“Buzz”；
# 3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
# 示例：
# n = 15,
# 返回:
# [
#     "1",
#     "2",
#     "Fizz",
#     "4",
#     "Buzz",
#     "Fizz",
#     "7",
#     "8",
#     "Fizz",
#     "Buzz",
#     "11",
#     "Fizz",
#     "13",
#     "14",
#     "FizzBuzz"
# ]


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


s076 = Solution076()
r076 = s076.fizzBuzz(8)
print(r076)  # ['1', '2', 'Fizz', '4', 'Buzz', 'Fizz', '7', '8']


# 077: 3的幂
# 给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。
# 整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x
# 示例 1：
# 输入：n = 27
# 输出：true
#
# 示例 2：
# 输入：n = 0
# 输出：false


class Solution077:
    def isPowerOfThree(self, n: int) -> bool:
        if n in [0, 2]:
            return False
        elif n in [1, 3]:
            return True

        while True:
            n1, n2 = divmod(n, 3)

            if n2 != 0:
                result = False
                break
            else:
                n = n1
        if n == 1:
            result = True

        return result


s077 = Solution077()
r077 = s077.isPowerOfThree(8)
print(r077)  # False


# 078: 反转字符串
# 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
# 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
# 示例 1：
# 输入：s = ["h","e","l","l","o"]
# 输出：["o","l","l","e","h"]
#
# 示例 2：
# 输入：s = ["H","a","n","n","a","h"]
# 输出：["h","a","n","n","a","H"]


class Solution078:
    def reverseString(self, s: list[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:] = s[::-1]

        # 或者
        # s.reverse()


s078 = Solution078()
word078 = ["h", "e", "l", "l", "o"]
s078.reverseString(word078)
print(word078)  # ['o', 'l', 'l', 'e', 'h']


# 079: 字符串中的第一个唯一字符
# 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
# 示例：
# s = "leetcode"
# 返回 0
# s = "loveleetcode"
# 返回 2


class Solution079:
    def firstUniqChar(self, s: str) -> int:
        num = 0
        for i, v in enumerate(s):
            if s.count(v) == 1:
                num = i
                break
            else:
                num = -1

        return num


s079 = Solution079()

r079 = s079.firstUniqChar("runner")
print(r079)  # 1


# 080: 实现 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 Solution080:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle) if needle in haystack else -1


s080 = Solution080()

r080 = s080.strStr("runner", "er")
print(r080)  # 4


# 081: 有效的字母异位词
# 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
# 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
# 示例 1:
# 输入: s = "anagram", t = "nagaram"
# 输出: true
#
# 示例 2:
# 输入: s = "rat", t = "car"
# 输出: false


class Solution081:
    def isAnagram(self, s: str, t: str) -> bool:
        dict_s = {}
        dict_t = {}

        for i in s:
            dict_s[i] = s.count(i)
        for i in t:
            dict_t[i] = t.count(i)

        a1 = dict_s == dict_t
        a2 = len(s) == len(t)
        return True if a1 and a2 else False


s081 = Solution081()

r081 = s081.isAnagram("anagram", "nagaram")
print(r081)  # True


# 082: 打乱数组
# 给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。
# 实现 Solution class:
# Solution(int[] nums) 使用整数数组 nums 初始化对象
# int[] reset() 重设数组到它的初始状态并返回
# int[] shuffle() 返回数组随机打乱后的结果
# 示例：
# 输入
# ["Solution", "shuffle", "reset", "shuffle"]
# [[[1, 2, 3]], [], [], []]
# 输出
# [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
# 解释
# Solution solution = new Solution([1, 2, 3]);
# solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
# solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
# solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]


class Solution082:
    def __init__(self, nums: list[int]):
        self.nums2 = nums[:]
        self.nums = nums

    def reset(self) -> list[int]:
        """
        Resets the array to its original configuration and return it.
        """
        return self.nums2

    def shuffle(self) -> list[int]:
        """
        Returns a random shuffling of the array.
        """
        import random
        random.shuffle(self.nums)
        return self.nums


nums082 = [1, 2, 3]
obj082 = Solution082(nums082)
param_1 = obj082.reset()
param_2 = obj082.shuffle()
print(param_1)  # [1, 2, 3]
print(param_2)  # [3, 2, 1]


# 083: 丢失的数字
# 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
# 示例 1：
# 输入：nums = [3,0,1]
# 输出：2
# 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
#
# 示例 2：
# 输入：nums = [0,1]
# 输出：2
# 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
#
# 示例 3：
# 输入：nums = [9,6,4,2,3,5,7,0,1]
# 输出：8
# 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
#
# 示例 4：
# 输入：nums = [0]
# 输出：1
# 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。


class Solution083:
    def missingNumber(self, nums: list[int]) -> int:
        return sum(range(len(nums) + 1)) - sum(nums)


s083 = Solution083()
r083 = s083.missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1])
print(r083)  # 8


# 084: 最小栈
# 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
# push(x) —— 将元素 x 推入栈中。
# pop() —— 删除栈顶的元素。
# top() —— 获取栈顶元素。
# getMin() —— 检索栈中的最小元素。
# 示例:
# 输入：
# ["MinStack","push","push","push","getMin","pop","top","getMin"]
# [[],[-2],[0],[-3],[],[],[],[]]
#
# 输出：
# [null,null,null,null,-3,null,0,-2]
#
# 解释：
# MinStack minStack = new MinStack();
# minStack.push(-2);
# minStack.push(0);
# minStack.push(-3);
# minStack.getMin();   --> 返回 -3.
# minStack.pop();
# minStack.top();      --> 返回 0.
# minStack.getMin();   --> 返回 -2.


class MinStack084:

    def __init__(self):
        self.my_list = []

    def push(self, val: int) -> None:
        self.my_list.append(val)

    def pop(self) -> None:
        self.my_list.pop()

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

    def getMin(self) -> int:
        return min(self.my_list)


m084 = MinStack084()
m084.push(-2)
m084.push(0)
m084.push(-3)
r001 = m084.getMin()  # -3
m084.pop()
r002 = m084.top()  # 0
r003 = m084.getMin()  # -2

print(r001)  # -3
print(r002)  # 0
print(r003)  # -2


# 085: 旋转图像
# 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
# 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
# 示例 1：
# 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
# 输出：[[7,4,1],[8,5,2],[9,6,3]]
#
# 示例 2：
# 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
# 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
#
# 示例 3：
# 输入：matrix = [[1]]
# 输出：[[1]]
#
# 示例 4：
# 输入：matrix = [[1,2],[3,4]]
# 输出：[[3,1],[4,2]]


class Solution085:
    def rotate(self, matrix: list[list[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        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


s085 = Solution085()
matrix085 = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]
s085.rotate(matrix085)
print(matrix085)  # [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]