956. 最高的广告牌

简介: 956. 最高的广告牌
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

前言

你正在安装一个广告牌,并希望它高度最大。这块广告牌将有两个钢制支架,两边各一个。每个钢支架的高度必须相等。

你有一堆可以焊接在一起的钢筋 rods。举个例子,如果钢筋的长度为 1、2 和 3,则可以将它们焊接在一起形成长度为 6 的支架。

返回 广告牌的最大可能安装高度 。如果没法安装广告牌,请返回 0

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/tallest-billboard
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

定义一个map
key:随意选两个子集产生的差值
在数组没有遍历之前,能够找到两个集合, 空集对空集,差值为0
value:有可能会有多个集合对产生同样的差值,记录产生当前差值那一对较好那一对集合较小的那个
在这里插入图片描述

谁的值大,谁是较好的一对
关心谁?基线最高的那个

在这里插入图片描述
3出现了,加工出map:在只考虑3的情况下,会有哪些差值产生

在这里插入图片描述

我老map是所有可能的集合所有可能的插值中最好的一对。
我新map是考虑了当前数字,对每一个老的集合接近左进右出来的新纪录。
我最终的新map怎么合并?老map和新map中的记录,综台起来,最好的变成新map,继续往下推。
当你推过了所有的数字,最终的map你看差值为0的最好一对就是你要的

为什么map中把所有差值都要记录?
那是因为你后面不知道会遇到什么数字。
举个例子,你最后一个数是一百万, 特别大,极大,它左边的数都没它大,但它是一百万。在来到1百万之前,我这个map千变万化,map中有可能有一 个差值是1百万,基线相当的高。
你遇到最后一个数字的时候,它1百万的差值代表什么?
比如说在你来到最后数字之前map里面有一个插值是1百万的基线10亿,
这说明有一一个集合它{10亿+ 100万},还有集合叫{10亿}。这时候你的一百万进去,
正好怼出一个差值为零的来。
所以为什么map要记录所有的差值,你不知道后面哪一个奇葩数能拱出大的来,
我不知道后面有什么奇葩的数,能让我一个重新插值为季的集合基线变得巨大,
不知道,所以我都留着。

代码

class Solution {
    public int tallestBillboard(int[] rods) {
        HashMap<Integer,Integer> dp=new HashMap<>(),cur;
        dp.put(0,0);
        for(int num:rods){
            if(num!=0){
                cur=new HashMap<>(dp);
                for(int d:cur.keySet()){
                    int diffMore=cur.get(d);
                    dp.put(d + num, Math.max(diffMore, dp.getOrDefault(num + d, 0)));
                    int diffXD=dp.getOrDefault(Math.abs(num-d),0);
                    if(d>=num){
                        dp.put(d-num,Math.max(diffMore+num,diffXD));
                    }else{
                        dp.put(num-d,Math.max(diffMore+d,diffXD));
                    }
                }
            }
        }
        return dp.get(0);
    }
}
相关文章
|
Kubernetes API 调度
Kubernetes必备知识: CNI
CNI的全称是 Container Network Interface,即容器网络的 API 接口。 它是 K8s 中标准的一个调用网络实现的接口。Kubelet 通过这个标准的 API 来调用不同的网络插件以实现不同的网络配置方式。实现了这个接口的就是 CNI 插件,它实现了一系列的 CNI API 接口。常见的 CNI 插件包括 Calico、flannel、Terway、Weave Net 以及 Contiv。
2256 0
Kubernetes必备知识: CNI
|
9月前
|
JavaScript 前端开发 Java
解决跨域问题大集合:vue-cli项目 和 java/springboot(6种方式) 两端解决(完美解决)
这篇文章详细介绍了如何在前端Vue项目和后端Spring Boot项目中通过多种方式解决跨域问题。
569 1
解决跨域问题大集合:vue-cli项目 和 java/springboot(6种方式) 两端解决(完美解决)
|
11月前
|
机器学习/深度学习 自然语言处理 算法
深度学习之量子神经网络
深度学习的量子神经网络(Quantum Neural Networks,QNN)是量子计算和深度学习的结合,旨在利用量子计算的独特特性来提升神经网络的性能。
541 0
|
11月前
|
机器学习/深度学习 人工智能 自然语言处理
AI在创造还是毁掉音乐?——探索人工智能对音乐创作的影响
在当今数字化时代,人工智能(AI)技术的快速发展不仅改变了我们的生活方式和工作方式,也在音乐创作领域引发了广泛的讨论和热议。最近,随着各类音乐生成AI模型的涌现,人们开始探讨AI在音乐创作中的作用,以及它对传统音乐产业的潜在影响。
766 5
io_uring之liburing库安装
io_uring之liburing库安装
967 0
|
11月前
|
应用服务中间件 Apache nginx
【独家揭秘】502 Bad Gateway不再神秘!五大绝招教你快速定位并解决,从此告别网络烦恼!
【8月更文挑战第19天】遇到502 &quot;Bad Gateway&quot;错误让不少开发者头疼。此错误指示Web服务器作为代理收到无效响应。本文将分步骤指导如何排查与解决502问题:首先检查服务器日志文件寻找线索;接着验证后端服务器状态及连通性;然后审查Web服务器配置确保代理设置无误;再检测后端服务器响应时间避免超时;最后利用抓包工具深入分析网络通信。遵循这些步骤,可助你高效定位并解决502错误。
1803 0
|
Python
Python实现万花筒效果:创造炫目的动态图案
Python实现万花筒效果:创造炫目的动态图案
220 2
|
人工智能 JSON 文字识别
开源VLM新标杆 InternVL 2.0 怎么用?部署、微调尽在魔搭社区!
7月4日下午,世界人工智能大会科学前沿论坛,上海人工智能实验室OpenGVLab发布了InternVL 2.0 版本,中文名书生·万象。
|
设计模式 编解码 程序员
探索 C++ 20 (co_await、co_yield 和 co_return)协程基本框架的使用
探索 C++ 20 (co_await、co_yield 和 co_return)协程基本框架的使用
1223 2
探索 C++ 20 (co_await、co_yield 和 co_return)协程基本框架的使用
|
前端开发 JavaScript IDE
WebStorm 打开多个项目的方法
【2月更文挑战第1篇】
1124 2
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问