首页 > 其他分享 >力扣——554砖墙(c语言)

力扣——554砖墙(c语言)

时间:2023-04-22 14:01:44浏览次数:43  
标签:joints hash int 554 力扣 砖块 砖墙 brick

title: 力扣——554砖墙(c语言)
题目描述:
你的面前有一堵矩形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。
砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。
如果你画的线只是从砖块的边缘经过,就不算穿过这块砖。你需要找出怎样画才能使这条线穿过的砖块数量最少,并且返回穿过的砖块数量。
你不能沿着墙的两个垂直边缘之一画线,这样显然是没有穿过一块砖的。

示例:
输入: [[1,2,2,1],
      [3,1,2],
      [1,3,2],
      [2,4],
      [3,1,2],
      [1,3,1,1]]
输出: 2

提示:
每一行砖块的宽度之和应该相等,并且不能超过 INT_MAX。
每一行砖块的数量在 [1,10,000] 范围内, 墙的高度在 [1,10,000] 范围内, 总的砖块数量不超过 20,000。

思路:

穿过的砖数最少,即穿过的砖缝最多。

1、怎么统计砖缝?

记录每块砖的位置,用hash表统计每块砖的砖缝。

brick_pos += wall[i][j];
hash_brick_joints[brick_pos]++;

2、哪条砖缝最多?

一直记录砖缝最大值。

if(max_brick_joints < hash_brick_joints[brick_pos]){
	max_brick_joints = hash_brick_joints[brick_pos];
}

代码如下:

#define INT_MAX 20000000

/*
*传入参数:wall,砖墙的列表;wallsize,砖墙的行数;wallColSize,每行砖的数目。
*/
int leastBricks(int** wall, int wallSize, int* wallColSize){
    int i, j;
    int brick_pos, max_brick_joints = 0;
    int hash_brick_joints[INT_MAX] = {0};
    for(i=0; i<wallSize; ++i)
    {
        brick_pos = 0;
        for(j=0; j<wallColSize[i]-1; ++j)
        {
            brick_pos += wall[i][j];
            hash_brick_joints[brick_pos]++;

            if(max_brick_joints < hash_brick_joints[brick_pos]){
                max_brick_joints = hash_brick_joints[brick_pos];
            }
        }
    }
    return wallSize - max_brick_joints;
}

执行结果(待提高):

通过

显示详情

执行用时:1060 ms, 在所有 C 提交中击败了5.09%的用户

内存消耗:84.7 MB, 在所有 C 提交中击败了5.11%的用户

标签:joints,hash,int,554,力扣,砖块,砖墙,brick
From: https://www.cnblogs.com/blue-Suri/p/17342950.html

相关文章

  • 力扣——6.动态规划
    title:动态规划6、最长上升子序列(1)采用动态规划,算法复杂度为O(n*n)intlengthOfLIS(int*nums,intnumsSize){inti,j,max=1;if(NULL==nums||0==numsSize){return0;}int*dp=(int*)malloc(numsSize*sizeof(int));memset(dp,0,nu......
  • 力扣——21.合并两个有序链表(c语言)
    title:力扣——21.合并两个有序链表(c语言)将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例:输入:1->2->4,1->3->4输出:1->1->2->3->4->41、递归实现:/***Definitionforsingly-linkedlist.*structListNode{......
  • 力扣——83.删除排序链表中的重复元素(c语言)
    title:力扣——83.删除排序链表中的重复元素(c语言)题目描述:给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。示例1:输入:1->1->2输出:1->2示例2:输入:1->1->2->3->3输出:1->2->3代码如下:/***Definitionforsingly-linkedlist.*structListNode{*......
  • 力扣——121.买卖股票的最佳时机(C语言)
    title:力扣——121.买卖股票的最佳时机(C语言)题目描述:给定一个数组,它的第i个元素是一支给定股票第i天的价格。如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。注意:你不能在买入股票前卖出股票。示例1:输入:[7,1,5,3,6,......
  • 力扣——193.有效电话号码(shell)
    title:力扣——193.有效电话号码(shell)给定一个包含电话号码列表(一行一个电话号码)的文本文件file.txt,写一个bash脚本输出所有有效的电话号码。你可以假设一个有效的电话号码必须满足以下两种格式:(xxx)xxx-xxxx或xxx-xxx-xxxx。(x表示一个数字)你也可以假设每行前后没有......
  • 力扣——192.统计词频(shell)
    title:力扣——192.统计词频(shell)题目描述:写一个bash脚本以统计一个文本文件words.txt中每个单词出现的频率。为了简单起见,你可以假设:words.txt只包括小写字母和''。每个单词只由小写字母组成。单词间由一个或多个空格字符分隔。示例:假设words.txt内容如下:th......
  • 力扣——195.第十行(shell)
    title:力扣——195.第十行(shell)给定一个文本文件file.txt,请只打印这个文件中的第十行。示例:假设file.txt有如下内容:Line1Line2Line3Line4Line5Line6Line7Line8Line9Line10你的脚本应当显示第十行:Line10方法1:awk'NR==10'file.txt方法2:tai......
  • 力扣——240.搜索二维数组II(c语言)
    title:力扣——240.搜索二维数组II(c语言)同《剑指offer》04题目描述:编写一个高效的算法来搜索mxn矩阵matrix中的一个目标值target。该矩阵具有以下特性:每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例1:输入:matrix=[[1,4,7,11,15],[2,5,8,12,19],......
  • 力扣——5.最长回文子串(c语言)
    题目描述:给定一个字符串s,找到s中最长的回文子串。你可以假设s的最大长度为1000。示例1:输入:"babad"输出:"bab"注意:"aba"也是一个有效答案。示例2:输入:"cbbd"输出:"bb"1、思路1:动态规划对于一个子串而言,如果它是回文子串,并且长度大于2,那么将它首尾两个字......
  • 力扣 406. 根据身高重建队列
    406.根据身高重建队列假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i]=[hi,ki] 表示第 i 个人的身高为 hi ,前面 正好 有 ki 个身高大于或等于 hi 的人。请你重新构造并返回输入数组 people 所表示......