【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)

简介: 本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。

🔍 LeetCode 系列:解决 4 道「搜索旋转排序数组」题 —— 二分查找的变形经典

旋转排序数组的问题是一类典型的二分查找变形题目。这类题目看似简单,却常常因为细节处理出错而导致调试困难。

本文一次性讲透这类问题,包括以下四道经典题:

  • LeetCode 33. 搜索旋转排序数组(无重复)
  • LeetCode 81. 搜索旋转排序数组 II(有重复)
  • LeetCode 153. 寻找旋转排序数组中的最小值(无重复)
  • LeetCode 154. 寻找旋转排序数组中的最小值 II(有重复)

📌 题目一:33. 搜索旋转排序数组

🔗 题目描述

给你一个整数数组 nums,它最初是按升序排列的,并经过一次旋转。给定一个目标值 target,若存在目标值返回其索引,否则返回 -1。

💡 解题思路

整体思路仍然是 二分查找,只是要结合旋转点的判断来决定查找方向。

  1. 每次取中点 mid
  2. 判断哪一边是有序的;
  3. 然后判断目标值是否落在有序区间内;
  4. 缩小边界继续搜索。

✅ Go 代码实现

func search(nums []int, target int) int {
   
    left, right := 0, len(nums)-1

    for left <= right {
   
        mid := (left + right) / 2

        if nums[mid] == target {
   
            return mid
        }

        // 左边有序
        if nums[left] <= nums[mid] {
   
            if nums[left] <= target && target < nums[mid] {
   
                right = mid - 1
            } else {
   
                left = mid + 1
            }
        } else {
    // 右边有序
            if nums[mid] < target && target <= nums[right] {
   
                left = mid + 1
            } else {
   
                right = mid - 1
            }
        }
    }

    return -1
}
AI 代码解读

📌 题目二:81. 搜索旋转排序数组 II(含重复元素)

🔗 题目描述

本题与 33 题几乎相同,但 nums可能含有重复元素

🧠 解题关键

在某些情况下,例如 [1, 0, 1, 1, 1],中间值与左右值相同,这时无法确定哪边是有序的,我们只能跳过重复元素

✅ Go 代码实现

func search(nums []int, target int) bool {
   
    left, right := 0, len(nums)-1

    for left <= right {
   
        mid := (left + right) / 2
        if nums[mid] == target {
   
            return true
        }

        if nums[left] == nums[mid] {
   
            left++
        } else if nums[left] < nums[mid] {
    // 左边有序
            if nums[left] <= target && target < nums[mid] {
   
                right = mid - 1
            } else {
   
                left = mid + 1
            }
        } else {
    // 右边有序
            if nums[mid] < target && target <= nums[right] {
   
                left = mid + 1
            } else {
   
                right = mid - 1
            }
        }
    }

    return false
}
AI 代码解读

📌 题目三:153. 寻找旋转排序数组中的最小值

🔗 题目描述

给你一个旋转排序数组,元素不重复。找到其中的最小值。

✨ 解题思路

旋转之后的数组,最小值一定出现在「无序」的部分。使用二分查找找「第一个小于右端点的数」。

✅ Go 代码实现

func findMin(nums []int) int {
   
    left, right := 0, len(nums)-1

    for left < right {
   
        mid := (left + right) / 2
        if nums[mid] > nums[right] {
   
            left = mid + 1
        } else {
   
            right = mid
        }
    }

    return nums[left]
}
AI 代码解读

📌 题目四:154. 寻找旋转排序数组中的最小值 II(含重复元素)

🧩 解题难点

与 153 题不同的是,这道题目允许数组中含有重复值

nums[mid] == nums[right] 时,无法判断最小值在哪一边,只能 right-- 缩小范围。

✅ Go 代码实现

func findMin(nums []int) int {
   
    left, right := 0, len(nums)-1

    for left < right {
   
        mid := (left + right) / 2
        if nums[mid] > nums[right] {
   
            left = mid + 1
        } else if nums[mid] < nums[right] {
   
            right = mid
        } else {
   
            right--
        }
    }

    return nums[left]
}
AI 代码解读

🧠 总结与对比

题号 类型 是否允许重复 返回结果 特殊处理
33 查找目标值 索引 判断左右哪边有序
81 查找目标值 ✅ 是 是否存在 nums[left] == nums[mid] 时,left++
153 查找最小值 最小值 典型二分,比较 mid 和 right
154 查找最小值 ✅ 是 最小值 处理重复值时 right--

🔍 类似题推荐

    1. 在排序数组中查找元素的第一个和最后一个位置
    1. 搜索二维矩阵
    1. 寻找峰值
    1. 寻找两个正序数组的中位数

🎯 结语

这四道题完美地展示了 二分查找在旋转数组上的变形应用,也是 LeetCode 中非常有代表性的一类题。

📌 只要掌握:

  • 判断有序区间
  • mid 与边界的比较逻辑
  • 如何处理重复元素的干扰

你就能轻松应对类似问题,写出高效、鲁棒的代码。


欢迎收藏 ⭐、点赞 👍 或评论交流 💬,我会继续更新更多高质量 LeetCode 题解!

目录
打赏
0
14
14
4
163
分享
相关文章
|
2月前
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
96 1
|
2月前
|
Go
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本篇博客详细解析了三道经典的动态规划问题:198. 打家劫舍(线性状态转移)、279. 完全平方数与322. 零钱兑换(完全背包问题)。通过 Go 语言实现,帮助读者掌握动态规划的核心思想及其实战技巧。从状态定义到转移方程,逐步剖析每道题的解法,并总结其异同点,助力解决更复杂的 DP 问题。适合初学者深入理解动态规划的应用场景和优化方法。
58 0
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本文讲解了两道经典的图论问题:**岛屿数量(LeetCode 200)** 和 **腐烂的橘子(LeetCode 994)**,分别通过 DFS/BFS 实现。在“岛屿数量”中,利用深度或广度优先搜索遍历二维网格,标记连通陆地并计数;“腐烂的橘子”则采用多源 BFS,模拟腐烂传播过程,计算最短时间。两者均需掌握访问标记技巧,是学习网格搜索算法的绝佳实践。
102 1
|
2月前
|
【LeetCode 热题100】回溯:括号生成 & 组合总和(力扣22 / 39 )(Go语言版)
本文深入解析了LeetCode上的两道经典回溯算法题:**22. 括号生成**与**39. 组合总和**。括号生成通过维护左右括号数量,确保路径合法并构造有效组合;组合总和则允许元素重复选择,利用剪枝优化搜索空间以找到所有满足目标和的组合。两者均需明确路径、选择列表及结束条件,同时合理运用剪枝策略提升效率。文章附有Go语言实现代码,助你掌握回溯算法的核心思想。
81 0
Go语言实战案例:多协程并发下载网页内容
本文是《Go语言100个实战案例 · 网络与并发篇》第6篇,讲解如何使用 Goroutine 和 Channel 实现多协程并发抓取网页内容,提升网络请求效率。通过实战掌握高并发编程技巧,构建爬虫、内容聚合器等工具,涵盖 WaitGroup、超时控制、错误处理等核心知识点。
Go语言实战案例:实现HTTP客户端请求并解析响应
本文是 Go 网络与并发实战系列的第 2 篇,详细介绍如何使用 Go 构建 HTTP 客户端,涵盖请求发送、响应解析、错误处理、Header 与 Body 提取等流程,并通过实战代码演示如何并发请求多个 URL,适合希望掌握 Go 网络编程基础的开发者。
Go语言实战:创建一个简单的 HTTP 服务器
本篇是《Go语言101实战》系列之一,讲解如何使用Go构建基础HTTP服务器。涵盖Go语言并发优势、HTTP服务搭建、路由处理、日志记录及测试方法,助你掌握高性能Web服务开发核心技能。
|
16天前
|
Go
如何在Go语言的HTTP请求中设置使用代理服务器
当使用特定的代理时,在某些情况下可能需要认证信息,认证信息可以在代理URL中提供,格式通常是:
81 0
监控局域网其他电脑:Go 语言迪杰斯特拉算法的高效应用
在信息化时代,监控局域网成为网络管理与安全防护的关键需求。本文探讨了迪杰斯特拉(Dijkstra)算法在监控局域网中的应用,通过计算最短路径优化数据传输和故障检测。文中提供了使用Go语言实现的代码例程,展示了如何高效地进行网络监控,确保局域网的稳定运行和数据安全。迪杰斯特拉算法能减少传输延迟和带宽消耗,及时发现并处理网络故障,适用于复杂网络环境下的管理和维护。
揭秘 Go 语言中空结构体的强大用法
Go 语言中的空结构体 `struct{}` 不包含任何字段,不占用内存空间。它在实际编程中有多种典型用法:1) 结合 map 实现集合(set)类型;2) 与 channel 搭配用于信号通知;3) 申请超大容量的 Slice 和 Array 以节省内存;4) 作为接口实现时明确表示不关注值。此外,需要注意的是,空结构体作为字段时可能会因内存对齐原因占用额外空间。建议将空结构体放在外层结构体的第一个字段以优化内存使用。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问