CodingTour —

ARTS #84

Algorithm

本周选择的算法题是：Search a 2D Matrix

规则

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

Solution

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        low, high = 0, m * n
        
        while low < high:
            mid = low + (high - low) // 2
            value = matrix[mid//n][mid%n]
            if value == target:
                return True
            elif value < target:
                low = mid + 1
            else:
                high = mid
        return False

Review

How OAuth works

简洁明了的解释了 OAuth 的工作原理和诞生背景。

OAuth 是授权（Authorization）而不是验证（Authentication）。

OAuth 是提供一个服务去给另一个服务授权，解决的是服务之间信任的问题。

Tip

更新了 Jekyll 的路由地址：原 /:year/:month/:day/:title 改成了 /posts/:slug/。

使用了 jekyll-redirect-from 插件，并用以下脚本更新历史文章的别名：

alias = os.path.splitext(post)[0]
alias = os.path.basename(alias).replace("-", "/")
alias = alias.replace(" ", "-")
alias = alias.replace("#", "")
lines.insert(2, f"redirect_from: /{alias}/\n")

当访问到这些链接时会通过一个 HTTP-REFRESH meta 标签重定向到新的 slug 页面。

Share

建立可评估工作流。