小李飞刀:做题第十一弹!

写在前面

最近忙着调教新装备,没有及时的写题解,但是没有在偷懒没刷题喔~
来认真整理下最近做的题目~

之前考虑按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

我的思路:
做两次循环,第一次循环用来做映射表,用hash表可以快速查询。
第二遍从头检查,在hash表中仅出现一次的字母,即最早不重复的字母。

第二题

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)]

我的思路:
从头遍历数组,如果对应数组的值不为0,则利用慢指针,将非零项向前移动归并。
最后一个非零项对应的索引到数组的最后则被0包围了~

第三题

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]


我的思路:
python感觉有很多小作弊的方式,比如这题先进行了逆序,然后再进行了位运算。
仅仅用了一行代码也是很奇特了。

第八题

922. 按奇偶排序数组 II
难度:简单
给定一个非负整数数组AA中一半整数是奇数,一半整数是偶数。
对数组进行排序,以便当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

我的思路:
适用两个指针,一个从0开始,一个从1开始,每次的步数为2,对应放入奇数和偶数几颗。

第九题

509. 斐波那契数
难度:简单
斐波那契数,通常用F(n)表示,形成的序列称为斐波那契数列。该数列由01开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0, F(1) = 1
F(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))

我的思路:
因为每一个数的构成,都是由前面的数的基础构成,所以用递归的思路去寻找递归栈。
递归栈的跳出条件为:n=0/1/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])

我的思路:
最大的算法,其实是排序后获取2个一组中最小的那个数,获得的总值最大。

第十一题

867. 转置矩阵
难度:简单
给定一个矩阵A, 返回A的转置矩阵。
矩阵的转置是指将矩阵的主对角线翻转,交换矩阵的行索引与列索引。
我的题解:

class Solution(object):
def transpose(self, A):
"""
:type A: List[List[int]]
:rtype: List[List[int]]
"""
return zip(*A)

我的思路:
zip()函数,打包为元组的列表。
zip(*)返回二维矩阵。—>解压

第十二题

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

我的思路:
最基础的思路是双重循环,外层数组要是遍历一维,内层主要是循环每个二维。
最开始以a[0]作为重复值的参考,如果比对过程中发现了重复的值,就记录下来,并因为考虑到参考值本身可能存在重复值,所以删除对应索引上的值,并根据记录下来的重复值,不断的遍历过程中,就减少,最终获得的就是正确值。

第十三题

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


我的思路:
另外增加一个数组用于记录重复值,因为可能存在同个数组中重复值,所以需要删除对应的索引上的值。

第十四题

349. 两个数组的交集
难度:简单
给定两个数组,编写一个函数来计算它们的交集。

示例:

输入: 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


我的思路:
循环其中一个数组,并新建hash记录重复值。最后遍历hash表,得出最终结果。

第十五题

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

注意:
输入的数组只包含01
输入数组的长度是正整数,且不超过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 - 输入有序数组
难度:简单
给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值index1index2,其中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 ,你要判断是否存在两个整数ab,使得+= 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

我的思路:
两个指针,一个从0开始,一个从开方数开始,不断逼近,判定是否平方和为对应值。

第十九题

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)

我的思路:
使用自定义hash表,并使用双指针,不断逼近,当于到两者都是元音的时候,进行数值交换。

第二十题

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

我的思路:
使用快慢两个指针,一个步数为1,一个步数为2,当存在环的时候,两者一定会相遇。

第二十一题

985. 查询后的偶数和
难度:简单
给出一个整数数组A和一个查询数组queries
对于第i次查询,有val=queries[i][0], index = queriesi,我们会把val加到A[index]上。然后,第i次查询的答案是A中偶数值的和。
(此处给定的 index = queriesi 是从 0 开始的索引,每次查询都会永久修改数组 A。)
返回所有查询的答案。
你的答案应当以数组 answer 给出,answer[i] 为第 i 次查询的答案。
示例:

输入:A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
输出:[8,6,2,4]
解释:
开始时,数组为 [1,2,3,4]。
将 1 加到 A[0] 上之后,数组为 [2,2,3,4],偶数值之和为 2 + 2 + 4 = 8。
将 -3 加到 A1 上之后,数组为 [2,-1,3,4],偶数值之和为 2 + 4 = 6。
将 -4 加到 A[0] 上之后,数组为 [-2,-1,3,4],偶数值之和为 -2 + 4 = 2。
将 2 加到 A3 上之后,数组为 [-2,-1,3,6],偶数值之和为 -2 + 6 = 4。

我的题解:

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

我的思路
每次比对前,比对所加数的奇偶,以及对应的数原有的奇偶。
当奇数+奇数,则总值加上俩奇数之和;当奇数+偶数,则总值不增加;当偶数加偶数,则总数增加新增值;当偶数+奇数,则总值减少原有偶数值。

小小总结

按tag来刷,会对对应思路有更为深刻的理解,小李要继续加油呀!