Algorithm

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

规则如下：

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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

Solution

Runtime：32 ms，快过 89.67%。

Memory：18.4 MB，低于 80.68%。

class Solution:

    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        row, column = len(matrix) - 1, 0
        while row >= 0 and column < len(matrix[-1]):
            num = matrix[row][column]
            if num == target:
                return True
            elif num > target:
                row -= 1
            else:
                column += 1
        return False

Review

https://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

Guido van Rossum 曾经在 2009 发过一篇文章说明“为什么 TRE 不适合用在 Python 这门语言上”。

主要论点：

TRE 不利于调试
TRE 并不是一个透明的优化，它会影响用户的编程方式 - 相同代码在支与不支持 TRE 的编译器下，可能得到不同的结果
1000 的递归深度已经够用了
Python 在意“用户（程序员）”的使用感受，相比递归、链表这些玩意儿，列表、序列更能显著提高用户的使用体验/感受

Python 的语言特性也不适合 TRE - 考虑如下代码：

def f(x):
    print('original')
    if x > 0:
        return f(x-1) # 指向的是下面的 f 函数
    return 0
  
g = f
  
def f(x):
    print('new')
    return x
  
print(g(5))
  
# original
# new
# 4

在 TRE 场景下，f 要跳到哪并不容易判断出来。

最后还放了一个大招：

After all TRE only addresses recursion that can easily be replaced by a loop. :-
— Guido van Rossum

Tip

关于 C++ 智能指针

auto/unique 使用所有权的概念，只有拥有对象的智能指针的析构函数会删除该对象，unique 的策略执行更严格；unique 相比 auto 更加安全，因为 auto 有拷贝语义，拷贝后原对象变得无效，再次访问原对象时会导致程序崩溃，unique 则禁止了拷贝语义，但提供了移动语义，可以使用 move 进行控制权限的转移
shared 共享所有权，能创建更智能的指针，跟踪特定对象的智能指针数，称为引用计数，赋值时计数+1，指针过期时计数减1，减为0时删除
weak 可以从一个 shared 或另一个 weak 构造而来，它不具备普通指针的行为，没有对操作符进行重载，只对 shared 进行观察，而不改变其引用计数，当被观察的 shared 指针失效后，相应的 weak 也失效；相比 oc，weak 更安全，weak 在需要访问资源时会生成一个 shared，能够保证在 shared 没有被释放之前，其所管理的资源不会被释放

Understanding Swift

关于 Swift 的一系列文章，以 FAQ 的方式来解释/回答问题，效率很高。

Algorithm

Solution

Review

Tip

关于 C++ 智能指针

Share