X

LEETCODE 1416. Restore The Array 解题思路分析

题目大意:

恢复数组

某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串,我们所知道的信息只有:数组中所有整数都在 [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.

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1416

解题思路分析:

这道题是标准的dp题目,使用递归加记忆数组的方式来解题非常轻松,可以算是模板级别的题目。

本题实际上是以不同的方式分割字符串,使得分割后的每一部分所代表的数字都要小于k,我们需要找出符合条件的分割方式数。首先我们定义一个递归函数help:

int help(char[] arr, int index, int k)

参数arr是原始字符串转化后的字符数组,index代表当前下标,k为题目给出的单个数字的最大值。返回值为从当前index到数组末尾,满足条件的分割数目。递归函内解决的问题实际上是从当前index开始找到一个大于等于1并且小于等于k的合理的数字,该数字可能由当前位(index),或者当前位与之后相邻的n位组成。因此我们需要从当前index循环至数组末尾,查看[index, i](i>=index && i<length)区间组成的数字是否小于k,如果是,代表当前区间是一个合理数字,也就是说我们在当前下标i处可以分割,接下来,我们将分割后的部分[i+1, length-1]交给子问题去解决,子问题的参数中,index等于当前i加1。其他参数保持不变。循环中,所有子问题的解相加,即是当前问题的返回值。

另外递归时,当index大于等于数组长度时,代表已经递归到数组末尾,也就是找到了一个合理的分割方式,此时返回1,这也是递归函数的一个终止条件。另外,如果当前index所指向的数字是0,这是不符合条件的(数字不能有前导0,数字0本身也不行),说明当前的分割方式不合理,返回0。

最后再考虑记忆数组(相当于动态规划解法的dp数组),使用递归方式解题的好处便是,我们可以很简单的建立记忆数组,建立记忆数组的方式是查看递归函数的参数中,有哪些是会发生变的即可,本题中,发生变的参数只有index,因此我们只需要建立一个一维数组即可。

如果你完全不懂动态规划的相关知识,或者你没能完全理解递归加记忆数组的解题方法,建议参考我之前总结过的这篇文章:LEETCODE常见算法之动态规划DP超详细白话讲解(上)

实现代码:

Integer[] memo; // 记忆数组
public int numberOfArrays(String s, int k) {
    // 初始化记忆数组
    memo=new Integer[s.length()];
    // 递归求解
    return help(s.toCharArray(),0,k);
}
// arr:原始字符串转化称为的字符数组
// index:当前下标
// 返回值:index到数组末尾区间内存在的合理方案数
int help(char[] arr, int index, int k){
    // 当递归至数组末尾时,返回1
    if(index==arr.length) return 1;
    // 当前数字是0,不合理,返回0
    if(arr[index]=='0') return 0;
    // 记忆数组中存在当前值,直接返回
    if(memo[index]!=null) return memo[index];
    // 当前数字
    long num=0;
    // 返回结果
    long res=0;
    for(int i=index;i<arr.length;i++){
        // 当前位上的数字
        int n=arr[i]-'0';
        // 当前数字
        num = num*10+n;
        // 如果当前数字大于k,不符合条件,退出循环
        if(num>k) break;
        // 递归求解
        res+=help(arr, i+1, k);
    }
    memo[index]=(int)(res%1000000007);
    return memo[index];
}

本题解法执行时间为37ms。

Runtime: 37 ms, faster than 92.87% of Java online submissions for Restore The Array.

Memory Usage: 58 MB, less than 100.00% of Java online submissions for Restore The Array.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1416-restore-the-array-解题思路分析/
Categories: leetcode
kwantong: