如何建设一个社交网站,前端是做网站的吗,徽信小程序是什么,wordpress技术cms主题#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域新星创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 知识回顾 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 暴力递归 求解思路 实现代码 运行结果 ⚡ 记忆化搜索 求解思路 实现代码 运行结果 ⚡ 动态规划 求解思路 实现代码 运行结果 共勉 知识回顾
该题和我们之前的题目在求解的思路上相似之处感兴趣的同学可以学习一下相关的内容。
【LeetCode: 1043. 分隔数组以得到最大和 | 暴力递归记忆化搜索动态规划 | 线性dp 区间dp】【LeetCode: 2369. 检查数组是否存在有效划分 | 暴力递归记忆化搜索动态规划 | 线性dp】【LeetCode: 1105. 填充书架 | 暴力递归记忆化搜索动态规划 | 线性dp 业务限制】 题目链接
1416. 恢复数组
⛲ 题目描述
某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串我们所知道的信息只有数组中所有整数都在 [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(indexs.length()){return 1;}long res0;for(int iindex;is.length();i){long sum0;for(int jindex;ji1;j){sumsum*10s.charAt(j)-0;}if(s.substring(index,i1).charAt(0)!0sumksum1){resprocess(i1,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) {dpnew long[s.length()];Arrays.fill(dp,-1);return process(0,s,k)%mod;}public int process(int index,String s,int k){if(indexs.length()){return 1;}if(dp[index]!-1) return (int)(dp[index]);long res0;long sum0,base10;for(int iindex;is.length()i-index10;i){if(s.substring(index,i1).charAt(0)0) continue;sumsum*bases.charAt(i)-0;if(sumksum1){resprocess(i1,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 ns.length();dpnew long[n1];dp[n]1;for(int indexn-1;index0;index--){long res0;long sum0,base10;for(int iindex;is.length()i-index10;i){if(s.substring(index,i1).charAt(0)0) continue;sumsum*bases.charAt(i)-0;if(sumksum1){resdp[i1]%mod;}}dp[index]res%mod;}return (int)(dp[0]%mod);}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
