搜索到
114
篇与
的结果
-
【简单】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) 的算法解决此问题。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/majority-element著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法摩尔投票法投票法是遇到相同的则 票数 + 1，遇到不同的则 票数 - 1。且“多数元素”的个数 > ⌊ n/2 ⌋，其余元素的个数总和 <= ⌊ n/2 ⌋。因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 >= 1。这就相当于每个 “多数元素” 和其他元素 两两相互抵消，抵消到最后肯定还剩余 至少1个 “多数元素”。无论数组是 1 2 1 2 1，亦或是 1 2 2 1 1，总能得到正确的候选人。作者：gfu链接：https://leetcode.cn/problems/majority-element/solution/3chong-fang-fa-by-gfu-2/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。class Solution: def majorityElement(self, nums: List[int]) -> int: num, count = nums[0], 0 for i in nums: if count == 0: num = i if i == num: count += 1 else: count -= 1 return num -
【中等】142. 环形链表 II 题目给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/linked-list-cycle-ii著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法双指针法在第上一题的基础上改一下。class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: fast, slow = head, head while True: if not (fast and fast.next): return slow, fast = slow.next, fast.next.next if fast == slow: break fast = head while fast != slow: fast, slow = fast.next, slow.next return fast
-
【简单】141. 环形链表 题目给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。 示例 1：输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：提示：链表中节点的数目范围是 [0, 104]-10000 <= Node.val <= 10000pos 为 -1 或者链表中的一个 有效索引 。 进阶：你能用 O(1)（即，常量）内存解决此问题吗？来源：力扣（LeetCode）链接：https://leetcode.cn/problems/linked-list-cycle著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法这个题目我看的很懵，一个pos不知道干啥的，给个list也没重复，然后看了下讨论，才知道替换法根据进阶，要O(1)空间，所以不能新建一个dict去存出现过的。然后根据数据提示，不可能出现字符，或小于10000，所以直接替换方法来自leetcode大神class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: while head: if head.val == 'F': return True head.val = 'F' head = head.next return False双指针法class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: # 如果没有头，直接返回false就行了 if not head: return False # 定义快慢两个指针 fast, slow = head, head # 快慢遍历，fast取下一个，slow取下下一个 while fast and fast.next and slow and slow.next and slow.next.next: # 赋值 fast = fast.next slow = slow.next.next # 如果相等了，就可以说明是环了 if fast == slow: return True return False
-
【简单】【每日一题】2315. 统计星号 给你一个字符串 s ，每 两个 连续竖线 '|' 为 一对 。换言之，第一个和第二个 '|' 为一对，第三个和第四个 '|' 为一对，以此类推。请你返回 不在 竖线对之间，s 中 '*' 的数目。注意，每个竖线 '|' 都会 恰好 属于一个对。示例 1：输入：s = "l|*e*et|c**o|*de|" 输出：2 解释：不在竖线对之间的字符加粗加斜体后，得到字符串："l|*e*et|c**o|*de|" 。 第一和第二条竖线 '|' 之间的字符不计入答案。 同时，第三条和第四条竖线 '|' 之间的字符也不计入答案。 不在竖线对之间总共有 2 个星号，所以我们返回 2 。示例 2：输入：s = "iamprogrammer" 输出：0 解释：在这个例子中，s 中没有星号。所以返回 0 。示例 3：输入：s = "yo|uar|e**|b|e***au|tifu|l" 输出：5 解释：需要考虑的字符加粗加斜体后："yo|uar|e**|b|e***au|tifu|l" 。不在竖线对之间总共有 5 个星号。所以我们返回 5 。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/count-asterisks著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。class Solution: def countAsterisks(self, s: str) -> int: flag = True count = 0 for c in s: if c == '|': flag = not flag elif flag and c == '*': count += 1 return count
-
83. 删除排序链表中的重复元素 遍历+递归 题目给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。示例 1：输入：head = [1,1,2] 输出：[1,2] 示例 2：输入：head = [1,1,2,3,3] 输出：[1,2,3]提示：链表中节点数目在范围 [0, 300] 内-100 <= Node.val <= 100题目数据保证链表已经按升序 排列来源：力扣（LeetCode）链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法遍历class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head: return head result = head while result is not None and result.next is not None: if result.val == result.next.val: result.next = result.next.next else: result = result.next return head递归class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: if head is None or head.next is None: return head head.next = self.deleteDuplicates(head.next) return head.next if head.val == head.next.val else head
-
21. 合并两个有序链表 双指针法+递归法 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1：输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]示例 2：输入：l1 = [], l2 = [] 输出：[]示例 3：输入：l1 = [], l2 = [0] 输出：[0]解法双指针法感觉有点暴力，没意思。class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: if list1 is None: return list2 if list2 is None: return list1 a = ListNode(0) result = a while list1 is not None or list2 is not None: if list1 is None and list2: result.next = list2 list2 = list2.next elif list2 is None and list1: result.next = list1 list1 = list1.next elif list1.val < list2.val: result.next = list1 list1 = list1.next else: result.next = list2 list2 = list2.next result = result.next return a.next递归法class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: if list1 is None: return list2 elif list2 is None: return list1 if list1.val < list2.val: list1.next = self.mergeTwoLists(list1.next, list2) return list1 list2.next = self.mergeTwoLists(list1,list2.next) return list2
-
448. 找到所有数组中消失的数字 set求差法+下标排除法 题目给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。示例 1：输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6] 示例 2： 输入：nums = [1,1] 输出：[2]提示：n == nums.length 1 <= n <= 105 1 <= nums[i] <= n进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法本来用暴力破解，直接推导式生成一个从1到nums长度+1的list，如果在nums则不添加，但是吧，超时了。class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: return [i for i in range(1, max(nums) + 1) if i not in nums]本来是想用求差的，但是list没这个方法，但是set有，所以换成set试一下。class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: return list(set(range(1, len(nums) + 1)).difference(set(nums)))虽然过了，但是这个方法并不符合进阶。秒呀法这个空间虽然小了，但是时间就长了。文字描述一下就是，既然给的list里面是1-n的数字，但是少了几个。如果把这些数字-1，那么就是一个下标，可以把这个下标的值取反，或者加至不存在于nums中的值，当遍历一过次后，那些不存在于nums中的值的下标的值不会被改变。在最后返回的时候排除掉被改变的值就行了。取反class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: for i in nums: t = abs(i) - 1 if nums[t] > 0: nums[t] = -nums[t] return [index + 1 for index, value in enumerate(nums) if value > 0]加上nclass Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: n = len(nums) for i in nums: nums[(i - 1) % n] += n return [index + 1 for index, value in enumerate(nums) if value <= n]
