力扣刷题——并查集 547有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected ，其中 isConnectedi = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnectedi = 0 表示二者不直接相连。返回矩阵中 省份 的数量。示例 1：输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]输出：2示例 2：输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]输出：3from typing import List class Solution: def findCircleNum(self, isConnected: List[List[int]]) -> int: def dfs(i: int): for j in range(cities): if isConnected[i][j] == 1 and j not in visited: visited.add(j) dfs(j) cities = len(isConnected) visited = set() provinces = 0 for i in range(cities): if i not in visited: dfs(i) provinces += 1 return provinces solution = Solution() print(solution.findCircleNum([[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]])) #input findCircleNum list

力扣刷题——单调栈 503给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。示例 1:输入: nums = [1,2,1]输出: [2,-1,2]解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。示例 2:输入: nums = [1,2,3,4,3]输出: [2,3,4,-1,4]from typing import List class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: n = len(nums) ret = [-1] * n stk = [] for i in range(n * 2 - 1): while stk and nums[stk[-1]] < nums[i % n]: ret[stk.pop()] = nums[i % n] stk.append(i % n) return ret solution = Solution() print(solution.nextGreaterElements([1,2,3,4,3])) #input nextGreaterElements list 739给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。示例 1:输入: temperatures = [73,74,75,71,69,72,76,73]输出: [1,1,4,2,1,1,0,0]示例 2:输入: temperatures = [30,40,50,60]输出: [1,1,1,0]示例 3:输入: temperatures = [30,60,90]输出: [1,1,0]from typing import List class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: res = [0] * len(temperatures) s = [] # print res for i in range(0, len(temperatures)): print(s) while s and temperatures[i] > temperatures[s[-1]]: print(res) res[s[-1]] = i - s[-1] s.pop() s.append(i) return res solution = Solution() print(solution.dailyTemperatures([73,74,75,71,69,72,76,73])) #input temperatures list

力扣刷题——分治思想 169给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。示例 1：输入：nums = [3,2,3]输出：3示例 2：输入：nums = [2,2,1,1,1,2,2]输出：2提示：n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。from typing import List class Solution: def majorityElement(self, nums: List[int]) -> int: n = len(nums) check_n = n/2 dic = {} new_nums = list(set(nums)) for i in nums: if i in dic.keys(): old_var = dic.get(i) dic[i]=int(old_var)+1 else: dic[i]=1 keys_list = list(dic.keys()) values_list = list(dic.values()) for i in range(len(keys_list)): if values_list[i] > check_n: return keys_list[i] solution = Solution() print(solution.majorityElement([3,2,3])) #input list240编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例 1：输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5输出：true示例 2：输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20输出：falsefrom typing import List class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: for row in matrix: for element in row: if element == target: return True return False solution = Solution() print(solution.searchMatrix(matrix,target)) #input list and target

力扣刷题——递归思想 70假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？示例 1：输入：n = 2输出：2解释：有两种方法可以爬到楼顶。1 阶 + 1 阶2 阶示例 2：输入：n = 3输出：3解释：有三种方法可以爬到楼顶。1 阶 + 1 阶 + 1 阶1 阶 + 2 阶2 阶 + 1 阶class Solution: def climbStairs(self, n: int) -> int: stair = {1: 1, 2: 2} for i in range(3, n + 1): stair[i] = stair[i - 1] + stair[i - 2] return stair[n] solution=Solution() print(solution.climbStairs(4)) #input number509斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0，F(1) = 1F(n) = F(n - 1) + F(n - 2)，其中 n > 1给定 n ，请计算 F(n) 。示例 1：输入：n = 2输出：1解释：F(2) = F(1) + F(0) = 1 + 0 = 1示例 2：输入：n = 3输出：2解释：F(3) = F(2) + F(1) = 1 + 1 = 2示例 3：输入：n = 4输出：3解释：F(4) = F(3) + F(2) = 2 + 1 = 3class Solution: def fib(self, n: int) -> int: if n == 0: return 0 elif n == 1: return 1 else: return self.fib(n - 1) + self.fib(n - 2) solution=Solution() print(solution.fib(1)) #input number