剑指 Offer 54. 二叉搜索树的第k大节点
剑指 Offer 54. 二叉搜索树的第k大节点
题目描述
给定一棵二叉搜索树，请找出其中第k大的节点。
示例 1:
1234567输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2输出: 4
示例 2:
123456789输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1输出: 4
限制：
1 ≤ k ≤ 二叉搜索树元素个数
解题思路
寻找二叉搜索树中的第k大元素，可以利用二叉搜索树的性质来做。二叉搜索树的中序遍历的结果是一个递增的有序序列，我们可以用count变量记录遍历的结点数量，然后在count==k的时候返回当前元素的值即可。
需要注意一点的是，如果按照左中右顺序遍历得到的是一个递增的序列，返回的是第k小的数；如果按照右中左的顺序遍历得到的是一个递减的序列，返回的是第k大的数。
具体的实现细节见代码：
123456789101112131415161718int res=INT32_MIN;vo ...
剑指 Offer 36. 二叉搜索树与双向链表
剑指 Offer 36. 二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
解题思路
这道题是一道关于树和链表转换的题，直接考虑用递归来完成。
用两个指针left和right来指示根节点root的左子树和右子树转换成一个有序的循环双向链表的头结点，然后根据条件判断，将left所指示的循环双向链表、root结点、right所指示的循环双向链表连接起来。在遇到空节点的时候不做任何操作，直接返回就行。
主要分为四种情况，分述如下：
le ...
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
123输入：nums = [1,2,3,4]输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。
提示：
0 <= nums.length <= 50000
1 <= nums[i] <= 10000
解题思路
这道题是简单题，思路一看就有，but，写了半天。。。
方法一 两层循环
首先想到的是，依次遍历整个数组，找到一个偶数，然后遍历它之后的元素，找到一个奇数，进行交换。循环往复，直至遍历结束。可以做一点小优化，找奇数的时候如果找不到就可以直接返回了。
具体细节可以参考以下代码：
1234567891011121314151617181920vector<int> exchange(vector<int>& nums){ bool existOdd=true; for(int i=0;i< ...
剑指 Offer 10- II. 青蛙跳台阶问题
剑指 Offer 10- II. 青蛙跳台阶问题
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
12输入：n = 2输出：2
示例 2：
12输入：n = 7输出：21
示例 3：
12输入：n = 0输出：1
提示：
0 <= n <= 100
解题思路
这道题是一道很经典的动态规划的题。
基本思路就是用动态数组中的元素dp[i]表示跳到i级台阶共有多少种跳法。那么我们可以很容易得到状态转移方程：
1dp[i] = dp[i-1] + dp[i-2] //因为一次只能跳一阶或者两阶台阶
然后边界条件就是跳到0级台阶的情况：
1dp[0] = 1
然后照此思想编程就可以了。
但是这里有一个问题需要注意，在台阶数很大的情况下，用int、long、long long可能都会溢出，由于输出的时候需要取模，所以我们可以用下述公式避免数据溢出的问题：
1(a + b) % c = (a % c ...
Leetcode958. 二叉树的完全性检验
Leetcode958. 二叉树的完全性检验
题目描述
给定一个二叉树，确定它是否是一个完全二叉树。
百度百科中对完全二叉树的定义如下：
若设二叉树的深度为 h，除第 h 层外，其它各层 (1toh−11 \quad to \quad h-11toh−1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1to2h1 \quad to \quad 2^h1to2h 个节点。）
示例 1：
123输入：[1,2,3,4,5,6]输出：true解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。
示例 2：
123输入：[1,2,3,4,5,null,7]输出：false解释：值为 7 的结点没有尽可能靠向左侧。
提示：
树中将会有 1 到 100 个结点。
解题思路
关于完全二叉树的定义还是比较熟悉的，但是乍一看到这道题有点懵。官方题解的方法是重新同一个code变量给每一个结点 ...
Leetcode718. 最长重复子数组
Leetcode718. 最长重复子数组
题目描述
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：
123456输入：A: [1,2,3,2,1]B: [3,2,1,4,7]输出：3解释：长度最长的公共子数组是 [3, 2, 1] 。
提示：
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100
解题思路
这道题和最长公共子序列有些类似，又有些不同。我们可以考虑使用动态规划法和滑动窗口法求解。
方法一：动态规划法
我们可以借鉴使用动态规划法求解最长公共子序列的思路，用dp[i][j]dp[i][j]dp[i][j]来表示A[0⋯i]A[0 \cdots i]A[0⋯i]和B[0⋯j]B[0 \cdots j]B[0⋯j]的最长公共子数组。那么，我们就可以很容易地得到状态转移方程：
ifA[i]==B[j]thendp[i+1][j+1]=dp[i][j]+1ifA[i]≠B[j]thendp[i+1][j+1]=0if \quad A[i]==B[j] \quad then ...
Leetcode695. 岛屿的最大面积
Leetcode695. 岛屿的最大面积
题目描述
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
示例 1:
12345678[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
示例 2:
1[[0,0,0,0, ...
Leetcode543. 二叉树的直径
Leetcode543. 二叉树的直径
题目描述
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
12345 1 / \ 2 3 / \ 4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
**注意：**两结点之间的路径长度是以它们之间边的数目表示。
解题思路
这道题可以借鉴Leetcode124. 二叉树中的最大路径和中的思路，用相似的DFS搜索方法来求解。
这道题相比较最大路径和，要简单了很多。我们需要求解左子树和右子树的层数，并且用左子树与右子树的和去更新路径长度最大值maxPath的值，而返回左子树与右子树层数的最大值加上根节点（1）的值。
具体步骤如下：
如果结点为空节点，返回为0；
用left和right来标记左子树和右子树的层数。然后用left+right的值去更新路径长度最大值maxPath的值；
计算max(left,right)+1的值，将其作为返回值返回。max(left,right)+1表 ...
Leetcode498. 对角线遍历
Leetcode498. 对角线遍历
题目描述
给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。
示例:
123456789输入:[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]输出: [1,2,4,7,5,3,6,8,9]
解释：
说明:
给定矩阵中的元素总数不会超过 100000 。
解题思路
这道题只需要模拟就可以了。这道题需要做的是三部分：一个是变向，一个是怎么对角移动坐标，最后一个是怎么处理边界条件。
先说变向问题，这个很好处理。首先用一个变量direction指示方向，1表示向右上角移动，0表示向左下角移动，然后变向的操作可以用direction = 1 - direction完成。
接下来就是对角移动。这个也很容易观察出规律：
右上角：
[row, col] -> [row - 1, col + 1]
newRow = row - 1;
newCol = col + 1;
左下角：
[row, col] -> [row + 1, ...
Leetcode470. 用 Rand7() 实现 Rand10()
Leetcode470. 用 Rand7() 实现 Rand10()
题目描述
已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。
不要使用系统的 Math.random() 方法。
示例 1:
12输入: 1输出: [7]
示例 2:
12输入: 2输出: [8,4]
示例 3:
12输入: 3输出: [8,1,10]
提示:
rand7 已定义。
传入参数: n 表示 rand10 的调用次数。
进阶:
rand7()调用次数的 期望值 是多少 ?
你能否尽量少调用 rand7() ?
解题思路
这道题是数学题，建议想不出来直接看答案！！！
这道题相对比较复杂，我们先看一个比较简单的例子来辅助理解。
rand2()生成rand4()：
假设已知rand2()可以均匀的生成[1,2]的随机数，那么如何用来均匀地生成[1,4]的随机数呢？首先，最直接的想法就是用rand2()生成两个数，将它们相加：
12345rand2() + rand2() = ? ==>[2,4] 1 + ...