把数组排成最小的数
题目
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2] 输出: "102"
分析
- 题目要求，数组中有ｍ和ｎ，如果mn<nm那么m和n的相对位置是正确的。类似选择排序。
代码
class Solution: def minNumber(self, nums: List[int]) -> str: #数字转字符串比较 numList=[str(x) for x in nums] for i in range(len(numList)): for j in range(i,len(numList)): if numList[i]+numList[j]>numList[j]+numList[i]: temp=numList[i] numList[i]=numList[j] numList[j]=temp return ''.join(numList)
把数字翻译成字符串
题目
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
分析
动态规划
- 对于一个数字
num[i]有两种处理方法：- 单独翻译
- 和前面的数组合翻译
- 新建
dp[]数组dp[i]用来存储前i个数的翻译方法数
- 如果只翻译自己：
dp[i]=dp[i-1] - 组合翻译:
dp[i]=dp[i-2]+dp[i-1]
- 对于一个数字
代码
class Solution: def translateNum(self, num: int) -> int: str_num=str(num) n=len(str_num) dp=[] for i in range(n+1): dp.append(1) for i in range(2,n+1): if str_num[i-2]+str_num[i-1] >='10' and str_num[i-2]+str_num[i-1]<='25': dp[i]=dp[i-1]+dp[i-2] else: dp[i]=dp[i-1] return dp[n]
礼物的最大价值
题目
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
分析
- 初始化：
- 状态表示：
dp[i][j]表示到达i,j位置处的最大价值 - 转移方程：
dp[i][j] = max{dp[i-1][j],dp[i][j-1]} + grid[i][j];
- 状态表示：
- 初始化：
代码
class Solution: def maxValue(self, grid: List[List[int]]) -> int: row=len(grid) col=len(grid[0]) if row==0 and col==0: return 0 dp=[[0 for _ in range(col)] for _ in range(row)] dp[0][0]=grid[0][0] for i in range(1,col): dp[0][i]=dp[0][i-1]+grid[0][i] for i in range(1,row): dp[i][0]=dp[i-1][0]+grid[i][0] for i in range(1,row): for j in range(1,col): dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j] return dp[row-1][col-1]
最长不含重复字符的子串
题目
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
分析
代码
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: head=tail=0 if len(s)<2:return len(s) res=1 while tail<len(s)-1: tail+=1 if s[tail] in s[head:tail]: while s[tail] in s[head:tail]: head+=1 # if head==tail: # break else: res=max(tail-head+1,res) return res #方法二：字典存储索引，简化了head++的循环 class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if len(s)<2:return len(s) head=tail=0 hashmap={} #{value:index} n=len(s) res=1 while tail<n: if s[tail] in hashmap: head=max(hashmap[s[tail]],head) hashmap[s[tail]]=tail+1 #直接将head指针指向重复元素的后面 res=max(tail-head+1,res) tail+=1 return res
丑数
题目
我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
分析
- 丑数即一个数等于 $ 2^x * 3^y * 5^z $ , x、y、z可以为 0，
- 思路一：优先队列 O(NlogN)
- 要去找第n个丑数，首先想到的就是一个个去生成。$ uglyNum=2^x * 3^y * 5^z$ ，由 11 生成了 2、3、5，接着 2、3、5利用前面公式继续生成
- 当然，生成过程是先放小的，并且我们需要去重，去重就需要用到 set
- 思路二：动态规划自底向上思想 O(n)O(n)
- 由于我们已经知道它的公式了，我们用三个指针 p2、p3、p5的数字变化表示了上一个丑数是通过乘以这个因子得到的。所以，下一个丑数
res[i] = min(res[p2] * 2, res[p3] * 3, res[p5] * 5)，接着移动指针即可
- 由于我们已经知道它的公式了，我们用三个指针 p2、p3、p5的数字变化表示了上一个丑数是通过乘以这个因子得到的。所以，下一个丑数
- 思路一：优先队列 O(NlogN)
- 丑数即一个数等于 $ 2^x * 3^y * 5^z $ , x、y、z可以为 0，
代码
class Solution: def nthUglyNumber(self, n: int) -> int: #动态规划dp[i]存储第i+1个丑数 p2,p3,p5=0,0,0 dp=[1 for _ in range(n)] for i in range(1,n): dp[i]=min(dp[p2]*2,min(dp[p3]*3,dp[p5]*5)) #下一个丑数 if dp[i]==dp[p2]*2:p2+=1 if dp[i]==dp[p3]*3:p3+=1 if dp[i]==dp[p5]*5:p5+=1 return dp[n-1] #如果第i个丑数==2*p2，也就是说前面0-p2个丑数*2不可能产生比第K个丑数更大的丑数了，所以p2++
