目录
  1. 1. 日常警醒
  2. 2. 剑指offer10-I.斐波那契数列
    1. 2.1. 题目
    2. 2.2. 题解
  3. 3. 剑指offer10-II.青蛙跳台阶问题
    1. 3.1. 题目
    2. 3.2. 题解
  4. 4. 剑指offer11.旋转数组的最小数字
    1. 4.1. 题目
    2. 4.2. 题解
  5. 5. 154.寻找旋转排序数组中的最小值II
    1. 5.1. 题目
    2. 5.2. 题解
  6. 6. 17.电话号码数字组合
    1. 6.1. 题目
    2. 6.2. 题解
每日一刷4

日常警醒

菜就要刷题,不要偷懒!

剑指offer10-I.斐波那契数列

题目

  • 难度:简单

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例1:

输入:n = 2
输出:1

示例2:

输入:n = 5
输出:5

提示:

  • 0 <= n <= 100

题解

  • 动态规划
    • 状态定义:设dp为一维数组,dp[i]代表斐波那契数列第i个数字
    • 转移方程:dp[i] = dp[i] + dp[i - 1],对应斐波那契数列公式
    • 初始状态:dp[0] = 0, dp[1] = 1
    • 返回值dp[n]
  • 空间优化
    • dp[i]只和dp[i-1]和dp[i-2]有关,因此,初始化三个整形变量sum, a, b,利用辅助变量 sum使 a, b 两数字交替前进即可
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
def fib(n):
a = 0
b = 1
for _ in range(n):
a, b = b, a+ b
return a % 1000000007

if __name__ == '__main__':
n = 2
print(fib(n))

剑指offer10-II.青蛙跳台阶问题

题目

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例1:

输入:n = 2
输出:2

示例2:

输入:n = 7
输出:21

示例3:

输入:n = 0
输出:1

提示:

  • 0 <= n <= 100

题解

  • 和上一道题目的思路是一样的
  • 动态规划
    • 状态定义:设dp为一维数组,dp[i]代表青蛙上一个i级台阶总共有多少种跳法
    • 转移方程:dp[i] = dp[i - 1] + dp[i - 2]
    • 初始状态:dp[0] = dp[1] = 1
    • 返回值dp[n]
  • 空间优化:
    • dp[i]只和dp[i-1]和dp[i-2]有关,因此,初始化三个整形变量sum, a, b,利用辅助变量 sum使 a, b 两数字交替前进即可
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
def numWays(n):
a = 1
b = 1
for _ in range(n):
a, b = b, a + b
return a % 1000000007

if __name__ == '__main__':
n = 7
print(numWays(n))

剑指offer11.旋转数组的最小数字

题目

  • 难度:简单

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1

示例1:

输入:[3,4,5,1,2]
输出:1

示例2:

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

题解

  • 这道题面新浪一面的时候,考过升级版有重复数字的(见下一题),这题是假设没有重复数字

  • 二分法

    • 未旋转情况:数组第一个数字比最后一个数字小
    • 旋转情况:
      • 左排序数组任一数字一定大于等于右排序数组任一数字
    • 二分查找:
      • 取mid,与数组最后一个数字比较
      • 如果数组mid的数字大于数组最后一个数字,说明最小值在mid右侧
      • 如果数组mid的数字小于数组最后一个数字,说明最小值在mid左侧
      • 如果数组mid的数字等于数组最后一个数字,无法说明最小值的区间,直接缩小判断区间
  • 时间复杂度:O(logn)

  • 空间复杂度:O(1)

def minArray(nums):

i, j = 0, len(nums) - 1

if nums[j] > nums[i] or len(nums) == 1:
return nums[0]

while i < j:
mid = (i + j) // 2
if nums[mid] > nums[j]:
i = mid + 1
elif nums[mid] < nums[j]:
j = mid - 1
else:
j = j - 1
return nums[i]

if __name__ == '__main__':

nums = [3,4,5,1,2]
print(minArray(nums))

154.寻找旋转排序数组中的最小值II

题目

  • 难度:困难

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例1:

输入: [1,3,5]
输出: 1

示例2:

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

说明:

题解

  • 新浪一面的代码题

  • 和上一题不一样的地方就是有了重复数字,例如下面case在上一题的代码就找不到正确的最小的数字:

    • [1,1,1,1,0,1,1]
    • 有重复数字时候,在判断nums[mid] < nums[len(nums) - 1]时,nums[mid]可能就是最小的数字,缩小区间时候就不是right = mid - 1,而是right = mid
  • case [1,1,1,1]情况,时间复杂度会变成O(n),因为需要不断执行缩小空间,直到只剩一个元素返回

  • 时间复杂度:O(logn)

  • 空间复杂度:O(1)

class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""

i, j = 0, len(nums) - 1

if nums[j] > nums[i] or len(nums) == 1:
return nums[0]

while i < j:
mid = (i + j) // 2
if nums[mid] > nums[j]:
i = mid + 1
elif nums[mid] < nums[j]:
j = mid
else:
j = j - 1
return nums[i]

17.电话号码数字组合

题目

  • 难度:中等

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

九键

示例:

输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。

题解

  • 触宝一面代码题,只不过改成26键,换了一个情景。(触宝有一款输入法面向海外用户,现有外国人要用26键打字,但是由于26键按键小,容易按错,按到本来想要按的键的相邻的键,现在外国人要输入hi,请输出他可能打出的所有情况)
  • 映射关系需要改变,面试里只要求我写hi这种情况。
    • h:[‘g’,‘h’,‘j’]
    • i:[‘u’,‘i’,‘o’]
  • 回溯法:一种通过穷举所有可能情况来找到所有解的算法,如果一个候选解最后被发现并不是可行解,回溯算法会舍弃它,并在前面的一些步骤做出一些修改,并重新尝试找到可行解。
  • 时间复杂度:O(3^N * 4 ^ M),其中 N 是输入数字中对应 3 个字母的数目(比方说 2,3,4,5,6,8), M 是输入数字中对应 4 个字母的数目(比方说 7,9),N+M 是输入数字的总数。
  • 空间复杂度:O(3^N * 4 ^ M),需要保存这么多结果
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
phone = {'2':['a','b','c'],
'3':['d','e','f'],
'4':['g','h','i'],
'5':['j','k','l'],
'6':['m','n','o'],
'7':['p','q','r','s'],
'8':['t','u','v'],
'9':['w','x','y','z']}
def back(comb, next_digits): #next_digits下一次输入的字母,comb组合情况
#如果没有新的输入,说明组合完成
if len(next_digits) == 0:
return output.append(comb)
else:
#遍历下一个输入的所有映射
for i in phone[next_digits[0]]:
#将当前字母添加到组合最后(comb+i),不断重复直到没有新的输入
#如果是i+comb就是加到前面
back(comb + i, next_digits[1:])

output = []
if digits:
back("",digits)
return output
文章作者: Lesy
文章链接: https://lesylin.com/2020/08/05/%E6%AF%8F%E6%97%A5%E4%B8%80%E5%88%B74/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment