写在前面
最近忙着调教新装备，没有及时的写题解，但是没有在偷懒没刷题喔~来认真整理下最近做的题目~
之前考虑按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 = None
class 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_a*l_b != r*c:
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 math
class Solution(object):
def judgeSquareSum(self, c):
“””
:type c: int
:rtype: bool
“””
a = int(math.sqrt(c))
b = 0
while a > b:
if a**2 + b**2 == c:
return True
elif a**2 + b**2 > c:
a -= 1
else:
b += 1
if a**2 + b**2 == 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 = None
class 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
我的思路
小小总结
发表回复