小李飞刀：做题第七弹！

写在前面的话做做做题，慢慢上手了就觉得刷题速度变快了，果然还是有点笨希望最后一窍快点通吧开始做题第一题169. 求众数难度：简单给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。我的题解：class Solution(object): def majorityElement(self, nums): """ :type nums: List[int] :rtype: int """ value = nums[0] count = 0 for i in nums: if value == i: count = count + 1 else: if count == 0: value = i count = 1 continue count =count - 1 return value 我的思路：这题参考了评论的题解，做了两次，明白了来龙去脉。中心思想就是：按顺序遍历数字，存在不同的数字就抵消相应的count，存在相同数字则增加，最后总能获取到唯一一个不会被抵消全部的数字，就是众数了。第二题136. 只出现一次的数字难度：简单给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？我的题解：class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ a = 0 for num in nums: a = a ^ num return a我的思路：异或，两个相同的数字的计算结果为0，最后剩余的则为唯一值第三题83. 删除排序链表中的重复元素难度：简单给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。我的题解：# Definition for singly-linked list.# class ListNode(object):# def init(self, x):# self.val = x# self.next = Noneclass Solution(object): def deleteDuplicates(self, head): """ :type head: ListNode :rtype: ListNode """ a = head if not a: return a while head.next: if head.next.val == head.val and head.next.next == None: head.next = None elif head.next.val == head.val and head.next.next: head.next = head.next.next else: head = head.next return a我的思路：当存在前后节点一致的时候，则前一个节点的next指向后一个节点的next，跳过即可。其他：因为链表的结构指向的是内存，遍历完之后指向最后的节点，所以需要一个a指向头结点。第四题100. 相同的树难度：简单给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。我的题解：# Definition for a binary tree node.# class TreeNode(object):# def init(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def isSameTree(self, p, q): """ :type p: TreeNode :type q: TreeNode :rtype: bool """ if not p and not q: return True if p and q: if p.val == q.val: return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right) else: return False else: return False我的思路：递归，主要是判断两个节点的值是否一致，一致的前提下，判断向下的左右节点及更向下是否一致。第五题88. 合并两个有序数组难度：简单给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明:初始化 nums1 和 nums2 的元素数量分别为 m 和 n。你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。我的题解：class Solution(object): def merge(self, nums1, m, nums2, n): """ :type nums1: List[int] :type m: int :type nums2: List[int] :type n: int :rtype: None Do not return anything, modify nums1 in-place instead. """ while m>0 and n>0: if nums1[m-1] >=nums2[n-1]: nums1[m+n-1] = nums1[m-1] m -= 1 else: nums1[m+n-1] = nums2[n-1] n -= 1 if n >0 : nums1[:n] = nums2[:n]class Solution(object): def merge(self, nums1, m, nums2, n): """ :type nums1: List[int] :type m: int :type nums2: List[int] :type n: int :rtype: None Do not return anything, modify nums1 in-place instead. """ while m>0 and n>0: if nums1[m-1] >=nums2[n-1]: nums1[m+n-1] = nums1[m-1] m -= 1 else: nums1[m+n-1] = nums2[n-1] n -= 1 if n >0 : nums1[:n] = nums2[:n]我的思路：因为nums1[m+n]为空的部分，所以我们可以从后向前写，判断两个数组的值，更大的数字不断向后挪，挪到一定程度的时候，剩余部分则为更长的数组的剩余未判断部分。第六题104. 二叉树的最大深度难度：简单给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。我的题解：# Definition for a binary tree node.# class TreeNode(object):# def init(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 if root.right is None and root.left is None: return 1 return max(self.maxDepth(root.right),self.maxDepth(root.left))+1 我的思路：递归图上为调用栈的情况，不断向下寻找更远的根节点。基线判断为：节点是否为空递归判断为：节点不为空且左节点或右节点还有值总结最近在看《算法图解》，感觉对递归理解更深一点，但学习之后重要的是实践，还是要多做题。