前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【Leetcode -598.范围求和Ⅱ -599.两个列表的最小索引总和】

【Leetcode -598.范围求和Ⅱ -599.两个列表的最小索引总和】

作者头像
YoungMLet
发布2024-03-01 09:56:34
1090
发布2024-03-01 09:56:34
举报
文章被收录于专栏:C++/Linux

Leetcode -598.范围求和Ⅱ

题目:给你一个 m x n 的矩阵 M ,初始化时所有的 0 和一个操作数组 op ,其中 ops[i] = [ai, bi] 意味着当所有的 0 <= x < ai 和 0 <= y < bi 时, M[x][y] 应该加 1。

在 执行完所有操作后 ,计算并返回 矩阵中最大整数的个数 。

示例 1: 输入: m = 3, n = 3,ops = [[2, 2], [3, 3]] 输出 : 4 解释 : M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。

示例 2 : 输入 : m = 3, n = 3, ops = [[2, 2], [3, 3], [3, 3], [3, 3], [2, 2], [3, 3], [3, 3], [3, 3], [2, 2], [3, 3], [3, 3], [3, 3]] 输出 : 4

示例 3 : 输入 : m = 3, n = 3, ops = [] 输出 : 9

思路是每次只需要判断最小的行和列,因为只是返回它们的个数,所以只需要行和列就够了;

代码语言:javascript
复制
		int maxCount(int m, int n, int** ops, int opsSize, int* opsColSize)
		{
		    int minrow = m, mincol = n;
		
		    for (int i = 0; i < opsSize; i++)
		    {
		        //判断最小行和最小列
		        //因为只是返回它们的个数,所以只需要行和列就够了
		        minrow = fmin(ops[i][0], minrow);
		        mincol = fmin(ops[i][1], mincol);
		    }
		    return minrow * mincol;
		}

Leetcode -599.两个列表的最小索引总和

题目:假设 Andy 和 Doris 想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。

你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个,则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。

示例 1: 输入: list1 = [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”],list2 = [“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”] 输出 : [“Shogun”] 解释 : 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2 : 输入 : list1 = [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”],list2 = [“KFC”, “Shogun”, “Burger King”] 输出 : [“Shogun”] 解释 : 他们共同喜爱且具有最小索引和的餐厅是“Shogun”,它有最小的索引和1(0 + 1)。

提示 : 1 <= list1.length, list2.length <= 1000 1 <= list1[i].length, list2[i].length <= 30 list1[i] 和 list2[i] 由空格 ’ ’ 和英文字母组成。 list1 的所有字符串都是 唯一 的。 list2 中的所有字符串都是 唯一 的。

思路是在一个数组中的餐厅寻找另外一个数组中相同的餐厅,并用 i 和 j 作为它们的索引,判断它们的索引是否是最小,因为在此次 i 的遍历中,j 只会越来越大,所以第一次出现相同的餐厅的时候,它们的索引就是最小的;但是可能还会有相同的最小的索引的情况,所以下一次判断索引的时候,等于最小索引的时候,也要放入返回数组中;

代码语言:javascript
复制
		char** findRestaurant(char** list1, int list1Size, char** list2, int list2Size, int* returnSize)
		{
		    //开辟返回的数组指针,开辟1000个是因为两个数组的长度最长是1000
		    char** ret = (char**)malloc(sizeof(char*) * 1000);
		
		    //提前开辟好二级指针中的一级指针的空间大小,因为1 <= list1[i].length, list2[i].length <= 30,加上'\0'就是31个
		    for (int i = 0; i < fmax(list1Size, list2Size); i++)
		    {
		        ret[i] = (char*)malloc(sizeof(char) * 31);
		    }
		
		    int len, sum, min = INT_MAX;
		    for (int i = 0; i < list1Size; i++)
		    {
		        for (int j = 0; j < list2Size; j++)
		        {
		            //相同餐厅
		            if (strcmp(list1[i], list2[j]) == 0)
		            {
		                //判断最小索引
		                sum = i + j;
		                if (sum < min)
		                {
		                    len = 0;
		                    min = sum;
		                    strcpy(ret[len++], list1[i]);
		                }
		
		                //下一个相同的餐厅它们俩的索引和也是等于最小索引
		                else if (sum == min)
		                {
		                    strcpy(ret[len++], list1[i]);
		                }
		                break;
		            }
		
		            //如果索引和大于最小索引和,提前跳出循环
		            if (i + j > min)
		                break;
		        }
		    }
		    *returnSize = len;
		    return ret;
		}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-02-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Leetcode -598.范围求和Ⅱ
  • Leetcode -599.两个列表的最小索引总和
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档