【算法刷题】——力扣第77场双周赛

🏳️‍🌈1.题目描述 给你一个字符串数组 words 和一个字符串 s &#x…

🏳️‍🌈1.题目描述

给你一个字符串数组 words一个字符串 s ,其中 words[i] 和 s 只包含 小写英文字母
请你返回 words 中是字符串 s 前缀 的 字符串数目
一个字符串的 前缀 是出现在字符串开头的子字符串。子字符串 是一个字符串中的连续一段字符序列。

示例:

输入:

words = [“a”,“b”,“c”,“ab”,“bc”,“abc”], s = “abc”

输出:

3

说明:

words 中是 s = “abc” 前缀的字符串为: “a” ,“ab” 和 “abc” 。
所以 words 中是字符串 s 前缀的字符串数目为 3 。

🏳️‍🌈2.题目分析

想着第一题简单,看完一遍题目看了下示例就直接写代码了。仅比较了每个字符串的第一个字符,啪一下很快啊,WA

果然,wa一下就老实了,认真看了下题目,匹配前缀,需要字符数组中每个字符串的每一个字符都与给定字符串进行匹配,如果成功就是前缀

(注意:给定字符串的长度需要满足 ≥ 字符数组中每个字符串的长度)

🏳️‍🌈3.代码实现

🏳️‍🌈1.题目描述

给你一个下标从 0 开始长度为 n 的整数数组 nums 。

下标 i 处的 平均差 指的是 nums 中 前 i + 1 个元素平均值和 后 n – i – 1 个元素平均值的 绝对差 两个平均值都需要 向下取整 到最近的整数。


请你返回产生 最小平均差 的下标。如果有多个下标最小平均差相等,请你返回 最小 的一个下标。

注意:

两个数的 绝对差 是两者差的绝对值。 n 个元素的平均值是 n 个元素之 和 除以(整数除法)n 。 0 个元素的平均值视为 0

示例 1:

输入: nums = [2,5,3,9,5,3]

输出: 3

解释:

  • 下标 0 处的平均差为:|2 / 1 – (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 – 25 / 5| = |2 – 5| = 3 。
  • 下标 1 处的平均差为:|(2 + 5) / 2 – (3 + 9 + 5 + 3) / 4| = |7 / 2 – 20 / 4| = |3 – 5| = 2 。
  • 下标 2 处的平均差为:|(2 + 5 + 3) / 3 – (9 + 5 + 3) / 3| = |10 / 3 – 17 / 3| = |3 – 5| = 2 。
  • 下标 3 处的平均差为:|(2 + 5 + 3 + 9) / 4 – (5 + 3) / 2| = |19 / 4 – 8 / 2| = |4 – 4| = 0 。
  • 下标 4 处的平均差为:|(2 + 5 + 3 + 9 + 5) / 5 – 3 / 1| = |24 / 5 – 3 / 1| = |4 – 3| = 1 。
  • 下标 5 处的平均差为:|(2 + 5 + 3 + 9 + 5 + 3) / 6 – 0| = |27 / 6 – 0| = |4 – 0| = 4 。

    下标 3 处的平均差为最小平均差,所以返回 3 。

提示:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105

🏳️‍🌈2.题目分析

题目意思就是求解nums数组,前 i+1 个元素的平均值 与 后 n-i-1 个元素的平均值 之差的绝对值的 最小值的位置下标 i

吸取第一题的教训理解题目意思后,才开始写代码,上来就是一个暴力双循环,啪一下很快啊,WA 果然还是老老实实想其他方法吧

因为每次都是从 下标 i 进行分隔,前面的i+1 个的元素和 与后面的元素和 两者相加就是nums数组的元素和,因此,后面元素的和 = 数组和 – 前面元素的和

  • 求nums数组元素和 count
  • 从前往后遍历数组 另设一个变量 sum 每次加上遍历的元素
  • 后面元素的和就是 count – sum
  • 求前后两个元素和的平均值 并求绝对值的差
  • 比较更新最小值下标

注意:n-i-1可能为 0 这个时候 就不能 作分母了。 求和数据是可能超过int类型的,因为选择long类型的变量记录和)

🏳️‍🌈3.代码实现

🏳️‍🌈1.题目描述

给你两个整数 mn 表示一个下标从 0 开始的 m x n 网格图。同时给你两个二维整数数组 guardswalls ,其中 guards[i] = [rowi, coli]walls[j] = [rowj, colj],分别表示第 i 个警卫和第 j 座墙所在的位置。

一个警卫能看到 4 个坐标轴方向(即东、南、西、北)的 所有 格子,除非他们被一座墙或者另外一个警卫 挡住 了视线。如果一个格子能被 至少 一个警卫看到,那么我们说这个格子被 保卫 了。
请你返回空格子中,有多少个格子是 没被保卫 的。

示例1:
image-20220501194352778

输入: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
输出: 7
解释: 上图中,被保卫和没有被保卫的格子分别用红色和绿色表示。 总共有 7 个没有被保卫的格子,所以我们返回 7 。

提示:

  • 1 <= m, n <= 10^5
  • 2 <= m * n <= 10^5
  • 1 <= guards.length, walls.length <= 5 * 10^4
  • 2 <= guards.length + walls.length <= m * n
  • guards[i].length == walls[j].length == 2
  • 0 <= rowi, rowj < m
  • 0 <= coli, colj < n
  • guards 和 walls 中所有位置 互不相同 。

🏳️‍🌈2.题目分析

根据题目描述,首先想到了是DFS,由于周赛时间是晚上10点半 —— 12点,写到这里就已经11点了,太晚了,要回宿舍睡大觉了…😪😪😪

第二天以dfs的思路写着写着就写不下去了,主要是怎么如何只进行四个方向的持续遍历,如果使用dfs会以每个格子为起点进行上下左右遍历,但是题目意思显然是 仅朝着四个方向,看了题解区大佬的解法,使用方向数组可以解决这个问题了。

  • 初始化一个 m x n 的数组res 数组值 -1表示墙 1表示守卫 2表示被保护 0表示没有被保护
  • 将墙和守卫的位置对res数组进行状态更新
  • 遍历每个守卫,使用方向数组,并不断进行四个方向遍历 直至遇到墙或者其他守卫 或者超过res数组边界 并将保卫的地方更新数组值为 2
  • 遍历数组res 统计0的个数 就是所求

🏳️‍🌈3.代码实现

就先分析前三题吧,第四题再想想🤔🤔🤔

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/1864.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部