当前位置: 首页 > news >正文

西安建设工程中心交易网站长尾关键词挖掘工具

西安建设工程中心交易网站,长尾关键词挖掘工具,大型网站建设费用,wordpress版本不一致如何更换空间文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目 标题和出处 标题:砖墙 出处:554. 砖墙 难度 5 级 题目描述 要求 你的面前有一堵矩形的、由 n\texttt{n}n 行砖块组成的砖墙。这些砖块高度相同&#xff08…

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:砖墙

出处:554. 砖墙

难度

5 级

题目描述

要求

你的面前有一堵矩形的、由 n\texttt{n}n 行砖块组成的砖墙。这些砖块高度相同(也就是一个单位高)但是宽度不同。每一行砖块的宽度之和相等。

你现在要画一条自顶向下的、穿过最少砖块的垂线。如果你画的线只是从砖块的边缘经过,就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线,这样显然是没有穿过一块砖的。

给你一个二维数组 wall\texttt{wall}wall,该数组包含这堵墙的相关信息。其中,wall[i]\texttt{wall[i]}wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线穿过的砖块数量最少,并且返回穿过的砖块数量

示例

示例 1:

示例 1

输入:wall=[[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]\texttt{wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]}wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
输出:2\texttt{2}2

示例 2:

输入:wall=[[1],[1],[1]]\texttt{wall = [[1],[1],[1]]}wall = [[1],[1],[1]]
输出:3\texttt{3}3

数据范围

  • n=wall.length\texttt{n} = \texttt{wall.length}n=wall.length
  • 1≤n≤104\texttt{1} \le \texttt{n} \le \texttt{10}^\texttt{4}1n104
  • 1≤wall[i].length≤104\texttt{1} \le \texttt{wall[i].length} \le \texttt{10}^\texttt{4}1wall[i].length104
  • 1≤sum(wall[i].length)≤2×104\texttt{1} \le \texttt{sum(wall[i].length)} \le \texttt{2} \times \texttt{10}^\texttt{4}1sum(wall[i].length)2×104
  • 对于每一行 i\texttt{i}isum(wall[i])\texttt{sum(wall[i])}sum(wall[i]) 是相同的
  • 1≤wall[i][j]≤231−1\texttt{1} \le \texttt{wall[i][j]} \le \texttt{2}^\texttt{31} - \texttt{1}1wall[i][j]2311

解法

思路和算法

任意一条垂线在每一行都是穿过砖块或者从砖块的边缘经过,且穿过砖块的数量与从砖块的边缘经过的数量之和一定等于砖墙的行数 nnn。为了找到穿过最少砖块的垂线,应该找到经过最多的砖块边缘的垂线,砖墙的行数与该垂线经过的砖块边缘的数量之差即为穿过的砖块数量的最小值。

为了找到经过最多的砖块边缘的垂线,需要统计从砖墙左端开始的所有不同距离的砖块边缘的数量,并用哈希表记录所有距离对应的砖块边缘的数量。

对于砖墙的每一行,从左到右遍历每一块砖,并维护砖块宽度之和,砖块宽度之和即为当前砖块的右边缘与砖墙左端的距离。对于每一块砖,将其宽度加到砖块宽度之和中,并将更新后的砖块宽度之和在哈希表中的次数加 111。由于不能沿着墙的两个垂直边缘之一画线,因此每一行的最后一块砖不用遍历。

由于题目没有要求得到画线的位置,只要求得到穿过的砖块数量的最小值,因此在遍历结束砖墙的全部行之后,只需要从哈希表中得到砖块边缘数量的最大值,不需要得到砖块边缘与砖墙左端的距离。得到砖块边缘数量的最大值之后,计算砖墙的行数与砖块边缘数量的最大值之差,即为穿过的砖块数量的最小值。

代码

class Solution {public int leastBricks(List<List<Integer>> wall) {int n = wall.size();Map<Long, Integer> map = new HashMap<Long, Integer>();for (List<Integer> row : wall) {long sum = 0;int bricks = row.size();for (int i = 0; i < bricks - 1; i++) {sum += row.get(i);map.put(sum, map.getOrDefault(sum, 0) + 1);}}int maxCount = 0;Set<Map.Entry<Long, Integer>> entries = map.entrySet();for (Map.Entry<Long, Integer> entry : entries) {int count = entry.getValue();maxCount = Math.max(maxCount, count);}return n - maxCount;}
}

复杂度分析

  • 时间复杂度:O(mn)O(mn)O(mn),其中 mmm 是砖墙每一行的平均砖块数量,nnn 是砖墙的行数。需要遍历砖墙中的每一行的除了最后一块砖的每块砖,并用哈希表记录每块砖的右边缘与砖墙左端的距离和次数。

  • 空间复杂度:O(mn)O(mn)O(mn),其中 mmm 是砖墙每一行的平均砖块数量,nnn 是砖墙的行数。需要使用哈希表记录每一行的除了最后一块砖的每块砖的右边缘与砖墙左端的距离和次数。

http://www.ritt.cn/news/24441.html

相关文章:

  • 做 ps pr 赚钱的 网站东莞网站推广及优化
  • 购物网站开店免费网站排名优化培训
  • 短视频软件seo入门教程
  • 免费网站优化今日头条新闻推荐
  • 外贸网站建设升上去湛江seo推广公司
  • 旅游网站开发的背景百度渠道开户哪里找
  • 贷款公司通过做网站来给予平台贷款万网官网域名查询
  • 邯郸公司网站建设短链接生成器
  • 网站开发的甘特图百度怎么投广告
  • 动态网站如何打开代写文章
  • 哪些行业做网站的多做网站企业
  • 无人区电影中加油站司机网络平台推广具体是怎么推广
  • 中国机械加工外协网seo技术服务外包公司
  • 邯郸市教育局官网seo和sem的区别
  • 给银行做网站培训行业seo整站优化
  • 智慧团建电脑版登录入口seo助理
  • 品牌好的佛山网站建设价格收录网
  • 泰安做网络推广的公司个人做seo怎么赚钱
  • 网站开发需要经历哪些主要阶段嘉兴网站建设
  • 公司网站后台维护怎么做seo应用领域有哪些
  • 王璞网站开发实战十大搜索引擎神器
  • b2b怎么开通网站seo排名
  • 西安政府网站建设公司哪家好怎么制作一个网页
  • 移动互联和网站开发成都网络推广外包
  • 宁波网站建设详细策划制作一个网站的基本步骤
  • 武汉网站建设027best国内新闻摘抄2022年
  • 网站收录就是没排名seo网站页面优化包含
  • 做网站爱网站推广营销
  • 做网站时无法上传图片广点通广告平台
  • 网站进度条搜索引擎优化怎么做的