使用滑动窗口算法解决一些问题

在Leetcode上做到了一道题。

题目

给你两个长度相同的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

解答

删去其中繁杂的题干，题意大概是从一个自然数串中，找出最长的和小于 maxCost 的串。此题可以用滑动窗口的思路解决。

滑动窗口

定义一个左指针 leftPtr，一个右指针 rightPtr ，开始时将两个指针都置于最左边。右侧指针每次向右移动一格，判断左指针所处的位置是否符合题意。如果不符合，将其向右移动，直到符合题意为止。存储最大的符合题意的距离，即为答案。

简单说来，可以理解成右指针拉着左指针向右动，它们之间用一根线（maxCost)相连。如果线足够长(rightPtr - leftPtr <= maxCost)，左指针就不会动，否则它也会跟着向右移。

代码

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int length = s.length();
        int[] cost = new int[length];
        for (int i = 0; i < length; i++) {
            cost[i] = Math.abs(s.charAt(i) - t.charAt(i));
        }
        int rightPtr = 0, leftPtr = 0, max = 0, nowCost = 0;
        while (rightPtr < length) {
            nowCost += cost[rightPtr];
            while (nowCost > maxCost) {
                nowCost -= cost[leftPtr];
                leftPtr++;
            }
            if (rightPtr - leftPtr + 1 > max) {
                max = rightPtr - leftPtr + 1;
            }
            rightPtr++;
        }
        return max;
    }
}

我做了什么？

一个基于Flask的Web应用，输入教务系统的账号密码，即可查询学生的平时成绩

怎么用？

打开这个链接，输入账号密码，即可查看到成绩

想看源代码？

本应用在GitHub上开源，点击这个链接查看。

部分代码实现

import json

from flask import Flask, request, render_template

from service import get_score_detail, get_gpa_info, beautify_msg

app = Flask(__name__)


@app.route('/')
def index():
    return render_template('index.html')


@app.route('/score', methods=["POST"])
def get_score():
    username = request.form['username']
    password = request.form['password']
    year = request.form['year']
    term = request.form['term']
    config = [username, password, year, term]
    score_list = beautify_msg(get_gpa_info(config, get_score_detail(config)))
    return json.dumps(score_list)


if __name__ == '__main__':
    app.run()

指定路由

使用@app.route()方法，可以包含参数指定路由及支持的请求方法

@app.route('/score', methods=["POST"])

获取表单数据

使用 Flask框架提供的 request对象，通过request.form获取表单中的数据

    username = request.form['username']
    password = request.form['password']
    year = request.form['year']
    term = request.form['term']

返回数据

使用 json.dumps方法将需要返回的对象转化为json，返回给前端

    return json.dumps(score_list)

模板页面

将页面放入 template文件夹，在方法中使用render_template函数渲染页面

@app.route('/')
def index():
    return render_template('index.html')

静态资源

将静态资源放入 static 文件夹，即可使用类似于 https://www.example.com/static/css/example.css 的方法访问静态资源

JetBrain全家桶，这是多少开发者梦寐以求的东西。可是，299美元一年的价格，让很多同学望而却步。殊不知，你的学校邮箱，可以让你获得免费的正版全家桶。带上邮箱，来吧！

首先，我们当然要先拥有一个教育邮箱。以浙江工业大学的邮箱为例，打开邮箱（mail.zjut.edu.cn），用户名是你的学号，密码是身份证号的后八位。

接下来，打开JetBrain的网站（ https://www.jetbrains.com/shop/eform/students ）填写你的个人信息。注意，填写邮箱时，选择刚才的学校邮箱。

你肯定希望在收件箱看见你的邮件吧。但是由于神奇的原因，这封邮件会出现在你的拦截队列。

进入拦截队列，选择投递邮件，你就可以在收件箱看见它。

点击 Confirm Request

阅读协议，选择 I Accept，你的学生权限申请就通过了。接下来，在新出现的界面注册一个jetbrain账号。

输入信息，点击提交。你就拥有了一套全家桶。

下载你想要的那个吧！

问题描述:
长江游艇俱乐部在长江上设置了 n 个游艇出租站 1, 2, …, n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 r(i, j)（1≤i<j≤n）。试设计一个算法,计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> distance;
    for (int i = 1; i < n; i++) {
        vector<int> tmp;
        tmp.reserve(n);
        for (int j = 0; j < i; j++) {
            tmp.push_back(0);
        }
        for (int j = i; j < n; j++) {
            int t;
            cin >> t;
            tmp.push_back(t);
        }
        distance.push_back(tmp);
    }
    vector<int> ans = {0};
    for (int i = 1; i < n; i++) {
        int min = ans[i - 1] + distance[i - 1][i];
        for (int j = 0; j < i; j++) {
            min = min < ans[j] + distance[j][i] ? min : ans[j] + distance[j][i];
        }
        ans.push_back(min);
    }
    cout << ans[n - 1] << endl;
    return 0;
}

WordPress提供了很方便的CSS编辑器，可以为你的页面添加样式。
打开你的主题，进入“自定义CSS”，输入

html {
    filter: progid:DXImageTransform.Microsoft.BasicImage(grayscale=1);
    -webkit-filter: grayscale(100%);
}

即可让你的页面变成灰色

悼念逝者，致敬英雄