这题应该是第三遍做了，依旧不记得怎么下手。 题解：递归+后序遍历 递归解析： 终止条件： 当越过叶节点，则直接返回 null ； 当 root 等于p,q ，则直接返回 root； 递推工作： 开启递归左子节点，返回值记为 left； 开启递归右子节点，返回值记为 right ； 返回值： 根据 left 和 right ，可展开为四种情况: 1.当 left 和 right 同时为空 ：说明 root 的左 / 右子树中都不包含 p,q,返回 null； 2.当 left 和 right同时不为空 ：说明 p, q 分列在 root 的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root； 3.当 left 为空 ，right 不为空 ：p,q都不在 root 的左子树中，直接返回 right 。具体可分为两种情况： (a)：p,q 其中一个在 root 的右子树中，此时 right 指向 p（假设为 p ）； (b)：p,q 两节点都在 root 的右子树中，此时的 right 指向 最近公共祖先节点 ； 4.当 left 不为空 ， right 为空 ：与情况 3. 同理 出处链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/ 就是普通的层次遍历，输出进行反转，没有看是否有更优解。 题意：按顺时针螺旋顺序依次打印矩阵中的元素 拿到题目第一想法： pop出矩阵的第一行，然后将矩阵逆时针旋转90度，再继续pop第一行… python实现代码如下： 其中java代码如下： 参考链接：https://leetcode-cn.com/problems/spiral-matrix/solution/mo-ni-guo-cheng-by-powcai-2/ 另外一种思路是，给出一个方向列表[(0,1),(1,0),(0,-1),(-1,0)]表示右，下，左，上的顺时针顺序。用visited保存遍历过的矩阵下标，当row,col越界，或矩阵元素已经访问过时，则利用方向列表进行转向！！

leetcode刷题

第一想法：用动态规划，建立一个dp数组 后看解析，发现可以用内存为O（1）的复杂度实现 新建两个头节点node1，node2； 遍历原链表，将小于x的结点跟在node1后面，大于等于x的结点跟在node2后面 最后将两个链表拼接起来 第一反应是用暴力把所有的按字典序排序的结果存到一个序列中，但是超时了。 后来看到题解中，用双指针法，发现真的是绝了这个思路，但是又觉得有点投机取巧了。 记得这道题我做腾讯笔试的时候做过类似的题目，当时同学用的回溯法，后续找到补上来。 先给出双指针的：

manifold笔记（科普类）

manifold theory
? 黎曼开始了关于延展性，维数，以及将 延展性数量化的讨论。他给了这些多度延展的量（几何对象）一个名称，德文写作 mannigfaltigkeit, 英文翻译为 manifold，英文字面意思可以理解为 “多层”，中国第一个拓扑学家江泽涵（北大老教授）把这个词翻译为 “流形”，取自文天祥《正气歌》，“天地有正气，杂然赋流形”，而其原始出处为《易经》，“大哉乾元，万物资始，乃统天。云行雨施，品物流形。” 这个翻 译比英文翻译更加符合黎曼的原意，即多样化的形体。。。。。 这是转的，看论文时搜到的，感觉挺解惑的！ 这个翻译第一眼看的时候太奇异了！ 作者：看海 链接：https://www.zhihu.com/question/30553302/answer/311788410 来源：知乎 data：20190509 黎曼，是一个养活了近一个世纪的数学家，并（目测）将要养活接下来至少500年的数学家的男人。 我对数学史不是很熟（以后有机会说不定会开个专栏扒扒历史），所以我这里写的所有和数学史有关的内容你都可以认为我在胡扯（对，我就是懒得查资料……）。今天只想谈谈数学，我会尽量做到科普，所以不要追究我的细节。我对这篇文章的定位是睡前读物，可能很长，但是绝对不会难读懂。 以及，不要因为看了我的文章而走上民科的道路，想要真正了解请老老实实从数学分析线性代数学起。 先PS：知乎上总有人问数学到底有啥用，我觉得我可以试试说点用处出来，虽然那些用处肯定不会是那些人的满意答案。 OK，Let's start! 流形的概念绝对是一个非常伟大的构想，以我浅薄的数学史知识，这个概念第一次出现大概就是在黎曼为了谋一份教职而做的一份公开报告里。在黎曼之前，几何几乎就是笛卡尔的坐标（当然这个也是一个非常伟大的概念），大家总是在一个高维的欧氏空间做东西。欧氏空间，大家可以理解为横平竖直的那种空间，比如的三维欧氏空间，就是在牛顿绝对时空观下我们生活的世界。二维的呢？就是高中折磨了大家很久的解析几何。关于这样的空间的例子，其实我们有很好的直观：比如两点之间直线最短，过直线外一点有且仅有一条直线和已知直线平行，三角形内角和180度等等，这些都是大家从小学就知道的事情。黎曼说，你们考虑的东西啊，TOO YOUNG！ TOO SIMPLE！应该考虑所谓的流形。 流形是啥呢？大家知道足球吧，就那个黑白花纹的，一块一块皮缝出来的球形物体。其实每一块皮基本上都是平的（就是你能理解的那种“平”），但是缝起来就是个足球。流形也是一样，它的比较数学化的表述是，有一个点组成的集合M，M中每一个点的附近都有一个邻域，那个邻域和欧式空间“长”的差不多（数学术语叫同胚，很形象的一个词）。还是刚刚的足球，足球上每一个点都在某块皮上，那块皮扯下来就是个平坦的东西。（不要追究细节，不要追究细节！） 这个概念为啥重要呢？因为大家的视野一下子变得不一样了！以前我们看几何对象，我们都是所谓的“外蕴”的看，就是说，我们在这个几何体在的更高维的空间里看它，比如足球，它是个二维的东西（就是一大块布嘛），但是我们是在三维空间看它。所以我们一眼就知道它是弯的！（对，就是你能理解的那个弯）可是假设你是在大航海时代前的人，你怎么知道地球其实是弯的？就跟足球一样弯？你不知道，你就算知道你也不确定你是不是真的知道。对于这种情况最常用的比喻就是，假如你是一只生活在足球上的蚂蚁，你怎么知道你是生活在一个足球上，而不是一个铺了和足球同样材质的、很大很大的（大到你一辈子都走不到边的）桌面上？ 流形的概念告诉我们，其实我们真的不知道，因为我们视野范围是有限的，而有限的范围内的东西和横平竖直的欧式空间一模一样……流形的概念伟大之处也在这里，它表明我们其实想要研究更加一般的空间，我们就不应该“外蕴”的去看它，而是应该“内蕴”的去看。什么叫“内蕴”，你就理解为，在流形自身上看。 伟大的黎曼告诉我们，其实“内蕴”的看能知道的东西比你想象的多得多。最简单的，我们是可以在不环游地球不走到太空里的情况下，知道地球是圆的。在说着这个之前，要谈另一个概念：度量。 其实度量从它名字来看就能理解，度量度量，就是量一量长度嘛。人类规定了单位米尺的长度，所以我们就可以度量北京到上海的距离，可以度量你一根手指的长度，一根发丝的长度。对于这种规定了怎么量长度的空间，数学上称为度量空间。而我们最熟悉的那种量长度的方式（其实你只知道这一种，相信我），称为欧氏度量。一个例子就是初中的二维的笛卡尔坐标，两个点之间的距离就是他们横纵坐标的差平方和再开方，那就是二维的欧式度量，也是我们认为最自然的度量。但是（凡事都要有个但是），度量并不是唯一的，就是说还存在其他量距离的方式。 最简单的，我说咱们这么量距离：随便两个不同东西之间的距离都是1（米），相同的东西之间的距离是0（米）（这里最开始有误，给大家造成误导了，现在是正确的版本）。你会发现你想要的性质它都有，比如你会要求 你先去北京再到上海的总路程（我这里是1+1） 不能比 直接去上海的总路程（我这里是1） 短（这个性质称为三角不等式），我这个度量显然满足。你还会要求我从上海到北京的距离和从北京到上海的距离是一样的，你看我的度量也满足，大家都是1。最后，你肯定还要求从北京到北京的距离是0，我的度量依然满足！最后的最后，你会要求说距离不能是负的吧，没事，我这儿要么是1要么是0，都不是负数。（数学上来说，满足这几条性质、再满足距离为零的只能是同一个物体的性质的一个二元函数就是一个度量） 其实咱们老祖宗早就知道了度量不唯一这件事情，所以他们发明了一个成语：缩地成寸。怎么缩地成寸？很简单嘛，定义一个度量（不是我上面说的平凡度量），任何两个东西（比如我和你）之间的距离永远不超过1米（这种度量存在，而且满足三角不等式），那北京到上海多远？反正1米不到。你身高多少？1米不到。你体重多少？……额，那是另外一回事了。注意，我们这里只谈距离（就是你理解的那个距离） OK，到这里，你脑子里应该有这么一个印象：我们生活的空间的所谓长度，其实只是某一种特定的测量方式得出来的长度，而这种测量方式并不是唯一的。（事实上有无穷多种方式来量，但是它们之中有很多是很无聊的，大家不去研究它们，比如我上面说的那个平凡度量）。下面，最有意思的来了。我们知道地球是个球，它不是欧氏空间，所以不存在无穷延伸的平直的直线，你在地球上随便找个方向一直走，总会回到原点的。所以其实你在地球上用的度量并不是你熟悉的欧氏度量，两点之间直线最短这句话，根本就是骗人！ 你的世界观崩溃了有没有！ 事实上，欧氏空间也不过是一种特殊的流形，流形才是最本质的概念。黎曼在一般的流形上定义了一类特殊的度量（就是规定了一种特殊的但是会比较有意思的怎么量距离的方式），我们称为黎曼度量。有了黎曼度量，我们就可以研究这个流形到底是不是弯的？有多弯？我们可以研究上面的“直线”是什么东西，从而我们可以研究怎么才能最短的从一个点到另一个点。翻译成人话就是有了黎曼几何，我们确信我们可以知道，一架飞机从北京飞到上海，怎么飞路程最短。甚至，我们在北京做一个足够精确的测量，我们就能知道地球是弯的。 ? 鉴于概念已经够多了，这次介绍的先到这儿吧。下次会在这个基础上继续谈谈黎曼几何，重点会介绍到底什么线是最短的，也就是说流形上什么东西是直线的推广。 我说这么多话，其实就是想给大家传达一个意思：数学不难，数学很有趣。但是，想要真正了解数学，请老老实实从数学分析线性代数学起。拒绝民科，从你做起。 ? ? ? 上回说到：我们生活的空间其实是个流形，测量距离的方式叫做一个度量，这回，我们就来聊聊这个流形上的“直线”是个什么玩意儿。 在欧氏空间里你为什么有直线的概念？因为你知道那就是一个坐标轴转一转：你轻轻的拿起x轴，然后在手中挥舞两下，再随便一扔，声称得到了一条直线。众人皆认为你说的好有道理，无言以对。可是流形就麻烦了，它没有坐标轴，它的坐标都是局部的，那直线同学的户口落哪儿好呢？落在北京这个邻域？还是落在上海那个邻域？你可以很聪明的说，很简单嘛，我们在这个邻域甲（就是不想用字母，以防吓坏小朋友）中取一条直线，然后对于和甲相邻的邻域乙（其实数学的定义中会要求这样的两个邻域的交集不是空集，虽然之前的那个足球的例子比较难看出来，你就想象成两块皮要缝起来，总要相互重叠的），我们的甲乙两块皮，哦不，两个邻域相交了，在相交的地方我们的直线已经定义好了（因为在甲上已经定义好了），所以在乙的坐标里面看，你就有一个小线段，我们把它延长，这不就得到了乙中的一条直线么，两个拼起来不就是比原来更长的一条直线了么。这样一步一步，似魔鬼的脚步，延长延长，在这光滑的流形上延长……你想的太简单了，因为你没有办法保证你在甲里面看是直线的东西到了乙里面就一定还是直的！（它会被掰弯的！） 说道这里，就到了我们的主角登场了，那就是真正意义上“直线”同学的身份证：测地线！（此处应有灯光效果+掌声）。 而在正式介绍它之前，我有必要对流形上的度量做一点说明。上次我说，度量就是量距离的方式，而流形往往是一个坑坑洼洼的东西，那上面的线也都是弯弯曲曲的，怎么测量一个弯曲的东西？物理告诉我们，很简单，你开着车走一趟，用每个时刻的速度乘以一小段时间，最后加起来，你就知道多长了。原理就是你在很短时间内把自己走的路当成直线，用你的速度乘以这么一小段时间就得到了一小段直线的距离，把所有这些小线段加起来就能近似原来曲线的长度。当这样的小时间取得足够短的时候，你也就足够接近真实的曲线长度（对学过一点微积分的人而言，这不就是积分嘛）。 速度，在流形上有另外一个高大上的名字叫切向量。一条曲线的长度，就是通过它每一点 切向量大小 的积分得到的。切向量的大小 是虾米？这就是我们的度量真正量出来的。也就是说，我们的度量不是真的测量曲线，而是测量曲线每一点的切向量（就是说我们的度量不是量路程的，它很笨，它只能告诉你速度多大），要得到最终的曲线长度，我们还需要一个积分的步骤。 至此，我们知道了曲线怎么求长度。于是流形上任何两个点之间的一条曲线，我们可以求它的长度，而流形上的“直线”，其实就是这两点间距离最短的那条曲线。既然这么一条曲线是最短的，那我们知道在它周围生活的曲线们都比它长，所以在连接这两个点的所有曲线生活的空间上定义一个函数叫做 求曲线长度函数，那么我们的测地线就是这个 求曲线长度函数 的最小值点。一般来说数学上对于这种最小值，最大值的点，都有办法描述他们，通常是用一些方程来描述。于是，我们的测地线的定义的终极版本粗线了：就是满足某一组特定方程的流形上的曲线。 所以怎么判断一条曲线是不是测地线？很简单，代入那组方程看看是不是成立就好了。反过来，解出那组方程，你就可以知道这个流形上所有的测地线长什么样子。一个很有意思的例子就是，我们亲爱的地球君，它上面的测地线就是所谓的“大圆”，就是所有过球心的平面和地球相交出来的那个圆。终于，我们知道从北京到上海怎么走最短了：取北京，上海，地心三个点，我们知道三个点确定一个平面，这个平面和我们的地表相交于一个大圆，北京和上海都在那个圆上，你只要沿着短的那条弧线从北京跑到上海，数学保证你走的路最短。（当然实际情况更复杂，地球也不是完美的球面） 最后的最后，请和我一起默念三遍咒语： 最短的是测地线，测地线不一定是最短的 最短的是测地线，测地线不一定是最短的 最短的是测地线，测地线不一定是最短的 作者：zero 链接：https://zhuanlan.zhihu.com/p/19880460 来源：知乎 data：20190509