算法总结 - 数组 -贪心算法

标签: 算法总结

1007. Minimum Domino Rotations For Equal Row

题目链接
In a row of dominoes, A[i] and B[i] represent the top and bottom halves of the i-th domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)

We may rotate the i-th domino, so that A[i] and B[i] swap values.

Return the minimum number of rotations so that all the values in A are the same, or all the values in B are the same.

If it cannot be done, return -1.

Example 1:

在这里插入图片描述

Input: A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
Output: 2
Explanation:
The first figure represents the dominoes as given by A and B: before we do any rotations.
If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.
Example 2:

Input: A = [3,5,1,2,3], B = [3,6,3,3,4]
Output: -1
Explanation:
In this case, it is not possible to rotate the dominoes to make one row of values equal.

Note

1 <= A[i], B[i] <= 6
2 <= A.length == B.length <= 20000


Abstract
有两行骰子, 每行个数一样多
可以把两行骰子在某个index上的位置互换
求最少经过多少次操作以后,可以让两行骰子里面的某一行的值都是一样的

Idea
贪心,检查数组里每一个元素,尽量选择用较少的反转就能达到目的的元素

Question to ask
在什么情况下可以确认某个骰子的值可以达到目标

Solution
维护三个map,

  • 一个记录第一行筛子中某数值出现的次数(mapA)
  • 一个记录第二行筛子中出现数值的次数
  • 最后一个记录某一个数值在第一行和第二行的index相等的次数(same)
    那么如果某一个数值的骰子可以通过交换同一列的骰子而达到都在一行的目的那么它必须满足一下的条件:
    mapA.get(i) + mapB.get(i) - same.get(i) == A.length
    之后就选择比较小的交换次数(min(mapA.get(i), mapB.get(i))),然后全局更新最小值即可。

Time Complexity
O(n)

Space Complexity
O(n)

Code

public int minDominoRotations(int[] A, int[] B) {
    Map<Integer, Integer> mapA = new HashMap<>();
    Map<Integer, Integer> mapB = new HashMap<>();
    Map<Integer, Integer> same = new HashMap<>();

    int min = Integer.MAX_VALUE;
    
    for (int i = 0; i < A.length; i++){
        mapA.put(A[i], mapA.getOrDefault(A[i], 0) + 1);
        mapB.put(B[i], mapB.getOrDefault(B[i], 0) + 1);
        if (A[i] == B[i]) same.put(B[i], same.getOrDefault(B[i], 0) + 1);
        //m1
        if (mapA.getOrDefault(A[i], 0) == A.length || B.length == mapB.getOrDefault(B[i], 0)){
            return 0;
        }
    }
    
    for (int i = 0; i < A.length; i++){
        // m2
        int cnt = mapA.get(A[i]) + mapB.getOrDefault(A[i], 0) - same.getOrDefault(A[i], 0);
        if (cnt == A.length && mapA.containsKey(A[i]) && mapB.containsKey(A[i])) {
            min = Math.min(min, Math.min(mapA.get(A[i]), mapB.get(A[i])) - same.getOrDefault(A[i], 0));
        }
    }
    return min == Integer.MAX_VALUE? -1 : min;
}

Mistake
1:如果input数组本来就有一行的筛子数相同,要进行检查short cut
2. 要么使用 map.getOrDefault() 要么检查map.containsKey(),避免出现null point情况

Summary
需要有抽象思维,把问题全局化和数学化

版权声明:本文为regina14原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/regina14/article/details/105873455

智能推荐

说说 Python Django 应用的基础目录结构

通过以下 django-admin 指令创建应用之后,就会生成应用的基础目录结构。 比如,我们建立了一个叫 ‘first’ 的应用,它的目录结构是这样的: 目录或文件 说明 最外层的 first/ 这是新应用的根目录,所有与该应用相关的内容都放在这里。 manage.py 用于管理 Django 项目的命令行工具。 里面一层的 first/ 目录 是一个...

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

猜你喜欢

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...

力扣困难难度 第4题 寻找两个正序数组的中位数

先看一眼题 我的思路: 设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。 ·每次比较nums[i]nums[j],如果前者小则i++,否则j++ ·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以...