前n项平方和怎么求？
设为前项平方和： 它的通项公式我们在中学阶段已经学习过，即 但是它的推导过程却不算简单。本文主要从组合数学的角度罗列一些此级数通项公式的推导方法。要理解本文的内容，读者应当学习过一些组合数学或离散数学的知识。
方法一：求解递推关系
考虑 上式为常系数非线性递推关系。若我们尝试直接求解，则需要先求通解，再求特解，然后将他们线性组合。显然，通解为，但是特解却并不好求。所以我们换个思路，尝试消去递推关系的非齐次项。 上述两式相减，并利用替换，可得 WOW，我们成功让等式右边的降幂了！这暗示着我们可以使用这个方法，将右边的幂函数一直降至常数。当然，随之而来的就是左边的递推关系会越变越复杂。 化简之后，我们得到了一个相当复杂的递推关系，但庆幸的是它是齐次的，我们无需再考虑通解。 我们列出上式的特征方程： 先别急着解它，我断言，它一定只有这一个实数根。否则，就将会以指数级的速度增长了，这与我们的直觉不符。当然，不难发现， 所以的的确确是它的四重根。那么该递推关系的解应该是： 注意到，根据的定义： 将前四项代入，得到一个线性方程组： 容易解得： 也就是 回顾我们的求解过 ...
LeetCode 1725. 可以形成最大正方形的矩形数目
1. 题目描述
给你一个数组rectangles，其中rectangles[i] = [li, wi]表示第i个矩形的长度为li、宽度为wi。
如果存在k同时满足k <= li和k <= wi，就可以将第i个矩形切成边长为k的正方形。例如，矩形[4,6]可以切成边长最大为4的正方形。
设maxLen为可以从矩形数组rectangles切分得到的 最大正方形 的边长。请你统计有多少个矩形能够切出边长为maxLen的正方形，并返回矩形数目。
示例 1：
输入：rectangles = [[5,8],[3,9],[5,12],[16,5]]输出：3解释：能从每个矩形中切出的最大正方形边长分别是 [5,3,5,5] 。最大正方形的边长为 5 ，可以由 3 个矩形切分得到。示例 2：
输入：rectangles = [[2,3],[3,7],[4,3],[3,7]]输出：3
提示：
1 <= rectangles.length <= 1000
rectangles[i].length == 2
1 <= li, wi <= 109
li != wi
来源： ...
剑指Offer 14-I. 剪绳子
1. 题目描述
给你一根长度为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。
示例 1：
输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10输出: 36解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 58
来源：力扣（LeetCode）
2. 解题思路
给定一个数，假设将其拆分成个因子。根据均值不等式，当且仅当时，有最大。
考虑函数 求导得 因此，当时，单减。时，取得最大值。
所以，我们的划分因子数应当为： 以上的讨论虽然找出了极值点，但局限于连续的情形下。题目的要求是分割为整数段，我们只能求出函数的极值点，然后分别尝试极值点左右的值。
比如，当时，计算出的极值点。我们自然会依次尝试它的左右整数点和，并尽可能将均分。 ...
LeetCode 1414. 和为K的最少斐波那契数字数目
1. 题目描述
给你数字k，请你返回和为k的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
斐波那契数字定义为：
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
数据保证对于给定的k，一定能找到可行解。
示例 1：
输入：k = 7输出：2 解释：斐波那契数字为：1，1，2，3，5，8，13，……对于 k = 7 ，我们可以得到 2 + 5 = 7 。
示例 2：
输入：k = 10输出：2 解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。
示例 3：
输入：k = 19输出：3 解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。
提示：
1 <= k <= 10^9
来源：力扣（LeetCode）
2. 解题思路
对于一个给定的数字k，注意到总是存在一个可行解的。那么在最优的方案下，它的拆分数中一定有一个最大的不超过k的Fibonacci数。
只要注意到这样一个事实，越小的数，最优方案的拆分数就越少。那么原问题就变为一个减而治之的问题。设不超过的k的最大的斐波那契 ...
剑指Offer 66. 构建乘积数组
1. 题目描述
给定一个数组A[0,1,…,n-1]，请构建一个数组B[0,1,…,n-1]，其中B[i]的值是数组A中除了下标i以外的元素的积, 即B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5]输出: [120,60,40,30,24]
提示：
所有元素乘积之和不会溢出32位整数 a.length <= 100000
来源：力扣（LeetCode）
2. 算法思路
乘积数组可以用一个表格表示：
A[0]
A[1]
...
A[n-2]
A[n-1]
B[0]
1
A[1]
...
A[n-2]
A[n-1]
B[1]
A[0]
1
...
A[n-2]
A[n-1]
...
...
...
...
A[n-2]
A[n-1]
B[n-2]
A[0]
A[1]
...
1
A[n-1]
B[n-1]
A[0]
A[1]
...
A[n-2]
1
其中B[i]的值是每一行的乘积。易见，我们只需分别从上三角自下而上、下三角自上而下循环乘A[i]即可。
cla ...
深入浅出算法复杂度分析
算法是计算机科学中最重要的部分，它们可以通过使用与语言和机器无关的方式进行研究。这意味着我们需要一种技术，使我们能够在不实现算法的情况下比较算法的效率。在算法分析中，两个最重要的工具是
计算的RAM模型。
最坏情况下复杂性的渐近分析。
本文将讨论算法的效率分析，以及常用的分析工具和方法。
0. Prerequisite
为了理解本文所写的内容，你需要掌握一些基本的高等数学知识。
极限的定义。
求极限的洛必达法则。
级数的定义与相关概念。
1. 算法的效率
一个算法主要有两种效率：时间效率和空间效率。时间效率，也称为时间复杂度，对应算法运行的速度。空间效率，也称为空间复杂度，是指算法根据其输入和输出所需的额外空间，或者说所需的内存单元数量。在计算机出现的早期，时间和空间等资源都是十分昂贵的。
半个多世纪依赖的技术创新使计算机的速度和内存大小提高了几个数量级。现在，算法所要求的额外空间通常不是人们关注的焦点。然而，算法时间效率重要性并不像空间那样降低。反而对于大多数问题，我们可以在时间上取得比在空间方面取得更令人满意的提升。因此，本文中，我们主要专注于算法的时间效率，当然但这里所 ...
「论文笔记」Time Series is a Special Sequence: Forecasting with Sample Convolution and Interaction.
1. 概要
论文针对的是时序预测问题（Time Series Forecasting，TSF），根据时间序列的特点创新性地提出了一个多层的神经网络框架sample convolution and interaction network（SCINet）用于时序预测。模型在多个数据集上都展示了其准确率上的优越性，且时间成本相对其他模型（如时序卷积网络TCN）也更低。本篇论文工作包含以下几点：
说明了TCN不适合解决TSF问题，尤其是其中的因果卷积对模型准确率反而有负面影响
基于时间序列的独特性提出了一个多层TSF框架SCINet，通过计算permutation entropy（PE）可以证明新的模型有更强的预测能力
构造了SCINet的基本块SCI-Block，它将输入的数据/特征下采样为两个子序列，然后使用不同的卷积滤波器提取每个子序列特征以保留不同特征的信息。同时为了减少下采样过程中信息丢失造成的影响，在每个SCI-Block中加入了两个序列间卷积特征的学习。
2. 知识梳理
2.1. 相关模型
目前用于时间序列预测的主要有三类深度神经网络：
RNNs及其变种（如LSTMs和G ...
LeetCode 3. 无重复字符的最长子串
1. 题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1：
输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2：
输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3：
输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""输出: 0
2. 算法思路
使用滑动窗口，记录下最大的窗口大小。
pos数组表示该字符上一次出现的位置，初始化为-1。
class Solution {public: int lengthOfLongestSubstring(string s) { int pos[256]; memset(pos, -1, 1024); int left = 0, right = 0, max_len = ...
LeetCode 747. 至少是其他数字两倍的最大数
1. 题目描述
给你一个整数数组nums，其中总是存在 唯一的 一个最大整数 。
请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。
示例 1：
输入：nums = [3,6,1,0]输出：1解释：6 是最大的整数，对于数组中的其他整数，6 大于数组中其他元素的两倍。6 的下标是 1 ，所以返回 1 。
示例 2：
输入：nums = [1,2,3,4]输出：-1解释：4 没有超过 3 的两倍大，所以返回 -1 。
示例 3：
输入：nums = [1]输出：0解释：因为不存在其他数字，所以认为现有数字 1 至少是其他数字的两倍。
2. 算法思路
寻找第二大的元素，比较最大元素和第二大元素的两倍即可。
class Solution {public: int dominantIndex(vector<int>& nums) { if (nums.size() == 1) return 0; int max = 0x80000000, sec = 0x80000 ...
LeetCode 334. 递增的三元子序列
1. 题目描述
给你一个整数数组nums，判断这个数组中是否存在长度为3的递增子序列。
如果存在这样的三元组下标(i, j, k)且满足i < j < k，使得nums[i] < nums[j] < nums[k]，返回true；否则，返回false。
示例 1：
输入：nums = [1,2,3,4,5]输出：true解释：任何 i < j < k 的三元组都满足题意
示例 2：
输入：nums = [5,4,3,2,1]输出：false解释：不存在满足题意的三元组
示例 3：
输入：nums = [2,1,5,0,4,6]输出：true解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
2. 算法思路
我们可以将整个数组看作是由成若干个降序的子序列而成的。
算法初始时设置两个哨兵min =0x7FFFFFFE和mid = 0x7FFFFFFF，满足min < mid，分别表示我们要寻找的三元组中的最小值和中间值。我们假设，序列中存在一个数max ...