问题描述
问题描述： 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。解题方法：（1）中心扩散法（注意偶数扩散和奇数扩散）方法在奇数下不能使用单个中心点得到偶数下的回文子串，因此，需要将偶数和奇数进行分别处理，高阶奇偶变化可以由低阶奇偶有限次扩展得到。时间复杂度:O(N^2)空间复杂度：O(1)（2）中心扩散法（消除奇偶，单层循环处理）枚举所有可能的中心点，有2*n - 1个中心点（共有n 个奇数中心点和n - 1个偶数中心点）时间复杂度:O(N^2)空间复杂度：O(1)代码（解题思路）
图解中心位置
class Solution: def countSubstrings1(self, s: str) -> int: def speard(l, r): """中心扩散""" count = 0 while l >= 0 and r <= len(s) - 1 and s[l] == s[r]: l -= 1 r += 1 count += 1 return count res = 0 # 奇数中心扩散 for i in range(len(s)): res += speard(i, i) # 偶数中心扩散 for i in range(len(s) - 1): res += speard(i, i + 1) return res def countSubstrings2(self, s: str) -> int: """暴力法""" n = len(s) ans = 0 for i in range(2*n - 1): l, r = i//2, i//2 + i%2 while l >= 0 and r < n and s[l] == s[r]: l -= 1 r += 1 ans += 1 return ans问题描述
问题描述： 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人。请你重新构造并返回输入数组people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j个人的属性（queue[0] 是排在队列前面的人）。代码
class Solution: def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]: res = [] # h_i: decrease # k_i: increase # 身高降序排列，排名升序排列 people = sorted(people, key=lambda x: (-x[0], x[1])) # 保证范围内的排序不出边界，并维护位置上的相对性 for p in people: if p[1] >= len(res): res.append(p) elif p[1] < len(res): res.insert(p[1], p) return res def reconstructQueue2(self, people): people = sorted(people, key=lambda x: (-x[0], x[1])) i = 0 while i < len(people): if i > people[i][1]: # insert->delete people.insert(people[i][1], people[i]) people.pop(i + 1) i += 1题目类型：原地哈希 ⭐️
问题描述
问题描述： 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。进阶：你能在不使用额 外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。解题方法：(1)暴力法时间复杂度：O(N)空间复杂度：O(N)(2)原地置换（索引与值对齐原则）时间复杂度：O(N)空间复杂度：O(1)代码
图解
class Solution: def finddisappearednumbers1(self, nums: List[int]) -> List[int]: """暴力法""" res = [] for val in range(1, len(nums) + 1): if val not in nums: res.append(val) return res def finddisappearednumbers2(self, nums): """原地置换""" n = len(nums) for num in nums: # index x = (num - 1) % n nums[x] += n print(nums) ret = [i + 1 for i, num in enumerate(nums) if num <= n] return ret问题描述
问题描述： 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。示例：输入:nums = [1,1,1], k = 2输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。解题方法：(1)暴力法时间复杂度：O(N^2)空间复杂度：O(1)(2)前缀表达式pre_A + k = pre_B时间复杂度：O(N)空间复杂度：O(N)代码（解题思路）
class Solution: def subarraySum1(self, nums, k): """暴力法""" count = 0 for start in range(len(nums)): sum = 0 for end in range(start, -1, -1): sum += nums[end] if sum == k: count += 1 return count def subarraySum2(self, nums, k): """前缀和表达""" # 统计当前前缀和 nums_times = defaultdict(int) nums_times[0] = 1 cur_sums = 0 count = 0 for i in range(len(nums)): cur_sums += nums[i] if cur_sums - k in nums_times: count += nums_times[cur_sums - k] nums_times[cur_sums] += 1 return count题目类型：DFS ⭐️
问题描述
问题描述： 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。实例：给定二叉树 1 / \ 2 3 / \ 4 5返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]解题方法：深度优先遍历时间复杂度：O(N)空间复杂度：O(height)代码（解题思路）
图解
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def diameterOfBinaryTree(self, root: TreeNode) -> int: # 标识路径 self.ans = 1 def dfs(root): if root is None: return 0 left = dfs(root.left) right = dfs(root.right) # 当前节点，左右结点的最长路径长度 self.ans = max(self.ans, left + right + 1) return max(left, right) + 1 dfs(root) return self.ans - 1以上是内存溢出为你收集整理的Python剑指offer打卡-21全部内容，希望文章能够帮你解决Python剑指offer打卡-21所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）