标签: 记忆化搜索

LeetCode刷题【488】祖玛游戏

你正在参与祖玛游戏的一个变种。

在这个祖玛游戏变体中,桌面上有 一排 彩球,每个球的颜色可能是:红色 'R'、黄色 'Y'、蓝色 'B'、绿色 'G' 或白色 'W' 。你的手中也有一些彩球。

你的目标是 清空 桌面上所有的球。每一回合:

  • 从你手上的彩球中选出 任意一颗 ,然后将其插入桌面上那一排球中:两球之间或这一排球的任一端。
  • 接着,如果有出现 三个或者三个以上颜色相同 的球相连的话,就把它们移除掉。
    • 如果这种移除操作同样导致出现三个或者三个以上且颜色相同的球相连,则可以继续移除这些球,直到不再满足移除条件。
  • 如果桌面上所有球都被移除,则认为你赢得本场游戏。
  • 重复这个过程,直到你赢了游戏或者手中没有更多的球。

给你一个字符串 board ,表示桌面上最开始的那排球。另给你一个字符串 hand ,表示手里的彩球。请你按上述操作步骤移除掉桌上所有球,计算并返回所需的 最少 球数。如果不能移除桌上所有的球,返回 -1

 

示例 1:

输入:board = "WRRBBW", hand = "RB"
输出:-1
解释:无法移除桌面上的所有球。可以得到的最好局面是:
- 插入一个 'R' ,使桌面变为 WRRRBBW 。WRRRBBW -> WBBW
- 插入一个 'B' ,使桌面变为 WBBBW 。WBBBW -> WW
桌面上还剩着球,没有其他球可以插入。

示例 2:

输入:board = "WWRRBBWW", hand = "WRBRW"
输出:2
解释:要想清空桌面上的球,可以按下述步骤:
- 插入一个 'R' ,使桌面变为 WWRRRBBWW 。WWRRRBBWW -> WWBBWW
- 插入一个 'B' ,使桌面变为 WWBBBWW 。WWBBBWW -> WWWW -> empty
只需从手中出 2 个球就可以清空桌面。

示例 3:

输入:board = "G", hand = "GGGGG"
输出:2
解释:要想清空桌面上的球,可以按下述步骤:
- 插入一个 'G' ,使桌面变为 GG 。
- 插入一个 'G' ,使桌面变为 GGGGGG -> empty
只需从手中出 2 个球就可以清空桌面。

示例 4:

输入:board = "RBYYBBRRB", hand = "YRBGB"
输出:3
解释:要想清空桌面上的球,可以按下述步骤:
- 插入一个 'Y' ,使桌面变为 RBYYYBBRRB 。RBYYYBBRRB -> RBBBRRB -> RRRB -> B
- 插入一个 'B' ,使桌面变为 BB 。
- 插入一个 'B' ,使桌面变为 BBBBBB -> empty
只需从手中出 3 个球就可以清空桌面。

 

提示:

  • 1 <= board.length <= 16
  • 1 <= hand.length <= 5
  • boardhand 由字符 'R''Y''B''G''W' 组成
  • 桌面上一开始的球中,不会有三个及三个以上颜色相同且连着的球
Related Topics
  • 广度优先搜索
  • 记忆化搜索
  • 字符串
  • 动态规划

  • 👍 258
  • 👎 0
  • 深度优先搜索方法,board 结尾借个空格好处理点

    上班摸鱼,凑合摸了一个小时多,水平有限

    深度优先搜索,

    删除连续相同颜色的,我在结尾添加了一个空格,代码稍微好写点具体参见reductionChars方法,不过这个还是写的不太完美,需要递归处理,应该有不用递归的写法的,回头再尝试

    具体还是看代码吧,有一些注解,应该能看看吧

    class Solution {
        HashSet<String> visited = new HashSet<>();
    
        int min = 100;
    
        public int findMinStep(String board, String hand) {
            //借个空结尾代码好处理点
            board = board+" ";
            boolean[] handUsed = new boolean[hand.length()];
            char[] boardChars = board.toCharArray();
            dfs(boardChars,hand,handUsed);
            //如果是100表示不能全消除
            return min==100?-1:min;
        }
    
        public void dfs(char[] chars, String hand , boolean[] handUsed){
            if (chars.length==1){
                //统计用了几个
                int usedCount = 0;
                for (boolean used : handUsed) {
                    if (used){
                        usedCount++;
                    }
                }
                min = Math.min(min,usedCount);
                return ;
            }
            //剪枝已经处理过的情况
            if (visited.contains(new String(chars))){
                return ;
            }
            //记录下当前情况已经处理过
            visited.add(new String(chars));
            //从handUsed所有在handUsed中没有标记的已用过的位置中取一个字符
            for (int idx = 0; idx < handUsed.length; idx++) {
                if (handUsed[idx]){
                    continue;
                }
                //标记已使用
                handUsed[idx] = true;
                //构造所有可能的组合情况
                List<char[]> list = insertChar(chars,hand.charAt(idx));
                for (char[] charArr : list) {
                    //继续递归
                    dfs(reductionChars(charArr),hand,handUsed);
                }
                //回溯标记未使用
                handUsed[idx] = false;
            }
        }
    
        /**
         * 往`char[] chars` 数组中所有能插入的位置插入一个新的字符`c`
         * 如果原来的被 插入位置和当前插入字符相同,只插入到后面一个位置
         * @param chars
         * @param c
         * @return
         */
        public List<char[]> insertChar(char[] chars, char c){
            List<char[]> list = new ArrayList<>();
            int idx = -1;
            while (++idx < chars.length){
                while (chars[idx]==c){
                    idx++;
                }
                char[] newChars = new char[chars.length+1];
                System.arraycopy(chars,0,newChars,0,idx);
                System.arraycopy(chars,idx,newChars,idx+1,chars.length-idx);
                newChars[idx] = c;
                list.add(newChars);
            }
            return list;
        }
    
        /**
         * 删除字符串数组中连续出现次数大于等于3的区段内容
         * @param chars
         * @return
         */
        public char[] reductionChars(char[] chars){
            //记录下当前的长度
            int length = chars.length;
            int idx = 0;
            char lastChar = chars[0];
            int lastCharCount = 1;
            while (++idx < chars.length){
                if (chars[idx] == lastChar){
                    lastCharCount++;
                }else{
                    //当前字符和前一个不同
                    if (lastCharCount>=3){
                        //从当前位置往前删除掉lastCharCount个
                        char[] newChars = new char[chars.length-lastCharCount];
                        System.arraycopy(chars,0,newChars,0,idx-lastCharCount);
                        System.arraycopy(chars,idx,newChars,idx-lastCharCount,chars.length-idx);
                        chars = newChars;
                        idx -= lastCharCount;
                    }
                    lastChar = chars[idx];
                    lastCharCount = 1;
                }
            }
            //如果没有能处理删除掉的字符则直接返回
            //如果长度发生了变化,尝试再处理一次,防止   WWRRRWW 变成了 WWWW后还要再处理一次的情况
            return length == chars.length?chars:reductionChars(chars);
        }
    }

    LeetCode刷题【70】爬楼梯

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

    注意:给定 n 是一个正整数。

    示例 1:

    输入: 2
    输出: 2
    解释: 有两种方法可以爬到楼顶。
    1.  1 阶 + 1 阶
    2.  2 阶

    示例 2:

    输入: 3
    输出: 3
    解释: 有三种方法可以爬到楼顶。
    1.  1 阶 + 1 阶 + 1 阶
    2.  1 阶 + 2 阶
    3.  2 阶 + 1 阶
    
    Related Topics
  • 记忆化搜索
  • 数学
  • 动态规划

  • 👍 1860
  • 👎 0
  • 题解

    本周开始滚动数组,动态规划相关专项练习。本题滚动数组的最明显直接的应用,类似于之前的斐波那契数列那题LeetCode刷题【剑指 Offer 10- I】斐波那契数列

    当用户在第n级台阶的时候,可以由n-1级往上走一级到达,也可以由n-2级往上走2级到达当前的n级。这两个状态是用户到达n级的时候的前一个状态。所以到达n级的时候应当是到达n-1和n-2级的两种情况的可能数量之和

    代码和斐波那契数列几乎一样

    class Solution {
        public int climbStairs(int n) {
            if (n<=3){
                return n;
            }
            int [] arr = new int[n+1];
            arr[1] = 1;
            arr[2] = 2;
            arr[3] = 3;
            int i = 4;
            while (i <=n){
                arr[i] = arr[i-1]+arr[i-2];
                i++;
            }
            return arr[n];
    
        }
    }

    LeetCode刷题【剑指 Offer 10- I】斐波那契数列

    写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:

    F(0) = 0,   F(1) = 1
    F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

    斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

    答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

     

    示例 1:

    输入:n = 2
    输出:1
    

    示例 2:

    输入:n = 5
    输出:5
    

     

    提示:

    • 0 <= n <= 100
    Related Topics
  • 记忆化搜索
  • 数学
  • 动态规划

  • 👍 230
  • 👎 0
  • 题解

    9月4日的每日一题,周末没写,

    接单题目,但是不简单其实

    根据题意可以直接知道,用下面这个递归就可以实现。但是实际按照这个直接递归了来写的话会直接超时。

    F(N) = F(N - 1) + F(N - 2)

    那么就有了以下这段代码

    class Solution {
        public int fib(int n) {
            if (n==0){
                return 0;
            }
            if (n==1){
                return 1;
            }
            int[] res = new int[n+1];
            res[0] = 0;
            res[1] = 1;
            int i = 2;
            while ( i <= n ){
                res[i] = (res[i-1] + res[i-2]) % 1000000007;
                i++;
            }
            return res[n];
        }
    }

    emmm、直观来说就是改递归为while遍历,但是这个res数组已经有一点滚动数组的味道了。但是这边我们其实可以看到,当到达i的时候 i-2之前的所有值都已经没有存在的意义了,所以还可以再优化下内存使用率的情况。如下:

    class Solution {
        public int fib(int n) {
            if (n==0){
                return 0;
            }
            if (n==1){
                return 1;
            }
            int a = 0;
            int b = 1;
            int i = 2;
            while ( i <= n ){
                if (i%2==0){
                    a = (a+b) % 1000000007;
                }else{
                    b = (a+b) % 1000000007;
                }
                i++;
            }
            return n%2==0?a:b;
        }
    }