早起刷题（Day 7）

今天没早起刷题，早起抢菜去了。淦！

LeetCode253. 会议室 II

#堆排序

题目描述

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回所需会议室的最小数量。

示例 1：
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2


示例 2：
输入：intervals = [[7,10],[2,4]]
输出：1
 
提示：
1 <= intervals.length <= 104
0 <= starti < endi <= 106

解题思路

(1). 按照最朴素的想法，要给公司部门安排会议，那么一定是优先考虑会议开始得早的部门，那么首先就是要排序。排序的条件就是开始时间越早越靠前；
(2). 安排新会议室的原则是所有已申请的会议室都被占用。那么就可以使用一个最小堆，堆中保存的是每场会议的结束时间；
(3). 当当前会议开始时，堆顶的会议还没结束，说明堆中所有的会议都不可能结束，那么就要申请新的会议室；
(4). 遍历完整个会议的记录，就可以得到要开辟的最大会议室数量。

时间复杂度

O(Nlog(N))

解题代码

type intHeap []int

func (h intHeap) Len() int {
	return len(h)
}

func (h intHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h intHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h *intHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *intHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func minMeetingRooms(intervals [][]int) int {
	
	sort.Slice(intervals, func(i,j int) bool {
		if intervals[i][0] == intervals[j][0] {
			return intervals[i][1] < intervals[j][1]
		}
		return intervals[i][0] < intervals[j][0]
	})

	var h intHeap
	heap.Push(&h, intervals[0][1])
	room := 1

	for i:=1; i<len(intervals); i++ {
		if intervals[i][0] >= h[0] {
			heap.Pop(&h)
		} else {
			room++
		}
		heap.Push(&h, intervals[i][1])
	}
	
	return room
}

LeetCode163. 缺失的区间

#模拟题

题目描述

给定一个排序的整数数组 _nums_ ，其中元素的范围在 闭区间 [lower, upper] 当中，返回不包含在数组中的缺失区间。

1
2
3

示例：
输入: nums = [0, 1, 3, 50, 75], lower = 0 和 upper = 99,
输出: ["2", "4->49", "51->74", "76->99"]

解题思路

(1). 这道模拟题挺恶心的，边界处理是关键；
(2). 根据数据范围遍历 nums，不能按从 lower 到 upper。

时间复杂度

O(N)

解题代码

func findMissingRanges(nums []int, lower int, upper int) []string {

	ret := []string{}
	if len(nums) == 0 {
		if lower == upper {
			s := strconv.Itoa(lower)
			ret = append(ret, s)
		} else {
			s := strconv.Itoa(lower) + "->" + strconv.Itoa(upper)
			ret = append(ret, s)
	}
		return ret
	}

	pre := lower
	for i:=0; i<len(nums); i++ {
		var s string
		if i == 0 {
			if nums[i] != pre {
				if nums[i] == pre+1 {
					s = strconv.Itoa(pre)
				} else {
					s = strconv.Itoa(pre) + "->" + strconv.Itoa(nums[i]-1)
				}
				ret = append(ret, s)
				pre = nums[i]
			}
		} else {
			if nums[i] == pre + 2 {
				s = strconv.Itoa(nums[i]-1)
			} else if nums[i] == pre + 1 {
				s = ""
			} else {
				s = strconv.Itoa(pre+1) + "->" + strconv.Itoa(nums[i]-1)
			}

			pre = nums[i]
			if s != "" {
				ret = append(ret, s)
			}
		}
		
		if i == len(nums)-1 {
			if nums[i] != upper {
				if nums[i] == upper-1 {
					s = strconv.Itoa(upper)
				} else {
					s = strconv.Itoa(nums[i]+1) + "->" + strconv.Itoa(upper)
				}
				ret = append(ret, s)
			}
			break
		}
	}

	return ret
}

LeetCode694. 不同岛屿的数量

#DFS

题目描述

给定一个非空 01 二维数组表示的网格，一个岛屿由四连通（上、下、左、右四个方向）的 1 组成，你可以认为网格的四周被海水包围。
请你计算这个网格中共有多少个形状不同的岛屿。两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。

示例 1：
11000
11000
00011
00011
给定上图，返回结果 1 。

示例 2：
11011
10000
00001
11011
给定上图，返回结果 3 。

注意：

11
1
和

 1
11
是不同的岛屿，因为我们不考虑旋转、翻转操作。

解题思路

(1). 海岛问题的拓展，一般思路就两种：dfs 或 bfs；
(2). 这道题要求输出的是不同形状海岛的数量，那么关键问题就是怎样表示海岛的形状；
(3). 回忆一下我们通过 dfs 找海岛的过程，每次都是先找到海岛最左上角的点，然后根据我们预设的方向数组来控制寻找的路径，那么通过这条寻找路径，就能确定海岛的形状；
(4). 要注意的是每个海岛左上角的起始点都是其坐标，要将其归零才可以在同一数值范围内进行判断，我们只需要在遍历 grid 的点的时候记录下此时的坐标，就可以计算该海岛上每个点相对于左上角点的坐标位置。

时间复杂度

O(N^2)

解题代码

func numDistinctIslands(grid [][]int) int {

	m := make(map[string]struct{})
	h_idx := []int{0,1,-1,0}
	w_idx := []int{1,0,0,-1}

	height, weight := len(grid), len(grid[0])
	s := ""
	bi, bj := 0, 0

	var dfs func(int,int)
	dfs = func(i, j int) {
		grid[i][j] = 0
		s += fmt.Sprintf("-%d-%d", i-bi, j-bj)

		for k:=0; k<4; k++ {
			h, w := i+h_idx[k], j+w_idx[k]
			if h >= 0 && h < height && w >= 0 && w < weight && grid[h][w] == 1 {
				dfs(h,w)
			}
		}
	}

	for i:=0; i<height; i++ {
		for j:=0; j<weight; j++ {
			if grid[i][j] == 1 {
				bi, bj, s = i, j, ""
				dfs(i,j)
				m[s] = struct{}{}
			}
		}
	}

	// for k, _ := range m {
	// 		fmt.Println(k)
	// }

	return len(m)
}

164. 最大间距

#基数排序

题目描述

给定一个无序的数组 nums，返回数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 2，则返回 0 。
您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

 示例 1:
输入: nums = [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。


示例 2:
输入: nums = [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
 

提示:
1 <= nums.length <= 105
0 <= nums[i] <= 109

解题思路

(1). 首先注意题目的要求：您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。 这就对选择的算法有了限制。快排和堆排的时间复杂度都是 O(Nlog(N))，基数排序时间复杂度是 O(N)，空间复杂度是 O(N)，符合题目要求；
(2). 那么这道题就转化成一道基数排序的算法了。基数排序可以参考另一篇博客常用排序算法

时间复杂度

O(N)

解题代码

func maximumGap(nums []int) (ans int) {
    n := len(nums)
    if n < 2 {
        return
    }

    buf := make([]int, n)
    maxVal := max(nums...)
    for exp := 1; exp <= maxVal; exp *= 10 {
        cnt := [10]int{}
        for _, v := range nums {
            digit := v / exp % 10
            cnt[digit]++
        }
        for i := 1; i < 10; i++ {
            cnt[i] += cnt[i-1]
        }
        for i := n - 1; i >= 0; i-- {
            digit := nums[i] / exp % 10
            buf[cnt[digit]-1] = nums[i]
            cnt[digit]--
        }
        copy(nums, buf)
    }

    for i := 1; i < n; i++ {
        ans = max(ans, nums[i]-nums[i-1])
    }
    return
}

func max(a ...int) int {
    res := a[0]
    for _, v := range a[1:] {
        if v > res {
            res = v
        }
    }
    return res
}