脑筋急转弯_leetcode.1033.移动石子直到连续

发表于 | 分类于 ， | 热度: ℃
字数统计: 2.6k | 阅读时长 ≈ 10

哎，最近忙着ACM和蓝桥杯（毕竟都是第一次参赛的小白），可把自己整迷糊了，当两项比赛全部告一段落，自己才是真的觉悟到自己与别人的差距以及自己的大脑思考问题的能力很是欠缺，还有就是思考不够全面，往往一道题明明自己已经写出了方法，但硬是在比赛途中想不出一种有效的方法去优化方法和更快的得出答案，总是赛后诸葛亮的想出这该怎么做，那该怎么做，这些欠缺都导致自己在ACM和蓝桥杯中丢失得分，看来还是得努力呀，不让自己变得更强又何能征战星辰大海呢，先来练练思维能力吧，从最简单的脑筋急转弯开始！

🌸题目

🍁三枚石子放置在数轴上，位置分别为 a，b，c。

每一回合，我们假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。

当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。

要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves]

示例 1：

1
2
3
4
5
6
7
8
输入：a = 1, b = 2, c = 5
输出：[1, 2]
解释：将石子从 5 移动到 4 再移动到 3，或者我们可以直接将石子移动到 3。
示例 2：

输入：a = 4, b = 3, c = 2
输出：[0, 0]
解释：我们无法进行任何移动。

提示：

  • 1 <= a <= 100
  • 1 <= b <= 100
  • 1 <= c <= 100
  • a != b, b != c, c != a

🌸解法：分类讨论

这道题给出的数据并没有直接给你排好序了的，他的数据顺序是乱的（这是一个小小的坑）

假设已经排好序了那么要求出最大次数和最小次数，即

  • 最大次数，无疑就是一步一步的走，即最后一个元素减去第一个元素 再减二（这很好推断，自己画一个数轴就知道了）
  • 最小次数，只能是1或者2，这就要分类讨论了
    • 最小次数为一，即只需要动一步，即已经有两个数是连续的了或者两个数之间只有一个空的时候,例如 1 2 5、1 3 5。
    • 最小次数为二，即除上面情况之后的所有情况

代码就很好得出了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Text {
	public static void main(String[] args) {
		
	}
    public int[] numMovesStones(int a, int b, int c) {
    	int max = Math.max(Math.max(a, b), c);//找到最大值
    	int min = Math.min(Math.min(a, b), c);//找到最小值
    	int cur = a + b + c - max - min; // 找到中间那个数
    	if(max - cur == 1 && cur - min == 1) { //如果已经是连续的了，则不用移动
    		return new int[]{0, 0};
    	}
    	if(max - cur <= 2 || cur - min <= 2) { //不连续但是有其中两个中间只有一个位置时候例如：1 3 4 、 1 3 5，都只需要最小移动一次即可连续
    		return new int[] {1, max - min - 2};
    	}else {//否则最少移动两次才可以连续
    		return new int[] {2, max - min - 2};
    	}
    }
}

🌸题目

你和你的朋友，两个人一起玩 Nim 游戏：

桌子上有一堆石头。
你们轮流进行自己的回合，你作为先手。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
j假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

示例1：

1
2
3
4
输入：n = 4
输出：false 
解释：如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿

走。
示例 2：

1
2
3
4
5
6
输入：n = 1
输出：true
示例 3：

输入：n = 2
输出：true

提示：

  • 1 <= n <= 2^31 - 1

🌸解法一：记忆化递归

  • 为什么在两个人「足够聪明」（你们是聪明人，每一步都是最优解）这个前提下，比赛的结果是「由输入数据确定的」

用具体的例子 8 进行分析可以得出结论：

当 N = 3 的时候，当前做出选择的人可以拿掉最后一块石头，获得胜利；
然后我们逐层向上分析，当 N = 4的时候，无论当前做出哪一种选择，对方都会赢，所以当前只能输掉比赛；
如果当前这一层的结点里「有输有赢」，因为我们「足够聪明」，所以必须选择可以让对方输掉的分支，好让自己赢；
对于这个问题的特点是，当 N不是 4 的倍数的时候，先手（当前做出选择的人），或者说游戏一开始做出选择的玩家一定会输。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean canWinNim(int n) {
    // 使用包装类型的布尔数组，可以用 null 这个状态，表示当前 n 的结果还没有被计算出来
    Boolean[] memo = new Boolean[n + 1];
    return dfs(n, memo);
}

private boolean dfs(int n, Boolean[] memo) {
    if (n <= 3) {
        return true;
    }

    if (memo[n] != null) {
        return memo[n];
    }

    // 如果 3 种选择，只要有一种对方输掉，自己就可以赢
    if (!dfs(n - 1, memo) || !dfs(n - 2, memo) || !dfs(n - 3, memo)) {
        memo[n] = true;
        return true;
    }
    // 否则自己输
    memo[n] = false;
    return false;
}

🌸解法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean canWinNim(int n) {
    if (n <= 3) {
        return true;
    }

    boolean[] dp = new boolean[n + 1];

    // dp[0] 的值可以不管，没有意义
    dp[1] = true;
    dp[2] = true;
    dp[3] = true;
    for (int i = 4; i <= n; i++) {
        dp[i] = !dp[i - 1] || !dp[i - 2] || !dp[i - 3];
    }
    return dp[n];
}

滚动数组优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean canWinNim(int n) {
    if (n <= 3) {
        return true;
    }

    boolean[] dp = new boolean[4];
    dp[0] = false;
    dp[1] = true;
    dp[2] = true;
    dp[3] = true;
    for (int i = 4; i <= n; i++) {
        dp[i % 4] = !dp[(i - 1) % 4] || !dp[(i - 2) % 4] || !dp[(i - 3) % 4];
    }
    return dp[n % 4];
}

🌸解法三：数学方法

让我们考虑一些小例子。显而易见的是，如果石头堆中只有一块、两块、或是三块石头，那么在你的回合，你就可以把全部石子拿走，从而在游戏中取胜。而如果就像题目描述那样，堆中恰好有四块石头，你就会失败。因为在这种情况下不管你取走多少石头，总会为你的对手留下几块，使得他可以在游戏中打败你。因此，要想获胜，在你的回合中，必须避免石头堆中的石子数为 4 的情况。

同样地，如果有五块、六块、或是七块石头，你可以控制自己拿取的石头数，总是恰好给你的对手留下四块石头，使他输掉这场比赛。但是如果石头堆里有八块石头，你就不可避免地会输掉，因为不管你从一堆石头中挑出一块、两块还是三块，你的对手都可以选择三块、两块或一块，以确保在再一次轮到你的时候，你会面对四块石头。

显然，它以相同的模式不断重复 n=4,8,12,16,…，基本可以看出是 4 的倍数。

1
2
3
public boolean canWinNim(int n) {
    return (n % 4) != 0;
}

可怕可怕。。。

🌸题目

给你两个字符串，请你从这两个字符串中找出最长的特殊序列。

「最长特殊序列」定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。

子序列 可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。

输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。

示例 1：

1
2
3
输入: "aba", "cdc"
输出: 3
解释: 最长特殊序列可为 "aba" (或 "cdc")，两者均为自身的子序列且不是对方的子序列。

示例 2：

1
2
输入：a = "aaa", b = "bbb"
输出：3

示例 3：

1
2
输入：a = "aaa", b = "aaa"
输出：-1

提示：

  • 两个字符串长度均处于区间 [1 - 100] 。
  • 字符串中的字符仅含有 ‘a’~’z’ 。

🌸解法一：暴力解法

暴力解法中，生成两个字符串所有的子序列共 2^n
个，将其存储在 hashmap 中，并记录每个子序列出现的次数。然后找出出现次数为 11 的最长子序列。如果不存在这样的子序列，返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int findLUSlength(String a, String b) {
    HashMap < String, Integer > map = new HashMap < > ();
    for (String s: new String[] {a, b}) {
        for (int i = 0; i < (1 << s.length()); i++) {
            String t = "";
            for (int j = 0; j < s.length(); j++) {
                if (((i >> j) & 1) != 0)
                    t += s.charAt(j);
            }
            if (map.containsKey(t))
                map.put(t, map.get(t) + 1);
            else
                map.put(t, 1);
        }
    }
    int res = -1;
    for (String s: map.keySet()) {
        if (map.get(s) == 1)
            res = Math.max(res, s.length());
    }
    return res;
}

🌸解法二：寻找规律

字符串 a 和 b 共有 3 种情况：

  • a=b。如果两个字符串相同，则没有特殊子序列，返回 -1。

  • length(a)=length(b) 且 a != b。例如：abc 和 abd。这种情况下，一个字符串一定不会是另外一个字符串的子序列，因此可以将任意一个字符串看作是特殊子序列，返回 length(a) 或 length(b)

  • length(a)> =length(b)。例如：abcd 和 abc。这种情况下，长的字符串一定不会是短字符串的子序列，因此可以将长字符串看作是特殊子序列，返回 max(length(a),length(b))。

1
2
3
4
5
6
7
public int findLUSlength(String a, String b) {
    if(a.equals(b)){
        return -1;
    }else{
        return Math.max(a.length(), b.length());
    }
}

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！

-------------本文结束感谢您的阅读-------------
云澈 wechat
扫一扫，用手机访问哦
坚持原创技术分享，您的支持将鼓励我继续创作！
0%