华为上机考试

菠萝2024-03-292024-05-19

华为机试

华为考试必须了解的：

机考时长2-2.5小时，3道题

可以使用IDE编辑器

ACM输入输出

OD考试三道题分数：100 + 100 + 200 分。

一般150分就算通过。分数越高，对定级越又帮助。

实习生机考、应届本硕秋招机考、留学生机考、博士机考：2h, 3个题目，总分600,150分合格。

分数计算： 通过率 * 题目分数

由于分数计算，所以有时候一定不要放弃做题。

注意事项：

防止被判定为作弊，要避免代码与别人的重复。
如果是刷到过的，建议抽离函数出来。

机考重点：

算法复习

如何复习算法？？？？

复习算法前提要掌握一定的数据结构（欸嘿

字符串类
链表类
数组类
队列 queue
栈 stack
哈希 map
图（
树
堆

掌握常见算法：

DFS 深搜
BFS 广搜
排序
二分
迭代
递归
回溯
分治
贪心
双指针
并查集: 可以用于判断是否成环

机考题目

【华为上机考试】华为机考，看这一篇就够了，适用于编程算法岗位 - 知乎 (zhihu.com)

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]

i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

思路很简单，就记录每次跳跃的长度，然后每次跳跃记录最长的跳跃，当 i == cover 的时候更新 ans即可。

func jump(nums []int) int {
	if len(nums) == 1 {
		return 0
	}
	cover := 0
	tmp := 0
	ans := 0
	for i := 0; i <= cover; i++ {
		tmp = max(tmp, nums[i]+i)
		if i == cover {
			ans++
			cover = tmp
			if cover >= len(nums)-1 {
				return ans
			}
		}
	}
	return -1
}

1190. 反转每对括号间的子串

给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中不应包含任何括号。

// o(n)做法

func reverseParentheses(s string) string {
	n := len(s)
	pair := make([]int, n)

	stack := make([]int, 0)
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			stack = append(stack, i)
		} else if s[i] == ')' {
			j := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			pair[i], pair[j] = j, i
		}
	}
	var ans []byte
	step := 1
	for i := 0; i < len(s); i += step {
		if s[i] == '(' || s[i] == ')' {
			// 换边
			i = pair[i]
			step = -step
		} else {
			ans = append(ans, s[i])
		}
	}
	return string(ans)
}

// o(n^2)
func reverseParentheses(s string) string {
    stack := [][]byte{}
    str := []byte{}
    for i := range s {
        if s[i] == '(' {
            stack = append(stack, str)
            str = []byte{}
        } else if s[i] == ')' {
            for j, n := 0, len(str); j < n/2; j++ {
                str[j], str[n-1-j] = str[n-1-j], str[j]
            }
            str = append(stack[len(stack)-1], str...)
            stack = stack[:len(stack)-1]
        } else {
            str = append(str, s[i])
        }
    }
    return string(str)
}

781. 森林中的兔子

森林中有未知数量的兔子。提问其中若干只兔子 “还有多少只兔子与你（指被提问的兔子）颜色相同?” ，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ，返回森林中兔子的最少数量。

解题思路：

贪心算法。还是比较简单的。

func numRabbits(answers []int) int {
	// 排序
	sort.Ints(answers)
	ans := 0
	for i := 0; i < len(answers); {
		cur := answers[i]
		j := i + 1
		for j < len(answers) && answers[j] == cur && j-i <= cur {
			j++
		}
		ans += cur + 1
		i = j
	}
	return ans
}

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替

解题思路：

单调栈的运用。

func dailyTemperatures(temperatures []int) []int {
	ans := make([]int, len(temperatures))
	// 单调递减栈 ==> 记录下标
	queue := make([]int, 0)
	for i := 0; i < len(temperatures); i++ {
		for len(queue) > 0 && temperatures[i] > temperatures[queue[len(queue)-1]] {
			// 弹出
			ans[queue[len(queue)-1]] = i - queue[len(queue)-1]
			queue = queue[:len(queue)-1]
		}
		// 讲 下标入栈
		queue = append(queue, i)
	}
	// 判断栈是否为空？不需要 初始化为 0 了吧？
	return ans
}

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

题解思路：

滑动窗口 + hashmap记录出现的值

func lengthOfLongestSubstring(s string) int {
	m := map[byte]int{}
	r, ans := -1, 0
	for i := 0; i < len(s); i++ {
		if i != 0 {
			delete(m, s[i-1])
		}
		for r+1 < len(s) && m[s[r+1]] == 0 {
			m[s[r+1]]++
			r++
		}
		ans = max(ans, r-i+1)
	}
	return ans
}

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

简单的DFS

回溯

func permute(nums []int) [][]int {
	ans := make([][]int, 0)
	st := make([]bool, len(nums))
	t := make([]int, 0, len(nums))

	var dfs func(cur int)

	dfs = func(cur int) {
		if len(t) == len(nums) {
			tmp := make([]int, len(nums))
			copy(tmp, t)
			ans = append(ans, tmp)
		}

		for i := 0; i < len(nums); i++ {
			// in
			if !st[i] {
				t = append(t, nums[i])
				st[i] = true
				dfs(cur + 1)
				// 回溯
				st[i] = false
				t = t[:len(t)-1]
			}
		}
	}
	dfs(0)
	return ans
}

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。

模拟问题（感觉像，就只是简单的使用栈来模拟（stack）

func isValid(s string) bool {
	n := len(s)
	if n == 1 {
		return false
	}
	str := []byte{'(', ')', '{', '}', '[', ']'}
	stack := make([]byte, 0)
	for i := 0; i < len(s); i++ {
		if s[i] == str[0] || s[i] == str[2] || s[i] == str[4] {
			stack = append(stack, s[i])
		} else {
			// 弹出栈
			if len(stack) == 0 {
				return false
			}
			for j := 0; j < 3; j++ {
				if s[i] == str[j*2+1] && stack[len(stack)-1] != str[j*2] {
					return false
				}
			}
			stack = stack[:len(stack)-1]
		}
	}
	if len(stack) > 0 {
		return false
	}
	return true
}

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

为什么老是栈的题目？？？

又是栈的模拟题

func decodeString(s string) string {
	stack := make([][]byte, 0)
	stackNum := make([]int, 0)
	var str []byte
	var nums []byte
	for i := 0; i < len(s); i++ {
		if s[i] == '[' {
			stack = append(stack, str)
			var parseInt int64 = 0
			if len(nums) > 0 {
				parseInt, _ = strconv.ParseInt(string(nums), 10, 64)
			}
			stackNum = append(stackNum, int(parseInt))
			str = []byte{}
			nums = []byte{}
		} else if s[i] == ']' {
			// 获取放大倍数
			num := stackNum[len(stackNum)-1]
			// 放大倍数的str == cur str
			tmp := make([]byte, len(str))
			copy(tmp, str)
			for j := 0; j < num-1; j++ {
				str = append(str, tmp...)
			}
			str = append(stack[len(stack)-1], str...)
			stack = stack[:len(stack)-1]
			stackNum = stackNum[:len(stackNum)-1]
		} else if unicode.IsLetter(rune(s[i])) {
			str = append(str, s[i])
		} else {
			// 数字：放入tackNum
			nums = append(nums, s[i])
		}
	}
	return string(str)
}

179. 最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：
输入：nums = [10,2]
输出："210"
示例 2：
输入：nums = [3,30,34,5,9]
输出："9534330"
思路：

通过自定义排序解决

只要尝试拼接当前2个比较大小即可

func largestNumber(nums []int) string {
	sort.Slice(nums, func(i, j int) bool {
		x, y := nums[i], nums[j]
		sx, sy := 10, 10
		for sx <= x {
			sx *= 10
		}
		for sy <= y {
			sy *= 10
		}
		// 对比拼接
		return sy*x+y > sx*y+x
	})
	if nums[0] == 0 {
		return "0"
	}
	var ans []byte
	for _, x := range nums {
		ans = append(ans, strconv.Itoa(x)...)
	}
	return string(ans)
}

LCP 09. 最小跳跃次数

为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。

为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。

示例 1：

输入：jump = [2, 5, 1, 1, 1, 1]

输出：3

解释：小 Z 最少需要按动 3 次弹簧，小球依次到达的顺序为 0 -> 2 -> 1 -> 6，最终小球弹出了机器。

我的评价是碰到自求多福（

看到hard题都没有想写的习惯了（呜呜呜

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。

相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

解题思路：

不多赘述，贪心算法，可以去看看卡尔的教学视频（还是比较好理解的

func candy(ratings []int) int {
	// 贪心算法（我敲了 还好看过 卡尔
	total := 0
	ans := make([]int, len(ratings))

	// init ans 1
	for i := 0; i < len(ratings); i++ {
		ans[i] = 1
	}

	// left --> right  根据left 更新 right的值
	for i := 0; i < len(ratings)-1; i++ {
		if ratings[i] < ratings[i+1] {
			ans[i+1] = ans[i] + 1
		}
	}

	// right --> left 根据right 更新 left 的值
	for j := len(ratings) - 1; j > 0; j-- {
		if ratings[j] < ratings[j-1] {
			ans[j-1] = max(ans[j]+1, ans[j-1])
		}
	}

	for _, v := range ans {
		total += v
	}
	return total
}

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

经典 2数之和

比较简单，不多赘述

func twoSum(nums []int, target int) []int {
	hmap := make(map[int]int)
	for i, v := range nums {
		hmap[v] = i
	}

	for i := 0; i < len(nums); i++ {
		if index, ok := hmap[target-nums[i]]; ok && index != i {
			return []int{i, index}
		}
	}

	return nil
}

2. 两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

也是比较简单的题目：

就是简简单单的模拟相加的过程，注意处理的细节还是比较简单的


func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	add := 0
	dump := &ListNode{}
	cur := dump
	for l1 != nil || l2 != nil || add != 0 {
		val := add
		if l1 != nil {
			val += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			val += l2.Val
			l2 = l2.Next
		}
		cur.Next = &ListNode{Val: val % 10}
		add = val / 10
		cur = cur.Next
	}
	return dump.Next
}

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

经典单调栈的题目

func trap(height []int) int {
	ans := 0
	l, r := 0, len(height)-1
	leftMax, rightMax := height[l], height[r]
	for l < r {
		if leftMax < rightMax {
			l++
			leftMax = max(leftMax, height[l])
			ans += leftMax - height[l]
		} else {
			r--
			rightMax = max(rightMax, height[r])
			ans += rightMax - height[r]
		}
	}
	return ans
}

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

经典的回溯采用 dfs 还是比较容易的

只需要注意发现规律：左边的括号一定 >= 右边

func generateParenthesis(n int) []string {
	ans := make([]string, 0)
	var dfs func(left, right int, s string)
	dfs = func(left, right int, s string) {
		if left == n && right == n {
			ans = append(ans, s)
			return
		}
		if left < n {
			dfs(left+1, right, s+"(")
		}
		if left > right {
			dfs(left, right+1, s+")")
		}
	}
	dfs(0, 0, "")
	return ans
}

554. 砖墙

你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。

你现在要画一条 自顶向下 的、穿过最少砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。

优化：考虑记录空隙的位置，采用map记录，然后找出空隙最多的即可求解

func leastBricks(wall [][]int) int {
	ans := len(wall)
	hmap := make(map[int]int)
	l := 0
	for i := 0; i < len(wall[0]); i++ {
		l += wall[0][i]
	}
	// 优化 ==>  记录空隙
	for i := 0; i < len(wall); i++ {
		pre := 0
		for j := 0; j < len(wall[i]); j++ {
			hmap[pre+wall[i][j]] += 1
			pre += wall[i][j]
		}
	}
	//
	hmap[0] = 0
	hmap[l] = 0
	temp := 0
	for _, v := range hmap {
		temp = max(temp, v)
	}
	return ans - temp
}

547. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

并查集或者 dfs 也可以

func findCircleNum(isConnected [][]int) int {
	//
	ans := 0
	p := make([]int, len(isConnected))
	hmap := make(map[int]struct{})
	// init p
	for i := 0; i < len(isConnected); i++ {
		p[i] = i
	}

	var find func(i int) int
	var union func(i, j int)
	//var check func(i, j int) bool

	find = func(i int) int {
		if p[i] == i {
			return i
		} else {
			p[i] = find(p[i])
			return p[i]
		}
	}

	union = func(i, j int) {
		u := find(i)
		v := find(j)
		if u == v {
			return
		}
		p[u] = v
	}

	//check = func(i, j int) bool {
	//	u := find(i)
	//	v := find(j)
	//	return u == v
	//}

	// for
	for i := 0; i < len(isConnected); i++ {
		for j := i + 1; j < len(isConnected); j++ {
			if isConnected[i][j] == 1 {
				union(i, j)
			}
		}
	}

	// get ans
	for i := 0; i < len(p); i++ {
		// get parent to check
		parent := find(i)
		if _, ok := hmap[parent]; !ok {
			ans++
			hmap[parent] = struct{}{}
		}
	}
	return ans
}


func findCircleNum(isConnected [][]int) int {
	n := len(isConnected)
	visited := make([]int, n)
	ans := 0
	var dfs func(i int)
	dfs = func(i int) {
		for j := 0; j < n; j++ {
			if isConnected[i][j] == 1 && visited[j] == 0 {
				visited[j] = 1
				dfs(j)
			}
		}
	}

	for i := 0; i < n; i++ {
		if visited[i] == 0 {
			dfs(i)
			ans++
		}
	}
	return ans
}

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

贪心 + 动态规划

func canJump(nums []int) bool {
	cover := 0
	for i := 0; i <= cover; i++ {
		cover = max(cover, nums[i]+i)
		if cover >= len(nums) -1 {
			return true
		}
	}
	return false
}

172. 阶乘后的零

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

数学证明一下就可以了，我们只要统计 5 的个数（因子）

func trailingZeroes(n int) int {
    var ans int 
    for n > 0 {
        n /= 5
        ans += n
    }
    return ans
}

// 为什么？

2 * 5 = 10

为什么求5 的个数

==> 2 < 5 ==> 2的倍数个数小于 5 ==> 5的个数（因子）

30 = 5 * 6

5 10 15 20 25 30

231. 2 的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

func isPowerOfTwo(n int) bool {
	return n > 0 && (n&(n-1) == 0)
}

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

dfs

func subsets(nums []int) [][]int {
	res, path := make([][]int, 0), make([]int, 0, len(nums))

	var dfs func(cur int)
	dfs = func(cur int) {
		tmp := make([]int, len(path))
		copy(tmp, path)
		res = append(res, tmp)
		for i := cur; i < len(nums); i++ {
			path = append(path, nums[i])
			dfs(i + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(0)
	return res
}

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

简单栈操作

func removeDuplicates(s string) string {
	ans := make([]byte, 0)
	for i := 0; i < len(s); i++ {
		if len(ans) != 0 {
			if ans[len(ans)-1] == s[i] {
				ans = ans[:len(ans)-1]
			} else {
				ans = append(ans, s[i])
			}
		} else {
			ans = append(ans, s[i])
		}
	}

	return string(ans)
}

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

双指针

或动态规划

func longestPalindrome(s string) string {
	ans := ""
	for i := 0; i < len(s); i++ {
		s1 := logest(s, i, i)
		s2 := logest(s, i, i+1)
		if len(s1) >= len(s2) {
			ans = s1
		} else {
			ans = s2
		}
	}
	return ans
}

func logest(s string, i, j int) string {
	for i >= 0 && j < len(s) && s[i] == s[j] {
		i--
		j++
	}
	return s[i+1 : j]
}

// 动态规划
func longestPalindrome(s string) string {
	size := len(s)
	if size < 2 {
		return s
	}
	dp := make([][]bool, size)
	maxStart, maxEnd, maxLen := 0, 0, 1
	for i := 0; i < size; i++ {
		dp[i] = make([]bool, size)
	}

	for r := 1; r < size; r++ {
		for l := 0; l < r; l++ {
			if s[l] == s[r] && (r - l <= 2 || dp[l+1][r-1]) {
                dp[l][r] = true
				if r-l+1 > maxLen {
                    maxLen = r - l + 1
					maxStart = l
					maxEnd = r
				}
			}
		}
	}
	return s[maxStart:maxEnd+1]
}

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

func longestCommonPrefix(strs []string) string {
	length := 0
	for j := 0; j < len(strs[0]); j++ {
		ch := strs[0][j]
		for i := 0; i < len(strs); i++ {
			if j > len(strs[i])-1 || strs[i][j] != ch {
				return strs[0][:length]
			}
		}
		length++
	}
	return strs[0][:length]
}

300. 最长递增子序列

子序列

是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，
[3,6,2,7]是数组 
[0,3,1,6,2,2,7]的子序列.
dp + 二分

// dp
func lengthOfLIS(nums []int) int {
	// 动态规划
	if len(nums) == 0 {
		return 0
	}
	dp := make([]int, len(nums))
    dp[0] = 1
	maxn := 1
	for i := 1; i < len(nums); i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		maxn = max(maxn, dp[i])
	}
	return maxn
}

// 二分 + dp
// 贪心 + 二分  [10,9,2,5,3,7,101,18]   [0,1,0,3,2,3]
func lengthOfLIS1(nums []int) int {
	dp := make([]int, 0)
	for _, v := range nums {
		l := twoDivide(dp, v)
		if l == len(dp) {
			dp = append(dp, v)
		} else { // 当前元素 v 可以替换原有的元素
			dp[l] = v
		}
	}
	return len(dp)
}

// 0 1 2 3

func twoDivide(nums []int, target int) int {
	l := 0
	r := len(nums) - 1
	for l <= r { // 0, 1  l = 0
		mid := l + (r-l)/2
		if nums[mid] >= target {
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	return l
}

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

其实还是比较简单的，首先进行对二位切片的排序，再考虑合并条件就可以了。

func merge(intervals [][]int) [][]int {
	ans := make([][]int, 0)
	// 首先根据左边排序
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	for i := 0; i < len(intervals); i++ {
		l1, r1 := intervals[i][0], intervals[i][1]
		for j := i + 1; j < len(intervals); j++ {
			l2, r2 := intervals[j][0], intervals[j][1]
			if r1 < l2 {
				break
			}
			// merge
			if r1 < r2 {
				r1 = r2
			}
			i++
		}
		ans = append(ans, []int{l1, r1})
	}
	return ans
}

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围

简单的 dfs 搜索题

func numIslands(grid [][]byte) int {
	var dfs func(x, y int)
	dfs = func(x, y int) {
		if x < 0 || x > len(grid)-1 || y < 0 || y > len(grid[0])-1 || grid[x][y] == '0' {
			return
		}
		// update
		grid[x][y] = '0'
		// search
		dfs(x-1, y)
		dfs(x+1, y)
		dfs(x, y-1)
		dfs(x, y+1)
	}
	ans := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == '1' {
				ans++
				dfs(i, j)
			}
		}
	}
	return ans
}

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

贪心 + 双指针

考虑怎么才能装最多的水即可

l，r 怎么移动，肯定是移动高度小的，才能使得装更多的水

func maxArea(height []int) int {
	l, r := 0, len(height)-1
	ans := 0
	for l < r {
		// update
		ans = max(ans, (r-l)*min(height[l], height[r]))
		if height[l] <= height[r] {
			l++
		} else {
			r--
		}
	}
	return ans
}