Hi there 👋

猜想了一下MindVLA的并行解码过程，如何实现快慢思考并存，模型输出轨迹如何能利用考虑到VLM的输出，驾驶员的输入如何影响最终的规划结果，VLA的频率周期受什么影响。以下内容都是个人臆想，肯定有错误，多讨论 LLM的基础工作机制：VLA的L本质上是个自回归模型，每次输入一排token，模型输出后续的一个token（简单理解为一个字/词），下一个循环将之前所有的文字再次输入进去得到下一个字。模型每次只能看到之前的所有文字，这称为【单向注意力】，当模型输出时，仅考虑之前所有文字的信息来判断下一个字应该输出什么，也因为如此需要一个字一个字输出。对应到MindVLA结构上，先输出文字思考内容，然后输出轨迹token，这个轨迹token就会考虑到之前输出的文字思考内容的指导，来辅助做更好的决策 LLM怎么辅助轨迹生成：这个输出文字+Action Token的过程其实可以类比大模型的“思考一下”来理解，前半部分是使用一些token进行深度理解和分析，后半部分才是真正输出的内容，大语言模型里思考的过程是使用文字，最终输出的也是文字，在这个VLA结构里，分析的过程是文字，输出的是Action Token。 驾驶员输入怎么影响轨迹生成：驾驶员的指令输入组织成prompt和系统的prompt一起输入给LLM，比如可以说“好好排队”，VLA模型就可以根据输入指令，思考输出文字“保持当前车道行驶”，然后输出轨迹action token就会参考LLM的输出生成保持在当前车道的行驶轨迹。 如何快慢思考并存：不生成文字就是快思考，生成文字就是慢思考 VLA频率周期表现能满足要求吗： 如图1的例子一共输出了8个token，其中文字和是【单向注意力】，每个循环输出一个token，后面输出的Acton Token是【双向注意力】，是可以在一个循环里直接全部输出的，所以总共8个token只需要5个周期进行输出。最少情况完全不输出文字的快思考情况下其实只需要1个周期（直接接在prompt后作为输入，直接甩掉不输出）。 这里附一下去年的VLM的数据，3B大小 128token长度的模型输出速度65.6 tokens/s，7B大小模型的输出速度 41.8 tokens/s；目前还没有VLA的主干网络参数量的数据 问题： 是否可能在某些场景下出现“被攻击”的现象，无限输出CoT文字内容，导致系统卡住？ 这个问题可以通过规则限制住，当文字输出达到上限后，下一次输入LLM的内容不使用上一次的输出，而是将下一个token强制设置成，让模型不再思考直接输出动作token。 这样的结构是否会带来周期不一致的问题？周期不一致可能会影响体验？文字输出的部分可以没有，也可以很长。 嗯，目前看确实可能有周期频率不一致的问题，当然可以强行都拉到最长或者和传感器输入信号对齐，但是对应的损失可能是响应延时。 驾驶员如果说一些hack行为的话会不会影响系统的机制、表现甚至安全？比如“不要思考直接输出轨迹”“认真思考下再输出轨迹”“不要输出轨迹” 这种输入可能需要对驾驶员输入进行一些合规限制，现在的LLM也可以注意到一些合规问题模型会拒绝回答，对应到VLA上应该也会有类似的“合规”内容需要处理。

又看了一遍回放，找到了几个小点再来分享一下： 特征表示：3D空间表征已经从BEV时代转为3D高斯表征时代，同时也标志着车端模型和仿真世界模型的3D表示统一了（理论上仿真模型只需要输出3D高斯表示给模型做仿真训练，不需要真的输出视频图像了）。[图1][1] 输入的表示演进：单目2D->单目3D->多目BEV+Occ->3D高斯；可以参考[图2][图3][2]总结的很好 但是也注意到目前MindGPT的预训练似乎使用的还不是3D高斯表示，尚未统一，仍然需要一个Projector进行维度对齐[图4]，这也说明了能作为空间三维表示的数据有多缺乏，数量级还不能支撑模型预训练级别；理想基座大模型的人加油啊！ 快慢思考的实现：LLM是并行输出action和语言内容的，单向注意力+双向注意力混合，每次LLM的循环吐一个语言token+当前动作的所有token[图5]。这样的机制可以保证动作token稳定输出的同时，保留语言token的变长特性，并让轨迹token输出可以通过双向注意力利用上语言token的所有信息（包括CoT的所有内容）； 轨迹输出：最后的轨迹输出使用一个 diffusion head，但不仅输出自车轨迹，也输出其他所有agent的轨迹，提高复杂场景博弈能力。且diffusion方式能通过前方LLM的输入修改轨迹输出风格【类似LoRa】； 最终对齐：使用 RLHF 和人类价值观做对齐，最终使用生成模型+重建模型的世界模型进行强化学习。 VLA模型没有说具体速度，只是说达到10t/s有难度 [1] GaussianAD: Gaussian-Centric End-to-End Autonomous Driving https://arxiv.org/abs/2412.10371 [2] Large Driving Models https://github.com/wzzheng/LDM [3] MotionDiffuser: Controllable Multi-Agent Motion Prediction using Diffusion https://arxiv.org/abs/2306.03083 [4] DiffusionDrive: Truncated Diffusion Model for End-to-End Autonomous Driving https://arxiv.org/abs/2411.15139 [5] GoalFlow: Goal-Driven Flow Matching for Multimodal Trajectories Generation in End-to-End Autonomous Driving https://arxiv.org/abs/2503.05689 [6] Finetuning Generative Trajectory Model with Reinforcement Learning from Human Feedback https://arxiv.org/abs/2503.10434

Doe-1: 大世界模型下的闭环自主驾驶 arxiv link 引言 自动驾驶技术发展迅速，已从基于规则的系统演进到复杂的人工智能模型。该领域的一个主要挑战是创建能够有效感知环境、预测未来状态并规划适当行动的系统，同时保持这些组件之间的持续反馈循环。清华大学的研究人员开发的 Doe-1 框架是解决这个问题的突破性方法。 如上图所示，Doe-1 提出了一种新颖的闭环自动驾驶框架，它将感知、预测和规划整合到一个大型世界模型中。与传统的将这些任务作为独立模块处理的方法不同，Doe-1 将它们整合成一个协同的系统，以连续的循环处理信息，使车辆能够动态响应其环境的变化。 自动驾驶系统的发展演化 自动驾驶系统传统上采用模块化架构，包括感知（理解环境）、预测（预判下一步会发生什么）和规划（决定采取何种行动）等独立组件。这种方法虽然直观，但也存在一些局限性： 模块之间的信息丢失可能会累积，从而降低整体性能 受限的可扩展性，因为每个模块需要单独的设计和优化 组件之间的弱交互妨碍了对复杂场景的整体推理 如上图所示，自动驾驶模型已经经历了几个世代的发展： 模块化端到端模型（图 a）将感知、预测和规划分开，但同时进行训练 直接端到端模型（图 b）直接将观察映射到动作 LLM/基于 VLM 的模型（图 c）利用语言模型解释场景并决定动作 驱动世界模型（图 d, Doe-1）创建了一个闭环系统，其中所有组件持续相互作用 最近的方法已经开始整合大型语言模型（LLMs）和视觉语言模型（VLMs），以提升场景理解和决策能力。然而，这些模型通常以开环方式运行，意味着它们没有考虑车辆行动如何影响未来对环境的感知。 理解 Doe-1 框架 Doe-1 背后的关键洞察是将自动驾驶视为一个闭环系统，其中感知、预测和规划紧密相连： 如图所示，自动驾驶主要有三种方法： 端到端自动驾驶（图 a）：将观察转化为描述，然后转化为行动 自动驾驶世界模型（图 b）：根据行动预测未来观测 闭环自动驾驶（图 c）：结合了两种方法，形成了一个完整的循环 Doe-1 实现了闭环方法（图 c），这种方法有多个优势： 完整的反馈循环：行动影响未来的观察 统一表示：所有组件共享同一底层模型 时间一致性：系统在时间步之间保持连贯性 这种方法使得 Doe-1 能够处理需要理解行动长期影响的复杂情景。 The Closed-Loop World Model Doe-1 的核心是一个基于自回归变压器架构的大型驾驶世界模型。这个模型将自动驾驶视为一个下一个标记的预测问题，系统学习生成序列中多模态标记的适当下一个元素。 该图说明了驾驶数据（包括传感器数据、轨迹和感知信息）如何被组织成一个序列，输入到 Doe-1 世界模型中。然后，模型随时间在不同的模态（图像、文本和动作）上进行下一标记的预测。 ...

Working is not boring, Earning money is boring. 自己做的Project Euler的题解，不见得最优，也不见得优雅，但是答案是对的。基本上可以暴力求解的都是直接暴力求的。 Problem 1:Multiples of 3 and 5 暴力遍历，能整除3或者5的话累加 int problem1() { long num = 0; for (int i = 0; i < 1000; i++) { if (i % 3 == 0 || i % 5 == 0) num += i; } return num; } Problem 2:Even Fibonacci numbers 把4000000以下的 fib 数列都求出来，再遍历一般累加奇数。 这里其实 fib 数列的奇偶性是有规律的，按照 奇-奇-偶 的形式无限循环，所以也可以用数列的第几项是否能被3整除来判断。 int problem2() { long num = 0; vector<int> fib; fib.push_back(1); fib.push_back(2); while (fib.back() < (4000000)) { fib.push_back(fib.at(fib.size() - 1) + fib.at(fib.size() - 2)); } for (auto f : fib) { if (f < 4000000) { cout << f << endl; if (f % 2 == 0) num += f; } } cout << endl; return num; } Problem 3:Largest prime factor 从小打到大找因数，当找到一个因数之后将原始数字除以这个因数，再继续判断。 long long problem3() { vector<long long > nums; long long num = 600851475143; long long n = 2; while (n <= num) { if (num % n == 0) { nums.push_back(n); num = num / n; } else { n++; } cout << n << endl; } cout << endl << endl; for (auto i : nums) cout << i << endl; cout << endl << endl; return nums.back(); } Problem 4:Largest palindrome product 暴力遍历，判断是回文数后记录最大值。 ...

做 Project Euler 的过程中很多大整数运算，所以先撸了一个大整数加法和大整数,使用string作为输入输出参数 大整数加法代码： // 大整数加法 string BIGadd(vector<string> nums) { if (nums.size() == 0) return "0"; if (nums.size() == 1)return nums.at(0); string out = ""; int sum = 0; int maxdig = 0; for (auto i : nums) maxdig = MAX(maxdig, i.size()); for (int k = 0; ; k++) { for (auto i = 0; i < nums.size(); i++) { if (nums.at(i).size() > k) sum += nums.at(i).at(nums.at(i).size() - k - 1) - 48; } if (sum == 0 && k>=maxdig) return out; out = (char)(sum % 10 + 48) + out; sum = sum / 10; } } 大整数乘法代码： // 大整数乘法 配套上面的使用 string BIGtimes(string m, string n) { vector<string> adds; for (int i = n.size() - 1; i >= 0; i--) { string line=""; int sum = 0; for (int k = m.size() - 1; k >= 0; k--) { sum += (n.at(i) - 48) * (m.at(k) - 48); line = (char)(sum % 10 + 48)+line; sum = sum / 10; } if(sum!=0) line = (char)(sum % 10 + 48)+line; for (int k = n.size()-1; k > i; k--)line = line + '0'; adds.push_back(line); } return BIGadd(adds); }

问题 暴力求解 解答分析 对于循环次数 对于判断范围 若不是因为爱着你，怎么会夜深还没睡意。每个念头都关于你，我想你 想你 好想你。 若不是因为爱着你，怎会不经意就叹息。有种不完整的心情，爱你 爱你 爱着你。 问题 最近做了一些 Project Euler 的题目。目前只做了前十题，感觉和一般的编程题目比还是挺有意思的，单一案例，不限时间，不限做法，只要做出来的就可以，你愿意的话暴力求解，手动去算都可以，还是挺有意思的。 前面有几道关于质数 (Prime Number) 的题目，需要判断一个数是否是质数，也就是这次的问题了。 Problem 7. 10001st prime By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number? Problem 10. Summation of primes The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. ...

一、在安装Caffe之前需要进行依赖项的安装 二、下载Caffe源码并对其进行编译 三、Caffe编译错误 nvcc fatal : Unsupported gpu architecture ‘compute_60’ 四、基准测试代码运行错误 五、测试与资料 老文章搬运 最近想在Jetson TX1这个板子上学习Caffe和机器学习一些内容，于是把安装Caffe的过程和其中遇到的问题做一个学习笔记。 首先正常的安装可以参考Caffe的官网和网上数不清的教程，这里不再记录了，重点说安装中出现的问题与解决办法。 一、在安装Caffe之前需要进行依赖项的安装 这里很多地方都讲到了，需要安装一些依赖库，下面是找到的比较全的 sudo apt-get install libprotobuf-dev protobuf-compiler gfortran \ libboost-dev cmake libleveldb-dev libsnappy-dev libopencv-dev\ libboost-thread-dev libboost-system-dev \ libatlas-base-dev libhdf5-serial-dev libgflags-dev \ libgoogle-glog-dev liblmdb-dev gcc-4.7 g++-4.7 但是在这其中中在给JetsonTX1安装libopencv-dev时会无法安装，因为安装了libopencv4tegra，这个是NVDIA官方给板子已经装的，所以一般情况下这个包不需要进行安装直接跳过无视错误信息就好。 二、下载Caffe源码并对其进行编译 这里建议参考 Tegra TX1 安装配置 + caffe run 这篇文章讲到需要使用g++4.7进行编译，因为默认使用的g++4.8在编译时会发生错误，我第一次并没有看到这篇文章，所以也理所当然的出错了。 三、Caffe编译错误 nvcc fatal : Unsupported gpu architecture ‘compute_60’ caffe编译时出现错误： nvcc fatal : Unsupported gpu architecture 'compute_60' 在网上找了很多资料也没有直接说明白这个问题的解决办法的，因为关于JetsonTX1的资料太少，后来在这篇文章 ...

C用了很久了，但是也没有说很系统平铺的整体看过，一直是用什么会什么，不用什么就过去了。既然C已经被我当做是一门已经掌握的语言，所以就重新扫一遍C里面不那么面熟的东西或者理解有偏差的东西，当做是个记录以备复习使用，也可以对C打个结了。 auto && register && static 怎么也没想到会把这三个放在一起，一个是C++中常用的声明类型的关键字，一个没见过的，和一个还算常用的，这里主要理解的偏差还是在 auto 上。 在C++中，auto作为一种自动判断变量类型的定义存在，比如当我使用 auto c = 10; 去定义 c 这个变量的时候，是和 int c = 10; 的作用是一样的，这样可以节省很多去考虑这个变量具体是什么类型以及大量的敲字母的时间，还可以避免一些打字错误，比如 vector<map<int,string>>::iterator a = 这种东西可以直接 auto a = 还是挺爽的。顺便这里提一嘴，C++中的 auto 后面必须赋值，否则编译器不知道到底要初始化成什么类型的。 在C中，auto 关键字是用来指定变量的存储位置的。这也是为什么要和 static 和 register 一起讲。 static 说过很多遍也用过很多遍了，是存储在静态存储区的，而这个不太常见的 register 就是指的平时我们使用中的变量，是直接存储在堆或者栈中的，所以 auto 关键字就只是用来指定是用 static 修饰的还是用 register 修饰的，也就是新建变量的存储位置，举例： int a = 10; //平时这样定义就相当于 auto in a = 10; auto相当于省略 register int b = 10; static int c = 10; 注意的是，平时我们在 int a = 10; 这样定义的时候就相当于省略了 auto 关键字，上面这段在定义的时候就是 a 和 b 定义是在堆或者栈中的，c定义在静态存储区中。而且在使用了 auto register static 修饰后，仍然需要增加变量类型，因为他们并不是定义变量类型的，而是变量的存储区域。 ...

LeetCode Contest 149 No.2 这里有 d 个一样的骰子，每个骰子上都有 f 个面，分别标号为 1, 2, …, f。 我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。 如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），模 10^9 + 7 后返回。 一开始我以为这是一道数学题，排列组合的数学题 因为上学的时候就是那样做的，只是有些特殊情况 然后我发现这道题的特殊情况数都数不完，我傻了 有那么一个瞬间我在想会不会是 DP ，似乎有点像 但是我不确定，随便想一下也没有想到 DP 怎么做 于是我就放弃这条思路去看 airpods 去了。。。。 竞赛结束之后我看了看别人的答案，只看了两秒钟 这不就是DP么，我关掉解答开始自己好好做这道题 开始： class Solution: def numRollsToTarget(self, d: int, f: int, target: int) -> int: MOD = 10**9 + 7 nums = [[0]*target for _ in range(d)] for i in range(min(f,target)): nums[0][i] = 1 for k in range(1,d): for i in range(1,target): nums[k][i] = sum(nums[k-1][max(0,i-f):i]) return nums[-1][-1]%MOD 下面以5个骰子，每个骰子6个面，要求总和为16举例： 创建一个5*16的数组，横向代表骰子的点数总和，纵向代表骰子的数量，表格内的数字代表用x个骰子拼凑出y的点数总和，共有多少种情况 首先填写第一行的数据：用一个骰子扔出总和是 1、2、3、4、5、6 的情况均只有一种，用一个骰子扔出总和是7、8、9等的情况不存在 填写第二行的数据： 用两个骰子扔出总和是1的可能情况不存在 用两个骰子扔出总和是2的可能情况只有1种，是(1,1) 用两个骰子扔出总和是3的可能情况有两种，是(1,2)和(2,1) 依次类推 我们可以这样去考虑：第二个骰子可能扔出的情况是1、2、3、4、5、6六种情况，举例如果我们要填写第二行第八个空格，即要求扔出的总和为8，那么8的可能情况数量为以前的骰子扔出的情况为7、6、5、4、3、2这六种情况的总和。即，当第二个骰子扔出1时，以前的骰子总和为7，第二个骰子扔出2时，以前的骰子总和为6，依次类推 在表格中表示即为，某一格的值为在上一行不包括当前格子向左数六个格子的总和，即下图橙色框表示的区域 以此类推填写完整个表格 在本例中，表格右下角的数字即为5个骰子扔出总和为16的可能情况数量，为735 将本例拓宽到d个骰子f个面扔出总和为target的情况数量即为题目要求 下面重新看一下程序并将整个过程梳理一遍 class Solution: def numRollsToTarget(self, d: int, f: int, target: int) -> int: MOD = 10**9 + 7 nums = [[0]*target for _ in range(d)] # 初始化数组 for i in range(min(f,target)): nums[0][i] = 1 # 填第一行的数 for k in range(1,d): for i in range(1,target): nums[k][i] = sum(nums[k-1][max(0,i-f):i]) # 依次填写后面行的数 return nums[-1][-1]%MOD #返回最终数的MOD值 建立一个二维矩阵，行数为d，列数为target，矩阵内容初始化为0 将第一行前f个数填为1 对于剩余的格子，每个格子等于上一行向前数f个数的和 返回矩阵的最后一个数 DONE ...

Contest 130 通过：4/4 排名：59/1293 1:58:42 6WA No.1018 可被 5 整除的二进制前缀 思考过多，还在想那样做对不对，做的太少所以对题目类型不熟悉。 No.1017 负二进制转换 2WA emmmmmm，这道题怎么就过了呢。。。 思考过程：用几个数字尝试拼凑了一下，感觉上是要拼凑到最近的2的幂次上去，但是并没有找到绝对的规律。 然后发现某一位数字可以通过其他位来拼凑，如 $(2)^1=(-2)^2+(-2)^1$ ，然后将原始数字以4进制做拆分，再由低位至高位依次处理大于1的情况。例如：$9=1\times(-2)^0+2\times(-2)^2$，负二进制表示为201，然后从低位到高位，分别处理2、3、4的情况，200 和 11000 相等，300 和 11100相等， 400 和 10000 相等。最后即可得到结果。（好麻烦啊） 看了一下别人的回答，类似于二进制转换，得到 %2 后再进行 /2 的操作。区别只是在奇数位时+1而不是-1。不知道如何证明这样是正确的，但是感觉上是正确的，嗯。不懂得东西先记住就好了。 另外还有一点思考，如何证明负二进制是可以表示所有数字的呢，类似的，负三进制是否可以，负四进制是否可以，待求证。 No.1019 链表中的下一个更大节点 1WA 以前做过一道类似的题，维护一个栈，当下一个数字比栈顶的数字大时，取出栈顶的数字并记录，否则将下一个数字入栈，全部循环后若栈内还有数字，均输出0。 这道题对比了一下我的做法和别人的，思路是一样的，但是代码量差距很大，自己在这种问题的边界条件和条件分类处理上有点死板和脑袋不清楚，所以代码量大，代码思路也不是十分清晰，还需要多多练习。 No.1020 飞地的数量 3WA 前面大量时间浪费在了一个错误的思路上，第一反应是和做过的类似，进行一个DFS的遍历，遍历每一个“陆地”，然后向四个方向去搜索，看是否能够找到依然是陆地并接触到边界，如果能，那么不是飞地，如果不能，是飞地，然后标记，进行计数。后来发现越做思路越乱，且复杂，在进行深度搜索的时候还需要维护一个表去标记该地是否是已经搜索过的，极度复杂。然后转回去做第二题，做第二题的途中想到，应该反向去搜索，从接触边界的陆地进行深度搜索，每个搜索过的陆地都进行标记，为不是飞地的陆地，全部搜索遍历结束后，再进行遍历计数。 两个可优化的点：一个是根据看别人的代码发现，我是使用迭代进行深度搜索的，有人是使用一个 queue，需要进行搜索的陆地都推入 queue 中，在搜索过程中新搜索到的相邻的不是飞地的地也推入 queue 中，直至整个 queue 清空为止，感觉这种方法思路更加清晰一些，下次做到类似的题需要尝试一下。 另外一个是搜索上下左右四个方向的时候，建立一个数组 [[0,1],[0,-1],[1,0],[-1,0]]，然后对每个点循环加这四个变量即可，这种方法在前面做题过程中有见到提过，但是自己仍然没有用过，后面遇到一样的题也是需要尝试一下使用这种方法实现。

Contest 131 通过：4/4 排名：44/917 1:10:59 2WA 这次竞赛整体感觉难度一般，基本看到题目后直接就有思路，看了看其他人的做法，基本上思路一样。但是依旧~~~错的多、逻辑复杂、做题的时候感觉考虑清楚了但是做的时候细节还是有没考虑到的地方。速度嘛，不要求了，目前的目的还是能做出来吧。 No.5016 删除最外层的括号 1WA 一开始使用迭代器进行 string 的遍历，然后在测试的时候，有时候测试结果是正确的，有时候是 out of range，最后也没有发现是什么原因，就先去做剩下三个题了，回来之后改成循环数字下标就好了，可能是最后一个位置超出了 string 的长度，以后还是多用下标比较合适，除非循环内要做的工作比较简单。 No.5017 从根到叶的二进制数之和 一开始初始值给错了，没有大问题。 No.5018 驼峰式匹配 居然，做到一半的时候，忘记题目了！！！ 做到一半的时候只记得要匹配对了就可以了，完全忘记了是只能插入小写字母，但是还好还好这道题给的测试用例比较全面，才通过了。 另外可以多接触一下库啊，isupper这种函数的用法，多知道一些总是好事。 No.5019 视频拼接 1WA 完完全全忘记了那次错误提交是为什么，明明是昨天刚做过的题…… 嗯，那就没啥说的了

Contest 132 通过：3/4 排名：99/1047 0:59:44 1WA 最后一道题规定时间内没有做出来，超时7分钟做出来的，无错误提交（似乎）。 这次竞赛感觉看完题都比较虚，但是其实做题之后的效果比预想的好，虽然最后一道题规定时间内没有做出来，但是感觉可以接受，也是很久没有出过 hard 的题目了，这次的 hard 题目实现的相当的。。。。复杂且乱，但是能做出来就是好事。 No.5024 除数博弈 1WA 看到这个题，感觉可能是动态规划后，第一个想法：动态规划都是简单的题了啊！ 是的，这道题还花了整整20分钟才做出来，感觉其中十分钟浪费在了不可置信上和另外一些事情上。。。这次做竞赛太不专心了，批评一下自己，竞赛还是要好好做的。 实现思路上没啥可说的，就是动态规划的思路，从小到大依次遍历所有约数对应的N-x的值，所有约数全部为 true 的时候，这时无论先手做如何操作，对方都是必胜的情况，所以这时的 N 为 false ，其余所有情况均为 true ，只需要在每一步操作时将 N 的值变为对应的 false 的 N-x 的值即可。 No.5030 节点与其祖先之间的最大差值 一开始脑袋有点乱，想用 pair<int,int> 去实现同时寻找最大值最小值，但是思路一直没有理顺，抱着这次竞赛就放弃了的态度（。。。。）就想着先只写一个 max 吧，很快完成之后，同样的方法复制一份 min ，游戏结束。 思路：后序遍历，先左后右找最大最小值，然后向上计算最大差值，重复循环即可。 注：这里的最大最小值是需要跟着遍历走的，而且必须是后序遍历，这样才不会左右子树之间的最大最小值互串。 No.5025 最长等差数列 最没想到的一道题，看完题目毫无思路，而且感觉以前见过类似的题，但是没有做，也没有去找答案怎么实现，感觉自己栽在了自己的手上。按照上一道题的破罐子破摔的思路，想着就用朴素方法做吧，最后一道 hard 的题目看着也不面善，这个至少朴素方法的思路还是有的，甚至实现后都没怎么跑例子测试，没想到直接通过了。思路也没啥思路，暴力搜索。 TODO: 认真去看看别人的实现，回来写一下思路。 No.5031 从先序遍历还原二叉树 好可惜的题，有了思路之后只剩下不到二十分钟了，然后最后快到时的时候其实主要思路也完成了，缺少一个判断，没有理清楚逻辑放在哪里，生生拖到七分钟。 字符串！字符串！字符串！重要的事情，唉，说三遍也不管用，不知道第几次栽在字符串上面了，但是我的字符串水平还是停留在磕磕绊绊能实现上。用了一个超复杂的方式把原始字符串的数据整齐的摆放在了一个 vector<pair<int,int» 当中，嗯，是我做事情的风格，东西要摆整齐。后面遍历问题倒是不大。 用一个 stack 保存当前处理的 TreeNode 节点，并留一个变量保存当前深度，对每一个新的数字，判断深度的关系:。情况1：如果新数是当前节点的下一层，判断当前节点的左子树是否为空，为空的话放在左子树，否则放在右子树。情况2：如果新数是当前节点的层数或者更高层，从 stack 中取出上一个保存的节点，并且深度-1，直到满足情况1为止。情况3：如果新数是当前节点的下一层以下，将当前处理的节点推入 stack 中，并且深度+1，这时需要判断当前节点的右子树是否为空 ，如果为空的话当前节点等于当前节点的左子树，否则为当前节点的右子树，直到满足情况1为止。 看到这里，我居然又忘记为什么这么判断了，唔，应该是因为原始数据为先序遍历的结果，所以新数如果比当前节点的子节点更深的话，有两种情况。一种是先序遍历的左子树，这时候左子树有值，右子树为空，那下一个处理的节点必定为左子树。另一种情况是之前经过了情况2后当前处理的节点上升到了该层，这时候当前层的左子树已经处理完毕了， 所以如果右子树不为空的话，当前要处理的必定在右子树内。 好了，什么乱七八糟的，因为是先序遍历，先输出再遍历左再遍历右，所以如果右子树有数的话，必定左子树是完整的了，所以如果右子树不为空，就继续处理右子树，否则处理左子树。OVER。 这次竞赛给我的感觉就是，感觉这道题应该有更好的办法吧，感觉这样实现好蠢，但是一时半会又想不到好的解决办法，最后直接使用朴素方法去实现，但是也没想到，其实朴素实现的结果都还不错，至少通过了，也没有出现超时的现象，虽然这个不应该是目标，目标应该是和我的能力之间有一段距离的，这样才能够得到提升。但是也告诉了我一个现在我做题时的一个不太好的想法，一直去寻找方法，而忽略朴素的实现方法，所以经常有时候一道题看了看没有好思路就一直放着，放很久都没有做。这样做一下竞赛，对自己有压力了，不得不做了，就会着急不管用什么方法先做出来再说，也会让自己踏实一些。 PS: 再碎碎念一下，过年的时候报名的比赛，居然忘记比了！居然忘记比了！！！简直了，当时就感觉这么久以后的事情到时候可能会忘记吧，果然不假。

Contest No.15 Biweekly 通过：4/4 排名：43 / 797 0:46:11 1WA No.5126 有序数组中出现次数超过25%的元素 给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。 请你找到并返回这个整数 示例： 输入：arr = [1,2,2,6,6,6,6,7,10] 输出：6 提示： 1 <= arr.length <= 10^4 0 <= arr[i] <= 10^5 我很认真地按照题目意思去做的。。。后来翻看别人的答案恍然大悟，其实就是求众数，可以用collections.Counter() 加上 most_common就可以了 时间复杂度：$O(n)$ class Solution: def findSpecialInteger(self, arr: List[int]) -> int: a = len(arr)//4 ln = 9999999999 n = 0 for num in arr: if ln == num: n+=1 else: ln = num n = 1 if n>a: return ln class Solution: def findSpecialInteger(self, arr: List[int]) -> int: c = collections.Counter(arr) return c.most_common(1)[0][0] No.5127 删除被覆盖区间 给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。 只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。 ...

Contest 167 通过：4/4 排名：107 / 1534 1:43:12 5WA No.5283 二进制链表转整数 给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。 请你返回该链表所表示数字的 十进制值 。 示例 1： 输入：head = [1,0,1] 输出：5 解释：二进制数 (101) 转化为十进制数 (5) 示例 2： 输入：head = [0] 输出：0 示例 3： 输入：head = [1] 输出：1 示例 4： 输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0] 输出：18880 示例 5： 输入：head = [0,0] 输出：0 提示： 链表不为空。 链表的结点总数不超过 30。 每个结点的值不是 0 就是 1。 嗯，水题。 时间复杂度：$O(n)$ class Solution: def getDecimalValue(self, head: ListNode) -> int: ans = 0 while head!=None: ans = ans*2+head.val head = head.next return ans No.5124 顺次数 我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。 请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表（从小到大排序）。 ...

Contest 168 通过：4/4 排名：61 / 1552 1:08:39 1WA No.5291 统计位数为偶数的数字 给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。 示例 1： 输入： nums = [12,345,2,6,7896] 输出： 2 解释： 12 是 2 位数字（位数为偶数） 345 是 3 位数字（位数为奇数） 2 是 1 位数字（位数为奇数） 6 是 1 位数字 位数为奇数） 7896 是 4 位数字（位数为偶数） 因此只有 12 和 7896 是位数为偶数的数字 示例 2： 输入： nums = [555,901,482,1771] 输出： 1 解释： 只有 1771 是位数为偶数的数字。 提示： 1 <= nums.length <= 500 1 <= nums[i] <= 10^5 嗯，水题。（但是大佬一行代码。。） 时间复杂度：$O(n)$ ...

最近在使用进行MATLAB进行一些计算的时候因为计算时间实在是太长了（五天。所以开始考虑进行算法优化，就在这时无意间看到了系统的CPU占用率，what？25%哈哈哈哈哈或或或或或或或或，matlab个ZZ。于是想起了parfor这回事，算法用的是动态规划算法，但是在每个递推过程中也要计算$2000 \times 2000$个循环，正好可以用并行计算，perfect，条件允许，直接开始！ 要啥简介，直接开干 来看一个简单的不能再简单的例子，我们用for将一个数组乘以2 n = 1000; a = rand(n,1); for i=1:n a(i) = a(i) * 2; end 试着跑一下，没什么问题（这要有啥问题可以不活了），看一下运行时间 Elapsed time is 0.000034 seconds. 一个n x 1大小的随机数组，然后把其中每个数乘以二，下面就是改成parfor并行计算的 n = 1000; a = rand(n,1); parfor i=1:n a(i) = a(i) * 2; end so easy。这样就改好了，matlab果然易用，同样看一下时间 Starting parallel pool (parpool) using the 'local' profile ... connected to 4 workers. Elapsed time is 32.119578 seconds. WTF，本来想要提高效率的，怎么会变得这么慢，不过看说明似乎干了些别的，再跑一遍试试？ Elapsed time is 0.183769 seconds. 看上去时间正常多了嘛不过还是比正常跑慢，怎么回事？首先如果看到上面这些，恭喜，这就是已经开始多核心并行计算了，后面我们来具体分析及使用MATLAB的并行计算。 MATLAB并行计算解释及分析 首先通俗解释一下我们做的事情，比如我们有一堆砖要搬，从A搬到B再搬到C结束。正常情况下，我们有一个小伙子来做这件事，他一次一次把所有砖从A搬到B再搬到C。这就是正常情况下的计算。 但是我们的CPU是多核心的，例如我们是有四个小伙子的，但是在搬砖过程中，这四个小伙子只有一个小伙子在搬砖，另外三个小伙子在围观。。。这怎么可能快嘛，但是我们的小伙子很能干，只要砖不是非常多，工作都能很快完成，时间差距不大，所以也就不需要所有人都上了。 并行计算就是让这几个小伙子都动起来，一起去做这件事，这样才能更加效率的解决工作量比较大的问题。在上面的例子中我们就是这样去做的。 但是 为什么第一次运行这么慢：因为matlab开始并行计算之前，需要进行一些预备工作，这些工作默认是没有开启的，所以在第一次进行并行计算的时候，需要首先进行预备工作，花费一些时间，这样时间长也是理所当然的了。 为什么第二次还是这么慢：虽然在工作中有更多的小伙子来干活，但是在干活中，还需要有一个人去给这些小伙子分配工作，这个分配工作的动作也是需要耗费时间的，这样在工作量非常小的情况下（如上例）这个分配工作的时间可能比做这项工作消耗的时间都要长，这样最终反而计算时间更长。 Parallel Pool 的设置 然后我们来看一下 MATLAB 中关于并行工具箱相关的设置： （matlab版本使用2015a，其他版本请找相关设置 matlab 中去做这项工作的部分叫做 Parallel pool。在 matlab 的设置界面中或者主界面的左下角的图标处可以进入并行计算工具箱的设置。大概长这样： 最上面的 Clusters 是关于计算的集群的设置，请选择 local （后面看我努力程度是否出个搭建集群的教程吧，非常简单） 点击蓝色文字处 Cluster Profile Manager 就可以对本地的这个 Cluster 进行配置了，中间最重要的配置是 Number of workers to start on your local machine 这个决定了有多少个小伙子给你干活，默认情况下，CPU 是几核的就填几。（这一步在实际运行中有一些疑问，核心数or线程数，等待后续进一步验证。）修改后可以顺手点击 Validate 进行验证，几项测试都通过的话就说明配置没有问题，退出设置后点击同样在主界面中左下角菜单中的另外一项 Start parallel pool 就可以打开了，或者在程序中运行到 parfor 时 MATLAB 也会自动开启。 ...

[TOC] 继续上一次的Project Euler的题解，不见得最优，也不见得优雅，但是答案是对的，思路也是没问题的。这次是11~20题。 Problem 11:Largest product in a grid 在一个20x20的表格内在横竖斜四个方向上找连续四个数字的最大乘积。 暴力遍历就对了，输入直接复制过来通过文本输入，给一个二维的 vector<vector<int>> ，开始可劲的遍历，计算四个方向。为了避免边界条件判断，这里分成了两部分，一部分向右，下，右下遍历，一部分向左上遍历，同样能遍历所有情况，同时避免了边界条件判断。 void problem11() { int out = 0; string input ="08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\ 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\ 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\ 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\ 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\ 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\ 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\ 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\ 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\ 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\ 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\ 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\ 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\ 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\ 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\ 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\ 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\ 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\ 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\ 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"; vector<int> nums; stringstream ss; ss << input; int n; while (ss >> n) { nums.push_back(n); } for (int i = 0; i < 15; i++) { for (int k = 0; k < 15; k++) { int nn = nums.at(i + k * 20) * nums.at(i + k * 20 + 21) * nums.at(i + k * 20 + 2 * 21) * nums.at(i + k * 20 + 3 * 21); out = MAX(out, nn); nn = nums.at(i + k * 20) * nums.at(i + k * 20 + 20) * nums.at(i + k * 20 + 2 * 20) * nums.at(i + k * 20 + 3 * 20); out = MAX(out, nn); nn = nums.at(i + k * 20) * nums.at(i + k * 20 + 1) * nums.at(i + k * 20 + 2 * 1) * nums.at(i + k * 20 + 3 * 1); out = MAX(out, nn); } } for (int i = 0; i < 15; i++) { for (int k = 3; k < 19; k++) { int nn = nums.at(i + k * 20) * nums.at(i + k * 20 - 19) * nums.at(i + k * 20 - 2 * 19) * nums.at(i + k * 20 - 3 * 19); out = MAX(out, nn); } } cout << out << endl;; } Problem 12:Highly divisible triangular number 题目写的挺绕的，按步骤做就好了，先是一个1 ~ n的等差数列的和，我这里用的方法麻烦了，在每个周期上加i就可以了。然后计算1 ~ sqrt(k)之间的能被整除的数字数量，乘以二就是因数数量，这边没有单独判断k是平方数的情况（因为这种情况根本不存在，k=i*(i+1)/2），最后判断一下数量大于500输出结果即可。 ...

[TOC] 继续上一次的Project Euler的题解，不见得最优，也不见得优雅，但是答案是对的，思路也是没问题的。这次是21~30题。 Problem 21:Amicable numbers 对于x，除自己以外的因数的和定义为d(x)，求出1000以下的所有满足d(a)=d(b) && a!=b的数对并求和。 遍历->求所有因数->求和记录->遍历判断并求和 void problem21() { map<int, int> mm; int out = 0; for (int i = 1; i < 10000; i++) { int sum = 0; for (int k = 1; k <= (i / 2); k++) { if (i % k == 0) sum += k; } mm.insert({ i, sum }); //cout << i << " " << sum << endl; } for (auto i : mm) { if (mm[i.second] == i.first && i.first != i.second) { cout << i.first << endl; out += i.first; } } cout << out << endl; } Problem 22:Names scores 有一群名字，要求排序，排序之后每个名字的数字和乘以位数再求和。 emmmmm，这个题似乎做得有一点点抄近路，直接STL排序，然后遍历求和即可。 void problem22() { string trianglefilename = "p022_names.txt"; ifstream fin; fin.open(trianglefilename, ios::in); vector<string> lines; string s; while (getline(fin, s)) { lines.push_back(s); } fin.close(); long out = 0; lines = split(lines.at(0), ','); for (int i = 0; i < lines.size(); i++) { lines.at(i) = lines.at(i).substr(1, lines.at(i).size() - 2); } sort(lines.begin(), lines.end()); for (int i = 0; i < lines.size(); i++) { int sum = 0; for (int i : lines.at(i)) { sum += i - 64; } out += sum * (i + 1); } cout << out << endl; } Problem 23:Non-abundant sums 完美数，除了本身以外的因数的和等于自身。 deficient，因数和小于自身；abundant，因数和大于自身。 这题太难解释了，直接题目抄过来自己看题目吧。 ...

罗马不是一天建成的，你也不会一下成为梦想中的人，但是只要在学习在努力，就是越来越接近的。 继续上一次的Project Euler的题解，不见得最优，也不见得优雅，但是答案是对的，思路也是没问题的。这次是31~40题。 (奇怪，这人怎么又开始用python写了 Problem 31: Coin sums 嗯。。挺经典挺常见的完全背包DP问题，但是我满脑子不知道在想什么，愣是没做出来，后来看了看别人的提示才想到应该按照硬币种类去循环。一直在想怎么去处理重复的情况。 这里是这道题的详细解释 这里是完全背包、01背包、多重背包的比较的参考资料（我没看 def pro31(): # 完全背包DP coin = [1, 2, 5, 10, 20, 50, 100, 200] methods = [0]*300 methods[0] = 1 for k in coin: for i in range(1, 210): if i >= k: methods[i] += methods[i-k] print(methods[200]) Problem 32: Pandigital products 很蠢的一个做法，每一个去遍历判断的 def pro32(): out = [] for i in range(10, 10000): numl = [] k = i while k != 0: if k % 10 not in numl: numl.append(k % 10) k = k//10 else: break if k == 0: for j in range(2, int(math.sqrt(i))): if i % j == 0: numll = [] k = j while k != 0: if (k % 10 not in numl) and (k % 10 not in numll): numll.append(k % 10) k = k//10 else: break if k == 0: k = i//j while k != 0: if (k % 10 not in numl) and (k % 10 not in numll): numll.append(k % 10) k = k//10 else: break if (k == 0) and (len(numl)+len(numll) == 9) and (0 not in numl) and (0 not in numll): print("%d %d %d" % (i, j, i//j)) if i not in out: out += [i] print(sum(out)) Problem 33: Digit cancelling fractions 这个问题第一次考虑的时候考虑错了，以为分子和分母相同的数字肯定一个在十位一个在个位的，导致一开始答案是错误的。其实可以在外层循环增加一些判断，这样速度会快一些。。。 ...

Lecture 1: Introduction to NLP and Deep Learning What is Natural Language Processing Intersecting of computer science artificial intelligence linguistics Goal let computer process or “understand” NL to perform tasks Performing tasks question answering Fully understanding and representing the meaning of language is a difficult goal. NLP Levels speech text Phonetic/Phonological Analysis OCR/Tokenization Morphological analysis (单词结构的形态分析) Syntactic analysis (句法分析) Semantic Interpertation (语义理解) Discourse Processing (上下文，语篇处理) (A tiny sample of) NLP Applications Spell checking, keyword search, finding synonyms Extracting information from websites Classifying Machine translation Spoken dialog systems Complex question answering NLP in industry … is taking off Search (written and spoken) like Spell Check Online advertisement matching Automated/assisted translation Sentiment analysis for marketing of finance/trading Speech recognition Chatbots/Dialog agents What’s special about human language a system specifically constructed to convey the speaker/writer’s meaning ...