0%

刷题记录

1.除自身以外的数组乘积

给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

1
2
输入: [1,2,3,4]
输出: [24,12,8,6]

说明:不能使用除法,在O(n)时间复杂度内解决此问题

解决思路:

​ 可以使用先从左到右进行遍历,记录每个位置左面的元素相乘获得的值,存储在output的对应位置,再从右到左进行遍历,记录每个位置右侧的元素乘积,再和output中已经存储的该位置左侧的元素乘积相乘,就可以得到最终结果,时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def productExceptSelf(self, nums):
"""
完美解
:type nums: List[int]
:rtype: List[int]
"""
left = 1
right = 1

len_nums = len(nums)

output = [0]*len_nums

#从左到右进行一次遍历,在output中对应位置记录该值左面的元素乘积
for i in range(0,len_nums):
output[i] = left
left = left*nums[i]

#从右到左进行一次遍历,记录每个值右面元素的乘积,和output中已经进行存储的左面乘积相乘,得到各个位置最终的结果
for j in range(len_nums-1,-1,-1):
output[j] *= right
right *= nums[j]

return output

2.缺失数字

给定一个包含 0, 1, 2, ..., nn 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

1
2
输入: [3,0,1]
输出: 2

示例 2:

1
2
输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

思路一:最常见的思路应该是先排序,然后顺序遍历,对不上则为缺失位置

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for key,value in emumerate(nums):
if key!=value:
return key
else:
return key+1

思路二:另一种比较巧妙地思路就是直接利用数学的方法来解决这个问题,仔细研究题目,我们可以发现题目中所给的nums数组内所有元素的加和可以看做等差数列的加和减去缺失数,因此我们可以直接计算等差数列的加和(n*(n-1))/2,然后减去nums数组的加和,二者相减即为缺失的数.

1
2
3
4
5
6
7
class Solution:
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return (int(len(nums)*(len(nums)-1)/2)- sum(nums))

爬楼梯问题(动态规划)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

1
2
3
4
5
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1
2. 2

示例 2:

1
2
3
4
5
6
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1
2. 1 阶 + 2
3. 2 阶 + 1

解题思路:首先经过题目分析我们最自然的可以想到,要想问到第n层楼梯的走法,那么一定为到第n-1和第n-2层楼梯走法之和,因此我们可以清楚地可以看出这是一道递归问题。即n(i) = n(i-1)+n(i-2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
def f(n):
if n==0|n==1:
return 1
else:
return f(n-1)+f(n-2)
if n>=2:
return f(n)
return 1

转换成非递归问题(其实本质就是讲递归问题由系统储存的信息改为程序储存,从而改编程序的运行方式,提高程序的运行效率

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
way = [0,1,2]
for i in range(3,n+1):
way.append(way[i-1]+way[i-2])
return way[n]