P、NP、NP-hard 和 NP-complete 是计算复杂性理论中的关键概念，用于描述不同类型的计算问题以及它们的求解难度。 P 类问题 P 类问题是指多项式时间内可以通过确定性算法解决的问题。这意味着，给定一个输入，问题可以在有限的步骤内得到解决，且步骤的数量是输入大小的多项式函数。换句话说，P 类问题的求解效率较高。例如，最短路径问题和排序问题都是 P 类问题。 NP 类问题 NP（Non-deterministic Polynomial time）类问题是指能够在多项式时间内验证解是否正确的问题。换句话说，虽然找到问题的解可能比较难，但一旦给出了解，我们可以在多项式时间内验证它是否正确。一个典型的 NP 问题是旅行商问题：找出某个城市之间的最短旅行路径可能很复杂，但给定一条路径，我们可以快速验证它是否满足要求。 NP-complete 问题 NP-complete 问题是 NP 类问题中的一种特殊类型。这类问题满足以下两个条件： 它是 NP 类问题，意味着给定解后可以在多项式时间内验证其正确性。 它是 NP …
在面试流程（例如筛选）的早期阶段，一位 Google 招聘人员曾向我问过这个问题。 在C++中，当你使用std::map访问一个不存在的键时，行为取决于你是如何访问它的。 使用下标操作符 访问时 如果键不存在，std::map 会默认插入一个该键的元素，并为其赋值为类型的默认值。比如，如果 map 的值类型是 int，那么它会插入该键并赋值为 0。 例子： std::map<int, int> myMap; int value = myMap; // 如果键10不存在，会插入myMap = 0 使用 at() 方法访问时 如果键不存在，at() 会抛出 …
我那辆奥迪Q5 SUV今年年检没通过，原因是左前车灯坏了，需要更换。车厂告诉我，光是订购零件就要700多英镑，加上人工费，总费用得1000英镑。但没办法，如果不修，车辆年检（MOT）就过不了，车也不能上路。 MOT是英国的机动车强制性安全检测（Ministry of Transport Test）的简称。 近侧前位置灯不工作 drl/位置灯集成（4.2.1(a)(ii)） Nearside Front Position lamp not working drl/position light integrated(4.2.1(a)(ii)) 上周我先去做了年检，花了50英镑。由于距离年检到期还有两周多，我先把车开回家，车厂同时订购零件。等了一个周末，大概三天后，车厂打电话让我把车送回去更换车灯。 车厂老板说90%的可能是车灯的问题，但不能完全确定，因为也有可能是线路的问题。他还说，如果去奥迪4S店检查，光是检查费就要200英镑。我问他对车灯问题有多大把握，他说他们是家族企业，经营多年，有足够的经验。此外，他还说，车上的线路看着很正常。 感觉这些车的零件本身就很贵。估计以后修保时捷会更贵。Q5这车也不算新了，那灯我也没觉得有多好看，但价格真是离谱，况且平时在车里也看不到车灯啊。 记得四年前右前车灯坏了，修理费才花了将近400英镑，当时在另一家车厂修的，车还在那里放了一周多，耽误了不少事。两三年前，车灯时好时坏，车厂订了个小零件，花了100多英镑，但后来发现不是那个问题。车厂建议我去4S店，告诉他们不是那个零件的问题。因为问题只出在白天行车灯上（Daylight），不影响年检结果，所以我当时没太在意。 车厂说，今年MOT规则改了，所有的车灯都必须正常工作。 奥迪没大问题，但小问题不断。之前我那辆A6的车门打不开，修了一次花了300多英镑，也因为不修年检过不了。听说奥迪还有“灯厂”之称。 今天去取车时，车厂老板和另一个人闲聊，说：“你看，这就是奥迪Q5的灯，一个灯就要1000英镑。”我问他这灯能用多久，他说正常情况下可以用很长时间。 奥迪之所以被称为“灯厂”的原因 奥迪之所以被称为“灯厂”，主要是因为其在汽车照明技术上的创新和领先地位。这个绰号的背后有几个关键原因： 早期的LED灯应用：奥迪是最早将LED（发光二极管）技术应用于车灯系统的汽车制造商之一。2004年，奥迪在A8车型上首次使用了LED日间行车灯。这种灯光设计不仅提升了车辆的辨识度，还为未来的汽车灯光技术发展奠定了基础。 激光大灯技术：奥迪在2014年推出了激光大灯，进一步提升了车灯照明的亮度和射程。激光大灯比传统的氙气或LED灯更加高效和强大，使夜间驾驶的视野更加清晰。 矩阵式LED大灯：奥迪开发了矩阵式LED大灯技术，该技术可以根据路况和对面来车的情况智能调节每个LED光源的亮度和角度，从而避免眩光，同时提供最佳的照明效果。这不仅提升了安全性，还极具科技感。 …
同步到微博 | 小破站 | 小红书。 过往都是体验: 来英国整整20年 All the past are experience. 转眼间，我已经来英国整整20年了，时间过得飞快。 2004年9月9日，我带着雅思6分（6666）的成绩来到英国留学（1+2模式，北京一年，国外两年，水本），降落在伦敦希思罗机场。那时，我一个人住在离学校仅3分钟路程的宿舍里，没有网络，每次上网都得去大学图书馆。到英国的第二天，我在街上花了12英镑买了一个电话号码，这个号码我一直用到现在。那段时间，我每周花5英镑买长途电话卡，给家里报平安。记得第二天我还拿着1英镑投进学校旁的电话亭，给家里打了个电话，结果说不到10秒钱就用完了。身上带着1600英镑现金，第一次用50英镑在小卖部买了面包和牛奶，花了大概1英镑多，店员还问我有没有小一点的零钱，因为50英镑面额太大。当时英国的物价，18个鸡蛋只要99便士。 同年，我开始打工，在Luton的一个类似劳工中介的地方找到了一份工作，但只做了一天就放弃了。工作很累，需要坐一个小时的车去工厂，在流水线上不停地往盒子里放马铃薯，重复的机械工作让我的手臂第二天酸痛不已。 年底时，我在一家中餐外卖店找到了一份工作，每周五和周六从下午3点工作到凌晨2点，包两顿饭，报酬是40英镑。那时最开心的事就是下班回家，洗完澡后边看《老友记》边吃饭。刚开始时，我还花5英镑让同在外卖店打工的中国人接送。后来业务熟练了，工资涨到了50英镑。为了提高效率，外卖店要求我们记住100多个对应菜名的数字，这样点餐时只写数字就能很快完成。 2005年暑假，我在大学里找到了一份为期一个月的合同工，帮助升级大学办公室的电脑，一个月下来挣了700多英镑，这是我在英国的第一份待遇较好的工作。 2005年，我开始在Luton的Brookes酒吧打工，负责调酒，持续了大概10个月，每周末工作两班，总共20小时。当时我还不到22岁，时薪是4.25英镑。每次夜店结束后，我最喜欢的任务就是扫地和捡酒瓶，因为经常能捡到钱。最长一次工作是下午1点到6点，然后休息1小时，接着从7点干到2点。 2006年，我以一等学位毕业，平均分是15.51/16分（3个A+，5个A），同年9月全奖读博。 2007年3、4月，通过了博士的开题报告。 2008年读博时遇到瓶颈，整个暑假都在家里打DOTA。突然有一天，灵感来了，瓶颈也随之解开。同年过了博士中期考核的答辩。 2009年，我获得了去瑞士交流学习一年的机会。因为签证拖延，晚了一个月才出发。那段时间，我经常往返于瑞士Fribourg和英国Luton，每周都坐Easy Jet（英国有名的廉价航空），并且有很多出差机会，那一年我飞了42次。 2010年1到5月，我几乎都在外面出差。5月17日从中国回到英国，5月20日通过了博士答辩。5月18日我还去了牙医那儿准备拔牙，牙医得知我两天后要答辩，建议等答辩通过后再拔。 2010年6月，我认识了现在的妻子。答辩通过后我无心写作，后来妻子催促我赶紧改论文并提交，我才动笔。同年我顺利博士毕业，年仅25岁。博士期间水了好几篇文章所以借着公款去了欧洲几个国家旅游：德国、法国、希腊、波兰、瑞士。 毕业后，我加入了一家创业公司，并申请了当年的Tier-1 General高技术移民签证。 2011年，我搬到了谢菲尔德，第一次考驾照没通过。 2012年8月，我结婚了，大娃出生，第二次通过了驾照考试。 …
2003年，我参加了高考，暑假后便到了北京，9月份入学中国农业大学国际学院（ICB）。不过当时我是通过“计划外”入学的，因为高考成绩没能达到农大的录取分数线，所以是自费进入这个中外合作办学项目的。大一在国内学习，大二大三则出国。 2003-2004学年是我计算机知识突飞猛进的第一个阶段。那时我非常专注于学习，学院还专门为我和另一位同学请了一位外教。我淘了一台二手老电脑，装了Windows 95/98系统。其他同学都在玩游戏，而我的老电脑只能用来学习和编程。我的宿舍床上堆满了计算机书籍，大多是从二手书市场或者地摊淘来的。那个时候我可能一个学期都没换过被子，床上卫生环境可能很糟糕。 学院有专门的计算机实验室，我们当时学习的是Java，Applet编程还很流行。我记得那时C#刚刚问世。我觉得电脑课上的内容很简单，于是外教给我布置了一个特殊的题目，并承诺如果我能完成，期末考核就给我A+。最后我确实做出来了，他也信守承诺给了我A+。 英文：The Computers at Early 2000s 本文一共 354 个汉字, 你数一下对不对. 回忆起20年前大学时期的学生生活(2003-2004电脑长什么样?). (AMP 移动加速版本) 赞赏我的几个理由. ¥ 打赏支持 扫描二维码，分享本文到微信朋友圈
“回溯 = DFS + 剪枝” 是一个对回溯算法简明且直观的描述。要理解这一点，我们可以先拆解这个等式中的几个关键概念。 深度优先搜索 (DFS) DFS（Depth-First Search）是一种图或树的遍历算法，它从根节点开始，沿着一个分支深入到尽可能远的节点，直到达到叶子节点或无可拓展的节点，然后回溯到上一个节点继续搜索其他分支。这种搜索策略自然地适合解决需要遍历所有可能状态的问题，如组合、排列问题等。 剪枝/Pruning 剪枝（Pruning）是指在搜索过程中，提前排除不符合条件的分支，以减少计算量。剪枝的主要作用是在搜索的过程中，避免无谓的计算。通过某些条件判断，可以在尚未完全展开某些分支时就停止搜索，从而减少时间复杂度。例如，当我们知道一个分支肯定不会产生有效解时，可以提前终止该分支的搜索过程。 回溯算法/Backtracking 回溯算法可以看作是深度优先搜索DFS的一种特例或具体应用。它采用DFS的思想，在搜索的过程中尝试每一种可能的选择（通常是通过递归实现），并在发现某个选择不符合条件或已经无法产生有效解时，及时回退（即“回溯”），然后继续尝试其他选择。这种“试探—回溯”的过程就构成了回溯算法。 结合三者的理解 DFS 为回溯算法提供了基本的搜索框架，即从起点开始沿着一个分支深入探索； 剪枝 则是在DFS基础上增加的优化步骤，目的是减少无效状态的探索。 因此，“回溯 = DFS + 剪枝” 是对回溯算法的一种总结。它表明回溯算法不仅仅是简单的深度优先搜索，还通过剪枝来提升效率。剪枝使得回溯算法在解决很多问题时比单纯的DFS更加高效，尤其是在解空间很大的情况下，剪枝能够大幅减少计算量，从而使得问题求解变得可行。 例子：Alpha-beta 算法剪枝 Alpha-beta 剪枝可以看作是一种回溯算法，它通过剪枝技术增强了深度优先搜索算法。 …
