小李飞刀：做题第十一弹！

写在前面最近忙着调教新装备，没有及时的写题解，但是没有在偷懒没刷题喔来认真整理下最近做的题目之前考虑按tag来刷题，后来收到了推荐的leetcode题解，就根据上面的说明陆续刷题啦tag主要做了：数组、双指针找时间要开始部署gitbook了，然后将题解部署到电子书上认真做题的分割线第一题387. 字符串中的第一个唯一字符难度：简单给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回-1。案例:s = “leetcode"返回 0.s = “loveleetcode”,返回 2.我的题解：class Solution(object): def firstUniqChar(self, s): "”" :type s: str :rtype: int """ mapa = dict() for i in s: if i not in mapa: mapa[i] = 1 else: mapa[i] += 1 for j in range(len(s)): a = s[j] if a in mapa and mapa[a] == 1: return j return -1我的思路：第二题283. 移动零难度：简单给定一个数组 nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。案例:输入: [0,1,0,3,12]输出: [1,3,12,0,0]返回 2.我的题解：class Solution(object): def moveZeroes(self, nums): """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """ l = len(nums) j = 0 for i in range(l): if nums[i] !=0: nums[j] = nums[i] j +=1 nums[j:l] = [0 for i in range(l-j)]我的思路：第三题268. 缺失数字难度：简单给定一个包含0, 1, 2, …, n中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。案例:输入: [3,0,1]输出: 2输入: [9,6,4,2,3,5,7,0,1]输出: 8我的题解：class Solution(object): def missingNumber(self, nums): """ :type nums: List[int] :rtype: int """ sum = 0 l =len(nums) sum_a = (1+l)*l/2 for i in nums: sum += i return sum_a - sum```第四题229. 求众数 II难度：简单给定一个大小为 n 的数组，找出其中所有出现超过⌊ n/3 ⌋次的元素。说明: 要求算法的时间复杂度为O(n)，空间复杂度为O(1)。案例:输入: [3,2,3]输出: [3]输入: [1,1,1,3,3,2,2,2]输出: [1,2]我的题解：class Solution(object): def majorityElement(self, nums): """ :type nums: List[int] :rtype: List[int] """ a = dict() b = list() n = len(nums) / 3 for i in nums: if i not in a: a[i] = 1 else: a[i] += 1 for j in a: if a[j] > n: b.append(j) return b我的思路：第五题101. 对称二叉树难度：简单给定一个二叉树，检查它是否是镜像对称的。例如，二叉树[1,2,2,3,4,4,3]是对称的。但是下面这个[1,2,2,null,3,null,3]则不是镜像对称的:我的题解：# 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 isSymmetric(self, root): """ :type root: TreeNode :rtype: bool """ if not root: return True return self.isSame(root.left,root.right) def isSame(self,leftNode,rightNode): if leftNode == None: return rightNode == None if rightNode == None: return leftNode == None if rightNode.val == leftNode.val: return self.isSame(leftNode.left,rightNode.right) and self.isSame(leftNode.right,rightNode.left) return False我的思路：第六题905. 按奇偶排序数组难度：简单给定一个非负整数数组A，返回一个由A的所有偶数元素组成的数组，后面跟A的所有奇数元素。你可以返回满足此条件的任何数组作为答案。示例：输入：[3,1,2,4]输出：[2,4,3,1]输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。我的题解：class Solution(object): def sortArrayByParity(self, A): """ :type A: List[int] :rtype: List[int] """ n = [0]len(A) k = 0 j = len(A) - 1 for i in range(len(A)): if A[i] % 2 ==1: #奇数 n[j] = A[i] j -= 1 else: n[k] = A[i] k += 1 return n我的思路：第七题832. 翻转图像难度：简单给定一个二进制矩阵A，我们想先水平翻转图像，然后反转图像并返回结果。水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转[1, 1, 0]的结果是[0, 1, 1]。反转图片的意思是图片中的0全部被1替换，1全部被0替换。例如，反转[0, 1, 1]的结果是[1, 0, 0]。我的题解：class Solution(object): def flipAndInvertImage(self, A): """ :type A: List[List[int]] :rtype: List[List[int]] """ #逆序 return [[j ^ 1 for j in i[::-1]] for i in A]我的思路：第八题922. 按奇偶排序数组 II难度：简单给定一个非负整数数组A，A中一半整数是奇数，一半整数是偶数。对数组进行排序，以便当A[i]为奇数时，i也是奇数；当A[i]为偶数时，i也是偶数。你可以返回任何满足上述条件的数组作为答案。我的题解：class Solution(object): def sortArrayByParityII(self, A): """ :type A: List[int] :rtype: List[int] """ count0 = 0 count1 = 1 re = [] for i in A: if i%2 == 0: re.insert(count0, i) count0 += 2 else: re.insert(count1, i) count1 += 2 return re我的思路：第九题509. 斐波那契数难度：简单斐波那契数，通常用F(n)表示，形成的序列称为斐波那契数列。该数列由0和1开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.给定N，计算F(N)。我的题解：class Solution(object): def fib(self, N): """ :type N: int :rtype: int """ if N == 0:return 0 if N==1 or N == 2:return 1 return (self.fib(N-1)+self.fib(N-2))我的思路：第十题561. 数组拆分 I难度：简单给定长度为2n的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。输入: [1,4,3,2]输出: 4解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).提示:n 是正整数,范围在 [1, 10000].数组中的元素范围在 [-10000, 10000].我的题解：class Solution(object): def arrayPairSum(self, nums): """ :type nums: List[int] :rtype: int """ nums.sort() return sum(nums[::2])我的思路：第十一题867. 转置矩阵难度：简单给定一个矩阵A， 返回A的转置矩阵。矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。我的题解：class Solution(object): def transpose(self, A): """ :type A: List[List[int]] :rtype: List[List[int]] """ return zip(A)我的思路：第十二题1002. 查找常用字符难度：简单给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现3次，但不是4次，则需要在最终答案中包含该字符3次。你可以按任意顺序返回答案。示例 1：输入：[“bella”,“label”,“roller”]输出：[“e”,“l”,“l”]我的题解：class Solution(object): def commonChars(self, A): """ :type A: List[str] :rtype: List[str] """ tmp = list(A[0]) for i in range(1,len(A)): tmp_list =list() for j in A[i]: if j in tmp: index = tmp.index(j) del tmp[index] tmp_list.append(j) tmp = tmp_list return tmp我的思路：第十三题350. 两个数组的交集 II难度：简单给定两个数组，编写一个函数来计算它们的交集。示例 1:输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2,2]输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出: [4,9]说明：输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。我们可以不考虑输出结果的顺序。我的题解：class Solution(object): def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ l = list() for i in nums2: if i in nums1: index = nums1.index(i) del nums1[index] l.append(i) return l我的思路：第十四题1002. 查找常用字符难度：简单给定两个数组，编写一个函数来计算它们的交集。示例:输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2]输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出: [9,4]说明:输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。我的题解：class Solution(object): def intersection(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ l = dict() a = list() for i in nums2: if i in nums1: if i not in l: l[i] = 1 for key in l: a.append(key) return a我的思路：第十五题566. 重塑矩阵难度：简单在MATLAB中，有一个非常有用的函数reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。示例：输入: nums = [[1,2], [3,4]]r = 1, c = 4输出: [[1,2,3,4]]解释:行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。我的题解：class Solution(object): def matrixReshape(self, nums, r, c): """ :type nums: List[List[int]] :type r: int :type c: int :rtype: List[List[int]] """ l_a = len(nums) l_b = len(nums[0]) if l_al_b != rc: return nums if l_a == r: return nums list_a = list() list_b = list() count = 0 for i in range(l_a): for j in range(l_b): list_b.append(nums[i][j]) count += 1 if count == c: list_a.append(list_b) list_b = list() count = 0 return list_a我的思路：第十六题485. 最大连续1的个数难度：简单给定一个二进制数组， 计算其中最大连续1的个数。示例 1:输入: [1,1,0,1,1,1]输出: 3解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是3注意：输入的数组只包含0和1。输入数组的长度是正整数，且不超过10,000。我的题解：class Solution(object): def findMaxConsecutiveOnes(self, nums): """ :type nums: List[int] :rtype: int """ max_l = 0 count = 0 for i in nums: if i == 1 : count +=1 else: ###遇到0 if count > max_l: max_l = count count = 0 if count > max_l: max_l = count return max_l我的思路：第十七题167. 两数之和 II - 输入有序数组难度：简单给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值index1 和index2，其中index1必须小于index2。说明:返回的下标值（index1 和 index2）不是从零开始的。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。我的题解：class Solution(object): def twoSum(self, numbers, target): """ :type numbers: List[int] :type target: int :rtype: List[int] """ l = len(numbers) i = 0 j = l - 1 l_a = list() while i < j: if numbers[i]+numbers[j] == target: l_a.append(i+1) l_a.append(j+1) return l_a elif numbers[i]+numbers[j] > target: j -= 1 else: i +=1 return null我的思路：第十八题633. 平方数之和难度：简单给定一个非负整数 c ，你要判断是否存在两个整数a和b，使得a²+b²= c。示例:输入: 5输出: True解释: 1 1 + 2 2 = 5我的题解：import mathclass Solution(object): def judgeSquareSum(self, c): """ :type c: int :rtype: bool """ a = int(math.sqrt(c)) b = 0 while a > b: if a2 + b2 == c: return True elif a2 + b2 > c: a -= 1 else: b += 1 if a2 + b2 == c: return True else: return False 我的思路：第十九题345. 反转字符串中的元音字母难度：简单编写一个函数，以字符串作为输入，反转该字符串中的元音字母。示例:输入: “hello"输出: “holle"我的题解：class Solution(object): def reverseVowels(self, s): "”” :type s: str :rtype: str """ y = [‘a’,’e’,‘i’,‘o’,‘u’,‘A’,‘E’,‘I’,‘O’,‘U’] p = 0 q = len(s) - 1 s = list(s) while p<=q: if s[q] not in y and s[p] not in y: p += 1 q -= 1 elif s[p] in y and s[q] not in y: q -= 1 elif s[q] in y and s[p] not in y: p += 1 else: flag = s[q] s[q] = s[p] s[p] = flag p += 1 q -= 1 return ‘’.join(s)我的思路：第二十题141. 环形链表难度：简单给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果pos是-1，则在该链表中没有环。我的题解：# Definition for singly-linked list.# class ListNode(object):# def init(self, x):# self.val = x# self.next = Noneclass Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ if not head: return False l1 = head l2 = head.next while l1 and l2 and l2.next: if l1 == l2: return True l1 = l1.next l2 = l2.next.next return False我的思路：第二十一题985. 查询后的偶数和难度：简单给出一个整数数组A和一个查询数组queries。对于第i次查询，有val=queriesi, index = queriesi，我们会把val加到A[index]上。然后，第i次查询的答案是A中偶数值的和。（此处给定的 index = queriesi 是从 0 开始的索引，每次查询都会永久修改数组 A。）返回所有查询的答案。你的答案应当以数组 answer 给出，answer[i] 为第 i 次查询的答案。我的题解：class Solution(object): def sumEvenAfterQueries(self, A, queries): """ :type A: List[int] :type queries: List[List[int]] :rtype: List[int] """ l =list() sum = 0 sum_a = 0 for j in A: if j%2 ==0: sum_a += j for i in range(len(queries)): A[queries[i][1]] += queries[i][0]#增加数值 if A[queries[i][1]] % 2 ==0:#是偶数 if queries[i][0]%2 ==0:#是偶数 sum = sum_a + queries[i][0] else:#是奇数 sum = sum_a + A[queries[i][1]] else:#是奇数 if queries[i][0]%2 ==0:#是偶数 sum = sum_a else: sum = sum_a - A[queries[i][1]] + queries[i][0] l.append(sum) sum_a =sum return l我的思路小小总结