人/狗/码的日常 2021-05-15

人

今天Ted选择的话题有些。。。怎么说呢，沉重，又或者很多人觉得这里我们很远。来聊聊临终关怀的话题。

虽然我才过40，可我在病重的时候，确实考虑过这个话题。来花时间欣赏BJ Miller的感人的演讲，我们如何看待死亡和尊重生命的重大问题。
What really matters at the end of life?

健身，来看看本周的成绩吧，还好还好，坚持了四天。为下周打气。

IMG_3740.PNG

狗

热死了，热死了。酷奇已经热的躺在地板上喘大气了。你能想象大热天的穿一身裘皮大衣么？酷奇就是这样的，很奇怪，今年是不是夏天来的太突然了，导致酷奇都没有换毛，往年天气一热，酷奇就会掉毛掉的厉害，因为要把外层的长毛都换掉。

我一回到电脑前写东西，他就乖乖的躺到我脚边陪我了。

码

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        
    }
};

解答：

最傻的是全遍历二维数组，这样效率是O(n^2)，完全没有利用数组在行列方向上都是排序的特性。

我刚拿到这个题目的时候，想到的是对每一行进行二分查找。这样效率是O(nlogn)

但其实这样效率还是不高的，没有利用到列方向上排序的特性。最后看了提示，才了解了最合适的解法：从二维数组的左下角开始查询，如果目标小于当前值，则查询位置向上移动，如果目标大于当前值，则查询位置向右移动。这种算法的效率是O(n)

C++版本解答

bool TwoDimensionalArraySearchClass::Find(int target, vector<vector<int> > array) {
    unsigned long row = array.size();
    if (row == 0) {
        return false;
    }
    
    unsigned long col = array[0].size();
    if (col == 0) {
        return false;
    }
    
    if ((target < array[0][0]) ||
        (target > array[row - 1][col - 1])) {
        return false;
    }
    
    long rowPos = 0;
    long colPos = col - 1;
    
    while ((rowPos <= (row - 1)) &&
           (colPos >= 0)) {
        if (target == array[rowPos][colPos]) {
            return true;
        } else if (target > array[rowPos][colPos]) {
            rowPos++;
        } else {
            colPos--;
        }
    }
    
    return false;    
}

OC版本解答

- (BOOL)findTarget:(NSInteger)target inTwoDimensionalArray:(NSArray *)array {
    NSInteger row = [array count];
    if (row == 0) {
        return NO;
    }
    
    NSInteger col = [array[0] count];
    if (col == 0) {
        return NO;
    }
    
    if ((target < [array[0][0] integerValue]) ||
        (target > [array[row - 1][col - 1] integerValue])) {
        return NO;
    }
    
    NSInteger rowPos = 0;
    NSInteger colPos = col - 1;
    
    while ((rowPos <= (row - 1)) &&
           (colPos >= 0)) {
        if (target == [array[rowPos][colPos] integerValue]) {
            return YES;
        } else if (target > [array[rowPos][colPos] integerValue]) {
            rowPos++;
        } else {
            colPos--;
        }
    }
    
    return NO;
}