[剑指Offer] Day 08

题目来源:剑指 Offer 10- I. 斐波那契数列写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下: F(0) = 0,   F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回…

[剑指Offer] Day 07

题目来源:剑指 Offer 26. 树的子结构输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构, 即 A中有出现和B相同的结构和节点值。 解题思路:如果树A或树B为空则不满足,直接返回。否则判断B是否为A节点的子结构,或A的左(右)子树的子结构。在递归函数中进行判断:如果B节点为空,表明已经匹配完成,返回true;如果B不为空,而A为空,或A、B节点的值不相同,则匹配失败,返回false;如果A、B的值相同则继续比较A、B的左右子树。 时间复杂度:O(N) 空间复杂度:O(1) class Solution { public boolean isSubStructure(TreeNode A, TreeNode B) { return (A != null &&…

[剑指Offer] Day 06

题目来源:剑指 Offer 32 - I. 从上到下打印二叉树从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。 解题思路:广度优先遍历二叉树。若根节点非空,则将其压入队列。当队列非空时,从队列中取出一个节点,将值加入可变列表。依次将其左右子树(非空)压入队列。从可变列表中取出值,依次放入数组,返回结果数组。 时间复杂度:O(N) 空间复杂度:O(N) class Solution { fun levelOrder(root: TreeNode?): IntArray { if (root == null) return intArrayOf() val queue = LinkedList<TreeNode>() val arr = mutableListOf<Int&…

[剑指Offer] Day 05

题目来源:剑指 Offer 04. 二维数组中的查找在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 解题思路:从二维数组的左上角或者右下角开始遍历。若查找目标小于当前位置的值,则向上走;反之向右侧走,直至找到目标值后返回true。若遍历到数组边界仍然未找到,则返回false。 时间复杂度:O(N) 空间复杂度:O(1) class Solution { fun findNumberIn2DArray(matrix: Array<IntArray>, target: Int): Boolean { var row = matrix.size - 1 var col = 0 while (row…

[剑指Offer] Day 04

剑指 Offer 03. 数组中重复的数字 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 解题思路:比较简单的做法是依次遍历,然后存HashMap。(时间、空间复杂度均为O(N)) 如果要求空间复杂度为O(1),则可以利用题目数据的特点,使用「交换位置法」和「置负数」法。 这里使用了「交换位置法」。依次遍历遍历数组,若当前的值与下标不相同,则将其与「当前值为下标」的数字相互交换,若这两个数字是相同的,则直接返回。注意,交换完成后仍然继续判断当前位置,直到下标和值相同,再把位置后移。 若遍历完数组,则说明不存在相同数字,返回-1。(按照题意不会出现这种情况) 时间复杂度:O(…

[剑指Offer] Day 03

剑指 Offer 05. 替换空格请实现一个函数,把字符串 s 中的每个空格替换成"%20"。 解题思路:使用StringBuilder,依次遍历字符串的字符,判断是否为空格,如果是空格则替换为"%20"。遍历完成后转换为string返回。 时间复杂度:O(N) 空间复杂度:O(N) class Solution { fun replaceSpace(s: String): String { var sb = StringBuilder() for (pos in 0 until s.length) { var str = if (s[pos] == ' ') { "%20" } else { s[pos].toString(…

[剑指Offer] Day 02

剑指 Offer 06. 从尾到头打印链表输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。 解题思路:首先遍历一遍链表,获得链表长度。然后创建对应长度的数组,再从头遍历链表,依次存到数组中,存放的时候从右侧开始放。 时间复杂度:O(N) 空间复杂度:O(1) class Solution { fun reversePrint(head: ListNode?): IntArray { var length = 0 var p = head while (p != null) { p = p.next length++ } var intArray = IntArray(length) p = head while (p != null) { intArray.set(…

[剑指Offer] Day 01

剑指 Offer 09. 用两个栈实现队列用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) 解题思路:定义两个栈inStack和outStack。入队操作比较简单:队列中元素入队时就push到inStack中。出队列时统一"倒"到outStack中,顺序上做了一次调换。要考虑以下几种情况:1.如果outStack中还有元素,直接pop即可;2.如果outStack没有元素,inStack也没有元素了,表明队列已经为空返回-1;3.如果outStack没有元素,inStack仍然有元素。先将所有元素"倒"到outStack中,然后弹出顶部元素即可。 class CQueue() { val inStack = Stack<Int>() val outStack = Stack<Int&…