Flip Game II

nanfeiyan 发布于2019-08-14 17:25 / 3091人阅读

摘要：题目链接的题，可以直接暴力，优化可以加，只有当所有可能的都是的时候，当前结果才是

Flip Game II

题目链接：https://leetcode.com/problems...

dp的题，可以直接暴力dfs，优化可以加memory，只有当所有可能的subproblem都是false的时候，当前结果才是false：

public class Solution {
    public boolean canWin(String s) {
        // if already in map
        if(memo.containsKey(s)) return memo.get(s);
        for(int i = 0; i < s.length() - 1; i++) {
            if(s.startsWith("++", i)) {
                String next = s.substring(0, i) + "--" + s.substring(i + 2);
                if(!canWin(next)) {
                    memo.put(s, true);
                    return true;
                }
            }
        }
        memo.put(s, false);
        return false;
    }
    
    Map memo = new HashMap();
}

GPU云服务器云服务器 Flip II game quartus ii

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66631.html

LeetCode[45] Jump Game II

摘要：复杂度思路每次设置一个窗口，观察在这一步下能到达的最远距离，不断的移动这个窗口。计数，需要移动几次，才能覆盖到末尾的值。 LeetCode[45] Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Eac...

keelii 2019-08-14 15:02 评论0 收藏0
[LintCode/LeetCode] Jump Game I & II

摘要：建立动规数组，表示从起点处到达该点的可能性。循环结束后，数组对所有点作为终点的可能性都进行了赋值。和的不同在于找到最少的步数。此时的一定是满足条件的最小的，所以一定是最优解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

rose 2019-08-14 15:27 评论0 收藏0
leetcode45. Jump Game II

摘要：转换为广度优先算法即为我们只需要找到每一步的开始节点和结束下标，找到下一轮遍历的最大下标，如果该下标超过了数组长度，那么结束遍历，返回步数，否则将上一轮的最终节点加一作为起始节点，并将下一轮最大下标最为结束节点，继续遍历。题目要求 Given an array of non-negative integers, you are initially positioned at the ...

shiguibiao 2019-08-15 10:50 评论0 收藏0
[LeetCode] 487. Max Consecutive Ones II

Problem Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0. Example 1:Input: [1,0,1,1,0]Output: 4Explanation: Flip the first zero will get the ...

nanfeiyan 2019-08-16 13:59 评论0 收藏0