前言

个人认为，这是一道非常经典的 LeetCode Hard 题目，第一次碰到时，感觉觉得如此之精妙，想破脑袋也不会想到使用什么样合适的数据结构去解决这道问题。时隔快5年，在2024年农历新年最后一个工作日，重温下这道经典的题目。

题目描述

中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

例如：

[2,3,4]，中位数是 3
[2,3]，中位数是 (2 + 3) / 2 = 2.5
给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

示例：

给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。

窗口位置 中位数
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6
因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。

提示：

你可以假设 k 始终有效，即：k 始终小于等于输入的非空数组的元素个数。
与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。

原题快速门

说句题外话，以现在卷的程度，是不是很多校招生必会解此题呢，想当年，这样的题目，是不太可能出现在现场笔试题目中的。^.^

解题思路

首先，拿到一道题目后，要分析输入规模，那其实老的题目这点是不太规范的，往往没有给你输入规模的描述，也就少了一些提示。我理解这道题目的输入规模应该如下：
n = len(nums)
1 <= k <= n <= 10^5
那么如果是这样的数据规模，所有O(n^2)的算法可以直接劝退，不用费脑子和精力去想了。接下来，要仔细想下题目的考点是哪一个，或者哪几个组合。显然这道题目非常贴心的告诉你一个考点，滑动窗口，什么是滑动窗口，题目的示例解释的非常清楚了，k表示滑动窗口的长度，窗口往右滑动时，前面的数出窗口，后面的数进入窗口，就是这么个过程。其次，要求窗口内数据的中位数，如果每次暴力的重新计算，那么需要排序，取中间值，显然这个方案的复杂度，最坏情况下会变成O(n^2logn)，应该是过不了testcase，那么这里就要引入数据结构，以O(1)时间计算中位数，如果滑动窗口内的数字保存在一个有序数组，那么计算中位数的复杂度为O(1)就很轻松了，但是删除和添加一个元素到有序数组，操作是O(N)的，那什么数据结构删除和添加一个元素是O(logn)以下的复杂度呢？啊，想到了，类似堆或者红黑树的数据结构。
那怎样使用有序的这些数据结构，实现滑动窗口中位数呢？最巧妙的设计在于，使用两个堆或者有序树的实例，一个维护前半段，一个维护后半段，那么中位数和前半段的最大值和后半段的最小值相关。如果是堆的话，前面半段使用最大堆，后面半段使用最小堆。如下图所示：

这里还有一个细节点，如果k是偶数，那么前半段和后半段的数字数量相等，否则前半段多维护一个数，所以前半段维护数字的数量是 k+1 除以 2 下取整，后半段维护数字的数量是 k 除以 2 下取整。所以当 k 为奇数时，前半段堆最大值就是中位数，否则，需要将两个堆顶的数字取平均。

代码实现

通过上面的分析，思路有了，我实际实现时，使用了Python3，以及SortedList这个有序List（底层实现采用了二分查找和分块算法。在插入元素时，它会将列表分块，并在每个块内部使用二分查找来维护有序性。这样可以在保证列表有序的同时，提高插入和查找元素的效率），效果和堆是类似的，就是优化插入和删除元素的时间复杂度。代码如下：

from sortedcontainers import SortedList

class Solution:
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
    n = len(nums)
    l = (k+1) // 2
    r = k // 2

    L = SortedList(nums[:k])
    R = SortedList()

    def L2R():
        x = L.pop()
        R.add(x)

    def R2L():
        x = R.pop(0)
        L.add(x)

    while len(L) > l:
        L2R()

    ans = []
    if l > r:
        ans.append(L[-1])
    else:
        ans.append((L[-1] + R[0]) / 2)

    for i in range(k, n):
        out_val = nums[i-k]
        if out_val in L:
            L.remove(out_val)
        else:
            R.remove(out_val)
        
        in_val = nums[i]
        if not L or in_val < L[-1]:
            L.add(in_val)
        else:
            R.add(in_val)
        
        if len(L) == l-1:
            R2L()
        elif len(L) == l+1:
            L2R()

        if l > r:
            ans.append(L[-1])
        else:
            ans.append((L[-1] + R[0]) / 2)
    
    return ans

结论

上述实现的代码，时间复杂度O(nlogk)，空间复杂度O(k)。所谓温故知新，最近也有些堆顶堆的题目出现在周赛上面，只是比起以前的题目，现在的题目不会直接把题目考点赤裸裸写在标题里面，需要你自己抽象转换，这步其实非常难，需要你特别熟悉这些题目考点，才能在关键时刻想到如何转换。

引言

强化学习是蛋糕顶上缀着的一颗樱桃，这不是我说的，而是深度学习领域Yann LeCun教授在CoRL 2017大会上做的演讲时提及的。他著名的“蛋糕”理论。“真正的”强化学习好比蛋糕上的樱桃，监督学习好比蛋糕上的糖衣，而蛋糕本身是非监督学习（预测学习）。这里LeCun也表示，这一比喻对做强化学习的兄弟可能不太友好。

认识下“樱桃”

什么是强化学习呢？举个通俗的例子，强化学习就好比一个女猎手（为啥是女猎手，因为我下面用了阿塔兰忒的图像，哈哈）进入了一个迷雾森林，里面充满了各种挑战和奖励。她得自己摸索，判断哪个方向更有“糖果”，哪个方向有“陷阱”。在这个过程中，她会慢慢学会，哦，原来这样做能得到糖果，那样做会掉进陷阱。

不过，这个魔法森林可不是那么容易走的。有时候，她会走错路，掉进陷阱，或者绕着同一个地方转圈圈。这时候，就需要神出手啦，给她点提示，让她知道哪个方向可能更有糖果。这就是我们常说的“智能体（agent）”和“环境（evironment）”之间的互动。

通过这样的摸索和学习，阿塔兰忒最终会走出迷雾森林，这就是强化学习的魅力所在啦！

小姐姐好看吧，也是我用AIGC生成的，嘿嘿。

其实上面简单通俗的语言，就已经把强化学习的原理展露出来了，强化学习（Reinforcement Learning，RL）是一种通过试错来学习的方法。在深度学习中，强化学习用于训练智能体（agent）在环境（evironment）中采取行动，以最大化累积奖励。与监督学习不同，强化学习没有明确的输入输出对，智能体需要通过与环境的交互来学习最佳策略。

深度学习中的强化学习原理涉及到状态（state）、动作（action）、奖励（reward）等核心概念。状态是指环境的当前状态，动作是智能体可以执行的操作，奖励是智能体采取某个动作后获得的正面或负面反馈。智能体在环境中不断尝试不同的动作，根据奖励信号来调整策略，以期获得最大的累积奖励。

深度强化学习在许多应用领域取得了显著的成果，例如自动驾驶、游戏AI、机器人控制等。在实际应用中，智能体需要与环境进行大量的交互来学习最佳策略，这通常需要大量的计算资源和时间。

实践环节

当然只知道上面的原理是不够的，实践出真知，这块怎么去实验呢？我想起了2017年，Deepmind公司发表在nature科学杂志上的AlphaGoZero论文，当时也是通过在围棋比赛上战胜人类冠军而出圈，零人类经验，其自我训练的时间仅为3天，自我对弈的棋局数量为490万盘。但它以100:0的战绩击败前辈。围棋显然我没法找到足够算力支持，但是找个简单的游戏，还是可行的，那么我想到了一个简单好玩的小游戏《flappy bird》，我首先做了一个通过玩家控制的版本：

是不是很熟悉，画面不够精致，但是也够用了，小白球作为小鸟，需要往前飞，又不能碰到白色障碍物。我自己来控制，还是比较难掌控的，很快就会死了。

那么怎么实现AI控制小鸟，就是我要完成的事情。首先上面说的环境（evironment）在这个游戏中就是这个游戏本身，智能体（agent）就是这个小鸟的大脑，控制小鸟的行动。关于环境（evironment），如何抽象状态（state）是关键，我想到有好几种方法：

1. 整个游戏画面作为state，画面的每个像素点就是state，智能体（agent）需要自己理解这个画面意味着什么，障碍物的距离，小鸟的位置等等；
2. 计算某一帧时环境变量，最近的障碍物顶部占据画面高度的比例，小鸟离最近障碍物的距离占画面宽度的比例，小鸟的垂直方向的位置，小鸟的速度等等；

显然不管环境（evironment）如何抽象，智能体（agent）都应该可以学会如何应对某一个具体的state，我在这篇文章中，先尝试了2这个方法，定义了5个变量：

environment[0] = closest.x / (WIN_WIDTH - bird.x) # 最近的障碍物的横坐标 = closest.x，小鸟的横坐标 = bird.x，屏幕的宽度 = WIN_WIDTH
environment[1] = closest.top / WIN_HEIGHT # 最近的障碍物上半部分下沿 = closest.top，屏幕的高度 = WIN_HEIGHT
environment[2] = closest.bottom / WIN_HEIGHT # 最近的障碍物下半部分上沿 = closest.bottom，屏幕的高度 = WIN_HEIGHT
environment[3] = bird.y / WIN_HEIGHT # 小鸟的纵坐标 = bird.y，屏幕的高度 = WIN_HEIGHT
environment[4] = bird.velocity / 10 # 小鸟的往前的速度 = bird.velocity

智能体（agent）简单定义为一个深度神经网络（4层的全连接网络），输入就是上面的evironment数组变量，输出为action，在这个游戏中就是两种行为：1、向上飞；2、保持不动，所以神经网络最终输出为2。

brain = Sequential(
    Linear(5, 16, name='linear1'),
    ReLU(name='relu1'),
    Linear(16, 64, name='linear2'),
    ReLU(name='relu2'),
    Linear(64, 16, name='linear2'),
    ReLU(name='relu3'),
    Linear(16, 2, name='linear2'),
)

那么就来到了最难设计的部分，奖励（reward）如何设计，这里又必须展开一些强化学习训练细节来讲下。强化学习的训练数据，是通过智能体（agent）和环境（evironment）不停的交互，产生的一系列动作（action）概率和一系列奖励（reward）来进行训练的。所以奖励（reward）的设计尤为关键，简单讲就是在迷雾森林中，你要准确的告诉阿塔兰忒往左是陷阱，会被扣分，往右是糖果，是个奖励，会加分。所以在每个具体游戏中，都需要去明确的制定合理的奖励（reward）规则，最后智能体（agent）才会做出利益最大化的动作（action），那么我这里是这样定义的：

for pipe in self.pipes:
    if pipe.hits(bird):
        reward = -450 # 撞到障碍物 pipe，扣450分
        done = True
        break
    elif pipe.avoid(bird):
        reward = 60 # 躲避障碍物 pipe，得60分

if bird.hitBottom():
    reward = -450 # 小鸟撞到底部，扣450分
elif bird.hitTop():
    reward = -450 # 小鸟撞到底部，扣450分

别小看这几句代码，简单但是扣分和得分是会影响智能体（agent）学习的速度的。我这里是调试了不少时间，才完成了整个训练，如果有朋友有兴趣，我可以详细来讲下这部分的训练实现和调试过程，这篇文章里我不进行展开。

结论

展示下最终的效果：

感觉效果还是十分nice的，视频转gif没处理好，感觉gif图的质量一般，我自己看AI玩的效果是真的6，我想下次可以再继续使用图片作为环境（environment），改一下模型结构（可能需要换成resnet等cnn作为backbone），硬train一发，也能得到类似的效果，这个就留作后续的任务，挖个小坑。

导语

好久没更新，从去年十月份来，工作突然很忙，平时剩下的时间用来学习、健身，给到总结写作，没剩下时间。加上人每隔一段时间，都会产生懈怠，就停更个人技术博客近半年。想想去年因为疫情在家办公期间，某种程度上来看，还是很幸福的，上班不用来回坐车，节省下来的时间，可以花在自己感兴趣的事情上，产生一些输出。

OK，言归正传，今天闲来无事，我翻出了女儿去年玩过的小游戏，她妈妈给她买的这类智力小游戏有不少，很偶尔会瞧见她们娘俩一起玩，估计是不太感兴趣。今天这款游戏，我小时候没见过，是一个新的小游戏，我就起一个应景的名字，《兔兔大战小狐狸》，今年是兔年，兔子要逃脱小狐狸的围追堵截，逃到安全的小土坑里，躲起来。

游戏介绍

游戏棋盘是一个5*5的方盘，左上、右上、左下、右下以及正中间有5个小土坑，如果棋盘上所有的兔子，都在土坑待着，就完成了任务。具体规则，我不码字，看如下说明：

如上面所说，游戏内置了60个关卡（因为随便摆放，是不一定能完成任务的），也有最少步骤的解答，我自己尝试玩了几个简单关卡（最少10步以内可以完成的），貌似还挺简单的。

然后，我翻到了关卡的最后4个关卡，哇，一下子震惊了，好难，最后一关官方解答，需要87步完成任务。

一些疑问

小朋友如果自己完成前面简单、中等题目，已经很不容易了。至于困难、专家级别的题目，如果能完成，小脑瓜不是一般聪明，非常了不起。但我想了下，官方说最后一题87步是最少步骤，这个怎么证明官方没错呢？或者有更少步骤的解法？我心想，是不是写个算法求解，看看是否是对的。

求解过程

首先是需要有个建模过程，棋盘规格是5*5方盘，上面有25个位置，5个位置是土坑。可以放置的角色是小狐狸、兔兔和蘑菇。兔兔和蘑菇都只占用一个格子，狐狸占用两个格子，还有头和尾巴，但我仔细想了下，狐狸头和尾巴，其实在算法中不需要区分，只需要区分狐狸是竖着还是横着放置的，你可以理解为狐狸的头总是在左边或者上方，尾巴在右边或者下方。这样对算法实现更简单。

比如60题，我会使用5个字符串表示5行，

"...X."
"FF.R."
"..X.R"
"X...."
"...R."

字符X表示蘑菇，F表示小狐狸（头或者尾），R表示小兔兔，最后.表示空位。

算法显然就是搜索算法，DFS还是BFS呢？我先用DFS实现了半天，会TLE，根本算不出最少步骤的解法。我后来想了下，最少步骤的解法确实不太适合DFS，因为DFS可能需要搜索完所有的解法空间（也可能我剪枝还不够），所以无法算出最少步骤。在DFS上，我其实花了不少时间优化，这个题目比刷题难，因为是自己出给自己的，也没有什么参考答案，都只能自己去想，如何建模和实现搜索算法，总之，自己试了半天，也不work。

OK，那么我就来试下BFS搜索，大概的逻辑步骤如下：

1. 建立一个队列，将游戏初始棋盘局面放到队列中；
2. 一一取出当前局面，评估可能变为的下一个局面；
3. 评估当前局面可能可以行动的小兔兔、小狐狸坐标；
4. 一一取出小兔兔、小狐狸，评估她们可能的移动到的位置；
5. 通过改变小兔兔、小狐狸位置，得到下一个局面；
6. 将2～5变化的到的局面插入队列（下一轮）；
7. 遍历完上一轮队列，步骤+1；
8. 把下一轮队列变为需要遍历的当前队列，重复2～7步骤；

代码实现：

int smartGame(vector<string> board) {
    int n = board.size();

    // 判断游戏是否结束
    set<vector<int>> finish_pos = {{0, 0}, {0, n-1}, {n-1, 0}, {n-1, n-1}, {n/2, n/2}};
    function<bool(vector<vector<int>>)> isFinished = [&](vector<vector<int>> ani_pos) -> bool {
        int n = ani_pos.size();

        for (int i = 0; i < n; ++i) {
            if (ani_pos[i][2] != -1) continue;
            vector<int> pos = {ani_pos[i][0], ani_pos[i][1]};
            if (finish_pos.find(pos) == finish_pos.end())
                return false;
        }

        return true;
    };

    // 分析棋盘局面，哪些可能移动的小兔兔、小狐狸所在位置
    function<void(vector<string>, vector<vector<int>>&)> analyzeBoard = [&](vector<string> board, vector<vector<int>>& ani_pos) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'X') {
                    continue;
                } else if (board[i][j] == '.') {
                    continue;
                } else if (board[i][j] == 'F') {
                    if ((i == 0 || board[i - 1][j] != 'F') && (i < n - 1 && board[i + 1][j] == 'F')) {
                        // vertical fox
                        ani_pos.push_back({i, j, 1});
                    } else if ((j == 0 || board[i][j - 1] != 'F') && (j < n - 1 && board[i][j + 1] == 'F')) {
                        // horizontal fox
                        ani_pos.push_back({i, j, 2});
                    }
                } else if (board[i][j] == 'R') {
                    ani_pos.push_back({i, j, -1});
                }
            }
        }
    };

    // 棋盘局面上某个小兔兔、小狐狸，做出某个移动后，返回新的局面
    function<vector<string>(vector<string>, vector<int>, vector<int>)> applyBoard = [&] (vector<string> board, vector<int> pos, vector<int> move) -> vector<string> {
        if (pos[2] == -1) {
            board[pos[0]][pos[1]] = '.';
            board[pos[0]+move[0]][pos[1]+move[1]] = 'R';
        } else {
            if (pos[2] == 1) {
                board[pos[0]][pos[1]] = '.';
                board[pos[0]+1][pos[1]] = '.';

                board[pos[0]+move[0]][pos[1]+move[1]] = 'F';
                board[pos[0]+move[0]+1][pos[1]+move[1]] = 'F';
            } else if (pos[2] == 2) {
                board[pos[0]][pos[1]] = '.';
                board[pos[0]][pos[1]+1] = '.';

                board[pos[0]+move[0]][pos[1]+move[1]] = 'F';
                board[pos[0]+move[0]][pos[1]+move[1]+1] = 'F';
            }
        }

        return board;
    };

    // 分析棋盘局面，可能移动的小兔兔、小狐狸，能做出哪些移动
    function<vector<vector<int>>(vector<string>, vector<int>)> nextMoves = [&] (vector<string> board, vector<int> pos) -> vector<vector<int>> {
        vector<vector<int>> moves;

        if (pos[2] == -1) {
            // up
            vector<int> t = pos;
            while (t[0] >= 0 && board[t[0]][t[1]] != '.') t[0] -= 1;
            if (t[0] >= 0 && board[t[0]][t[1]] == '.' && t[0] < pos[0]-1) {
                moves.push_back({t[0]-pos[0], 0});
            }
            // down
            t = pos;
            while (t[0] < n && board[t[0]][t[1]] != '.') t[0] += 1;
            if (t[0] < n && board[t[0]][t[1]] == '.' && t[0] > pos[0]+1) {
                moves.push_back({t[0]-pos[0],0});
            }
            // left
            t = pos;
            while (t[1] >= 0 && board[t[0]][t[1]] != '.') t[1] -= 1;
            if (t[1] >= 0 && board[t[0]][t[1]] == '.' && t[1] < pos[1]-1) {
                moves.push_back({0, t[1]-pos[1]});
            }
            // right
            t = pos;
            while (t[1] < n && board[t[0]][t[1]] != '.') t[1] += 1;
            if (t[1] < n && board[t[0]][t[1]] == '.' && t[1] > pos[1]+1) {
                moves.push_back({0, t[1]-pos[1]});
            }
        } else if (pos.size() == 3) {
            if (pos[2] == 1) {
                // up
                if (pos[0] > 0 && board[pos[0]-1][pos[1]] == '.') {
                    moves.push_back({-1, 0});
                }
                // down
                if (pos[0] < n-2 && board[pos[0]+2][pos[1]] == '.') {
                    moves.push_back({1, 0});
                }
            } else if (pos[2] == 2) {
                // left
                if (pos[1] > 0 && board[pos[0]][pos[1]-1] == '.') {
                    moves.push_back({0, -1});
                }
                // right
                if (pos[1] < n-2 && board[pos[0]][pos[1]+2] == '.') {
                    moves.push_back({0, 1});
                }
            }
        }

        return moves;
    };

    // 棋盘局面的签名，用作去重
    function<string(vector<string>)> signature = [&](vector<string> board) -> string {
        string r;
        for (auto l : board) {
            r += l;
        }
        return r;
    };

    // 1. 初始棋盘局面，入到队列
    queue<vector<string>> q;
    unordered_set<string> seen;
    q.push(board);
    seen.insert(signature(board));

    int ans = 0;

    while (!q.empty()) {
        int size = q.size();
        while (size --) {
            // 2. 一一取出当前局面，评估可能变为的下一个局面；
            vector<string> t = q.front();
            q.pop();
            vector<vector<int>> ani_pos;

            // 3. 评估当前局面可能可以行动的小兔兔、小狐狸坐标；
            analyzeBoard(t, ani_pos);

            if (isFinished(ani_pos)) {
                return ans;
            }

            // 4. 一一取出小兔兔、小狐狸，评估她们可能的移动到的位置；
            for (auto pos: ani_pos) {
                vector<vector<int>> moves = nextMoves(t, pos);
                for (int i = 0; i < moves.size(); ++i) {
                    vector<int> move = moves[i];
                    // 5. 通过改变小兔兔、小狐狸位置，得到下一个局面；
                    vector<string> nxtBoard = applyBoard(t, pos, move);
                    string sig = signature(nxtBoard);
                    if (seen.find(sig) == seen.end()) {
                        // 6. 将2～5变化的到的局面插入队列（下一轮）；
                        q.push(nxtBoard);
                        seen.insert(sig);
                    }
                }
            }
        }

        // 7. 遍历完上一轮队列，步骤+1；
        // 8. 把下一轮队列变为需要遍历的当前队列，重复2～7步骤；
        ans++;
    }

    return -1;
}

还要强调一点优化，我用了一个unordered_set去做棋盘局面去重，曾经看见过的局面，就不需要再去考虑了，因为即使从该局面出发有解，肯定也不会比之前出现时更优的，这个很好理解吧。

结论

最终通过算法验证，最后4题的最优解确实和官方的步骤数量一样，并且我后来记录了最优解算法的到的步骤，虽然有些顺序和官方题解不一致，我仔细比对了下，仅仅是某些步骤中，可以交换顺序而已，不是计算错误。别看是思路很简单，就是BFS搜索算法，但是面对一个没有参考答案的问题，建模、优化和调试，哪一样都不轻松，很开心，今天可以完成任务，并且写下这篇文章，明天继续加油～

导语

最近在学python数据处理的几个常用库，分别是numpy、matplotlib和pandas。这几个库应该是python数据处理的第三方神器库，学了一招图像手绘风格处理，非常有意思，记录下来。

图像手绘风格

手绘风格示例：

第二幅就是有手绘的感觉，当然是基于第一章图片处理得到的。手绘风格可以总结为以下几点：

• 黑白灰色
• 边界线条较重
• 相邻的像素，如果是相同或者相近色彩趋于白色
• 略有光源效果

具体如何通过程序实现呢？接下来就来逐一介绍下。

梯度的重构

利用像素之间的梯度值和虚拟深度值对图像进行重构，根据灰度变换来模拟人类视觉的明暗程度。代码如下：

import numpy as np
from PIL import Image

a = np.asarray(Image.open('xxx.jpeg').convert('L')).astype('float')

depth = 10.
grad = np.gradient(a)
grad_x, grad_y = grad
grad_x = grad_x*depth/100.
grad_y = grad_y*depth/100.

下面这行代码是通过pillow库读取原先图像，RGB值转为灰度值。

a = np.asarray(Image.open('xxx.jpeg').convert('L')).astype('float')

这几行代码是计算灰度图像的像素间梯度，并且根据虚拟深度重构梯度值，depth初始化为10，depth取值0～100。

depth = 10.
grad = np.gradient(a)
grad_x, grad_y = grad
grad_x = grad_x*depth/100.
grad_y = grad_y*depth/100.

光源效果

根据灰度变化来模拟人类视觉的远近程度。

• 设计一个位于图像斜上方的虚拟光源
• 光源相对于图像的俯视角为Elevation，方位角为Azimuth
• 建立光源对各个点梯度值的影响函数
• 运算各个点的新像素值

代码如下：

vec_el = np.pi/2.2                  # 光源的俯视角度，弧度值
vec_az = np.pi/4.                   # 光源的方位角度，弧度值
dx = np.cos(vec_el)*np.cos(vec_az)  # 光源对x轴的影响
dy = np.cos(vec_el)*np.sin(vec_az)  # 光源对y轴的影响
dz = np.sin(vec_el)                 # 光源对z轴的影响

A = np.sqrt(grad_x**2 + grad_y**2 + 1.)     # 光源归一化
uni_x = grad_x/A
uni_y = grad_y/A
uni_z = 1./A
b = 255*(dx*uni_x+dy*uni_y+dz*uni_z)

最后，对像素值进行裁剪至0～255，防止越界。

b = b.clip(0, 255)
im = Image.fromarray(b.astype('uint8'))
im.save('xxxHD.jpeg')

最后

程序虽然小，效果还是比较有意思的，我给女儿看了，她说你画画不是很丑的吗，为啥画的这么好？哈哈，我和她说，这是计算机处理的，不是我手画的，小小的年纪充满大大的问号。

其实，这里最重要的是对图像灰度值计算梯度，这是Computer Vision里面传统图像处理的关键，CV相关的技术，由于可以可视化，实现之后，还是比较有意思的。

导语

上周记录了极客挑战赛的情况，其中一道非常有趣的题，本周继续，本周题目也是游戏，大概的游戏形式是横版闯关类的：

还是借用网上游戏的图片说明下大概的意思，玩家一个英雄，进入一个场景（横版的），会有一个（每个场景仅一个）怪物与玩家英雄对抗，玩家有血条，有蓝量，6个技能（其中1个技能是升级其他5个技能），然后需要做的就是打到场景中的怪物，冲往下一个关卡。

摸索

有了之前游戏的经验之后，我知道了，上来就是一顿摸索，其实和上周说的游戏类似，客户端是个状态机，英雄有血量和蓝量，每次和怪物对抗之后，客户端会上传一堆指令到服务端，服务端重放这一堆指令，看最终的英雄状态和怪物状态是否合法，是不是英雄还活着，怪物已经死亡，然后就可以进行到下一关。

一共是有9个怪物，一旦进入游戏，可以得到所有怪物的属性：

bosses = [
    {
        "Name": "小壶守卫",
        "Model": "Boss_ball",
        "Hp": 396,
        "Skill1_harm": 63,
        "Skill2_harm": 71,
        "Award_hp": 133,
        "Award_mp": 1695,
        "New_star": 0
    },
    {
        "Name": "苇名二心",
        "Model": "Boss_sword",
        "Hp": 532,
        "Skill1_harm": 59,
        "Skill2_harm": 89,
        "Award_hp": 157,
        "Award_mp": 1678,
        "New_star": 0
    },
    {
        "Name": "古达",
        "Model": "Boss_guda",
        "Hp": 643,
        "Skill1_harm": 57,
        "Skill2_harm": 97,
        "Award_hp": 142,
        "Award_mp": 1362,
        "New_star": 1
    },
    {
        "Name": "中壶守卫",
        "Model": "Boss_ball",
        "Hp": 668,
        "Skill1_harm": 59,
        "Skill2_harm": 67,
        "Award_hp": 178,
        "Award_mp": 1458,
        "New_star": 0
    },
    {
        "Name": "苇名三心",
        "Model": "Boss_sword",
        "Hp": 687,
        "Skill1_harm": 31,
        "Skill2_harm": 101,
        "Award_hp": 212,
        "Award_mp": 2659,
        "New_star": 0
    },
    {
        "Name": "黑古达",
        "Model": "Boss_guda",
        "Hp": 852,
        "Skill1_harm": 77,
        "Skill2_harm": 91,
        "Award_hp": 132,
        "Award_mp": 4157,
        "New_star": 2
    },
    {
        "Name": "大壶守卫",
        "Model": "Boss_ball",
        "Hp": 1502,
        "Skill1_harm": 71,
        "Skill2_harm": 105,
        "Award_hp": 154,
        "Award_mp": 3089,
        "New_star": 0
    },
    {
        "Name": "苇名零心",
        "Model": "Boss_sword",
        "Hp": 1611,
        "Skill1_harm": 97,
        "Skill2_harm": 127,
        "Award_hp": 189,
        "Award_mp": 6493,
        "New_star": 0
    },
    {
        "Name": "超黑古达",
        "Model": "Boss_guda",
        "Hp": 2988,
        "Skill1_harm": 101,
        "Skill2_harm": 153,
        "Award_hp": 0,
        "Award_mp": 0,
        "New_star": 3
    }
]

简单讲一下“Award_hp”和“Award_mp”这两个值，就是你击败怪物后，得到的奖励，可以分别增加对应的hp和mp，其他字段就是对应意思了。

hero = {
    "Hp": 520,
    "Mp": 1806,
    "Power": {
        "Cost_mp": 233,
        "Attack_increase": [
            {
                "skill_i": 1,
                "skill_j": 1,
                "skill_k": 1,
                "skill_l": 1,
                "skill_u": 1
            },
            {
                "skill_i": 6,
                "skill_j": 1,
                "skill_k": 2,
                "skill_l": 3,
                "skill_u": 5
            },
            {
                "skill_i": 6,
                "skill_j": 2,
                "skill_k": 2,
                "skill_l": 3,
                "skill_u": 4
            },
            {
                "skill_i": 6,
                "skill_j": 1,
                "skill_k": 2,
                "skill_l": 3,
                "skill_u": 4
            },
            {
                "skill_i": 6,
                "skill_j": 2,
                "skill_k": 2,
                "skill_l": 3,
                "skill_u": 4
            },
            {
                "skill_i": 6,
                "skill_j": 2,
                "skill_k": 3,
                "skill_l": 3,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 1,
                "skill_k": 2,
                "skill_l": 4,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 2,
                "skill_k": 3,
                "skill_l": 3,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 2,
                "skill_k": 2,
                "skill_l": 4,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 2,
                "skill_k": 3,
                "skill_l": 3,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 2,
                "skill_k": 3,
                "skill_l": 4,
                "skill_u": 5
            }
        ]
    },
    "Skills": {
        "skill_i": {
            "Cost_mp": 489,
            "Attack_hp": 187
        },
        "skill_j": {
            "Cost_mp": 134,
            "Attack_hp": 50
        },
        "skill_k": {
            "Cost_mp": 186,
            "Attack_hp": 70
        },
        "skill_l": {
            "Cost_mp": 251,
            "Attack_hp": 95
        },
        "skill_u": {
            "Cost_mp": 352,
            "Attack_hp": 134
        }
    }
}

经过几次手打的尝试之后，客户端上传的指令，类似["skill", "skill_j"]，["attack", "Hero", "Boss", "skill_j"]这两条连续指令，表示英雄发动了技能skill_j，并且命中了怪物，反过来，怪物击中英雄也有类似连续指令，不展示了。手打很容易通过前三关，后面几关越来越难，手残党直接放弃。

思考一番之后，其实客户端只需要传送英雄攻击怪物的动作序列即可，不需要构造英雄“挨打”的序列，嘻嘻～所以问题转换为英雄的蓝量够不够击败怪物。如果不存在技能升级，那么就是一个背包问题，算是一个无限背包问题（实际上整体问题属于一个有限背包问题，因为技能其实是有施放次数上限，这里计算背包问题时，先不考虑）。

确定了是无限背包问题，也有两条建模路径：

• 确定的蓝量能够产生最大的耗血量；
• 确定的血量用最少多少蓝量可以完成；

OK，二选一，上来我选择了第一条，很快能写出背包问题代码：

# W指的是最大的蓝量，w是技能耗的蓝量树组，v是技能产生的伤害
# 最后dp返回的数组，每一个元素有两位[x, y]，x表示产生的最大伤害，y表示达到这个最大伤害使用的技能序号
def knapsack01D(w, v, W):
    n = len(w)
    dp = []
    for i in range(W+1):
        dp.append([0,-1])

    for i in range(n):
        knapsackComplete(dp, w[i], v[i], i)

def knapsackComplete(dp, w, v, i):
    W = len(dp)
    j = w
    while j < W:
        if dp[j-w][0]+v > dp[j][0]:
            dp[j][2] = i
        dp[j][0] = max(dp[j-w][0]+v, dp[j][0])
        j += 1

虽然背包代码写得很轻松，但是后面就陷入了一个死胡同，我拿着这个函数，疯狂尝试，怎么试呢？前面1～3关我不升级技能，看能不能通过，发现不行，那升一级，发现可以通关，升两级不行，那我就升一级，然后到了4～6关，我再用此策略，结果发现弄来弄去，只能通过4～6关，获得第二颗星星的奖励，死活打不过7～9关怪物。

问题建模

当我要放弃的时候，我看了一眼答案提示，答案没有代码实现哈，但其中有一句话点醒了我：

设状态 dpAi 表示强化i次的情况下，伤害j血量的最小蓝耗，dpBi 表示强化i次的情况下，完成j这个boss之后剩余的最大蓝耗，然后两个dp依次计算，就可以得到最终策略了。

这句话得多读几遍，也就是说，我们可以把所有升级后的对应血量蓝耗情况都计算出来，然后还得多算一个矩阵，表示强化了i次情况下，击败第j个怪物之后，剩余的最大蓝耗，首先上面我算的蓝耗和血量的背包问题，反过来建模，通过确定血量耗最少蓝的结果，去计算击败某个怪物之后剩余蓝量。

想清楚整体模型之后，动手写了代码，确定血量消耗最小蓝耗问题，也不是特别难，基于这个结果，去构建完成j这个boss之后剩余的最大蓝耗，稍微多想下，也可以写出来，代码大致如下：

# 根据hero和boss的数组初始化背包问题相对应的值
# dp最后保存的是血量j对应消耗最小蓝耗
# dp2表示哪个技能实施后达到的最小蓝耗（就是去往下一个最佳状态，需要施放的技能）
v = [489, 134, 186, 251, 352]
w = [187, 50, 70, 95, 134]
ws = [[]] * 11
W = 2988
dp = []
dp2 = []
skills = ["skill_i", "skill_j", "skill_k", "skill_l", "skill_u"]
for i in range(11):
    for j in range(len(skills)):
        w[j] = w[j] + hero['Power']['Attack_increase'][i][skills[j]]
    ws[i] = copy.deepcopy(w)
    t1, t2 = knapsack01D2(ws[i], v, W)
    dp.append(copy.deepcopy(t1))
    dp2.append(copy.deepcopy(t2))

# matrix[i][j]表示i次强化后，怪物j被打败之后，剩余的蓝量
matrix = []
for i in range(11):
    matrix.append([-1]*9)

bosses_hp = [396, 532, 643, 668, 687, 852, 1502, 1611, 2988]
bosses_award = [1695, 1678, 1362, 1458, 2659, 4157, 3089, 6493, 0]
initial = 1806-134

for i in range(11):
    if initial >= (i+1)*233+dp[i][bosses_hp[0]]:
        matrix[i][0] = initial-(i+1)*233-dp[i][bosses_hp[0]]

    if matrix[i][0] >= 0:
        matrix[i][0] += bosses_award[0]

for i in range(9)[1:]:
    if matrix[0][i-1] >= dp[0][bosses_hp[i]]:
        matrix[0][i] = matrix[0][i-1] - dp[0][bosses_hp[i]]

    if matrix[0][i] >= 0:
        matrix[0][i] += bosses_award[i]

print(dp[6][1502])

tracing = [[]]*9
for j in range(9)[1:]:
    r = 0
    for i in range(11)[1:]:
        for k in range(i+1):
            if matrix[k][j-1] >= 233*(i-k) and matrix[k][j-1]-233*(i-k)-dp[i][bosses_hp[j]] >= 0:
                matrix[i][j] = max(matrix[i][j], matrix[k][j-1]-233*(i-k)-dp[i][bosses_hp[j]])

            if matrix[i][j] > r:
                r = matrix[i][j]
                tracing[j] = [k, i]
        if matrix[i][j] >= 0:
            matrix[i][j] += bosses_award[j]

matrix矩阵的最终结果：

[[2096, 2382, 2065, 1779, -1,   -1,   -1,   -1,   -1],
 [1897, 2232, 1967, 1743, 2671, 4680, 3981, -1,   -1],
 [1696, 2067, 1851, 1666, -1,   4508, 3923, -1,   -1],
 [-1,   1866, 1692, 1556, -1,   4331, 3844, 6507, -1],
 [-1,   1679, 1548, 1461, -1,   4160, 3777, 6547, -1],
 [-1,   -1,   1364, -1,   -1,   -1,   3642, 6520, -1],
 [-1,   -1,   -1,   -1,   -1,   -1,   3510, 6502, 2],
 [-1,   -1,   -1,   -1,   -1,   -1,   3382, -1,   -1],
 [-1,   -1,   -1,   -1,   -1,   -1,   3236, -1,   -1],
 [-1,   -1,   -1,   -1,   -1,   -1,   3095, -1,   -1],
 [-1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1]]

可以看到，最终要打败第9个怪物，只有一种升级的可能性，其他升级方法都不可行，但是具体怎么升级呢？眼睛看，也能看出来，就没有写代码找了，因为需要升级的话，肯定是越早越好的，应该在打第一个怪物时做1次升级（本来游戏规定要升级1次，也就是第1行已经是升级过的情况），第5个怪物升级3次，第6个怪物再升级2次，叭叭叭，顺利通关～～

结论

这题的关键是怎么把背包问题建模，并且有连续好几个动态规划的子问题，层层相扣，加上出题人卡的数值，刚刚好只有一个解，我在疯狂尝试我自己方法的时候，也是差不多无助的状态，等到看到提示之后，又充满信心，解决了问题，也算是波谷到波峰的爽感。类似动态规划问题，在极客赛可能算简单的，但是放在平时刷题时，算难度高的，涉及到好几个状态矩阵的计算，又是一个和一个相关联的情况。挺有意思的一题，后面再继续写一篇极客挑战赛～