Dayx2:剑指offer

本文主要是介绍Dayx2:剑指offer，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

44. 第N个数字 Leecode400
    在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …中找到第 n 个数字。
    注意:
    n 是正数且在32位整数范围内 ( n < 231)。

复杂度分析
时间复杂度：O(N)O(N)。
空间复杂度：O(1)O(1)。

import math
def findNthDigit(self, n: int) -> int:# 首先判断target是几位数，用digits表示base=9digits=1while n-base*digits>0:n-=base*digitsbase*=10digits+=1#计算target值first_number = 10**(digits-1)target=first_number+ math.ceil(n/digits) - 1 #!!!math.ceil保证n=30[21/2-1=9而不是10的错误] 结果不会从20减到19# 找到target中对应的数字return int(str(target)[(n-1)%digits])

45. 把数组排成最小的数
    输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
    e.g:输入数组[3, 32, 321]，则打印出这3个数字能排成的最小数字321323。

def PrintMinNumber(self, numbers):if not numbers: return ""num=map(str,numbers)num.sort(lambda x,y:cmp(x+y,y+x))   #python2 #等价于num.sort(cmp=lambda x,y:cmp(x+y,y+x))#return "".join(num)#python3
from functools import cmp_to_key
def PrintMinNumber(self, numbers):from functools import cmp_to_keyif not numbers: return ""num=list(map(str,numbers))num.sort(key=cmp_to_key(self.cmp))#nums.sort(key=cmp_to_key(lambda a, b: (a + b > b + a) - (a + b < b + a)))return int(''.join(num))def cmp(self,a,b):s1=a+bs2=b+aif s1>s2: return 1elif s1<s2: return -1else: return 0

特别感谢：python中sort()方法的cmp参数

46. 把数字翻译成字符串
    给定一个数字，我们按照如下规则把它翻译为字符串：
    0翻译成”a”，1翻译成”b”，……，11翻译成”l”，……，25翻译成”z”。

python中str是可以比较大小的 '10'<'30'; 返回True

敲重点：dp

#原书的题。从0开始表示。范围为‘0’ ~ ‘25’
def numDecodings(self, s: str) -> int:n=len(str)f=[0]*(n+1)f[0],f[1]=1,1for i in range(2,n+1):if '10'<=s[i-2:i] <='25':     #注意：s[0]~s[n-1]f[i]=f[i-2]+f[i-1]else:f[i] = f[i - 1]return f[n]#范围为‘1’ ~ ‘26’
def numDecodings(self, s: str) -> int:if s[0]=='0' or not s:return 0n=len(s)f = [0] * (n + 1)f[0], f[1] = 1, 1for i in range(2,n+1):if s[i-1]=='0':if s[i-2] in {'1','2'}:f[i]=f[i-2]else:return 0else:if '10' <= s[i - 2:i] <= '26':  # 注意：s[0]~s[n-1]f[i] = f[i - 2] + f[i - 1]else:f[i] = f[i - 1]return f[n]

47. 礼物的最大价值
    在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。
    可从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格直到到达棋盘的右下角。
    请计算你最多能拿到多少价值的礼物？

注意：下标从1开始算，不用处理边界问题。f[i - 1]不会越界。

def getMaxValue_2(self, grid):"""优化空间O(n)"""rows,cols=len(grid),len(grid[0])f=[0]*(cols+1)   #If matrix初始化f=[[0]*(cols+1) for _ in range(rows+1) ]for i in range(1,rows+1):for j in range(1,cols+1):f[j]=max(f[j],f[j-1]) + grid[i][j]  #!!!f[j]是上一行的j列results存储；f[j-1]是目前行的j-1列results存储return f[cols]

更general 见下

#次优 之matrix版  
f=[[0]*(cols+1) for _ in range(rows+1) ]
for i in range(1, rows + 1):for j in range(1, cols + 1):f[i][j]=max(f[i-1][j]+f[i][j-1]) + grid[i][j]return f[rows][cols]

---

#变形练习
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。
问总共有多少条不同的路径？

def uniquePaths(self, m: int, n: int) -> int:"""优化空间O(n)"""rows,cols=m,nf=[1]*colsfor i in range(1,rows):for j in range(1,cols):f[j]=f[j]+f[j-1]return f[-1]

更general 见下

class Solution:def uniquePaths(self, m: int, n: int) -> int:rows,cols=m,nf=[[0]*(cols) for _ in range(rows) ]  #!!!f[m-1][n-1]for i in range(m): f[i][0]=1for j in range(n): f[0][j]=1for i in range(1,rows):  #!!!从1 startfor j in range(1,cols):f[i][j]=f[i-1][j]+f[i][j-1]return f[-1][-1]

48. 无重复字符的最长子串 Leecode 3
    给定一个字符串，请找出其中不含有重复字符的 最长子串 的长度。

'''优化的滑动窗口'''
def lengthOfLongestSubstring_2(self, s: str) -> int:maxlen,l=0,0pos={} #dictfor idx, ch in enumerate(s):if ch in pos:l=max(pos[ch]+1, l)maxlen = max(maxlen, idx-l+1)pos[ch]=idx  #!!!updatereturn maxlen'''滑动窗口'''
#[双指针算法]当窗口内出现重复字符时，移除左边元素直到删除重复元素，继续移动窗口右端。
def lengthOfLongestSubstring(self, s: str) -> int:if not s: return 0maxlen, l = 0, 0mem=set() #窗口的元素(变动的)for idx in range(len(s)):while s[idx] in mem:mem.remove(s[l])  #先remove;再l+=1l=l+1mem.add(s[idx])maxlen=max(maxlen, idx-l+1)return maxlen

Set remove() 方法 注意：
该方法不同于 discard() 方法，因为 remove() 方法在移除一个不存在的元素时会发生错误，而 discard() 方法不会。

这篇关于Dayx2:剑指offer的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---