【LeetCode】剑指 Offer <二刷>(3)

这篇具有很好参考价值的文章主要介绍了【LeetCode】剑指 Offer <二刷>(3)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

题目:剑指 Offer 06. 从尾到头打印链表 - 力扣(LeetCode)

题目的接口:

解题思路:

代码:

过啦!!!

题目:剑指 Offer 07. 重建二叉树 - 力扣(LeetCode)

题目的接口:

解题思路:

代码:

过啦!!!

写在最后:


题目:剑指 Offer 06. 从尾到头打印链表 - 力扣(LeetCode)

【LeetCode】剑指 Offer <二刷>(3),38 天二刷剑指 Offer,leetcode,算法,职场和发展,go

题目的接口:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {

}

解题思路:

这道题我读完之后想到了两种思路,1、直接从后往前去链表的值放进数组,但是这样既不好写,复杂度也非常的高,不推荐,

2、先将链表存进一个临时数组,再创建一个返回数组,将临时数组的值从后往前存进返回数组中,这样就实现了,来看代码:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 
func reversePrint(head *ListNode) []int {
    r := make([]int, 0)
    for head != nil {
        r = append(r, head.Val)
        head = head.Next
    } 

    ans := make([]int, 0)
    i := len(r) - 1
    for i >= 0 {
        ans = append(ans, r[i])
        i--
    }

    return ans
}

不过做完这道题之后,我去翻看题解区,看到了一个大佬写了一个很妙的解法,就是利用递归的特性,用 append 函数将链表的值倒着连接成一个切片返回。

代码:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {
    var f func(head *ListNode) []int 
    f = func(head *ListNode) []int {
        if head == nil {return []int{}}
        return append(f(head.Next), head.Val) 
    }
    return f(head)
}

过啦!!!

【LeetCode】剑指 Offer <二刷>(3),38 天二刷剑指 Offer,leetcode,算法,职场和发展,go

题目:剑指 Offer 07. 重建二叉树 - 力扣(LeetCode)

【LeetCode】剑指 Offer <二刷>(3),38 天二刷剑指 Offer,leetcode,算法,职场和发展,go

题目的接口:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {

}

解题思路:

这种二叉树的题目一般也是有两种解法,一个递归一个迭代,递归比较简单,所以我们当然是先来递归,这里递归的核心思路就是根据题目给的前序和中序遍历找到这棵树的根节点,以及左右子树,具体思路如下:

前序的第一个值就是根节点,根据这个根节点我们就能找到中序遍历中的根节点位置,然后将中序数组分成左右子树两个部分,再根据中序左右子树的长度,我们就能找到前序数组左右字数的位置,再递归求解即可,代码如下:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    for k := range inorder {
        if inorder[k] == preorder[0] {
            return &TreeNode {
                Val:   preorder[0],
                Left:  buildTree(preorder[1:k+1], inorder[0:k]),
                Right: buildTree(preorder[k+1:], inorder[k+1:]),
            } 
        }
    }
    return nil
}

递归求解还是相对简单的,比较有难度的就是迭代的解法,使用这个迭代法的核心思想就是:若这颗树是一颗只有左子树的树,相当于一条单链表 那中序遍历和先序遍历的结果是反过来的,利用这个特性,我们就能用栈来存储节点,到最左下的位置时,开始取栈中元素和中序数组匹配,如果遇到不相等的情况,证明这个不相等的值是右节点,代码思路如下:

代码:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {return nil}

    root := &TreeNode{preorder[0], nil, nil}
    stack := []*TreeNode{}
    stack = append(stack, root)
    var inorderIndex int

    // 首先一直遍历到最左下的地方
    // 这里的意思就是一直找左子树,直到找不到
    for i := 1; i < len(preorder); i++ {
        preorderVal := preorder[i]
        node := stack[len(stack)-1]
        if node.Val != inorder[inorderIndex] {
            node.Left = &TreeNode{preorderVal, nil, nil} // 组装二叉树的左子树
            stack = append(stack, node.Left)
        } else { // 已经到了最左下的位置
            // 这里的逻辑是:不断出栈直到不匹配,而不匹配的那个节点就是右节点
            for len(stack) != 0 && stack[len(stack)-1].Val == inorder[inorderIndex] {
                node = stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                inorderIndex++
            }
            // 将这个右子树的节点入栈
            // 也就是这个右子树将作为新的根节点,继续找他的左子树(重新上去走循环)
            node.Right = &TreeNode{preorderVal, nil, nil} // 组装二叉树的右子树
            stack = append(stack, node.Right)
        }
    }
    return root
}

过啦!!!

【LeetCode】剑指 Offer <二刷>(3),38 天二刷剑指 Offer,leetcode,算法,职场和发展,go

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~文章来源地址https://www.toymoban.com/news/detail-687990.html

到了这里,关于【LeetCode】剑指 Offer <二刷>(3)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】剑指 Offer <二刷>(4)

    目录 题目:剑指 Offer 09. 用两个栈实现队列 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 10- I. 斐波那契数列 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这道题我用 C++ 写的时候是比较简单顺手的,用 STL 可以

    2024年02月10日
    浏览(43)
  • (搜索) 剑指 Offer 38. 字符串的排列 ——【Leetcode每日一题】

    难度:中等 输入一个字符串,打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组,但里面 不能有重复元素 。 示例: 输入:s = “abc” 输出:[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”] 限制 : 1 = s 的长度 = 8 💡思路:回溯 可以直接 暴力穷举 ,但

    2024年02月12日
    浏览(50)
  • 【leetcode刷题之路】剑指Offer(3)——搜索与回溯算法

    7 搜索与回溯算法 7.1 【BFS】剑指 Offer 32 - I - 从上到下打印二叉树 https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/   这里借助队列来实现广度优先遍历,由于需要访问每一层的节点,而且这一层访问才可以访问下一层,所以可以考虑队列的先进先出,先把每一层的节

    2024年02月13日
    浏览(59)
  • 【leetcode刷题之路】剑指Offer(4)——分治+排序算法+动态规划

    8 分治算法 8.1 【递归】剑指 Offer 07 - 重建二叉树 https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/   前序遍历是根左右,中序遍历是左根右,这也就意味着前序遍历的第一个节点是整棵树的根节点,顺着这个节点找到它在中序遍历中的位置,即为in_root,那么in_root左边的都在左子

    2024年02月11日
    浏览(59)
  • 【算法】双指针——leetcode盛最多水的容器、剑指Offer57和为s的两个数字

    盛水最多的容器 (1)暴力解法   算法思路:我们枚举出所有的容器大小,取最大值即可。   容器容积的计算方式:   设两指针 i , j ,分别指向水槽板的最左端以及最右端,此时容器的宽度为 j - i 。由于容器的高度由两板中的较短的板决定,因此可得容积公式 :

    2024年02月13日
    浏览(48)
  • 【LeetCode】剑指 Offer(28)

    目录 题目:剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 55 - I. 二叉树的深度 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 55 - II. 平衡二叉树 - 力扣(Leetcode) 题目的接

    2023年04月24日
    浏览(52)
  • 【LeetCode】剑指 Offer(26)

    目录 题目:剑指 Offer 51. 数组中的逆序对 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这一道题,我的思路是用双指针暴力求解, 但这个数组长度,O(N^2)的时间复杂度肯定是不可能把所有样例跑完, 看了大佬的思路,用的是归并排序,(如果不

    2023年04月11日
    浏览(43)
  • 【LeetCode】剑指 Offer(27)

    目录 题目:剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 那么这道题呢, 如果只是作为一道题,或者说笔试题, 我们当然是二话不说直接暴力拿下, 来看代码: 是的,就是这么简单,三行代码暴力拿下

    2023年04月13日
    浏览(45)
  • 【LeetCode】剑指 Offer(25)

    目录 题目:剑指 Offer 49. 丑数 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 丑数这道题用到一点动态规划的思想, 具体思路如下: 根据题意: 如果说第一个丑数是一,包含质因子 2、3 和 5 的数称作丑数, 那么我们发现,之后的丑数: 都是前

    2023年04月09日
    浏览(52)
  • 【LeetCode】剑指 Offer(21)

    目录 题目:剑指 Offer 39. 数组中出现次数超过一半的数字 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 40. 最小的k个数 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这道题,我的思路是直接排序, 然后返回中间

    2023年04月10日
    浏览(66)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包