算法 2.5 贪心算法：行相等的最少多米诺旋转【leetcode

2021-02-25  本文已影响0人  珺王不早朝

题目描述

在一排多米诺骨牌中，A[i] 和 B[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分
一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字
我们可以旋转第 i 张多米诺，使得 A[i] 和 B[i] 的值交换
返回能使 A 中所有值或者 B 中所有值都相同的最小旋转次数
如果无法做到，返回 -1

示例：
输入：A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
输出：2

示例：
输入：A = [3,5,1,2,3], B = [3,6,3,3,4]
输出：-1

数据结构

算法思维

关键知识点：贪心算法（greedy algorithm）

核心理念
求解步骤
  1. 创建数学模型来描述问题
  2. 把求解的问题分成若干个子问题
  3. 对每一子问题求解，得到子问题的局部最优解
  4. 把子问题的解合并成原来问题的一个解

解题步骤

一. Comprehend 理解题意
行相等的最小多米诺旋转
细节问题
二. Choose 选择数据结构与算法
数据结构选择
算法思维选择
三. Code 编码实现基本解法
解题思路剖析
代码实现
class Solution {
    public int minDominoRotations1(int[] A, int[] B) {
        int n = A.length;
        //记录1-6数字分别在A，B中出现的次数、在多米诺骨牌出现的次数
        int[] countA = new int[6];
        int[] countB = new int[6];
        int[] countAB = new int[6];
        
        //遍历骨牌，统计出现次数
        for (int i = 0; i < n; i++) {
            countA[A[i] - 1]++;
            countB[B[i] - 1]++;
            countAB[A[i] - 1]++;
            if (A[i] != B[i])
                countAB[B[i] - 1]++;
        }
        
        //在骨牌统计表找到出现次数等于骨牌总数的数字
        for (int i = 0; i < 6; i++) {
            if (countAB[i] == n) { //计算最小的旋转次数
                return (n - Math.max(countA[i], countB[i]));
            }
        }

        //找不到返回-1
        return -1;
    }
}

时间复杂度：O(n)
  • 统计 1 - 6 数字出现的次数，遍历多米诺骨牌 O(n)
  • 寻找在所有多米诺骨牌出现的数字及最小多米诺旋转，需要对 6×3 数组进行操作 O(1)

空间复杂度：O(1)
  • 常数级变量空间 O(1)

执行耗时：7 ms，击败了 33.33% 的Java用户
内存消耗：46.1 MB，击败了 85.16% 的Java用户

四. Consider 思考更优解
剔除无效代码 优化空间消耗
寻找更好的算法思维
贪心算法
  1. 创建数学模型来描述问题
    • 给定两个由 1-6 数字组成的数组 A 和 B
    • 通过多米诺旋转（交换 A[i] 和 B[i] ），使得 A 或 B 中元素全部相同
    • 要求进行尽可能少的交换来完成任务
  2. 划分子问题
    最小多米诺旋转如果存在，一定是下面两种情况中的一种：
    • 将 A 或 B 中的元素全部变成 A[0]
    • 将 A 或 B 中的元素全部变成 B[0]
  1. 求解子问题
    • 尝试将A中的元素全部变成A[0]
      • 需要交换(A[1], B[1])，(A[3], B[3])
      • 执行2次多米诺旋转操作
    • 再尝试将B中的元素全部变成A[0]
      • 需要交换(A[0], B[0])，(A[2], B[2]) ，(A[4], B[4])
      • 执行3次多米诺旋转操作
    • 尝试将A中的元素或B中的元素全部变成B[0]
      • 很快发现第二张牌的两个数字没有5，那么不可能将A中或B中元素全部变成B[0]
  2. 合并子问题的解
    • 尝试将A中的元素全部变成A[0]
      执行2次多米诺旋转操作
    • 再尝试将B中的元素全部变成A[0]
      执行3次多米诺旋转操作
    • 尝试将A中的元素或B中的元素全部变成B[0]
      不可能将A中或B中元素全部变成B[0]

综上最小多米诺旋转次数为 2

五. Code 编码实现最优解
解题思路剖析
class Solution {
    public int minDominoRotations(int[] A, int[] B) {
        int n = A.length;
        int rotations = check(A[0], A, B, n);//元素全部变成A[0]，最少需要多少次旋转

        //如果A[0]==B[0], 那么不用继续检查B[0]
        //如果A[0]!=B[0] 且可以将A或B中的元素全部变成A[0]，那么也不用再检查B[0]
        if (rotations != -1 || A[0] == B[0])
            return rotations;
        else
            return check(B[0], A, B, n); //全部变成B[0]，最少需要多少次旋转
    }

    //检查将A或者B中元素全部变成x需要多少次旋转
    public int check(int x, int[] A, int[] B, int n) {
        //rotationsA存将A中元素变成x需要多少次旋转，rotationsB存将B中元素变成x需要多少次旋转
        int rotationsA = 0, rotationsB = 0;

        //遍历骨牌判断是否能完成任务（在A中完成或者在B中完成）
        for (int i = 0; i < n; i++) {
            // 如果当前多米诺骨牌上没有数字x，那么不可能完成任务
            if (A[i] != x && B[i] != x) return -1;
            // 如果当前多米诺骨牌上A[i]不是x，那么rotationsA需要+1
            else if (A[i] != x) rotationsA++;
            // 如果当前多米诺骨牌上B[i]不是x，那么rotationsB需要+1
            else if (B[i] != x) rotationsB++;
        }
        
        // 返回最小旋转次数
        return Math.min(rotationsA, rotationsB);
    }
}

时间复杂度：O(n)
  • 最差情况：需要遍历所有骨牌 O(n)

空间复杂度：O(1)
  • 常数级内存空间 O(1)

执行耗时：4 ms，击败了 99.06% 的Java用户
内存消耗：46.2 MB，击败了 77.42% 的Java用户

六. Change 变形与延伸
题目变形
延伸扩展
上一篇下一篇

猜你喜欢

热点阅读