[Leetcode] Dynamic Programming

satjd

2019/01/06

Categories: Algorithm 基础知识 Tags: leetcode

139. Word Break

/**
 * 通过对原问题的观察,我们可以发现,一个较长的字符串如果能用这个单词集表示的话
 * 那么一定存在一个原来串的前缀,这个前缀也可以用单词集表示
 * 那么,这个问题也就满足了最优子结构性质,当判断一个字符串是否能表示时,
 * 枚举其所有前缀,找到多个能在单词集中表示的前缀,然后扔掉这个前缀,看后面的部分
 * 后面的部分如果和单词集中的某个单词相等,那么整个串就满足要求
 * 递推关系式:
 * dp[i]表示[0,i)的子串是否能用单词集表示
 * dp[i] = (dp[j] && wordDict.contains(substring(0,i))) || ... || ...
 * 其中 0 <= j < i
 */
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (wordDict.isEmpty()) {
            return false;
        }
        
        // 将List转成HashSet,用于优化contains的效率
        HashSet<String> wordsHashSet = new HashSet<>();
        for (String str : wordDict) {
            wordsHashSet.add(str);
        }
        
        int slen = s.length();
        boolean dp[] = new boolean[slen + 1];
        dp[0] = true;
        for (int i=1; i <= slen; i++) {
            for (int j = 0 ; j < i ; j++) {
                if (dp[j] == true && wordsHashSet.contains(s.substring(j,i)))
                {
                    dp[i] = true;
                    // 这一行break很关键,一旦找到一个j可以让dp[i]为true
                    // 那么就可以停止搜索后面的j了,如果不停止,会搜索很多没用的j,导致tle
                    break;
                }
            }
        }
        
        return dp[s.length()];
    }
}

472. Concatenated Words

/**
 * isCon方法就是139-word-break这道题的解。
 * 这道题在139-word-break这道题上进行了一点变化
 * 首先我们按照字符串的长短进行从短到长的排序
 * 然后,对于每一个串,该问题都可以转化为:
 * 用下标小于这个串(也就是比这个短的串)的集合来表示这个串的问题。
 * 那么这个问题和139题也就完全一样了。
 * 我们从前到后扫描这个已经排好序的字符串集合,
 * 对于每一个字符串都像139题这样求解一次,就可以解决这个问题了
 */
class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Arrays.sort(words,new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });
        LinkedList<String> ret = new LinkedList<String>();
        Set<String> wordsSet = new HashSet<>(words.length);
        
        for (String s : words) {
            if (isCon(wordsSet,s)) {
                ret.add(s);
            }
            wordsSet.add(s);
        }
        
        return ret;
    }
    
    private boolean isCon(Set<String> wordsSet, String s) {
        if (wordsSet.isEmpty()) {
            return false;
        }
        int slen = s.length();
        boolean dp[] = new boolean[slen + 1];
        dp[0] = true;
        for (int i=1; i <= slen; i++) {
            for (int j = 0 ; j < i ; j++) {
                if (dp[j] == true && wordsSet.contains(s.substring(j,i)))
                {
                    dp[i] = true;
                    // 这一行break很关键,一旦找到一个j可以让dp[i]为true
                    // 那么就可以停止搜索后面的j了,如果不停止,会搜索很多没用的j,导致tle
                    break;
                }
            }
        }
        
        return dp[s.length()];
    }
}

466. Count The Repetitions

/**
 * 思路:
 * 首先,我们可以观察到,当我们用s2在S1中匹配时,若能够匹配到s1的k个子序列
 * 那么,用S2在S1中匹配时,能得到的子序列的个数就是(k/n2)
 * 所以,我们使用s2在S1中匹配,算出匹配数之后除以n2即可得到答案
 * 
 * 那么如何算出s2在S1中匹配的子序列个数呢?
 * 最暴力的方法就是看S1中的每一个字符和s2[index]是否相等,
 * 若相等 index++ 若不等,再看下一个字符,直到index == s2.length()为止,那么这个就算作一次匹配
 * 我们扫描一遍S1,就可以得到匹配数。
 * 时间复杂度:O(n1 * S1.length) 10^8 tle.
 * 这个暴力的方法显然没有利用到S1的周期性特点,如果想要利用这个特点
 * 可以观察原数组的性质,发现这个index在匹配的时候的变化位置是周期性的。
 * 具体来讲:
 * 对于每一段s1,一定都至少会有一个能匹配上s2的某个字符的点,令m = s2.length
 * 那么当n1 > m时,根据鸽巢原理,一定会有两个s1段取同一个m,这就形成了周期
 * 发现周期后,我们就不用按照暴力的方法继续往下算了,
 * 发现周期后,可以得到每个周期内匹配到的子序列个数p1,形成周期之前的匹配数p2,最后剩下的一个不完整周期的匹配数p3
 * 那么结果就是p1+p2+p3
 * 这三个数的具体计算方法和详细题解:参考:https://leetcode.com/articles/count-the-repetitions/
 */
class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        if (n1 == 0 || s1.length() == 0 || s2.length() == 0) return 0;
        int ret = 0;
        int[] counts = new int[n1 + 1];
        HashMap<Integer,Integer> matchIndexs = new HashMap<>(n1 + 1);
        int count = 0;
        int index = 0;
        
        for (int i = 0 ; i < n1 ; i++) {
            for (int j = 0 ; j < s1.length() ; j++) {
                if (s1.charAt(j) == s2.charAt(index)) {
                    index ++;
                    if (index == s2.length()) {
                        count++;
                        index = 0;
                    }
                }
            }
            counts[i] = count;
            
            Integer k;
            if ((k = matchIndexs.get(index)) != null) {
                // 第一个周期开始之前的匹配数
                ret += counts[k];
                // 每个周期内新增的匹配数 * 周期个数
                ret += (count - counts[k])*((n1 - 1 - k)/(i - k));
                //最后不能匹配成一个完整周期的剩余串能形成的匹配数
                ret += counts[k + ((n1 - 1 - k)%(i - k))] - counts[k];
                
                return ret / n2;
            } else {
                matchIndexs.put(index,i);
            }
        }
        
        return counts[n1 - 1] / n2;
    }
}

403. Frog Jump

/**
 * 作为一个典型的多阶段图问题,考虑使用dp进行解决
 * 进一步确认,该问题也具有最优子结构:
 * stones[k]如果为能跳到,那么它一定包含一个j<k,stones[j]能跳到
 * 且从j到k的距离能满足要求
 * 
 * 那么dp的关键就是使用一个维度记录在每一个石头上青蛙可以跳的距离
 * 状态转移方程:
 * dp[i][k] --> 青蛙在第i块石头上,下一步跳k步这种情况是否能成立
 * 
 * 初始化dp[0][1] = true 代表青蛙在第0个石头,目前能够跳1步
 * 外层循环i 0到(石头个数-1),
 *   内层循环扫描j<i 如果dp[j][(stones[i]-stones[j])]==true,说明从j可以跳(stones[i]-stones[j])步到i
 *     那么更新三个值:
 *     dp[i][(stones[i]-stones[j])]=true 表示跳到i之后,下一次还可以跳(stones[i]-stones[j])步
 *     dp[i][(stones[i]-stones[j])-1]=true 表示跳到i之后,下一次还可以跳(stones[i]-stones[j])-1步
 *     dp[i][(stones[i]-stones[j])+1]=true 表示跳到i之后,下一次还可以跳(stones[i]-stones[j])+1步
 * 最后看dp[stones.length-1]这一行的所有列,如果有true则返回true,否则返回false
 * 
 * 还有一个坑点是dp[][]的第二个维度取多大的问题,这取决于我们在每一个石头上能跳步数的取值范围
 * 开始我以为是整个stones数组里的max值,但后来发现某个用例是[1,2143483647],
 * 按照我这种方式,dp数组的第二个维度显然不能开这么大
 * 但再仔细一想,在某个石头上,最多也只能跳stones.length+1步,因为就算每个格都经过一次,每经过一次下一次多跳1步
 * 也只能把步数增加到stones.length+1,因此,dp数组的第二维开这么大就可以了……
 */
class Solution {
    public boolean canCross(int[] stones) {
        boolean[][] dp = new boolean[stones.length][stones.length+1];
        
        dp[0][1] = true;
        for (int i = 0; i < stones.length; i++) {
            for (int j = 0; j < i; j++) {
                int prevJump = stones[i] - stones[j];
                if(prevJump <= stones.length && dp[j][prevJump]) {
                    dp[i][prevJump] = true;
                    if (prevJump - 1 >= 0) {
                        dp[i][prevJump - 1] = true;
                    }
                    if (prevJump + 1 <= stones.length) {
                        dp[i][prevJump + 1] = true;
                    }
                }
            }
        }
        for (int i = 0; i < stones.length; i++) {
            if(dp[stones.length - 1][i]) {
                return true;
            }
        }
        return false;
    }
}