讨论/题目交流/🐱 第 24 场夜喵双周赛/
🐱 第 24 场夜喵双周赛
展开讨论
力扣 (LeetCode)发起于 2020-04-18
最近编辑于 2020-04-18

第四题的测试用例简直是不给穷举法的本菜鸡留活路。

本菜鸡终于做出来了,穷举+缓存,算是耍赖么

class Solution {
    public int numberOfArrays(String s, int k) {
        int[] n=new int[s.length()+1];
        for(int i=0;i<n.length;i++){
            n[i]=-1;
        }
        int res=func(s,0,k,n);
        return res;
    }
    
    public int func(String s,int l,int k,int[] arr){
        if(l>=s.length()){
            return 1;
        }
        if(s.charAt(l)=='0'){
            return 0;
        }
        int n=0;
        int res=0;
        for(int i=l;i<s.length();i++){
            int n2=Integer.parseInt(s.charAt(i)+"");
            if(n*1.0<=(k-n2)/10.0){
                if(arr[i+1]==-1){
                    arr[i+1]=func(s,i+1,k,arr);
                }
                res+=arr[i+1];
                if(res>=1000000007){
                    res%=1000000007;
                }
            }
            else{
                break;
            }
            n=n*10+n2;
        }
        return res;
    }
}
1
展开全部 32 讨论