使用滑动窗口算法解决一些问题
在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美元一年的价格,让很多同学望而却步。殊不知,你的学校邮箱,可以让你获得免费的正版全家桶。带上邮箱,来吧!
你需要准备的东西:
- 一个.edu的教育邮箱
- 不错的网络连接
首先,我们当然要先拥有一个教育邮箱。以浙江工业大学的邮箱为例,打开邮箱(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%);
}
即可让你的页面变成灰色
悼念逝者,致敬英雄