我的博客

python 获取微信公众号 access token

目录
  1. 接口详情
  2. 代码

接口详情

https请求方式: GET https://api.weixin.qq.com/cgi-bin/token?grant_type=client_credential&appid=APPID&secret=APPSECRET

参数说明

参数 是否必须 说明
grant_type 获取access_token填写client_credential
appid 第三方用户唯一凭证
secret 第三方用户唯一凭证密钥,即appsecret

返回说明

正常情况下,微信会返回下述JSON数据包给公众号:

1
{"access_token":"ACCESS_TOKEN","expires_in":7200}

代码

1
2
3
4
5
6
7
8
9
10
exp_time = 0
access_token = ''
def get_access_token():
global exp_time, access_token
if time.time() > exp_time:
r = requests.get('https://api.weixin.qq.com/cgi-bin/token?grant_type=client_credential&appid=APPID&secret=APPSECRET')
d = json.loads(r.text)
access_token = d['access_token']
exp_time = time.time() + d['expires_in'] - 10 # 减一点防止快到时间的时候已经失效了
return access_token

在 django 里直接把这个代码写到任意一个 views 里就可以了。

其他地方需要 access_token 就直接调这个函数,保证不会短时间内重复申请。

之前我会存到数据库里,但实际上没必要。

django 微信公众号开发 - 给用户主动推送消息(发送模板消息,python公众号开发)

目录
  1. 介绍
  2. 限制
  3. 准备步骤
  4. 官方文档
  5. 添加模板
  6. 获取 access token
    1. 接口详情
    2. 代码
  7. 调用接口,发送模板消息
    1. 接口详情
    2. 代码

介绍

给微信公众号用户主动推送消息指的是发送模板消息。可以随时给用户发送提醒。功能非常丰富,比如提醒用户特定事件(该付费了,商品降价,任务执行成功,遇到错误等等)。

不仅可以向用户发送文字消息,还可以实现用户点击后跳转指定网页或小程序。

限制

但是该功能也受到很多限制。模板消息顾名思义,只能根据模板发送消息,模板可以从模板库选择,也可以自己创建,但是必须通过审核才能使用。而且只有微信公众号可以使用模板消息,且要通过微信认证(目前的条件是必须要有营业执照才能注册公众号,个人注册的是订阅号,无法通过微信认证)

准备步骤

  1. 通过微信认证

  2. 另外要发送消息,先要绑定用户 openid,具体操作请间我前一篇文章:django 微信公众号开发 - 获取授权 绑定用户微信 openid

官方文档

官方文档写的比较复杂,而且没有示例代码。

微信模板消息官方文档:https://developers.weixin.qq.com/doc/offiaccount/Message_Management/Template_Message_Interface.html

添加模板

image.png

这时候需要记下模板 id

image.png

获取 access token

接口详情

https请求方式: GET https://api.weixin.qq.com/cgi-bin/token?grant_type=client_credential&appid=APPID&secret=APPSECRET

参数说明

参数 是否必须 说明
grant_type 获取access_token填写client_credential
appid 第三方用户唯一凭证
secret 第三方用户唯一凭证密钥,即appsecret

返回说明

正常情况下,微信会返回下述JSON数据包给公众号:

1
{"access_token":"ACCESS_TOKEN","expires_in":7200}

代码

1
2
3
4
5
6
7
8
9
10
exp_time = 0
access_token = ''
def get_access_token():
global exp_time, access_token
if time.time() > exp_time:
r = requests.get('https://api.weixin.qq.com/cgi-bin/token?grant_type=client_credential&appid=APPID&secret=APPSECRET')
d = json.loads(r.text)
access_token = d['access_token']
exp_time = time.time() + d['expires_in'] - 10 # 减一点防止快到时间的时候已经失效了
return access_token

python 获取微信公众号 access token

调用接口,发送模板消息

接口详情

http请求方式: POST https://api.weixin.qq.com/cgi-bin/message/template/send?access_token=ACCESS_TOKEN

POST数据说明

POST数据示例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
{
"touser":"OPENID",
"template_id":"ngqIpbwh8bUfcSsECmogfXcV14J0tQlEpBO27izEYtY",
"url":"http://weixin.qq.com/download",
"miniprogram":{
"appid":"xiaochengxuappid12345",
"pagepath":"index?foo=bar"
},
"data":{
"first": {
"value":"恭喜你购买成功!",
"color":"#173177"
},
"keyword1":{
"value":"巧克力",
"color":"#173177"
},
"keyword2": {
"value":"39.8元",
"color":"#173177"
},
"keyword3": {
"value":"2014年9月22日",
"color":"#173177"
},
"remark":{
"value":"欢迎再次购买!",
"color":"#173177"
}
}
}

参数说明

参数 是否必填 说明
touser 接收者openid
template_id 模板ID
url 模板跳转链接(海外帐号没有跳转能力)
miniprogram 跳小程序所需数据,不需跳小程序可不用传该数据
appid 所需跳转到的小程序appid(该小程序appid必须与发模板消息的公众号是绑定关联关系,暂不支持小游戏)
pagepath 所需跳转到小程序的具体页面路径,支持带参数,(示例index?foo=bar),要求该小程序已发布,暂不支持小游戏
data 模板数据
color 模板内容字体颜色,不填默认为黑色

注:url和miniprogram都是非必填字段,若都不传则模板无跳转;若都传,会优先跳转至小程序。开发者可根据实际需要选择其中一种跳转方式即可。当用户的微信客户端版本不支持跳小程序时,将会跳转至url。

返回码说明

在调用模板消息接口后,会返回JSON数据包。正常时的返回JSON数据包示例:

1
2
3
4
5
{
"errcode":0,
"errmsg":"ok",
"msgid":200228332
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def send_msg(idx):
users = UserProfile.objects.filter(school=request.user.userpro file.school, user_type='工作人员', vacation_manage=True)
data = {
"touser":"OPENID",
"template_id":"xxxxxxxxx",
"url":"https://xxxx.com/view/%d/" % idx,
"data":{
"first": {
"value": "",
"color": "#173177"
},
"keyword1":{
"value": '',
"color":"#173177"
},
"keyword2": {
"value": data,
"color":"#173177"
},
"keyword3": {
"value": '',
"color":"#173177"
},
"remark":{
"value": description,
"Data": description,
"color":"#173177"
}
}
}
for u in users:
if u.openid:
data['touser'] = u.openid
url = 'https://api.weixin.qq.com/cgi-bin/message/template/send?access_token=' + get_access_token()
r = requests.post(url, json.dumps(data))

Leetcode 85. 最大矩形 maximal rectangle

目录
  1. 暴力
  2. 转换为多个 84 题的问题,对每一行使用递增栈方法
  3. 动态规划

题目链接
这个题目是 84 题的升级版
84 题题解

暴力

暴力,能过(但是 84 题用类似的策略是不行的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
n = len(matrix)
if n == 0: return 0
m = len(matrix[0])
max_l = [[0] * m for i in range(n)]
for i in range(n):
cur = 0
for j in range(m):
if matrix[i][j] == '1':
cur += 1
else:
cur = 0
max_l[i][j] = cur
ans = 0
for i in range(n):
for j in range(m):
if matrix[i][j] == '1':
minl = max_l[i][j]
for k in range(i, n):
if matrix[k][j] == '0': break
minl = min(minl, max_l[k][j])
ans = max(ans, minl * (k-i+1))
return ans

max_l 是每个点向左延伸最多有多少个格子。

计算 max_l 矩阵要遍历 n × m。

然后再从每个点开始,看这个点作为右上顶点的矩形的最大面积,这个又需要沿着 n 方向遍历。

所以时间复杂度是 O(n^2 × m)

转换为多个 84 题的问题,对每一行使用递增栈方法

上面的方法 max_l 的每一列都相当于 84 题中的一个问题。
下面的代码直接拿来了 84 题的代码,对每一行调用了那个函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
hs = [0] + heights + [0]
s = []
ans = 0
for i, h in enumerate(hs):
while s and hs[s[-1]] > h:
j = s.pop()
ans = max(ans, hs[j] * (i-s[-1]-1))
s.append(i)
return ans

def maximalRectangle(self, matrix: List[List[str]]) -> int:
n = len(matrix)
if n == 0: return 0
m = len(matrix[0])
dp = [int(i) for i in matrix[0]]
ans = self.largestRectangleArea(dp)
for i in range(1, n):
for j in range(m):
if matrix[i][j] == '1':
dp[j] += 1
else:
dp[j] = 0
ans = max(ans, self.largestRectangleArea(dp))
return ans

动态规划

从每个为 1 的位置,我们可以计算当前位置上这样的矩形的面积:

  1. 高度尽量往上延伸(到上面第一个 0 或者边界)
  2. 左右尽量宽

那么全局最大的面积一定在这里面。

任意一点都有一个 h 高度,l 左边界,r 右边界。矩形面积是 h × (r - l)则里的 l 是该点左边第一个 0 (或边界)的右边一个元素的下标。r 是最右边的一个 0 或者(边界)下标。

这里 h 好计算,当前是 0,h 设为 0,不是 0 则 h 是上一行的 h 加一。

l 和 r,以 l 为例,始终维护当前左边界,(初始为 0)如果当前是 1,l 是当前左边界和上一行左边界的最大值(因为我们要看整个左边界的情况);如果当前是 0,就更新当前左边界为当前下标加一,l 设为 0。(这里设为 0 起始并不是真的 0,而且对本行该位置计算不起作用(因为当前位置 h 肯定为 0,一乘就是 0 了)主要是相当于重置了状态,下一行的左边界就不受本行限制了。

r 的情况类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
n = len(matrix)
if n == 0: return 0
m = len(matrix[0])
l = [0] * m
r = [m] * m
h = [0] * m
ans = 0
for i in range(n):
for j in range(m):
if matrix[i][j] == '1':
h[j] += 1
else:
h[j] = 0
cur = 0
for j in range(m):
if matrix[i][j] == '1':
l[j] = max(cur, l[j])
else:
cur = j + 1
l[j] = 0
cur = m
for j in range(m-1, -1, -1):
if matrix[i][j] == '1':
r[j] = min(cur, r[j])
else:
r[j] = m
cur = j
for j in range(m):
ans = max(ans, h[j] * (r[j] - l[j]))
return ans

leetcode 第 175 场周赛 1348. 推文计数 tweet counts per frequency

目录
  1. 一个问题
  2. 代码
  3. 直接遍历代码

https://leetcode-cn.com/problems/tweet-counts-per-frequency

这题稍微有点麻烦,比赛的时候样例返回有问题。

但本身不难,维护一个字典,把每个用户的时间放入一个数组,查询时,先排序,然后二分找到起始点,向后遍历,要注意的是,如果后面的时间范围中没有推文,也要往数组里补充相应数量的 0。

一个问题

感谢 xie-wei-9@leetcode-cn 同学帮我指出问题。

问题是每次 get 要先排序,排序的平均时间复杂度是 O(nlogn),带来的好处是通过 O(logn) 的一次查找避免了扫描全部元素。整个时间复杂度 O(nlogn)。

实际上如果扫描全部元素时间复杂度是 o(n)。这样看来使用排序+二分查找,时间复杂度反而更高了。

我重新写了一个扫描全部元素的代码,结果发现时间耗时会更长一点。(最后附代码)

image.png

因为实际运行时间和操作顺序、数量还有数据本身都有关系。也和排序的算法具体的实现有关。如果插入操作很少,而查询操作很多,而排序又是插入排序,可能每次重新排序所用的操作数量很少(如果是普通的快速排序,在列表基本有序的情况下排序效率反而很低接近于 n^2)

虽然这样,但我这个代码写的确实是有问题的,写的不好,如果当时我考虑到这点,我不会这么写。可能使用一个有序数据结构存时间会更好(暂时没有更新代码)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import bisect
class TweetCounts:

def __init__(self):
self.ul = {}

def recordTweet(self, tweetName: str, time: int) -> None:
if tweetName not in self.ul: self.ul[tweetName] = []
self.ul[tweetName].append(time)

def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
self.ul[tweetName].sort()
#print(self.ul[tweetName])
if freq == 'minute':
f = 60
elif freq == 'hour':
f = 3600
else:
f = 86400
b = bisect.bisect(self.ul[tweetName], startTime-1)
ans = []
cnt = 0
limit = startTime + f
for n in self.ul[tweetName][b:]:
#print(n)
if n > endTime:
ans.append(cnt)
r = (endTime - limit) // f
if limit < endTime:
ans.append(0)
if r > 0:
ans += [0] * r
return ans
if n >= limit:
# 0-59 60-119
ans.append(cnt)
r = (n - limit) // f
if r > 0:
ans += [0] * r
limit += (r + 1) * f
cnt = 0
cnt += 1
ans.append(cnt)
if limit < endTime:
ans.append(0)
r = (endTime - limit) // f
#print(r, limit)
if r > 0:
ans += [0] * r
return ans

直接遍历代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import bisect
class TweetCounts:

def __init__(self):
self.ul = {}

def recordTweet(self, tweetName: str, time: int) -> None:
if tweetName not in self.ul: self.ul[tweetName] = []
self.ul[tweetName].append(time)

def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
if freq == 'minute':
f = 60
elif freq == 'hour':
f = 3600
else:
f = 86400
result = [0] * math.ceil((endTime - startTime+1) / f)
for t in self.ul[tweetName]:
if startTime <= t <= endTime:
result[(t - startTime) // f] += 1
return result

Leetcode 5335. 参加考试的最大学生数 maximum students taking exam

目录
  1. 状态压缩 dp
    1. 解题思路
    2. 代码
  2. 超时代码

https://leetcode-cn.com/contest/weekly-contest-175/problems/maximum-students-taking-exam/

直接搜索会超时(附超时代码)

可以使用状态压缩 dp

状态压缩 dp

解题思路

seat_map 用一个整数表示一行的状态

line_state 标识任意一行所有可行的座位安排(其实就是没有相邻的)因为单就一行来看,只要没人相邻就 ok

line_state 中任意一个和 seat_map 的任意一行做按位与,看是否变化,就可以知道这一行是否可以这么座(是否会坐到坏座位)

两行之间的是否合法,就是一行右移、左移再和另一行按位与。

本思路参考了排行榜上 leoGW 的代码,思路一致,但是重写了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
def maxStudents(self, seats: List[List[str]]) -> int:
n = len(seats)
m = len(seats[0])
dp = [[-1] *(1<<m) for i in range(n)]
seat_map = [0] * n # 每个整数代表一行的座位,整数每个二进制位为 0 代表座位不能用, 1 代表能用
for i, l in enumerate(seats):
for ch in l:
if ch == ".":
seat_map[i] = (seat_map[i] << 1) + 1 # 1 代表当前座位可用
else:
seat_map[i] = (seat_map[i] << 1) + 0 # 0 代表当前座位不可用

line_state = []
num = []
for i in range(1<<m):
x = 3 # 3 的二进制是 011,表示有两个座位挨着的情况
f = True
for j in range(m):
if i & x == x: # 有相邻座位
f = False
break
x <<= 1
if not f: continue
line_state.append(i)
num.append(str(bin(i)).count('1'))
if i & seat_map[0] == i:
dp[0][i] = num[-1]
print(line_state)
print(num)
for i in range(1, n):
for j, jn in zip(line_state, num):
if j & seat_map[i] == j:
for k in line_state:
if ((j << 1) & k ==0 ) and ((j >> 1) & k == 0): # 两行没有斜对角的人
dp[i][j] = max(dp[i-1][k] + jn, dp[i][j])
return max(dp[n-1])

超时代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
cnt = 0
class Solution:
def maxStudents(self, seats: List[List[str]]) -> int:
global cnt, mcnt
n = len(seats)
m = len(seats[0])
mp = [[0] * m for i in range(n)]
# for i in range(n):
# for j in range(m):
# if seats[i][j] == '#':
# mp[i]
cnt = 0
mcnt = 0
#print(n, m)
def dfs(i, j):
global cnt, mcnt
#print(i, j)
if i == n:
mcnt = max(mcnt, cnt)
return
ni, nj = i, j + 1
if nj == m: ni, nj = i+1, 0
if seats[i][j] == '.':
if mp[i][j] == 0:
cnt += 1
mp[i][j] += 100
if j - 1 >= 0:
if i - 1 >= 0:
mp[i-1][j-1] += 1
if i + 1 < n:
mp[i+1][j-1] += 1
mp[i][j-1] += 1
if j + 1 < m:
if i - 1 >= 0:
mp[i-1][j+1] += 1
if i + 1 < n:
mp[i+1][j+1] += 1
mp[i][j+1] += 1

dfs(ni, nj)
cnt -= 1
mp[i][j] -= 100
if j - 1 >= 0:
if i - 1 >= 0:
mp[i-1][j-1] -= 1
if i + 1 < n:
mp[i+1][j-1] -= 1
mp[i][j-1] -= 1
if j + 1 < m:
if i - 1 >= 0:
mp[i-1][j+1] -= 1
if i + 1 < n:
mp[i+1][j+1] -= 1
mp[i][j+1] -= 1
dfs(ni, nj)
dfs(0, 0)
return mcnt

百度智能云免费 SSL 证书的申请与部署(nginx HTTPS 配置,http 请求重定向)

目录
  1. 申请
  2. 部署
  3. http 请求重定向到 https
  • 无法访问此网站
  • 百度云目前说每个用户可以申请三个免费 ssl 证书,每个证书有效期 1 年,每个证书只能在一个域名上使用。

    环境:

    我的服务器是百度云服务器,CentOS 系统,安装了 nginx,原来是 http,现在要部署 https

    申请

    申请还是比较方便的,填写基本信息,在百度云购买的域名可以自动设置 dns 验证,然后没多长时间就发下来了。

    下载证书需要设置一个四位数字的密码,用于解压压缩包。

    百度云控制台证书下载.png

    因为我用的是 nginx,所以选 nginx。

    下载以后解压得到了一个 crt 文件是证书,一个 key 文件是对应的私钥。

    部署

    把 crt 文件和 key 文件放到 web 服务器上,要注意保护证书和私钥,同时要保证 nginx 有权限访问它们。

    首先要找到 nginx 配置文件。

    1
    2
    [root@instance-z85mlgpk ~]# whereis nginx
    nginx: /usr/sbin/nginx /usr/lib64/nginx /etc/nginx /usr/share/nginx /usr/share/man/man8/nginx.8.gz /usr/share/man/man3/nginx.3pm.gz

    配置文件在 /etc/nginx/nginx.conf ,编辑 nginx 配置文件

    1
    vi /etc/nginx/nginx.conf

    原来是

    改为

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    server {  
    listen 443 ssl default_server;
    listen [::]:443 ssl default_server;
    server_name xuemiyixin.com;
    ssl_certificate crts/xuemiyixin.com.crt;
    ssl_certificate_key crts/xuemiyixin.com.key;
    ssl_session_cache shared:SSL:1m;
    ssl_session_timeout 5m;

    ssl_ciphers HIGH:!aNULL:!MD5;
    ssl_prefer_server_ciphers on;
    # 后面还有其他内容,不用修改 .....

    改完保存后,输入命令 nginx -s reload,因为我是 nginx 已经在运行了,如果你的 nginx 未在运行可以直接输入 nginx 启动 nginx。

    如果没报错就配置成功了。

    http 请求重定向到 https

    但是这是你用原来的链接访问的时候会得到错误:

    无法访问此网站

    xxxxx.com 拒绝了我们的连接请求。

    请试试以下办法:

    ERR_CONNECTION_REFUSED

    因为这是 80 端口已经不再开放了,你得把网址前面的 http 改成 https 才能访问到(端口 443)

    所以为了用户体验可以把 80 端口的 http 请求重定为 https 请求

    1
    2
    3
    4
    5
    6
    server {  
    listen 80;
    server_name www.xxxx.com;

    rewrite ^(.*)$ https://$host$1 permanent;
    }

    改完保存后,输入命令 nginx -s reload,再次重新载入配置,在访问 http,就可以直接重定向到 https 了。

    Leetcode 84. 柱状图中最大的矩形 Largest Rectangle in Histogram

    目录
    1. 会超时的方法:
      1. 双重循环
      2. 分治算法
    2. 正确解法
    3. 超时代码
      1. 超时代码一 双重循环
      2. 超时代码一 分治

    https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

    会超时的方法:

    双重循环

    最简单的思路,时间复杂度 O(n^2) 会超时(最后附超时代码)

    分治算法

    先找到当前数组中最小元素。

    那么答案将在一下三种情况中:

    1. 包含最小元素,那么高度是最小元素高度,长度是整个区间
    2. 不包含最小元素,且在最下元素左边 (递归左半区间)
    3. 不包含最小元素,且在最下元素有边 (递归右半区间)

    这个方法的平均时间复杂度是 O(nlogn)

    但是最坏情况时间复杂度仍是 O(n^2) 也会超时(最后附超时代码)

    正确解法

    从前向后遍历,过程中维护一个递增的栈。

    如果下一个大于栈顶元素,就直接入栈。

    如果小于,就把栈里大的元素都弹出来,并且计算高度是弹出的元素高度,宽度是当前元素到栈顶元素之间。

    为什么可以以弹出元素高度为高度,当前位置和栈顶元素位置间的距离为宽度呢?因为栈是递增的,比弹出元素高度低的元素一定都在栈里,栈顶一定是离这个元素最近的一个(高度小于该元素的元素)换句话就是它们之间的元素高度都大于该元素。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
    hs = [0] + heights + [0]
    s = []
    ans = 0
    for i, h in enumerate(hs):
    while s and hs[s[-1]] > h:
    j = s.pop()
    ans = max(ans, hs[j] * (i-s[-1]-1))
    s.append(i)
    return ans

    超时代码

    超时代码一 双重循环

    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
    maxa = 0
    for i in range(len(heights)):
    minh = heights[i]
    for j in range(i, len(heights)):
    minh = min(minh, heights[j])
    maxa = max(maxa, minh * (j-i+1))
    return maxa

    超时代码一 分治

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
    def solve(l, r, d):
    if l >= r: return 0
    if l == r-1: return heights[l]
    min_i = l
    min_h = heights[l]
    for i, h in enumerate(heights[1+l:r]):
    if h < min_h:
    min_h = h
    min_i = i+l+1
    return max(min_h * (r - l), solve(l, min_i, d+1), solve(min_i+1, r, d+1))
    return solve(0, len(heights), 0)

    参考

    leetcode 79. 单词搜索 word search

    目录
    1. 解题思路
    2. 代码

    https://leetcode-cn.com/problems/word-search/

    解题思路

    在每个点都能向上下左右四个方向搜索。

    但是注意,不能回到已经搜索过的地方,所以定义了 mp 记录所有点是否已经搜索过了。
    否则会出现如:

    1
    [['A', 'B']], 'ABA'

    1
    2
    3
    [['A', 'B'],
    ['D', 'C']]
    'ABCDA'

    这种被认为是 True

    可以看一个具体的例子的搜索过程:

    1
    2
    3
    4
    [["A","B","C","E"],
    ["S","F","E","S"],
    ["A","D","E","E"]],
    "ABCESEEEFS"

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    0 0 A
    0 1 B
    0 2 C
    0 3 E
    1 3 S
    1 2 E
    2 2 E
    2 3 E
    backtrack
    backtrack
    backtrack
    2 3 E
    2 2 E
    1 2 E
    1 1 F
    1 0 S

    开始是从 左上 沿着第一行一直到 右上,再到第二行最右的 S,这时候没有继续向下,而是先往左了,这导致后面搜到三个 E,就到角落里了,所以这里出现了回溯,退回了三步,还是回到了这个 S,从这里往下走,才能找到最终的答案。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
    n = len(board)
    m = len(board[0])
    def dfs(i, j, index):
    mp[i][j] = False
    #print('\t' * index, i, j, word[index-1])
    if index == len(word):
    return True
    for ii, jj in [(0,1),(0,-1),(1,0),(-1,0)]:
    if 0 <= i + ii < n and 0 <= j + jj < m and board[i+ii][j+jj] == word[index] and mp[i+ii][j+jj]:
    if dfs(i+ii, j+jj, index + 1):
    return True
    #print('backtrack')
    mp[i][j] = True
    return False
    for i in range(n):
    for j in range(m):
    if board[i][j] == word[0]:
    mp = [[True] * m for i in range(n)]
    if dfs(i, j, 1):
    return True
    return False

    代码二,这个有一个防止回到上一个位置的策略,但是与 mp 冗余了,是没有必要的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
    n = len(board)
    m = len(board[0])
    def dfs(i, j, index, last_d):
    mp[i][j] = False
    print('\t' * index, i, j, word[index-1])
    if index == len(word):
    return True
    skip_d = [1, 0, 3, 2, -1][last_d]
    for d, (ii, jj) in enumerate([(0,1),(0,-1),(1,0),(-1,0)]):
    if skip_d != d and 0 <= i + ii < n and 0 <= j + jj < m and board[i+ii][j+jj] == word[index] and mp[i+ii][j+jj]:
    if dfs(i+ii, j+jj, index + 1, d):
    return True
    print('backtrack')
    mp[i][j] = True
    return False
    for i in range(n):
    for j in range(m):
    if board[i][j] == word[0]:
    mp = [[True] * m for i in range(n)]
    if dfs(i, j, 1, -1):
    return True
    return False

    s = Solution()
    s.exist(
    [["A","B","C","E"],
    ["S","F","E","S"],
    ["A","D","E","E"]],
    "ABCESEEEFS"
    )

    django 微信公众号开发 - 获取授权 绑定用户微信 openid

    目录
    1. 数据库(Model)建立保存用户 openid 的字段
    2. 跳转到用户授权页面
    3. 用户授权后通过 code 获取 access_token
    4. 添加回调域名
    5. 最终代码总览
      1. urls.py
      2. views.py
      3. models.py
    6. 错误解决

    官方文档

    流程稍微有点复杂,但是这个比较重要,通过授权获得用户 openid 才能进行给用户主动推送消息等功能。

    特别注意:这个必须要微信公众号(个人的订阅号不能用这个功能)进行了微信认证才能使用。还有回调域名需要是 https 的,现在有地方可以申请到免费 https 证书,可以参考我的这篇文章 百度智能云免费 SSL 证书的申请与部署(nginx HTTPS 配置,http 请求重定向)

    数据库(Model)建立保存用户 openid 的字段

    因为我们让用户授权的目的就是得到 openid,获得 openid 后要存到数据库中,并和用户建立对应关系。

    我用的是 django 自带的用户系统,官方推荐建立一个自定义的 UserProfile 之类的 Model 保存用户相关信息。

    1
    2
    3
    4
    5
    6
    7
    from django.db import models
    from django.contrib.auth.models import User


    class UserProfile(models.Model):
    user = models.OneToOneField(User, on_delete=models.CASCADE, null=True, default=None)
    openid = models.CharField("微信 openid", max_length=32)

    openid 的长度貌似是 28 位,这里定义的最大长度 32 应该够用。

    参考

    跳转到用户授权页面

    这个页面是微信的页面,需要我们加上参数,让用户跳转过去,url 是

    1
    https://open.weixin.qq.com/connect/oauth2/authorize?appid=APPID&redirect_uri=REDIRECT_URI&response_type=code&scope=SCOPE&state=STATE#wechat_redirect

    appid 去公众号平台 - > 开发 -> 基本配置 里找。

    redirect_uri 是成功以后的回调地址,是你自己的一个 url,要通过 urlEncode 进行编码

    response_type 写 code

    scope 可选填 snsapi_base 或 snsapi_userinfo

    state 非必填,所以直接不加这个参数了

    关于 python 的 urlEncode 可以使用:

    1
    2
    3
    import urllib.parse
    s='https://xxx.com/api/weixin_bind_callback/'
    urllib.parse.quote(s)

    结果是:'https%3A//xxx.com/api/weixin_bind_callback/'

    它没有处理斜杠,添加一个 safe 参数就可以处理斜杠了

    1
    2
    3
    import urllib.parse
    s='https://xxx.com/api/wexin_bind_callback/'
    urllib.parse.quote(s, safe='')

    结果是:'https%3A%2F%2Fxxx.com%2Fapi%2Fwexin_bind_callback%2F'

    我的这个 url 的最终结果是:

    1
    https://open.weixin.qq.com/connect/oauth2/authorize?appid=XXXX&redirect_uri=https%3A%2F%2FXXXX.com%2Fweixin%2Fbind%2Fcallback%2F&response_type=code&scope=snsapi_userinfo#wechat_redirect

    用户授权后通过 code 获取 access_token

    下面的逻辑要写在上面给用户访问的 url 里的回调的页面里。

    请求 url 是:

    https://api.weixin.qq.com/sns/oauth2/access_token?appid=APPID&secret=SECRET&code=CODE&grant_type=authorization_code

    APPID 和 secret 去公众号平台 - > 开发 -> 基本配置 里找。

    code 是返回的 code

    grant_type 就写 authorization_code

    这里需要使用 http 客户端库,例如 python3 的 requests 或者 python2 的 urllib2,请求微信的接口

    python3 的例子:

    1
    2
    3
    4
    5
    import requests
    APPID = ''
    secret = ''

    r = requests.get('https://api.weixin.qq.com/sns/oauth2/access_token?appid=APPID&secret=SECRET&code=CODE&grant_type=authorization_code')

    请求结果是:

    1
    2
    3
    4
    5
    6
    7
    {
    "access_token":"ACCESS_TOKEN",
    "expires_in":7200,
    "refresh_token":"REFRESH_TOKEN",
    "openid":"OPENID",
    "scope":"SCOPE"
    }

    这时候需要再发起一次请求才能得到用户的信息。

    这次的请求 url:

    https://api.weixin.qq.com/sns/userinfo?access_token=ACCESS_TOKEN&openid=OPENID&lang=zh_CN

    这个返回的结果是:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    {   
    "openid":" OPENID",
    "nickname": NICKNAME,
    "sex":"1",
    "province":"PROVINCE",
    "city":"CITY",
    "country":"COUNTRY",
    "headimgurl": "http://thirdwx.qlogo.cn/mmopen/g3MonUZtNHkdmzicIlibx6iaFqAc56vxLSUfpb6n5WKSYVY0ChQKkiaJSgQ1dZuTOgvLLrhJbERQQ4eMsv84eavHiaiceqxibJxCfHe/46",
    "privilege":[ "PRIVILEGE1" "PRIVILEGE2" ],
    "unionid": "o6_bmasdasdsad6_2sgVt7hMZOPfL"
    }

    最终的 view 是:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    def weixinbind_callback(request):
    code = request.GET.get('code')
    state = request.GET.get('state')
    # print(code, state)
    APPID = 'xxxxxx'
    secret = 'xxxxx'
    r = requests.get(
    'https://api.weixin.qq.com/sns/oauth2/access_token?appid=%s&secret=%s&code=%s&grant_type=authorization_code' % (APPID, secret, code)
    )
    print(r.text)
    d = json.loads(r.text)
    # {
    # "access_token":"ACCESS_TOKEN",
    # "expires_in":7200,
    # "refresh_token":"REFRESH_TOKEN",
    # "openid":"OPENID",
    # "scope":"SCOPE"
    # }
    r = request.get(
    'https://api.weixin.qq.com/sns/userinfo?access_token=%s&openid=%s&lang=zh_CN' % (d['access_token'], d['openid'])
    )
    # print(r.text)
    dd = json.load(r.text)
    # {
    # "openid":" OPENID",
    # "nickname": NICKNAME,
    # "sex":"1",
    # "province":"PROVINCE",
    # "city":"CITY",
    # "country":"COUNTRY",
    # "headimgurl": "http://thirdwx.qlogo.cn/mmopen/g3MonUZtNHkdmzicIlibx6iaFqAc56vxLSUfpb6n5WKSYVY0ChQKkiaJSgQ1dZuTOgvLLrhJbERQQ4eMsv84eavHiaiceqxibJxCfHe/46",
    # "privilege":[ "PRIVILEGE1" "PRIVILEGE2" ],
    # "unionid": "o6_bmasdasdsad6_2sgVt7hMZOPfL"
    # }
    request.user.userprofile.openid = dd['openid']
    request.user.userprofile.nickname = dd['nickname']
    request.user.userprofile.wsex = dd['sex']
    request.user.userprofile.province = dd['province']
    request.user.userprofile.city = dd['city']
    request.user.userprofile.country = dd['country']
    request.user.userprofile.headimgurl = dd['headimgurl']
    request.user.userprofile.privilege = dd['privilege']
    request.user.userprofile.unionid = dd['unionid']
    request.user.userprofile.save()
    return HttpResponseRedirect('/weixin/')

    添加回调域名

    网页授权域名

    到公众号平台 设置-> 公众号设置 -> 功能设置 -> 网页授权域名 的配置选项中,把刚刚的回调的 url 的域名添加上,有一个认证文件。

    他说要把文件传到服务器上,但是这个对于 django 不太方便,可以直接写一个 view 返回这个文件内容就可以了,我直接放到 urls 文件里了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    from django.urls import path
    from django.http import HttpResponse

    def weixin_verify(request):
    return HttpResponse('PJRLUusp1NXyuD70')



    urlpatterns = [
    # 微信开发
    path('weixin/', account.views.weixin_page),
    path('weixin/bind/', account.views.weixinbind),
    path('weixin/bind/callback/', account.views.weixinbind_callback),
    path('MP_verify_PJRLUusp1NXyuD70.txt', weixin_verify),


    ]

    最终代码总览

    urls.py

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    from django.urls import path
    from django.http import HttpResponse

    def weixin_verify(request):
    return HttpResponse('PJRLUusp1NXyuD70')

    urlpatterns = [
    # 微信开发
    path('weixin/', account.views.weixin_page),
    path('weixin/bind/', account.views.weixinbind),
    path('weixin/bind/callback/', account.views.weixinbind_callback),
    path('MP_verify_PJRLUusp1NXyuD70.txt', weixin_verify),


    ]

    views.py

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    import requests
    from django.shortcuts import render
    from django.http import HttpResponse, HttpResponseRedirect
    import time
    import json


    def weixin_page(request):
    return render(request, 'weixin_index.html')


    def weixinbind(request):
    return HttpResponseRedirect('https://open.weixin.qq.com/connect/oauth2/authorize?appid=XXXXX&redirect_uri=https%3A%2F%2FXXXXX.com%2Fweixin%2Fbind%2Fcallback%2F&response_type=code&scope=snsapi_userinfo#wechat_redirect')


    def weixinbind_callback(request):
    code = request.GET.get('code')
    state = request.GET.get('state')
    print(code, state)
    APPID = 'xxxxx'
    secret = 'xxxxx'
    r = requests.get(
    'https://api.weixin.qq.com/sns/oauth2/access_token?appid=%s&secret=%s&code=%s&grant_type=authorization_code' % (APPID, secret, code)
    )
    print(r.text)
    d = json.loads(r.text)
    # {
    # "access_token":"ACCESS_TOKEN",
    # "expires_in":7200,
    # "refresh_token":"REFRESH_TOKEN",
    # "openid":"OPENID",
    # "scope":"SCOPE"
    # }
    r = requests.get(
    'https://api.weixin.qq.com/sns/userinfo?access_token=%s&openid=%s&lang=zh_CN' % (d['access_token'], d['openid'])
    )
    print(r.content)
    dd = json.loads(r.content.decode('utf8'))
    # {
    # "openid":" OPENID",
    # "nickname": NICKNAME,
    # "sex":"1",
    # "province":"PROVINCE",
    # "city":"CITY",
    # "country":"COUNTRY",
    # "headimgurl": "http://thirdwx.qlogo.cn/mmopen/g3MonUZtNHkdmzicIlibx6iaFqAc56vxLSUfpb6n5WKSYVY0ChQKkiaJSgQ1dZuTOgvLLrhJbERQQ4eMsv84eavHiaiceqxibJxCfHe/46",
    # "privilege":[ "PRIVILEGE1" "PRIVILEGE2" ],
    # "unionid": "o6_bmasdasdsad6_2sgVt7hMZOPfL"
    # }
    request.user.userprofile.openid = dd['openid']
    request.user.userprofile.nickname = dd['nickname']
    request.user.userprofile.wsex = dd['sex']
    request.user.userprofile.province = dd['province']
    request.user.userprofile.city = dd['city']
    request.user.userprofile.country = dd['country']
    request.user.userprofile.headimgurl = dd['headimgurl']
    request.user.userprofile.privilege = json.dumps(dd['privilege'])
    #request.user.userprofile.unionid = dd['unionid']
    request.user.userprofile.refresh_token_time = time.time()
    request.user.userprofile.save()
    return HttpResponseRedirect('/weixin/')

    models.py

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    from django.db import models
    from django.contrib.auth.models import User

    class UserProfile(models.Model):
    user = models.OneToOneField(User, on_delete=models.CASCADE, null=True, default=None)
    # 微信开发
    openid = models.CharField("微信 openid", max_length=32, default='')
    nickname = models.CharField("微信昵称", max_length=256, default='')
    wsex = models.CharField("微信性别", max_length=3, default='')
    province = models.CharField("微信省份", max_length=50, default='')
    city = models.CharField("微信城市", max_length=50, default='')
    country = models.CharField("微信国家", max_length=50, default='')
    headimgurl = models.CharField("微信头像", max_length=200, default='')
    privilege = models.CharField("微信权限", max_length=3, default='')
    unionid = models.CharField("微信 unionid", max_length=32, default='')
    refresh_token = models.CharField("微信 refresh_token", max_length=512, default='')
    refresh_token_time = models.IntegerField(default=0)

    html 部分省略了

    错误解决

    微信登录失败 redirect_uri域名与后台配置不一致,错误码10003

    到公众号平台 设置-> 公众号设置 -> 功能设置 -> 网页授权域名 的配置选项中,修改授权回调域名。

    见上文 添加回调域名。

    错误

    Leetcode 76. 最小覆盖子串 minimum window substring

    目录
    1. 解题思路
    2. 代码

    https://leetcode-cn.com/problems/minimum-window-substring/

    解题思路

    l 和 r 是当前目标串的最左下标和最右下标。

    r 不断向前进。

    l 在保证当前字母没有必要保留时向前进(没有必要指:这个字母不在目标字符串里 或者 这个字母当前数量已经超过要求),这是一个贪心策略

    cnt 统计了目标字母还需要多少。

    n 是 cnt 中的字母有几种的数量已经满足了。

    ans 则是最终的答案

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution:
    def minWindow(self, s: str, t: str) -> str:
    import collections
    cnt = collections.Counter(t)
    ans = ''
    n = 0 # 当前我满足了 t 中的字母的种数
    l = 0
    for r, ch in enumerate(s):
    if ch not in cnt:
    continue
    cnt[ch] -= 1
    if cnt[ch] == 0:
    n += 1
    while s[l] not in cnt or cnt[s[l]] < 0: # 看看当前 l 处的字母是否必要,没必要 l 就加以
    if s[l] in cnt: cnt[s[l]] += 1
    l += 1
    if n == len(cnt):
    if not ans or len(ans) > r - l + 1:
    ans = s[l: r+1]
    return ans