| 🚀 算法题 🚀 |
🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯
| 🚀 算法题 🚀 |
🍔 目录
🚗 知识回顾
该题和我们之前的题目在求解的思路上相似之处，感兴趣的同学可以学习一下相关的内容。
-
【LeetCode: 1043. 分隔数组以得到最大和 | 暴力递归=＞记忆化搜索=＞动态规划 | 线性dp & 区间dp】
-
【LeetCode: 2369. 检查数组是否存在有效划分 | 暴力递归=＞记忆化搜索=＞动态规划 | 线性dp】
-
【LeetCode: 1105. 填充书架 | 暴力递归=＞记忆化搜索=＞动态规划 | 线性dp & 业务限制】
🚩 题目链接
⛲ 题目描述
某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [1, k] 之间，且数组中的数字都没有前导 0 。
给你字符串 s 和整数 k 。可能会有多种不同的数组恢复结果。
按照上述程序，请你返回所有可能输出字符串 s 的数组方案数。
由于数组方案数可能会很大，请你返回它对 10^9 + 7 取余 后的结果。
示例 1：
输入：s = “1000”, k = 10000
输出：1
解释：唯一一种可能的数组方案是 [1000]
示例 2：
输入：s = “1000”, k = 10
输出：0
解释：不存在任何数组方案满足所有整数都 >= 1 且 <= 10 同时输出结果为 s 。
示例 3：
输入：s = “1317”, k = 2000
输出：8
解释：可行的数组方案为 [1317]，[131,7]，[13,17]，[1,317]，[13,1,7]，[1,31,7]，[1,3,17]，[1,3,1,7]
示例 4：
输入：s = “2020”, k = 30
输出：1
解释：唯一可能的数组方案是 [20,20] 。 [2020] 不是可行的数组方案，原因是 2020 > 30 。 [2,020] 也不是可行的数组方案，因为 020 含有前导 0 。
示例 5：
输入：s = “1234567890”, k = 90
输出：34
提示：
1 <= s.length <= 10^5.
s 只包含数字且不包含前导 0 。
1 <= k <= 10^9.
🌟 求解思路&实现代码&运行结果
⚡ 暴力递归
🥦 求解思路
- 该题目让我们求解的是将s进行一个划分，每一个划分的部分都小于等于k的总体方案数。
- 总体求解思路还是动态规划，为什么呢？因为我们想要求解的是从0位置开始，到s的最后一个位置结束，满足每个部分小于等于k的总体方案数目。如果说我们此时划分了0-cur位置，那么从cur-最后一个结束位置还需要重复这个过程，所以说，该过程是存在重复子问题的，我们可以通过动态规划来进行一个求解。
- 首先，我们还是设计一个递归函数，递归函数的含义是从index位置开始进行划分，找到所有满足的方案数。
🥦 实现代码
class Solution {
private int mod=(int) 1e9 + 7;
public int numberOfArrays(String s, int k) {
return (int)(process(0,s,k)%mod);
}
public long process(int index,String s,int k){
if(index>=s.length()){
return 1;
}
long res=0;
for(int i=index;i<s.length();i++){
long sum=0;
for(int j=index;j<i+1;j++){
sum=sum*10+s.charAt(j)-'0';
}
if(s.substring(index,i+1).charAt(0)!='0'&&sum<=k&&sum>=1){
res+=process(i+1,s,k)%mod;
}
}
return res%mod;
}
}
🥦 运行结果
时间超限了，不要紧哦，我还有锦囊妙计！
⚡ 记忆化搜索
🥦 求解思路
- 根据我们递归的分析，在递归的过程中会产生重复的子过程，所以我们想到了加一个缓存表，也就是我们的记忆化搜索。
- 因为题目给定我们的k的限制条件是k≤10^9 ，所以我们最多只要枚举 10个数字就行了，这个也是我们优化的一个点，否则时间还是会超限的。
🥦 实现代码
class Solution {
private int mod=(int) 1e9 + 7;
private long[] dp;
public int numberOfArrays(String s, int k) {
dp=new long[s.length()];
Arrays.fill(dp,-1);
return process(0,s,k)%mod;
}
public int process(int index,String s,int k){
if(index>=s.length()){
return 1;
}
if(dp[index]!=-1) return (int)(dp[index]);
long res=0;
long sum=0,base=10;
for(int i=index;i<s.length()&&i-index<=10;i++){
if(s.substring(index,i+1).charAt(0)=='0') continue;
sum=sum*base+s.charAt(i)-'0';
if(sum<=k&&sum>=1){
res+=process(i+1,s,k)%mod;
}
}
return (int)(dp[index]=res%mod);
}
}
🥦 运行结果
⚡ 动态规划
🥦 求解思路
- 按照我们之前递归和记忆化搜索的思路，通过动态规划实现出来。
🥦 实现代码
class Solution {
private int mod=(int) 1e9 + 7;
private long[] dp;
public int numberOfArrays(String s, int k) {
int n=s.length();
dp=new long[n+1];
dp[n]=1;
for(int index=n-1;index>=0;index--){
long res=0;
long sum=0,base=10;
for(int i=index;i<s.length()&&i-index<=10;i++){
if(s.substring(index,i+1).charAt(0)=='0') continue;
sum=sum*base+s.charAt(i)-'0';
if(sum<=k&&sum>=1){
res+=dp[i+1]%mod;
}
}
dp[index]=res%mod;
}
return (int)(dp[0]%mod);
}
}
🥦 运行结果
💬 共勉
|
最后，我想和大家分享一句一直激励我的座右铭，希望可以与大家共勉！ |
