面试常见算法

---

最长不含重复字符的子字符串：

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例：

输入:"abcabcbb"'
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

来源：剑指Offer第48题
相关企业：

公司	出现时间
美团外卖	2020.03
字节跳动	2020.03

解法一：滑动窗口 + 双指针
时间复杂度：O(n**2)
空间复杂度：O(1)
思路：

• 设定两个指针low和high分别指向窗口的尾部和头部
• 分情况解决,其实本质是动态规划的思路:
  1.如果当前字符不在滑动窗口内的时候,比较之前的存储的最大结果与当前的滑动窗口的大小,取最大的
  2.如果当前字符在滑动串口内时,将low指针向前移直到当前字符不在滑动窗口内

代码：

def lengthOfLongestSubstring(self, s: str) -> int:
        result, low = 0, 0
        for high in range(len(s)):
            if s[high] not in s[low:high]:
                result = max(high-low + 1, result)
            else:
                while s[high] in s[low:high]:
                    low += 1
        return result

解法二：滑动窗口 + 哈希表
时间复杂度：O(n)
空间复杂度：O(n)
思路：
上面的代码我们可以看到,当字符在滑动窗口内的时候,我们还需要进行一次遍历,如果我们早在之前就记录下来了字符的位置,通过直接查找,是不是会节省很多时间呢?
我们想到了使用哈希表,因为它的存储和查找的时间复杂度都为O(1)
与上面相比较是利用空间换取了时间
代码：

def lengthOfLongestSubstring(self, s: str) -> int:
        dic, low, result = {}, 0, 0
        for i in range(len(s)):
            if s[i] in dic:
                low = max(dic[s[i]] + 1, low) 
            dic[s[i]] = i
            result = max(result, i - low + 1)
            
        return result

---

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点p、q，最近公共祖先表示为一个结点 x，满足x 是 p、q的祖先且 x的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树:
root = [3,5,1,6,2,0,8,null,null,7,4]

二叉树.png

示例：

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5和节点 1的最近公共祖先是节点3。

说明：

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉树中。

来源：剑指Offer第68-II题
相关企业：

公司	出现时间
美团外卖	2020.03
字节跳动	2020.03

解法：递归查找
时间复杂度：O(n)
空间复杂度：O(n)
思路：由于lowestCommonAncestor(root, p, q)的功能是找出以root为根节点的两个节点p和q的最近公共祖先。 我们考虑：

• 如果p和q分别是root的左右节点，那么root就是我们要找的最近公共祖先
• 如果root是None，说明我们在这条寻址线路没有找到，我们返回None表示没找到
• 我们继续在左右子树执行相同的逻辑。
• 如果左子树没找到，说明在右子树，我们返回lowestCommonAncestor(root.right, p , q)
• 如果右子树没找到，说明在左子树，我们返回lowestCommonAncestor(root.left, p , q)
• 如果左子树和右子树分别找到一个，我们返回root

代码：

def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root.val == p.val or root.val == q.val: return root
        l = self.lowestCommonAncestor(root.left,  p , q)
        r = self.lowestCommonAncestor(root.right,  p , q)
        
        return root if l and r else l or r

---

两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以0开头。
示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

来源：LeetCode 第2题
相关企业：

公司	出现时间
字节跳动	xxx

解法：遍历
时间复杂度：O(n)
空间复杂度：O(n)
思路：从头遍历两个链表，将每一位的值相加，大于等于10时，则下位进1，当一个链表遍历结束后，则将单独遍历另外一个链表即可；注意：当两个链表都遍历结束时，需检查进位标记是否存在，否则可能漏掉最后一位
代码：

 def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        temp =  0
        res = l = ListNode(0)
        while l1 or l2:
            value = temp
            if l1: 
                value += l1.val
                l1 = l1.next
            if l2:
                value += l2.val
                l2 = l2.next
            
            temp = value // 10
            l.next = ListNode(value % 10)
            l = l.next
            
        if temp:
            l.next = ListNode(temp)
            
        return res.next

---

字符串的排列

给定两个字符串s1和 s2，写一个函数来判断s2 是否包含 s1的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例：

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释:s2 包含 s1的排列之一 ("ba").

来源：LeetCode 第567题
相关企业：

公司	出现时间
字节跳动	xxx

解法：滑动窗口 + 哈希表
时间复杂度：O(n)
空间复杂度：O(n)
思路：维护窗口大小为len(s1)的两个指针left和right，在字符串s2上滑动，判断窗口内的hash表是否和s1的hash表一致。
代码：

 def checkInclusion(self, s1: str, s2: str) -> bool:
        char_dic = collections.Counter(s1)
        left, right = 0, len(s1) - 1
        while right < len(s2):
            if collections.Counter(s2[left : right + 1]) == char_dic:
                return True
            left += 1
            right += 1

        return False

---

盛水最多的容器

给你n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点(i, ai)。在坐标内画n条垂直线，垂直线i的两个端点分别为 (i, ai) 和(i, 0)。找出其中的两条线，使得它们与x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且n 的值至少为2。

蓄水池.png
图中垂直线代表输入数组[1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为49。
示例：

输入：[1,8,6,2,5,4,8,3,7]
输出：49

来源：LeetCode 第11题
相关企业：

公司	出现时间
百度	2020.04

解法：双指针
时间复杂度：O(n)
空间复杂度：O(1)
思路：
设置双指针i,j 分别位于容器壁两端，根据规则移动指针（后续说明），并且更新面积最大值result，直到 i == j 时返回 result。
指针移动规则与证明:

每次选定围成水槽两板高度h[i]、h[i]中的短板，向中间收窄1格。以下证明：

• 设每一状态下水槽面积为 S(i, j)(0 <= i < j < n)，由于水槽的实际高度由两板中的短板决定，则可得面积公式 S(i, j) = min(h[i], h[j]) × (j - i)。
• 在每一个状态下，无论长板或短板收窄 1 格，都会导致水槽 底边宽度 −1：
  1.若向内移动短板，水槽的短板 min(h[i], h[j])可能变大，因此水槽面积 S(i, j)可能增大。
  2.若向内移动长板，水槽的短板 min(h[i], h[j])不变或变小，下个水槽的面积一定小于当前水槽面积。
  因此，向内收窄短板可以获取面积最大值。

换个角度理解：

若不指定移动规则，所有移动出现的 S(i, j)的状态数为 C(n, 2)，即暴力枚举出所有状态。
在状态S(i, j)下向内移动短板至 S(i + 1, j)（假设h[i] < h[j]），则相当于消去了 S(i, j - 1), S(i, j - 2), ... , S(i, i + 1)状态集合。而所有消去状态的面积一定 <= S(i, j);
短板高度：相比 S(i, j) 相同或更短(<= h[i]);
底边宽度：相比 S(i, j) 更短。
因此所有消去的状态的面积都 < S(i, j)。通俗的讲，我们每次向内移动短板，所有的消去状态都不会导致丢失面积最大值 。

代码：

def maxArea(self, height: List[int]) -> int:
        
        i, j , result = 0, len(height) - 1, 0;
        while i < j:
            if height[i] < height[j]:
                result = max(result, height[i] * (j - i))
                i += 1
            else:
                result = max(result, height[j] * (j - i))
                j -= 1
        
        return result

---

打印菱形

给定一个奇数n，打印实心的菱形
示例：

输入: n = 3

输出: n = 3的菱形.png

输入：n = 5

输出： n = 5的菱形.png

来源：
相关企业：

公司	出现时间
快手	2020.04

解法：双循环
时间复杂度：O(n)
空间复杂度：O(1)
思路：将菱形拆分为上下两个三角形，分别进行打印：

• 上方三角形：因只需输出奇数个数的三角形，循环使用切片方式，只循环奇数对应的循环，每行对应的空格个数space_count为(n - i - 1) // 2；星号数量star_count为i + 1
• 下方三角形：只需输出n//2行即可，每行空格个数space_count为i + 1；星号数量star_count为n - 2 * (i + 1)
  代码：

 def printDiamond(self, n: int) -> void:
        for i in range(n)[0: n: 2]:
          space_count, star_count = (n - i - 1) // 2, i + 1
          print(' ' * space_count + '*' * star_count)

        for i in range(n // 2):
            space_count, star_count = i + 1, n - 2 * (i + 1)
            print(' ' * space_count + '*' * star_count)