剑指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 ...
LeetCode 6. Z字形变换
1. 题目描述
将一个给定字符串s根据给定的行数numRows，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为"PAYPALISHIRING"行数为3时，排列如下：
P A H NA P L S I I GY I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4输出："PINALSIGYAHRPI"
解释：
P I NA L S I GY A H RP I
示例 3：
输入：s = "A", numRows = 1输出："A"
2. 解题思路
我们将Z形字符串沿垂直方向按照V形划分。
|P |A | H | N|A P |L S| ...
深入浅出OS中的并发与同步
0. 并发，是机遇也是挑战
0.1 并发与并行
自从多道程序设计技术诞生以来，资源的利用率和系统的吞吐量就得到了极大的提高，也由此出现了多道批处理系统。
多道程序设计具有以下三个特点：
多道：同一时间段内有多道程序在内存中执行。
宏观上并行：系统内的多个程序都处于运行过程中的状态。
微观上串行：这些程序轮流占有CPU，交替执行。
当多道程序运行在可抢占式的操作系统上时，就产生了并发（Concurrent）问题：CPU在一个进程的指令流上的任何一点都可能产生中断，转而去执行其他进程。当系统有一个以上CPU时，那么进程（线程）的执行效率还可以得到进一步的提升，一个CPU执行一个进程（线程）时，另一个CPU可以执行另一个进程，且它们之间互不抢占CPU资源，可以同时执行，此时的这种方式我们称之为并行（Parallel）。
gantt
title 三个进程并发执行
dateFormat m
axisFormat %M
section 进程A
占用CPU : crit, active, p1,0, 5
section 进程B
...
雅可比行列式，多元函数微积分的计算神器！
雅可比行列式在多元函数微积分中的应用非常广泛，我们在很多地方都能见到它的身影。合理运用雅可比行列式，可以简化我们的计算。
本文主要总结了一些雅可比行列式在多元函数微积分的计算方面的应用。
0. 什么是雅可比行列式
雅可比行列式通常称为雅可比式(Jacobian)，它是以n个n元函数的偏导数为元素的行列式 。事实上，在函数都连续可微（即偏导数都连续）的前提之下，它就是函数组的微分形式下的系数矩阵（即雅可比矩阵）的行列式。
雅可比行列式来源于多元函数微分的方程组，所以自然离不开函数的微分。所谓行列式，不过是一个多元函数微分方程组的系数罢了。
1. 求隐函数方程组的导数
所以在引出雅可比行列式之前，我们有必要先探究一下多元函数方程组和它的偏导数的性质。
隐函数存在定理
根据隐函数存在定理，我们知道一个二元方程能够唯一确定一个一元函数。
一元隐函数存在定理 设二元函数满足，且在点的某邻域内有连续偏导数。则方程在点的某一邻域中唯一确定了一个具有连续导数的函数。满足且。其偏导数为：
二元隐函数存在定理 设三元函数满足，在点的某邻域内有连续偏导数，方程在点的某一邻域中唯一确定了一个具有连续 ...
二阶线性非齐次微分方程特解的五大求解方法
求解非齐次线性微分方程可以说是考研数学中的一大重点和难点。
本文是作者在复习考研数学的过程中，总结的一些常用的可以用于求解二阶线性非齐次微分方程的特解的方法。
我们知道，对于一个二阶线性非齐次微分方程，它的通解是它对应的二阶线性齐次微分方程的通解加上它自己的一个特解。而它所对应的二阶线性齐次微分方程的通解通常有两种情况：若该方程为常系数，我们根据特征方程容易求得通解。但若该方程为变系数，情况就稍麻烦些。大多数的变系数线性高阶微分方程不能利用初等函数求解（如，它的解是无穷级数形式的），只有对于一些特殊形式的二阶变系数线性齐次微分方程，我们才可以利用降阶法等方法求得初等函数解。
求得对应齐次方程的通解后，另一个难点在于求它的一个特解，这也正是考研数学可以说必考的知识点。考虑到变系数方程求解的难度，一般考研题如果考察求解二阶线性非齐次微分方程，则通常是常系数的（不排除变系数的情况）。
下面我们以一个二阶常系数线性非齐次微分方程为例，分别讲解五种方法如何用于求此二阶微分方程的特解。
1. 待定系数法
待定系数法是最常用也是最基本的一种方法。
该微分方程的特征方程为，得特征根，从而通解为。
现 ...