graph 算法题目思考

Graph算是非常常见的题目，一般会给你一个2d array或一个数组代表联系，你可以使用这个输入来转换成一个图表示的数据结构，之后在图里做搜索。常见的算法：

• BFS，DFS
• union find
• A*
• Floyd and dijkstra

Leetcode里的题目的话主要都是dfs, bfs就可以解决，有些需要思考几个之间的关系的题目可以使用union find来做。少部分计算路径的题目需要使用一些基本的最短路径算法。

Array 算法题的思考

数组类的算法是在我做的题目中是最多的，相对来说也是最好理解的它也可以包罗万象，使用各种各样的算法。用数组可以实现很多基本的数据结构。比如heap。所以这部分需要好好掌握。

SWAP

需要应用到数组元素交换是一类非常常见的题目，比如说求最大的K个数，这种题目一般都是使用基本的快速排序思想。也就是说，我们把这个数组分成两部分，一部分是比当前这个数字大的，另外一部分是比这个当前数字小的，这样我们可以快速的把一个array分成两部分，然后再分别对这两部分进行处理。

如果只是需要移动一些数字，比如说移动零或者整个数组只有三个数，那么可以用一些更简单思想，比如说记录下所有非0的数，或者记录下这些数字的个数，然后把前面全换成这些非0数，后面换成零。这样做的好处就是不需要交换。或者一个记录非0的地方，另外一个记录当前位置，如果这个不是零，那么就遇上一个非0的东西交换。所以总体思路都是双指针的思想，一个记录当前遍历的位置，另外一个记录上一次符合条件的位置。

• 27. Remove Element
• 75. Sort Colors
• 283. Move Zeroes
• 215. Kth Largest Element in an Array

subarray

这又是一大类数组常遇到的题目，比如说求子数组的和，或者判断这个子数组是否符合某些规律等等。与字符串处理substring有异曲同工之妙，一般也都是双指针，如果发现和大于某个值的时候，那么就把起始值增大。

String 算法思考

String 类型的题目算是leetcode里第二多的题型，其实这个和array的使用方法差不太多，只不过其中有一些特定的使用场景。我在这里会将string分为几类问题，可能不能包括所有的类别，尽量使用较为统一的思路解释遇到的题目。

数据类型

首先要说清楚一点，在java中String是immutable的，也就是当你创建一个string后是不能修改的，如果你需要给他加内容，java会重新创一个新的实例。这样的问题就是如果使用s+=a,这样时间复杂度是O(n),在java中会重新复制一遍string再给你创建。

解决办法就是使用StringBuilder，这个的时间复杂度对于增加就是O(1).其中内部实现就是一个char[]

• sb.append(String str)
• sb.toString()

组合问题

这类问题就是需要得到某个字符串中包含的所有子集,或者是permutation.这类题日非常相似，需要找出符合条件的所有组合。基本思路是样的，可以使用DFS与backtrack实现。例如 Combination Sum,可以把这题变成一个子问题选择了数字n后，求解sum-n的子问题的解答。所以可以先排序选择第一个元素，然后在函数中记录以下这些：

树形算法题的思考

树形是一大题型，这类题目相对来说比较简单，在我看来掌握树形的最大要点就是递归的思想，这可以说用在了这类题目中的方方面面。主要涉及这些题型：

• 构建树（数组，链表）
• 遍历，判断是合理的树
• 找节点（LCA）
• 树的基本属性（高度），找路径

构建树

这类题目的基本思路就是先找到根结点（root），然后把整个数组或者链表分成左右两个部分。之后，这个根节点的左子树就是递归调用数组的右半部分。右半边子树就是递归调用，这个函数的右半部分。总体还是比较简单的，题目可以参看

• 108.Convert Sorted Array to Binary Search Tree
• 109.Convert Sorted List to Binary Search Tree

这里有一道题，关于如何利用链表来构造。其中有一点，它可以使用一个固定的prev linked list node。在每次递归结束的时候都会调用next，这样我们就不需要每次遍历找到中心结点，而是利用之前的结果来找到中间的那个节点。也就是说，在这里我们并不需要一开始就把父节点找到，而是可以先存好左子树，之后再到root。

学习方法

学习的原因

人学习的原因是为了获得更多的知识，更加了解这个世界，并将它们使用在生活中使自己过得更好。所以对于我来说学习知识的意义就在于应用它们。透过学习，我们能够做到从未能做到的事情，重新认知这个世界及我们跟它的关系，以及扩展创造未来的能量。人们可以把认知过程分为6个阶段，即知识、理解、应用、分析、综合、评价。面对不同的学习领域，所需要达到的认知程度也是不同。对于某领域的专家那么就可以评价，而这个知识对于自己的生活关系不大时，只需达到第一个阶段即可。

另外成长型心智的人也会更加乐于学习。他们倾向于超越自己，往往会以自身进步为标准，常常处于尝试或探索状态，最终是自我解放，在不断学习中不断成长。

当今世界的发展速度太快，新的知识层出不穷，如果不持续学习，一直使用以前的方法，那么很有可能被他人淘汰。没有个人核心竞争力的话那终将被他人取代，这就是社会的残酷。而找寻个人特长的方法就是不断学习，走在他人的前面。

学习能力

学习能力的定义

学习能力或称专家精神的概括性行为表现：紧跟本专业内新知识、新技术动态，并运用到实际问题解决，能在本领域的研究项目中发挥主要作用，乐于分享知识经验。

• 动机 (motives)：从动机上，学习能力强的人，必定是一个认知需求水平比较高的个体。一个认知需求高的个体，肯定是格物致知的人，必定在某些领域掌握更加精深或偏向原理性的基础知识，所以也许他的方向很偏，但总能分享一些这样的知识点，而且这些知识点不应该是松散的，而应该是聚焦莫一或某几个领域的。
• 个性特质 (traits)：从个性特质上，学习能力强的个体和一般的个体也是有差异的，比如爱钻研、爱看书。学习本身对他来说会比较容易，但更应看到的是，学习过程本身对这类人也是一种享受。
• 自我形象 (self-image)：学习能力好的人，绝对不是学过什么就扔一边的人， 他们优秀的学习动机和能力能使得他们成为一个领域的专家
• 社会角色 (social role, values)：一个学习能力强的人，是不会自己憋在肚子里“财不外露”的，而且大部分学习能力强的人遇到同一领域的共同爱好者，会倾囊相倒。因此，知识的分享，也是学习能力强的人的一种表现
• 经验 (experience)：你曾经成功迅速学习过哪门知识，掌握过什么能力与技巧？分享一下你之前所需的知识与技能吧（这块跟上面分享心得是有差异的）。这块实际上你就不用听内容，你就看他表情和语气语调以及呼吸频率等非语言线索，真正学习能力强并通过学习对工作有过帮助的人，会自如地侃侃而谈，看他讲话的感觉，肯定特享受。换句话说，这时候他的自我效能感爆棚，感觉这一亩三分地，自己就是真正的主人。
• 知识 (knowledge)：你知道你所从事职业的新兴思想潮流吗？你知道最新崛起的几位大家是谁吗？你能说说你最喜欢的职业领域几位大牛吗，能比较一下他们的成就和思想吗？作为面试官，那怕你面试的是个土木工程师而你对土木一窍不通也没关系，如果他在编，你就让他编，放心吧，一个人讲的时候的流畅程度和自信程度是装不出来的，如果没有点实在货，三句话就露怯。

学习知识的来源

我的学习的知识分为以下几大块：

运动

运动的意义

运动对于人的各个方面都有一定的好处。从科学的角度来说，可以促进血液循环，增强心肺功能，提高身体免疫力。运动也可以帮助睡眠，保持好心情。当今社会，由于生产方式的改变，导致人们运动越来越少。但是从人的天性来说，有一定的运动量才符合人们的生物规律。一个好的身体也是工作的本钱，如果生一场大病那么你将无法完成任何事情。所以说适当的运动，对于人的各个方面都非常有用，你一定需要在日程中安排固定的时间来运动

运动的目标

运动的目标多种多样，我认为有以下几种目的：

1. 增加肌肉
2. 减少脂肪
3. 训练耐力
4. 训练力量
5. 塑造形体

每一种运动的目的都可以产生不同的运动计划和方法，弄清楚自己的训练目标非常重要。可以从以下三个方面来思考

时间管理的意义

为什么我们需要管理时间？因为时间是唯一有限的资源，时间是一去不复返的，而其他的都可以再生。任何人都无法回到过去，每一分每一秒都是我们需要管理好的财富。俗话说时间就是金钱，金钱人们很少会乱花，对于大笔的开支都会仔细算计，有人甚至会做预算，计划好未来的开销。时间也是一样,把时间花在有意义的地方十分重要。

管理时间的目的就是为了实现自己人生的目标，所以找好自己人生的目标是第一步。你希望十年后，二十年后的你是怎样的呢？这个问题真的需要我们每个人好好思考一下。因为这个问题决定了你准备过一个怎样的生活。找到了人生目标之后就需要思考为了达成这个目标你需要做一些什么事情，不要做有悖于目标达成的事。这些安排可以是长期的，也可以是明天就可以开始做的事情。我认为管理时间的对象是任务、事项，而不是时间。时间只是我们做某件事情所需要花费的代价而已，管理好自己需要做的事情，也就是计划分配多少时间到这些事情之中。

再次阅读李笑来的《跟时间做朋友》，对于时间管理有新的想法。重中之重是明白积累的力量。

设立目标的一些注意事项

在设立目标的时候要知道自己的能力，注意可实现性。越不切实际的目标越不可能实现，你也会越早的放弃。一种好的方法就是事前验尸，思考可能导致自己失败的原因。假设你已经失败了，你可能在什么地方出错。

营养的种类

营养的意义

营养素在人体内的功能主要分为3个方面：

1. 供给能量和维持体温
2. 作为“建筑”材料构成和修补身体组织
3. 作为调节物质，维持机体的正常生命活动，如同机器中的润滑油一样

人体所需能量和营养素

能量

能量是维持人生命活动必不可少的部分，单位一般为千卡或千焦。1kcal=4.184kJ. 能量的消耗主要由以下4个方面

技术文档写作

1. 思想的组织

1.1 金字塔原理

• 结论先行：一篇文章只支持一个中心思想，这个中心思想将概括各级各组的所有观点，必须放在文章最开头。
• 以上统下： 上一层级的观点必须是对下一层级观点的概括，下一层级的观点是对上一层级观点的解释、支持。
• 归类分组：把具有共同点的观点归类分组，同一组中的观点都必须属于同一个范畴。
• 逻辑递进：每组中的观点都必须按照逻辑顺序进行组织。

1.2 序言

1.2.1 SQAC

• S:背景 介绍读者熟悉的某些“背景”
• Q:疑问 由此引发读者最初的“疑问”
• A:回答 针对该“疑问”给出的“答案”，也就是文章的中心思想
• C:冲突 说明发生的“冲突”

1.2.2 TOPS

• Target to Audiences 有的放矢 内容面向读者，抓住读者的注意力
• Overarching 贯穿整体 能够全面概括后面的内容
• Powerful 掷地有声 有见解
• Supportable 言之有据 有论点可以支撑

1.3 自上而下构建

1. 提出中心思想
2. 设想读者最初提问
3. 写序言
4. 与读者进行疑问、回答式对话

1.4 自下而上构建

1. 列出想表达的所有观点
2. 找出各观点之间的逻辑关系
3. 概括总结，得出结论

1.5 归类分组

• 相互独立（ Mutually Exclusive）：同一组的各个观点之间必须相互独立、相互排斥，没有重叠。
• 完全穷尽（ Collectively Exhaustive ）：同一组的所有观点完全穷尽，没有遗漏。

1.6 逻辑顺序

• 时间顺序
• 重要性顺序
• 结构顺序

2 语言的表达

2.1 文章的易读性

2.1.1 词汇

突出含义、简洁易懂、避免歧义，明确是否