Day27_滑动窗口_剑指Offer
滑动窗口的最大值Hard 原题连接：滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例：
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：
你可以假设 k 总是有效的，在输入数组 不为空 的情况下，1 ≤ k ≤ nums.length。
解题思路问题：
需要时刻记录当前窗口中的最大值
当窗口移动时需要考虑是否移除的 ...
Day26_字符与数字_剑指Offer
表示数值的字符串medium 原题连接：表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
数值（按顺序）可以分成以下几个部分：
若干空格一个 小数 或者 整数（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数若干空格小数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（’+’ 或 ‘-‘）下述格式之一：至少一位数字，后面跟着一个点 ‘.’至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字一个点 ‘.’ ，后面跟着至少一位数字整数（按顺序）
可以分成以下几个部分：
（可选）一个符号字符（’+’ 或 ‘-‘）至少一位数字部分数值列举：[“+100”, “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]
部分非数值列举：[“12e”, “1a3.14”, “1.2.3”, “+-5”, “12e+5.4”]
示例：
输入：s = "0"
输出：true
输入：s = "e"
输出：false
输入：s = "."
输出：false
输入：s = & ...
Day25_顺序_剑指Offer
顺时针打印矩阵Easy 原题连接： 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示：
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100
解题思路固定顺时针：向左，向下，向右，向上
实现：
设立上下左右边界，在走完一边后，减少对应的边界范围（如：输出矩阵最上一行后，上边届从0转至1）
依据 向左，向下，向右，向上 循环执行输出，完成一端需要判断下一步是否有路可走（向左到端头，先判断向下是否可以走）
Java代码class Solution {
public int[] spiralOrder(int[][] matrix) {
if ...
Day24_数字规律_剑指Offer
剪绳子medium 原题连接：剪绳子
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18
示例：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 58
解题思路总长度固定，拆成不同长短的子段，算最大乘积
子段长度越相等，积越大（算术几何均值不等式）
不要分出长度为1的子段
自然对数 e 约等于 2.7
所以设总长度为常数N，拆成a段长度为x，我们有：
N = a * x ; ans = x ^ a;
得到：ans = ( x ^ ( 1 / x ) ) ^ N，由于N为常数，ans最终的值会趋近于 2.7 * ...
Day23_数组计算_剑指Offer
数组中出现次数超过一半的数字Easy 原题连接：数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例：
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
1 <= 数组长度 <= 50000
解题思路摩尔投票：记录一个值当作目标值，对比接下来的值是否和目标值一致，一致则计数加一，否则减一，当计数为零时更换目标值
使用前提：数组中一定存在超过一半的符合要求的数，否则算法不成立【1，1，4，4，4，7，7】会返回 7 而不是 4 ，当数组中一定存在超过一半的目标数，剩余的数全部对撞目标数，留下的也一定是目标数。
Java代码class Solution {
public int majorityElement(int[] nums) {
//摩尔投票算法：对拼消耗
int ans = 0, maxNum = 0;
for(int num : nums) ...
Day22_数组中的重复数字_剑指Offer
数组中数字出现的次数medium 原题连接：数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
限制：
2 <= nums.length <= 10000
解题思路因为题目要求了时间复杂度不能超过O(n)，空间复杂度不能超过O(1)，所以无法使用HashMap做记录统计值
前置知识：
关于异或（相同返回0，不同返回1）：A^A=0 , A^B=B^A 和 A^0=A ，所以A^B^A = A^A^B = 0^B = B
一个十位数，对应着唯一的二进制值（废话），所以如果两个数的二进制某个位置值不同，那一定是不同值
实现：
对nums中所有数据进行异或，能得到除了重复数字之外的，两个只出现了一次的数的异或结果
找 ...
Day21_二进制计算_剑指Offer
二进制中1的个数Esay 原题连接：二进制中1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
示例：
输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
输入：n = 128 (控制台输入 00000000000000000000000010000000)
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1& ...
Day19_计算与二叉树的遍历_剑指Offer
重建二叉树medium 原题连接：重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例：
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Input: preorder = [-1], inorder = [-1]
Output: [-1]
限制：
0 <= 节点个数 <= 5000
解题思路
先序遍历是指：根节点优先遍历，然后遍历左节点，再是右节点（根左右）；中序遍历是指：先遍历左节点，再遍历根节点，最后遍历右节点（左根右）
在没有单子树的前提下，对于先序遍历，根节点后一定跟着自己的左节点；对于中序遍历，根节点后一定跟着自己的右节点；且先序遍历第一位一定是总的根节点
先序遍历可以用于查找每一个子节点的根与左节点关系，而且是从第一个值开始查：数组存
中序遍历在知道某一个根节点时可以知道其根与右节点关系，但是需要提前找到根：Map存
实现：先序遍历找到 ...
Day19_计算与二叉树_剑指Offer
求1+2+…+nmedium 原题连接：求1+2+…+n
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例：
输入: n = 3
输出: 6
输入: n = 9
输出: 45
限制：
节点总数 <= 10000
解题思路递归，如果大于1，就返回 n-1在sumNum的值 + n，等于1 就直接返回1
Java代码class Solution {
public int sumNums(int n) {
if(n == 1) return 1;
if(n > 1) return sumNums(n-1)+n;
return -1;
}
}
二叉搜索树的最近公共祖先Esay 原题连接：二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x， ...