0%

刷题记录

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 745 阅读时长 ≈ 1 分钟
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, ..., n 中 n 个数的序列，找出 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]