复试智力题和LEETCODE算法代码题目总结

一、智力题

1. 你让工人为你工作 7 天，给工人的回报是一根金条。金条平分成相连的 7 段，你必须在每天结束时给他们一段金条，如果只许你两次把金条弄断，你如何给你的工人付费？

考虑到7=1+2+4，即三位的二进制，刚好切两次，切成1,2,4，这样每天都可以的工资都可以用这三段来表示，其中需要和工人进行交换

1. 一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。 每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子

如果只有一个人戴黑色，则第一次关灯就知道自己是黑色，如果是两个人带，则，第一次因为对方没打，所以知道自己应该也是黑色的，所以第二次关灯会打自己，如果是三个人带，则第一次看到两个人有黑色，但没打，可能是只是他们，但是第二次还没打，说明自己也是黑色，否则第二次就打了，故第三次会一起打，即有三顶黑色帽子

二、机器学习

1. 统计学习三要素：模型，策略，算法
实现统计学习步骤

• 有限训练数据集合
• 确定可能的模型的假设空间，即学习模型的集合
• 确定模型选择准则，即学习策略
• 实现求解最优模型的算法，即学习算法
• 选择最优模型
• 利用模型进行预测

2. 基本概念

• 输入空间、特征空间、输出空间：一般输入空间和特征空间不区分，有时为不同空间，让输入空间映射为特征空间
• 联合概率分布
• 假设空间：监督学习的目的就是找一个输入和输出的映射关系，这些映射关系的集合就是假设空间，学习到的模型就是这些映射关系的最优解

三、力扣代码题目

**1. **Two Sum

题目描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

class Solution(object):
  def twoSum(self, nums, target):
    dct = {}
    for i, n in enumerate(nums):
      c = target - n
      if c in dct:
        return [dct[c], i]
      else:
        dct[n] = i

解题思路

利用enumerate函数，一次遍历记录住数组的内容和下标，如果对应的值在字典里，就可以返回其下标，否则将其内容映射为字典的下标

**2. **Binary Search

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lens = len(nums)
        high = lens -1
        low = 0
        while(high >= low):
            mid = int((high + low)/2)
            if target == nums[mid]:
                return mid
            elif target > nums[mid]:
                low = mid + 1
            elif target < nums[mid]:
                high = mid - 1
        return -1

基础的二分查找，需要注意重新设置的时候要把low的+1，high的-1，否则可能会无限循环。