Two Sigma：面试真题 - 编程（下）

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def getKthElement(k):
            """
            - 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
            - 这里的 "/" 表示整除
            - nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
            - nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
            - 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
            - 这样 pivot 本身最大也只能是第 k-1 小的元素
            - 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
            - 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
            - 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
            """
            
            index1, index2 = 0, 0
            while True:
                # 特殊情况
                if index1 == m:
                    return nums2[index2 + k - 1]
                if index2 == n:
                    return nums1[index1 + k - 1]
                if k == 1:
                    return min(nums1[index1], nums2[index2])

                # 正常情况
                newIndex1 = min(index1 + k // 2 - 1, m - 1)
                newIndex2 = min(index2 + k // 2 - 1, n - 1)
                pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
                if pivot1 <= pivot2:
                    k -= newIndex1 - index1 + 1
                    index1 = newIndex1 + 1
                else:
                    k -= newIndex2 - index2 + 1
                    index2 = newIndex2 + 1
        
        m, n = len(nums1), len(nums2)
        totalLength = m + n
        if totalLength % 2 == 1:
            return getKthElement((totalLength + 1) // 2)
        else:
            return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2

# 不转换为字符串
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 :
            return False
        elif  x == 0: #防止求log时，底数为0
            return True
        else:
            length = 1
            while 10**length<x:
                length += 1
            
            length -= 1 
            
            while x != 0:
                if x//(10 ** length) == x %10:
                    x = x % 10**length // 10
                    length -=2
                else:
                    return False
            return True

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        def _divide(a, b):
            if (a<b): return 0
            
            cnt = 1
            tb = b
            while (tb+tb)<a:
                cnt += cnt
                tb += tb
            
            return cnt + _divide(a-tb, b)
        
        INT_MIN, INT_MAX = -2**31, 2**31 - 1
        
        # if dividend == 0: return 0
        # if divisor == 1: return dividend
        # if divisor == -1:
        # if dividend>INT_MIN: 
        # return -dividend
        # return INT_MAX
        
        sign = 1
        if (dividend>0 and divisor<0) or (dividend<0 and divisor>0):
            sign = -1
        
        dividend, divisor = abs(dividend), abs(divisor)
        
        res = _divide(dividend, divisor)
        
        if sign>0:
            return min(INT_MAX, res)
        return max(INT_MIN, -res)

# 出现频率较高
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        
        ans = "0"
        m, n = len(num1), len(num2)
        for i in range(n - 1, -1, -1):
            add = 0
            y = int(num2[i])
            curr = ["0"] * (n - i - 1)
            for j in range(m - 1, -1, -1):
                product = int(num1[j]) * y + add
                curr.append(str(product % 10))
                add = product // 10
            if add > 0:
                curr.append(str(add))
            curr = "".join(curr[::-1])
            ans = self.addStrings(ans, curr)
        
        return ans
    
    def addStrings(self, num1: str, num2: str) -> str:
        i, j = len(num1) - 1, len(num2) - 1
        add = 0
        ans = list()
        while i >= 0 or j >= 0 or add != 0:
            x = int(num1[i]) if i >= 0 else 0
            y = int(num2[j]) if j >= 0 else 0
            result = x + y + add
            ans.append(str(result % 10))
            add = result // 10
            i -= 1
            j -= 1
        return "".join(ans[::-1])

# 出现频率很高的一道题
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 1:
            return intervals

        intervals.sort(key=lambda x: x[0])
        merged = [intervals[0]]
        left = merged[-1]
        for right in intervals[1:]:
            if right[0]<=left[1]:
                left[1] = max(right[1], left[1])
            else:
                merged.append(right)
                left = merged[-1]
        
        return merged

from typing import List

# 初始化确定的逻辑还不是很明白

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        
        dp = [[0]*5 for _ in range(len(prices))]
        
        dp[0][1] = -prices[0]
        dp[0][3] = -prices[0] 
        
        for i in range(1, len(prices)):
            dp[i][0] = dp[i-1][0]
            dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1])
            dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2])
            dp[i][3] = max(dp[i-1][2] - prices[i], dp[i-1][3])
            dp[i][4] = max(dp[i-1][3] + prices[i], dp[i-1][4])
        
        return dp[-1][4]

import collections
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        #存储有向图
        edges = collections.defaultdict(list) #{k: [v1, v2]} 以k为先导课程的课有[v1, v2]
        # 存储每个节点的入度
        in_degree = [0]*numCourses
        result = 0
        
        for info in prerequisites:
            edges[info[1]].append(info[0])
            in_degree[info[0]] += 1
        
        q = collections.deque([u for u in range(numCourses) if in_degree[u]==0])
        
        while q:
            u = q.popleft()
            result += 1
            for v in edges[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    q.append(v)
        
        return result == numCourses

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        neighbors = [(1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1)]

        rows = len(board)
        cols = len(board[0])

        # 遍历面板每一个格子里的细胞
        for row in range(rows):
            for col in range(cols):

                # 对于每一个细胞统计其八个相邻位置里的活细胞数量
                live_neighbors = 0
                for neighbor in neighbors:

                    # 相邻位置的坐标
                    r = (row + neighbor[0])
                    c = (col + neighbor[1])

                    # 查看相邻的细胞是否是活细胞
                    if (r < rows and r >= 0) and (c < cols and c >= 0) and abs(board[r][c]) == 1:
                        live_neighbors += 1

                # 规则 1 或规则 3 
                if board[row][col] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                    # -1 代表这个细胞过去是活的现在死了
                    board[row][col] = -1
                # 规则 4
                if board[row][col] == 0 and live_neighbors == 3:
                    # 2 代表这个细胞过去是死的现在活了
                    board[row][col] = 2

        # 遍历 board 得到一次更新后的状态
        for row in range(rows):
            for col in range(cols):
                if board[row][col] > 0:
                    board[row][col] = 1
                else:
                    board[row][col] = 0

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
    
        num1_len, num2_len = len(num1), len(num2)

        i, j = num1_len-1, num2_len-1
        last_sum = 0
        ans = []

        while i>=0 or j>=0 or last_sum>0:
            _num1 = int(num1[i]) if i>=0 else 0
            _num2 = int(num2[j]) if j>=0 else 0

            temp_sum = _num1 + _num2 + last_sum
            ans.append(str(temp_sum%10))
            last_sum = temp_sum//10
            i -= 1
            j -= 1

        return ''.join(ans[::-1])

from typing import List

class Solution:
    def compress(self, chars: List[str]) -> int:
        n = len(chars)
        if n<2: return 1
        
        chars.append(None)
        n += 1

        cnt = 1
        left = 0
        right = 1
        tot_used = 0
        
        while right<n:
            if chars[left] != chars[right]:
                if cnt == 1:
                    temp_char = chars[left]
                else:
                    temp_char = list(chars[left]) + list(str(cnt))
                chars[tot_used: tot_used+len(temp_char)] = temp_char
                tot_used += len(temp_char)
                cnt = 1 
            else:
                cnt += 1
            left += 1
            right += 1
        
        return tot_used

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        
        def dfs(i):
            for j in range(n):
                if isConnected[i][j] == 1 and j not in visited:
                    visited.add(j)
                    dfs(j)
        
        visited = set()
        n = len(isConnected)
        ans = 0

        for i in range(n):
            if i not in visited:
                dfs(i)
                ans += 1
        
        return ans

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        m = len(n)
        candidates = [10 ** (m - 1) - 1, 10 ** m + 1]
        selfPrefix = int(n[:(m + 1) // 2])
        for x in range(selfPrefix - 1, selfPrefix + 2):
            y = x if m % 2 == 0 else x // 10
            while y:
                x = x * 10 + y % 10
                y //= 10
            candidates.append(x)

        ans = -1
        selfNumber = int(n)
        for candidate in candidates:
            if candidate != selfNumber:
                if ans == -1 or \
                        abs(candidate - selfNumber) < abs(ans - selfNumber) or \
                        abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:
                    ans = candidate
        return str(ans)

class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:

        if root is None:
            return ""
        
        if root.left is None and root.right is None:
            return str(root.val)
        
        # if root.left is None:
        # return f"{root.val}()({self.tree2str(root.left)})"

        if root.right is None:
            return f"{root.val}({self.tree2str(root.left)})"

        return f"{root.val}({self.tree2str(root.left)})({self.tree2str(root.right)})"

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        # 特殊情况处理
        if k==1: 
            return True  # 特殊情况1
        target, resid = sum(nums)//k, sum(nums)%k
        if resid!=0: 
            return False # 特殊情况2
        
        nums=sorted(nums, reverse=True)
        if nums[-1]>target: 
            return False # 特殊情况3
        # 预处理
        while nums and nums[0]==target:
            nums.pop(0)
            k-=1 # 如果有等于target的数字 则先弹出
        
        if not nums: 
            return True # 特殊情况4

        # 递归判断 （回溯法）
        def dfs(groups, nums):
            
            if not nums: return True
            v=nums[0]
            for i in range(k):
                if groups[i]+v<=target:
                    # 向下递归
                    groups[i]+=v
                    if dfs(groups, nums[1:]): 
                        return True
                    # 回置状态
                    groups[i]-=v
                
                if groups[i]==0: break # 避免重复搜索
            return False
        
        return dfs([0]*k, nums)

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        
        def check_words(x, y):
            x_len, y_len = len(x), len(y)
            if x_len+1 != y_len:
                return False
            i,j = 0, 0
            while  i<x_len and j<y_len:
                if x[i] == y[j]:
                    i += 1
                j += 1
            return i == x_len

        words.sort(key=lambda x : len(x))
        n = len(words)
        dp = [1] * n
        res = 0
        for i in range(n):
            for j in range(i):
                if check_words(words[j], words[i]):
                    dp[i] = max(dp[i], dp[j]+1)
        
            res = max(res, dp[i])

        return res

class Solution:
    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
        min_dist = float('inf')
        min_point = None
        res = -1

        idx = 0
        for i,j in points:
            if i == x or j==y:
                dist = abs(i-x) + abs(j-y)
                # print(dist)
                if dist < min_dist:
                    min_dist = dist
                    min_point = [i, j]
                    res = idx
    
            idx += 1
        
        return res