463. 岛屿的周长

给定一个 row x col 的二维网格地图 grid ,其中:grid[i][j] = 1 表示陆地, grid[i][j] = 0 表示水域。

网格中的格子水平和垂直方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。

岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 1:

img

输入:grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出:16
解释:它的周长是上面图片中的 16 个黄色的边

示例 2:

输入:grid = [[1]]
输出:4

示例 3:

输入:grid = [[1,0]]
输出:4

解题思路

通过观察不难看出每个格子都有4条边,而两个格子相邻时会去掉两条边,所以周长应该为 4*格子数量 - 2*响铃的边;由于格子相邻是互相的,所以寻找相邻的格子时只寻找右下方的即可

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func islandPerimeter(grid [][]int) int {
var count, edge int
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[i]); j++ {
if grid[i][j] == 0 {
continue
}
count++
if j+1 < len(grid[i]) && grid[i][j+1] == 1 {
edge++
}
if i+1 < len(grid) && grid[i+1][j] == 1 {
edge++
}
}
}
return 4*count - 2*edge
}

解题思路

因为总共就一个岛屿,所以我们从遇到的第一块土地开始,基于他递归上下左右4个点:从土地到土地不会产生周长,从土地到海洋会产生周长,从土地到边界会参数周长,将这些周长相加即可。

在上述过程中,递归会导致重复,造成重复计算,将遍历过得土地做一个特殊标记,区别于1和0表示已经访问过了。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func islandPerimeter(grid [][]int) int {
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[i]); j++ {
if grid[i][j] == 1 {
return dfs(grid, i, j)
}
}
}
return 0
}

func dfs(grid [][]int, x, y int) int {
if x < 0 || x >= len(grid) || y < 0 || y >= len(grid[0]) {
return 1
}
if grid[x][y] == 0 {
return 1
}
if grid[x][y] == 2 {
return 0
}
grid[x][y] = 2
return dfs(grid, x-1, y) + dfs(grid, x+1, y) + dfs(grid, x, y-1) + dfs(grid, x, y+1)
}

495. 提莫攻击

在《英雄联盟》的世界中,有一个叫 “提莫” 的英雄,他的攻击可以让敌方英雄艾希(编者注:寒冰射手)进入中毒状态。现在,给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间,你需要输出艾希的中毒状态总时长。

你可以认为提莫在给定的时间点进行攻击,并立即使艾希处于中毒状态。

示例1:

输入: [1,4], 2
输出: 4
原因: 第 1 秒初,提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟,直到第 2 秒末结束。
第 4 秒初,提莫再次攻击艾希,使得艾希获得另外 2 秒中毒时间。
所以最终输出 4 秒。

示例2:

输入: [1,2], 2
输出: 3
原因: 第 1 秒初,提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟,直到第 2 秒末结束。
但是第 2 秒初,提莫再次攻击了已经处于中毒状态的艾希。
由于中毒状态不可叠加,提莫在第 2 秒初的这次攻击会在第 3 秒末结束。
所以最终输出 3 。

解题思路

先考虑两个相邻攻击时间节点timeSeries[i]timeSeries[i-1]的差,如果大于攻击持续时间duration,则第i-1次攻击持续

duration,反之则持续timeSeries[i] - timeSeries[i-1],最后一次攻击始终会持续duration,将它们相加即可

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func findPoisonedDuration(timeSeries []int, duration int) int {
if len(timeSeries) == 0 {
return 0
}
var total int
for i := 1; i < len(timeSeries); i++ {
if timeSeries[i]-timeSeries[i-1] < duration {
total += timeSeries[i] - timeSeries[i-1]
} else {
total += duration
}
}
return total + duration
}

496. 下一个更大元素 I

给你两个没有重复元素的数组nums1nums2 ,其中nums1nums2的子集。

请你找出nums1中每个元素在nums2中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在,对应位置输出 -1 。

示例 1 :

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于 num1 中的数字 4 ,你无法在第二个数组中找到下一个更大的数字,因此输出 -1 。
对于 num1 中的数字 1 ,第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 ,第二个数组中没有下一个更大的数字,因此输出 -1 。

示例 2:

输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 ,第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ,第二个数组中没有下一个更大的数字,因此输出 -1 。

提示

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • nums1nums2中所有整数 互不相同
  • nums1 中的所有整数同样出现在 nums2

进阶:你可以设计一个时间复杂度为O(nums1.length + nums2.length)的解决方案吗?

解题思路

循环nums1,在nums2中查找它的位置,并想有遍历寻找第一个比它大的元素

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func nextGreaterElement(nums1 []int, nums2 []int) []int {
res := make([]int, len(nums1))
for i := 0; i < len(nums1); i++ {
j := 0
for ;j<len(nums2) && nums1[i] != nums2[j]; {
j++
}
for ;j<len(nums2); j ++ {
if nums1[i]< nums2[j] {
res[i] = nums2[j]
break
}
}
if j == len(nums2){
res[i] = -1
}
}
return res
}

解题思路

由于nums1nums2的子集,整体思路就是求出nums2中每个元素对应的下一个更大元素,存在map中,其中keynums2中的元素值,value为下一个更大元素。

正序遍历数组nums2,对于当前考察元素nums2[i]来说:

  • 如果栈为空,将nums[i]入栈,继续向后遍历,看是否有大于nums[i]
  • 如果栈不为空且其值大于栈顶元素,由于正序遍历所以当前元素nums[i]是栈顶元素的下一个更大元素。所以栈顶元素出栈作为keynums[i]作为value存入map。对于出栈后的新栈,继续上诉操作,知道nums[i]不再大于栈顶元素或者栈为空时入栈。

数组遍历完后,查看栈是否为空,不为空时栈类元素为没有更大的元素,值为-1

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func nextGreaterElement(nums1 []int, nums2 []int) []int  {
stack := make([]int, 0)
mapList := make(map[int]int)
for _, v := range nums2 {
if len(stack) == 0 {
stack = append(stack, v)
continue
}
i := 0
for ; i < len(stack); i++ {
if v > stack[i] {
break
}
}
for j := i; j < len(stack); j++ {
mapList[stack[j]] = v
}
stack = stack[:i]
stack = append(stack, v)
}
for _,v := range stack {
mapList[v] = -1
}
for k, v := range nums1 {
nums1[k] = mapList[v]
}
return nums1
}

500. 键盘行

给你一个字符串数组 words ,只返回可以使用在美式键盘同一行的字母打印出来的单词。键盘如下图所示。

美式键盘中:

  • 第一行由字符"qwertyuiop"组成。
  • 第二行由字符`”asdfghjkl” 组成。
  • 第三行由字符"zxcvbnm"组成。

American keyboard

示例 1

输入:words = [“Hello”,”Alaska”,”Dad”,”Peace”]
输出:[“Alaska”,”Dad”]

示例 2

输入:words = [“omk”]
输出:[]

示例 3:

输入:words = [“adsdf”,”sfd”]
输出:[“adsdf”,”sfd”]

提示:

  • 1 <= words.length <= 20
  • 1 <= words[i].length <= 100
  • words[i]由英文字母(小写和大写字母)组成

解题思路

以键盘字母为key,所在行数为value存入map。遍历words中每一个单词的字母,是否在同一行

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func findWords(words []string) []string {
var (
res []string
keyboard map[byte]int
)
keyboard = map[byte]int{
'q': 0, 'w': 0, 'e': 0, 'r': 0, 't': 0, 'y': 0, 'u': 0, 'i': 0, 'o': 0, 'p': 0,
'a': 1, 's': 1, 'd': 1, 'f': 1, 'g': 1, 'h': 1, 'j': 1, 'k': 1, 'l': 1,
'z': 2, 'x': 2, 'c': 2, 'v': 2, 'b': 2, 'n': 2, 'm': 2,
}
for _, word := range words {
b := true
lowercase := strings.ToLower(word)
for i := 1; i < len(lowercase); i++ {
if keyboard[lowercase[i-1]] != keyboard[lowercase[i]] {
b = false
break
}
}
if b {
res = append(res, word)
}
}
return res
}

解题思路

利用strings库提供的ContainsAny函数,判断输入的单词是否出现在键盘的某一行中,如果一个单词在多行中出现则表示不符合标准

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func findWords2(words []string) []string {
line1 := "qwertyuiopQWERTYUIOP"
line2 := "asdfghjklASDFGHJKL"
line3 := "zxcvbnmZXCVBNM"
var res []string
for _, word := range words{
b1 := strings.ContainsAny(word, line1)
b2 := strings.ContainsAny(word, line2)
b3 := strings.ContainsAny(word, line3)
if (b1 && !b2 && !b3) || (!b1 && b2 && !b3) || (!b1 && !b2 && b3){
res = append(res, word)
}
}
return res
}

506. 相对名次

给出N名运动员的成绩,找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”,“银牌” 和“ 铜牌”(”Gold Medal”, “Silver Medal”, “Bronze Medal”)。

(注:分数越高的选手,排名越靠前。)

示例 1:

输入: [5, 4, 3, 2, 1]
输出: [“Gold Medal”, “Silver Medal”, “Bronze Medal”, “4”, “5”]
解释: 前三名运动员的成绩为前三高的,因此将会分别被授予 “金牌”,“银牌”和“铜牌” (“Gold Medal”, “Silver Medal” and “Bronze Medal”).
余下的两名运动员,我们只需要通过他们的成绩计算将其相对名次即可。

提示:

  1. N是一个正整数并且不会超过 10000。
  2. 所有运动员的成绩都不相同。

解题思路

  1. 将原位置存入Hash
  2. 排序
  3. 循环排序后的数组,从map中出去原位置作为下标加入返回数组中

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func findRelativeRanks(score []int) []string {
mapList := make(map[int]int, len(score))
for k, v := range score {
mapList[v] = k
}
sort.Ints(score)
res := make([]string, len(score))
for i := 0; i < len(score); i++ {
if len(score)-i == 1 {
res[mapList[score[i]]] = "Gold Medal"
continue
}
if len(score)-i == 2 {
res[mapList[score[i]]] = "Silver Medal"
continue
}
if len(score)-i == 3 {
res[mapList[score[i]]] = "Bronze Medal"
continue
}
res[mapList[score[i]]] = strconv.Itoa(len(score) - i)
}

return res
}

575. 分糖果

给定一个偶数长度的数组,其中不同的数字代表着不同种类的糖果,每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

示例 1:

输入: candies = [1,1,2,2,3,3]
输出: 3
解析: 一共有三种种类的糖果,每一种都有两个。
最优分配方案:妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。

示例 2 :

输入: candies = [1,1,2,3]
输出: 2
解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1],妹妹有两种不同的糖果,弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。

注意:

  1. 数组的长度为[2, 10,000],并且确定为偶数。
  2. 数组中数字的大小在范围[-100,000, 100,000]内。

解题思路

因为是平均分配,所以妹妹糖果的情况为:

  • 最多:所有糖果数量的一半(此时糖果种类大于等于糖果总数的一半)
  • 最少:1种(所有糖果为一类)

所以妹妹获得糖果种类为:min(总数的一半,糖果种类)

示例代码:排序

1
2
3
4
5
6
7
8
9
10
func distributeCandies(candyType []int) int {
sort.Ints(candyType)
count := 1
for i := 1; i < len(candyType) && count < len(candyType)/2; i++ {
if candyType[i] != candyType[i-1] {
count++
}
}
return count
}

示例代码:Map

1
2
3
4
5
6
7
8
9
10
func distributeCandies(candyType []int) int {
mapList := make(map[int]struct{}, 0 )
for _, v := range candyType {
mapList[v] = struct{}{}
}
if len(mapList) < len(candyType)/2 {
return len(mapList)
}
return len(candyType)/2
}