《Hello算法》笔记
本文探讨了工程问题求解的挑战、布尔量的内存存储、深度优先遍历二叉树的方式、二分查找的应用限制、辅助哈希表求解两数之和问题,并提供了动态规划问题的判断标准。
1.在工程领域中,大量问题是难以达到最优解的,许多问题只是被“差不多”地解决了。问题的难易程度一方面取决于问题本身的性质,另一方面也取决于观测问题的人的知识储备。人的知识越完备、经验越多,分析问题就会越深入,问题就能被解决得更优雅。
2.即使表示布尔量仅需 1 位(1或0),它在内存中通常也存储为 1 字节。这是因为现代计算机 CPU 通常将 1 字节作为最小寻址内存单元。
3.深度优先遍历就像是绕着整棵二叉树的外围“走”一圈,在每个节点都会遇到三个位置,分别对应前序遍历、中序遍历和后序遍历。
4.二分查找仅适用于有序数据。若输入数据无序,为了使用二分查找而专门进行排序,得不偿失。因为排序算法的时间复杂度通常为O(logn) ,比线性查找和二分查找都更高。对于频繁插入元素的场景,为保持数组有序性,需要将元素插入到特定位置,时间复杂度为O(n) ,也是非常昂贵的。
5.辅助哈希表求解两数之和。
6.判断一个问题是不是动态规划的方法:
(+)问题包含最大(小)或最多(少)等最优化描述。
(+)问题的状态能够使用一个列表、多维矩阵或树来表示,并且一个状态与其周围的状态存在递推关系。
(-)问题的目标是找出所有可能的解决方案,而不是找出最优解。
(-)问题描述中有明显的排列组合的特征,需要返回具体的多个方案。