9月刷题/Mock interview接龙活动（缺米刷题的来）

AnApple_Aday 发表于 2020-9-15 21:35
几题backtracking

求加米。。 今天加米额度用完了，过几小时有新额度了 再来给前面的朋友加~

Day 80, solved 1 problem.

事多，先做两道

4道interval的题目 起晚了 显示1天前了

20200914:
3: 0011, 0235, 0236, 0238, 0253, 0616
4: 0072, 0239
5:

09-15-2020

09/14 Day 14 补打卡：

91 Decode Ways
这个题目一定要用DP 用memorized DFS会超时

题目就是假设不一定valid
关于0的corner case比较多  101， 230

想一下做法要考虑一下跟0相关的Corner case


45 Jump Game II
O(N) time O(1) space的solution
一直在算一个走过的所有点的furthest是多少
用int curEnd和curFurthest = nums[i]+i
if curEnd == i  jump++ curEnd = curFurthest


44 Wildcard Matching
看自己的答案就挺好的
关键是要记住
I, j  =  ([j] == *) && (dp[i-1][j-1] == true || dp[i-1][j] == true || dp[i][j-1] == true)


自己的solution挺好 最佳solution能省掉dp存储空间
不需要dp的原因是因为你其实不需要保整个dp只需要保存当前计算所需要的几个variable或者一行的status

要画出这个矩阵的样子
写出dp[i][j]的逻辑判断
I, j  =  ([i] ==[j] || [j] == ?) && dp[i-1][j-1] == true
I, j  =  ([j] == *) && (dp[i-1][j-1] == true || dp[i-1][j] == true || dp[i][j-1] == true)

起始条件要注意  s为空时 p可以为多个***

夏夜的未央 发表于 2020-9-16 03:37
91 Decode Ways
这个题目一定要用DP 用memorized DFS会超时

DFS + MEMO这个很快的，供参考
public int numDecodings(String s) {
        if (s == null || s.length() == 0) return 0;
        
        int[] memo = new int[s.length()];
        Arrays.fill(memo, -1);
        
        return dfs(s, 0, memo);
    }
   
public int dfs(String s, int start, int[] memo) {
        if (start == s.length()) return 1;
        if (memo[start] != -1) return memo[start];
        int res = 0;
        for (int i = start; i < s.length() && i - start <= 2; i++) {
            int d = Integer.parseInt(s.substring(start, i + 1));
            if (s.charAt(start) != '0' && d <= 26) {
                res += dfs(s, i + 1, memo);
            }
        }
        memo[start] = res;
        return res;
    }

打卡

帮我多加点米，急需看面经，就差几分了。多谢！