最近面试遇到的算法题汇总

背景

今年受疫情的影响，工作不太好找。也投了不少简历，只有几家邀面试的：58同城、最右、快手、新东方，除了最右其它都是视频面试。总的来看：公司对个人能力要求还是挺高的，面试问的问题都是由浅入深，算法也是必考的。

算法

1、用递归写一个算法，计算从1到100的和。

func sum(value: Int) -> Int {
    if value <= 0 {
        return 0
    }
    let number = value
    return value + sum(value: number - 1)
}

写完算法之后又围绕着问了几个问题，都是算法基础：

• 算法的时间复杂度是多少?

  $O(n)$

• 递归会有什么缺点？

  数据规模过大时，容易造成栈溢出。 每一轮递归都要分配栈空间，做栈帧平衡。

• 不用递归能否实现，复杂度能否降到 $O(1)$？

  可以。使用等差数列通项公式：$n*(n+1)/2$。具体实现如下：

  func sum(n: Int) -> Int {
      return n * (n + 1) >> 1
  }

2、给定一个Int型数组，用里面的元素组成一个最大数，因为数字可能非常大，用字符串输出。

分析：实际上就是一个排序而已，只不过它是按高位优先级更高的原则，这一点跟字符串的比较保持一致，如果再加一些Swift的高阶函数，很容易写出来。

func largestNumber(_ nums: [Int]) -> String {
    let sort = nums.map {"\($0)"}.sorted {(lStr, rStr) -> Bool in
        return lStr + rStr > rStr + lStr
    }
    let result = sort.joined()
    if result.prefix(1) == "0" {
        return "0"
    } else {
        return result
    }
}

3、给定一个Int型数组，找出第一个只出现一次的数字。

分析：可以通过遍历把数组元素存入到字典中，以数组元素的value为字典的key，数组元素的index为字典的value。在遍历过程中，如果遇到重复的key，则更改其value为一个定值（为避免出错，这里设这个定值为数组元素的count）。那么遍历完成后，字典中所有value=count的key即为数组中存在重复的数字，而其它的key（即数组中不存在重复的数字）的value肯定是小于count的，这时候我们再对字典的 values进行升序排序，设排序后的数组为sort，如果sort中第一个元素的值等于count，说明元素组中不存在只出现一次的数字；否则，sort中的第一个元素即为第一个只出现一次的数字的index。

func findFirstNumberOnlyAppearsOnce(in nums: [Int]) -> Int? {
    var dict = [Int: Int]()
    let count = nums.count
        
    for (index, number) in nums.enumerated() {
         if !dict.keys.contains(number) {
             dict[number] = index
         } else {
             dict[number] = count
         }
     }
        
     if let result = dict.values.sorted().first {
         if result == count {
             return nil
         }
         return nums[result]
     }
     return nil
}

<求职路艰辛，持续更新中>

打赏