主要指的是时间和空间复杂度的权衡。感觉大的出发点有两个：
查找出现次数超过一半的数字。一半显然对应着中位数，因此只需要进行基于快排划分的期望时间是O(n)的查找即可。需要注意的是，可能会出现不允许修改原始数组的情况，这个时候可以使用计数的方法进行判定：如果下一个数字和之前保存的数字相同，则计数加一，否则减一，当计数为0时更新保存的数字。显然计数到最后保存的数字就是出现次数超过一半的数字。
查找数组中的前k个数字，方法与上题一样。需要注意的是海量数据的情况，在不修改原始数据的情况，可以使用堆或者红黑树实现提取前k个，可以借此熟悉一下multiset容器上的操作。
计算数据流的中位数，在书中对于几种可选数据结构进行了较为详细的分析。如果排除AVL树的话，使用堆实现比较好，因此考虑使用最大堆+最小堆组合的方式，最大堆放左侧数据，最小堆放右侧数据。
需要注意的是，如何确保最大堆中全部的数据都小于最小堆中的数据。这里可以采用将数据全部先插入最大堆，之后把堆顶出队后放入最小堆，这个方法比较巧妙。在完成这个操作之后，如果原来是需要在最大堆插入，则把最小堆的堆顶在出队放入最大堆。这道题在leetcode分类是hard，确实需要认真思考一些技巧。
还需要注意的是STL里面最大堆模版是less<int>，最小堆是greater<int>。盲猜是因为按照递减less排序的时候需要最大堆？
计算连续子数组的最大和，使用动态规划即可，注意不是子序列(子序列也可以用do做，但是状态转移方程不一样)。
计算1出现个数，主要是先发现数学规律，再合理设计递归形式，避免直接暴力计算。具体可分为两种情况分别处理：
当然，为了进一步提高效率，可以使用while循环的方法替代递归形式。
和上题类似，也是数学规律题。直接把结果对应位置算出来就行了，不要暴力模拟。
题目有两个地方需要注意，第一是自定义sort的比较函数，第二是处理大数问题——转换成字符串数字的拼接和比较。如果需要详细数学证明的话，那么就相对比较麻烦，按照书中的要求应当从自反性、对称性和传递性三个方面去分别证明。
数字翻译成字符串，实际是动态规划问题。状态是以第i位结尾的字符串，选择是单独作为字符or与之前的字符一同翻译(如果合法)。
礼物最大价值，也是个二维迷宫数组上的决策问题，显然应该利用动态规划的思路来优化。在完成基本的动态规划之后可以考虑进行空间的压缩。
字符串上的子串，显然暴力是O(n^2)，观察可知字串的选取具有在字符串上滑动的效果。因此如果这道题有优化思路的话，应该是利用滑动窗口摊还分析到O(n)。可以借助hash表来判断当前窗口在添加新数据的时候是否有重复出现；如果有，则需要收紧窗口左边界。
这种做法需要维护一个hash表，并且在窗口滑动中不断插入/删除，可以学习书中的做法，用数组记录上次访问到该字符时对应的字符串下标，之后分情况讨论：如果当前字符串之前出现过，并且当前下标到到之前对应字符下标的距离小于记录的上次最长子字符串，要重设新的最长不重复子串长度长度为这个距离，否则直接在上一步的最长不重复子串上累加1即可。需要注意及时更新记录访问的数组。
首先抛出了一个新的定义——丑数。之后应当分析一下定义，最好把前几个丑数写出来，分析一下规律。一旦写出了前六七个丑数，就大概能看到规律了。2、3、4、5、6、8、10、12...可以发现，如果一个数是丑数，则它可以写出2^a*3^b*5^c的形式，其中(a+b+c>=0, a>=0, b>=0, c>=0)，这也表明了每一个新的丑数都是从之前的丑数基础上乘2、3、或5得到的，因此我们需要记录上一个可能被乘2、3、5的位置，并比较三种选择中产生的最小值作为新的值，插入到数组中。
显然，暴力的方法时间复杂度为O(n^2)，因此优化时应当思考如何走一遍O(n)就得到结果。可以使用hash表来统计访问的次数。这样一层循环就可以得到结果。
数组的逆序对。应当与排序问题联系起来，因为排序就是逐步消除数组中的逆序对。可以使用归并排序，在分治的过程中统计逆序对的个数。具体实现应当在两个有序数组融合的时候，进行逆序对的统计。
求两个链表的公共节点。可以形式化地把链表画出来，然后可以发现链表的首个公共节点就是链表开始分叉的地方。因此，假设两个链表的连接方向全部调转，那么首先分叉的节点就是要找的节点。而链表的反转就是后序遍历。可以利用辅助栈来实现这个比较。如果不允许使用辅助栈，则需要考虑先将两个链表的长度变为相等后再比较。
原文：https://www.cnblogs.com/hesun/p/13399942.html