【面试真题】求和问题 & 三门问题
发布网友
发布时间：2024-12-30 15:06
共1个回答
热心网友
时间：2024-12-30 17:46
给定一个非负整数数组 nums 和一个非负整数目标值 target，请在该数组中找出和为目标值 target 的两个不相等的整数，返回它们的数组下标。
示例1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例2：
输入：nums = [2,3,2,5,1,4], target = 4 输出：[1,4] 解释：因为 nums[1] + nums[4] = 3 + 1 == 4 ，返回 [1, 4] ；而 nums[0] 和 nums[2] 相等，因此不能作为答案。
本题和经典的 LeetCode 题类似：
题目很 easy，只要有 coding 基础 的童鞋应该都毫无压力。一次遍历即可，使用一个哈希表在遍历过程中记录每个数字对应的下标。同时，每次遍历时判断下 target 减去当前数字后的值是否出现在哈希表中。如果是，并且这个数字和当前数字不相等，那么就返回它们的下标即为答案。时间和空间复杂度都是 O(n) 。
也可以不额外使用哈希表，而是对数组作切片，切出当前数字之前的部分替代哈希表的角色：
在前面的题目中要求两个整数不相等，这里放宽，改为：只要两个整数相加等于 target 即可，无论这两个数字是否相等。但是，数组中同一位置的数字仅能使用一次。
前面的题目仅要求返回一种满足条件的答案即可，而这次是在(ii)的基础上要求返回所有满足条件的答案。
EASY~! 我们修改下哈希表的模式：将每个 key 对应的 value 由1个下标(int)修改为1组下标(list)。这样，不同位置上数值相等的数字才不会互相覆盖。
另外，每遇到一个满足条件的答案，我们都记录到一个 list 中，而非立即将它返回。
在利用两数之和(ii)中实现的函数(可进行适当修改)，实现三数之和。
三数之和很容易转化为两数之和。我们可以遍历数组，记每次遍历的数字为 nums[i]，每次遍历时计算 remain = target - nums[i]，然后将这个 remain 作为新的 target 转化到数组中 nums[i] 后面的部分 nums[(i+1):] 去求两数之和。
发现我毫无压力地将之前的题目都 KO 掉了，面试官放了个大招，当时他的原话是这样的：
其实无论是两个数还是三个数甚至四个数求和都好，都是归属于求和问题，既然这样，你就实现下满足求和为 target 的所有方案吧。无论是两个数字还是三个数字、N个数字，只要能够加起来等于 target，就是满足条件的答案，你最终只需要返回满足条件的方案数即可。
经历过刚刚的三数之和转化为两数之和求解的过程，我已经有了一种 insight：N 数之和可以转化为 N-1 数之和，N-1 数之和 又可以转化为 N-2 数之和 ... 这形成了递推的状态转移方式，那么一种解决思路当然就是 DP——动态规划了！
令 dp[i][s] 为遍历到第 i(i=0,1,..,n-1) 个数时和为 s(s=0,1,..,target) 的方案数，分情况考虑：
同时，对于数组中不大于 target 的那些数字，我们可以初始化：dp[i][nums[i]] = 1
由上可知，i 时刻仅和 i-1 时刻的状态相关，因此可以压缩掉这一维，以实现空间优化：
最后来了道经典的三门问题：
有三扇门，其中只有一扇门里有奖品。现在玩家去抽奖，选中有奖品的那扇门即为胜利。在选择一扇门之后，主持人会帮他在剩下两扇门中去掉一个肯定没有奖品的门，最终剩下1扇门。
这时，玩家可以选择：最终剩下的那扇门 或者 坚持原来一开始选择的门。请问他应该选择哪种策略？这两种策略下他获胜的概率分别是多少？
请先用数学理论进行解释，再使用代码模拟出这两种策略的选择过程(模拟1000次实验)以及计算出对应的概率。
Easy to know, 如果坚持最开始的选择，那么玩家获胜的概率就是1/3 。
而如果选择最终剩下的那扇门又想要获胜，那么一开始选择的那扇门必定不能有奖品，这种情况发生的概率为2/3 。接下来在此基础上，主持人会剔除掉没有奖品的那扇门，那么剩下的就自然是有奖品的门了。因此，后面这种情况发生的概率为1。于是，最终获胜的概率就是 2/3 。
这场面试还挺好玩的，公司主要考查应聘者的算法基本素质和学习能力，同时还有一方面就是和企业文化相关：talk is cheap, show me the code! 通常的面试 coding test 一般也不会超过3道，像这种整场面试都由 coding test 贯穿始终的实属罕见。都是风景，幸会！
