力扣

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 示例 1： 输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1 示例 2： 输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3 提示： m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] 的值为 '0' 或 '1' func numIslands(grid [][]byte) int { } func numIslands(grid [][]byte) int { ans := 0 var dfs func(row, col int) dfs = func(i, j int) { // 深度优先 尽可能往里面走 grid[i][j] = '0' // 判断四周的 // 上 if i > 0 && grid[i-1][j] == '1' { dfs(i-1, j) } // 左 if j > 0 && grid[i][j-1] == '1' { dfs(i, j-1) } // 右 if i < len(grid)-1 && grid[i+1][j] == '1' { dfs(i+1, j) } // 下 if j < len(grid[i])-1 && grid[i][j+1] == '1' { dfs(i, j+1) } } for i := 0; i < len(grid); i++ { for j := 0; j < len(grid[i]); j++ { if grid[i][j] == '1' { ans++ dfs(i, j) } } } return ans }

力扣链接: https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/ 力扣难度 中等 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 示例 1： 输入：nums = [3,4,5,1,2] 输出：1 **解释：**原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。 示例 2： 输入：nums = [4,5,6,7,0,1,2] 输出：0 **解释：**原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。 ...

力扣链接:https://leetcode.cn/problems/find-peak-element/description/ 力扣难度 中等 峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞ 。 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。 示例 示例 1： 输入：nums = [1,2,3,1] 输出：2 解释：> 3 是峰值元素，你的函数应该返回其索引 2。 示例 2： 输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5 解释：> 你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。 提示： 1 <= nums.length <= 1000 -231 <= nums[i] <= 231 - 1 对于所有有效的 i 都有 nums[i] != nums[i + 1] func findPeakElement(nums []int) int { } func findPeakElement(nums []int) (idx int) { // 暴力遍历找最大值 for i, v := range nums { if v > nums[idx] { idx = i } } return } func findPeakElement(nums []int) (idx int) { // 二分查找 红蓝染色法 // 蓝色的第一个数就是答案 left := 0 right := len(nums) - 1 for left < right { mid := left + (right-left)/2 if nums[mid] < nums[mid+1] { left = mid + 1 } else { right = mid } } return right }

力扣链接:34. 在排序数组中查找元素的第一个和最后一个位置 力扣难度 中等 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 示例 1： 输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4] 示例 2： 输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1] 示例 3： 输入：nums = [], target = 0 输出：[-1,-1] 提示： 0 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9 nums 是一个非递减数组 -10^9 <= target <= 10^9 func searchRange(nums []int, target int) []int { } func searchRange(nums []int, target int) []int { // 暴力遍历 // 时间复杂度 On // 空间复杂度 O1 ans := []int{-1, -1} for i, num := range nums { if target == num { if ans[0] == -1 { ans[0] = i } ans[1] = max(ans[1], i) } } return ans } func searchRange(nums []int, target int) []int { // 二分查找 + 遍历 // 时间复杂度 O(Logn) // 空间复杂度 O(1) ans := []int{-1, -1} // 二分查找 // 找到了目标数以后左右扩展下标 n := len(nums) // // 折半查找法 index := binSearch(nums, target, 0, n-1) if index == -1 { return ans } // 下标存在的 for i := index; i > -1 && nums[i] == target; i-- { // 左扩张 ans[0] = i } for i := index; i < n && nums[i] == target; i++ { // 右扩张 ans[1] = i } return ans } func binSearch(nums []int, target int, j, y int) int { // j 是头 // y 是尾 // 查找到的话就返回下标 否者就是-1 if y < j { return -1 } // 获取中间数 // midIndex := (j + y) / 2 midIndex := j + (y - j) / 2 if nums[midIndex] == target { return midIndex } // 左边 index := binSearch(nums, target, j, midIndex-1) if index != -1 { return index } // 左边 index = binSearch(nums, target, midIndex+1, y) if index != -1 { return index } return -1 } func searchRange(nums []int, target int) []int { // 二分查找 红蓝染色法 // 目的是符合 大于等于target的最小下标 // 蓝色部分一定是 大于等于 目标值的 // 红色部分一定是 小于 目标值的 // 时间复杂度 O(Logn) // 空间复杂度 O(1) start := lowerBound(nums, target) if start == len(nums) || nums[start] != target { return []int{-1, -1} // nums 中没有 target } end := lowerBound(nums, target+1) - 1 return []int{start, end} } func lowerBound(nums []int, target int) int { left, right := 0, len(nums)-1 // 闭区间 [left, right] for left <= right { // 区间不为空 mid := left + (right-left)/2 // 区中间值 if nums[mid] >= target { // 若中间值大了, 中间值右边部分会被染成蓝色 right = mid - 1 } else { left = mid + 1 } } // left 指向的就是红色 + 1 // right 指向的就是蓝色 - 1 return left }

力扣链接: https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/ 力扣难度 中等 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 示例 示例 1: 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个 子序列，不是子串。 提示： 0 <= s.length <= 5 * 10^4 s 由英文字母、数字、符号和空格组成 func lengthOfLongestSubstring(s string) int { } func lengthOfLongestSubstring(s string) int { ans := 0 left := 0 // 左下标 store := make(map[byte]int) for right, i3 := range s { i2 := byte(i3) store[i2]++ for store[i2] > 1 { store[s[left]]-- left++ } ans = max(ans, right-left+1) } return ans }

力扣链接:713. 乘积小于 K 的子数组 力扣难度 中等 给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。 示例 示例 1： 输入：nums = [10,5,2,6], k = 100 输出：8 解释：> 8 个乘积小于 100 的子数组分别为：[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。 需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。 示例 2： 输入：nums = [1,2,3], k = 0 输出：0 提示: 1 <= nums.length <= 3 * 10^4 1 <= nums[i] <= 1000 0 <= k <= 10^6 func numSubarrayProductLessThanK(nums []int, k int) int { } func numSubarrayProductLessThanK(nums []int, k int) int { if k <= 1 { return 0 } ans := 0 prod := 1 // 乘积 left := 0 for right, num := range nums { prod *= num for prod >= k { prod = prod / nums[left] left++ } ans += right - left + 1 } return ans }

力扣链接:209. 长度最小的子数组 力扣难度 中等 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [nums[l], nums[l+1], ..., nums[r-1], nums[r]] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。 示例 示例 1： 输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：> 子数组 [4,3] 是该条件下的长度最小的子数组。 示例 2： 输入：target = 4, nums = [1,4,4] 输出：1 示例 3： 输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0 提示： 1 <= target <= 10^9 1 <= nums.length <= 10^5 1 <= nums[i] <= 10^4 进阶： 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。 func minSubArrayLen(target int, nums []int) int { } func minSubArrayLen(target int, nums []int) int { n := len(nums) ans := n + 1 s := 0 left := 0 // 左边下标 for right, num := range nums { // 右边下标 s += num for s-nums[left] >= target { s -= nums[left] left++ } if s >= target { ans = min(ans, right-left+1) } } if ans == n+1 { return 0 } return ans } func minSubArrayLen(target int, nums []int) int { n := len(nums) ans := n + 1 s := 0 left := 0 // 左边下标 for right, num := range nums { // 右边下标 s += num for s >= target { ans = min(ans, right-left+1) s -= nums[left] left++ } } if ans == n+1 { return 0 } return ans }

力扣链接:42. 接雨水 力扣难度 困难 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 示例 1： 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：> 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2： 输入：height = [4,2,0,3,2,5] 输出：9 提示： n == height.length 1 <= n <= 2 * 10^4 0 <= height[i] <= 10^5 func trap(height []int) int { } func trap(height []int) int { ans := 0 n := len(height) prefixMaxNum := make([]int, n) suffixMaxNum := make([]int, n) prefixMaxNum[0] = height[0] for i := 1; i < n; i++ { prefixMaxNum[i] = max(height[i], prefixMaxNum[i-1]) } suffixMaxNum[n-1] = height[n-1] for i := n - 2; i >= 0; i-- { suffixMaxNum[i] = max(height[i], suffixMaxNum[i+1]) } for i := 0; i < n; i++ { ans += min(prefixMaxNum[i], suffixMaxNum[i]) - height[i] } return ans } func trap(height []int) int { ans := 0 n := len(height) left := 0 // 指向最左边 right := n - 1 // 指向最右边 pro_max := 0 // 前缀最大值 suf_max := 0 // 后缀最大值 for left <= right { pro_max = max(pro_max, height[left]) suf_max = max(suf_max, height[right]) if pro_max < suf_max { ans += pro_max - height[left] left++ } else { ans += suf_max - height[right] right-- } } return ans }

力扣链接:11. 盛最多水的容器 力扣难度 中等 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明： 你不能倾斜容器。 示例 示例 1： 输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：> 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。 示例 2： 输入：height = [1,1] 输出：1 提示： n == height.length 2 <= n <= 10^5 0 <= height[i] <= 10^4 func maxArea(height []int) int { } func maxArea(height []int) int { ans := 0 i := 0 // 左指针下标 j := len(height) - 1 // 右指针下标 // 循环 for i < j { // 目前的面积 ans = max(ans, min(height[j], height[i])*(j-i)) // 最小的高 * 相距的宽 if height[i] <= height[j] { i++ } else { j-- } } return ans }

力扣链接:15. 三数之和 力扣难度 中等 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。 注意： 答案中不可以包含重复的三元组。 示例 示例 1： 输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。 示例 2： 输入：nums = [0,1,1] 输出：[] 解释：> 唯一可能的三元组和不为 0 。 示例 3： 输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：> 唯一可能的三元组和为 0 。 提示： 3 <= nums.length <= 3000 -10^5 <= nums[i] <= 10^5 func threeSum(nums []int) [][]int { } func threeSum(nums []int) [][]int { ans := make([][]int, 0) // 数组排序 // 因为 输出的顺序和三元组的顺序并不重要，因此我们将原数组顺序打乱，按照从小到大排序方便后续处理 sort.Ints(nums) // 便利选择第一个数数 K 使得后面两边的数 J L 两个数加起来 等于 K的倒数 J + L = - K n := len(nums) for i := 0; i < len(nums)-2; i++ { // 后面至少还有2个数，因此需要遍历到len(nums)-2 if i > 0 && nums[i] == nums[i-1] { // 重复要跳过 i == 0 时前面没有数 continue } j := i + 1 l := n - 1 for j < l { s := nums[i] + nums[j] + nums[l] if s > 0 { l-- } else if s < 0 { j++ } else { // 找到目标 ans = append(ans, []int{nums[i], nums[j], nums[l]}) // 避免重复 继续看一下相临的数是否重复，是的话都跳过 j++ for j < l && nums[j] == nums[j-1] { j++ } l-- for j < l && nums[l] == nums[l+1] { l-- } } } } return ans } func threeSum(nums []int) [][]int { ans := make([][]int, 0) // 数组排序 // 因为 输出的顺序和三元组的顺序并不重要，因此我们将原数组顺序打乱，按照从小到大排序方便后续处理 sort.Ints(nums) // 便利选择第一个数数 K 使得后面两边的数 J L 两个数加起来 等于 K的倒数 J + L = - K n := len(nums) for i := 0; i < len(nums)-2; i++ { // 后面至少还有2个数，因此需要遍历到len(nums)-2 if i > 0 && nums[i] == nums[i-1] { // 重复要跳过 i == 0 时前面没有数 continue } // 优化 一 最小的2个数和nums[i]加起来都>0 这不用进入 if nums[i]+nums[i+1]+nums[i+2] > 0 { continue } // 优化 一 最大的2个数和nums[i]加起来都<0 这不用进入 if nums[i]+nums[n-1]+nums[n-2] < 0 { continue } j := i + 1 l := n - 1 for j < l { s := nums[i] + nums[j] + nums[l] if s > 0 { l-- } else if s < 0 { j++ } else { // 找到目标 ans = append(ans, []int{nums[i], nums[j], nums[l]}) // 避免重复 继续看一下相临的数是否重复，是的话都跳过 j++ for j < l && nums[j] == nums[j-1] { j++ } l-- for j < l && nums[l] == nums[l+1] { l-- } } } } return ans }