我的博客

牛客编程巅峰赛S2第5场Python解法

目录
  1. 第一题
    1. 代码
  2. 第二题
    1. 示例1
      1. 返回值
    2. 示例2
      1. 返回值
    3. 示例3
      1. 返回值
    4. 代码
  3. 第三题
    1. 示例1
      1. 返回值
    2. 示例2
      1. 返回值
    3. 代码

https://ac.nowcoder.com/acm/contest/9556

这次题目比周末的简单。

第一题

链接:https://ac.nowcoder.com/acm/contest/9556/A

给你一个含有n个元素的数组arr[i],请你告诉牛牛这个数组的中位数大还是平均数大,如果中位数更大输出1,如果平均数更大输出-1,如果中位数和平均数相等输出0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def Answerofjudge(self , arr ):
# write code here
arr.sort()
s = sum(arr)
av = s / len(arr)
i = len(arr) >> 1
if len(arr) % 2 == 1:
x = arr[i]
else:
x = (arr[i] + arr[i-1]) / 2
if abs(x - av) < 1e-7:
return 0
elif av > x:
return -1
return 1

排序,算平均数和中位数

第二题

链接:https://ac.nowcoder.com/acm/contest/9556/B

牛牛非常怕他的女朋友,怕到了走火入魔的程度,以至于每当他看到一个字符串同时含有n,p,y三个字母他都害怕的不行。现在有一个长度为m的只包含小写字母‘a’-‘z’的字符串x,牛牛想知道能令他不害怕的最长子串的长度是多少。(对于字符串”abc”来说,”c”,”ab”都是原串的子串,但”ac”不是原串子串)

示例1

1
"abcdefghijklmn"

返回值

1
14

示例2

1
"ynp"

返回值

1
2

示例3

1
"ypknnbpiyc"

返回值

1
7

代码

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
class Solution:
def Maximumlength(self , x ):
# write code here
d = {'n': 0, 'p': 0, 'y': 0} # 统计当前窗口内的三个字母数量
l, r = 0, 0 # 窗口左右指针
ans = 0 # 窗口最大值
f = False # 当前窗口内是否同时出现三种字母
c = 0
while l < len(x) and r < len(x):
if not f:
if x[r] in 'npy':
if d[x[r]] == 0:
c += 1
if c == 3:
f = True
d[x[r]] += 1
r += 1
else:
if x[l] in 'npy':
if d[x[l]] == 1:
c -= 1
f = False
d[x[l]] -= 1
l += 1
if not f:
ans = max(ans, r - l)
return ans

滑动窗口,l 是起始位置,r是终止位置,r - l 是窗口大小(即当前字符串长度)

第三题

链接:https://ac.nowcoder.com/acm/contest/9556/C

给定牛牛一个后缀表达式s,计算它的结果,例如,1+1对应的后缀表达式为1#1#+,‘#’作为操作数的结束符号。

其中,表达式中只含有‘+’、’-‘、’*‘三种运算,不包含除法。

本题保证表达式一定合法,且计算过程和计算结果的绝对值一定不会超过101810^{18}1018

示例1

1
"1#1#+"

返回值

1
2

示例2

1
"12#3#+15#*"

返回值

复制;)

1
225

代码

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
class Solution:
def solve(self , str ):
# write code here
# 解析后缀表达式
x = str.split('#')
xx = []
for p in x:
while len(p) != 1 and not p.isdigit(): # 判断是否粘连 ++ 或者 ++3 类似的情况
xx.append(p[0])
p = p[1:]
xx.append(p)
x = xx
# 后缀表达式求值
ns = [] # 操作数栈
for p in x:
if p.isdigit():
ns.append(int(p)) # 入栈
else:
o1 = ns.pop() # 出栈
o2 = ns.pop()
if p == '+':
a = o1 + o2
elif p == '-':
a = o2 - o1
else:
a = o2 * o1
ns.append(a) # 运算结果入栈
return ns[0]

先按照 ‘#’ split 字符串,这时候可能有 符号 + 操作数 或者 符号 + 符号黏在一起的情况。例如 “1#1#1#1#+++”,这里需要依次处理 split 后的每个元素。只要元素长度大于 1 且不是数字,就一定是粘连的情况,这时候第一个字符必然是符号,把符号取下来,继续验证是否粘连,直到没有粘连。

比特币地址聚类

目录
  1. Automatic Bitcoin Address Clustering[C]// IEEE International Conference on Machine Learning & Applications. IEEE, 2017
  2. Research on Anonymization and De-anonymization in the Bitcoin System[J]. Computer ence, 2015
    1. ATC方法(Analysis of the Transaction Chain)
  3. An analysis of anonymity in the Bitcoin system,in SocialCom/PASSAT 2011

Automatic Bitcoin Address Clustering[C]// IEEE International Conference on Machine Learning & Applications. IEEE, 2017

论文 Ermilov D , Panov M , Yanovich Y . Automatic Bitcoin Address Clustering[C]// IEEE International Conference on Machine Learning & Applications. IEEE, 2017:461-466. 指出

Research on Anonymization and De-anonymization in the Bitcoin System[J]. Computer ence, 2015

论文 Shentu Q C , Yu J P . Research on Anonymization and De-anonymization in the Bitcoin System[J]. Computer ence, 2015. (pdf)介绍了比特币的隐私问题,文中总结了比特币保障隐私的方法:

  1. 比特币地址无法对应到用户
  2. 比特币交易也不包含个人信息
  3. 比特币新交易传播迅速,也很难探测交易发布者的 IP

但是比特币隐私的问题有:

  1. 对于一些中心化的比特币服务者,比如交易所等,能获取比特币用户的身份信息
  2. 用户可能将一些比特币地址公布在网络上,将会导致一些比特币地址被标记
  3. 交易链是公开且可被追溯的
  4. 多输入交易会暴露不同地址的关系(Gathering some or all inputs when sending Bitcoins to others, which may expose other addresses of the sender)
  5. The change address of transactions could be classified by attackers to the sender

文中指出了比特币隐私的漏洞:

  1. F. Reid,H. Martin, An analysis of anonymity in the Bitcoin system,in SocialCom/PASSAT 2011.
  2. Taint Analysis, blockchain.info, https://bockchina.info/en/taint,2015.10
  3. M. Ober, S. Katzenbeisser, K. Hamacher, Structure and Anonymity of the Bitcoin Transaction Graph, Future Internet, vol5, pp237-250, 2013
  4. D. Ron and A. Shamir, Quantitative analysis of the full Bitcoin transaction graph, ePrint 2012:584.
  5. Androulaki, E.; Karame, G.; Roeschlin, M.; Scherer, T.; Capkun, S. Evaluating User Privacy in Bitcoin; IACR Cryptology ePrint Archive, vol. 2012:596
  6. Sarah Meiklejohn, Marjori Pomarole, Grant Jordan, Kirill Levchenko, Damon McCoy, Geo_rey M. Voelker, and Stefan Savage. A fistful of bitcoins: Characterizing payments among men with no names. In Proceedings of the 2013 Conference on Internet Measurement Conference, IMC ‘13, pages 127-140, New York, NY, USA, 2013. ACM.

还有分析比特币地址和真实用户关系的方法:

  1. Androulaki, E.; Karame, G.; Roeschlin, M.; Scherer, T.; Capkun, S. Evaluating User Privacy in Bitcoin; IACR Cryptology ePrint Archive, vol. 2012:596
  2. Sarah Meiklejohn, Marjori Pomarole, Grant Jordan, Kirill Levchenko, Damon McCoy, Geo_rey M. Voelker, and Stefan Savage. A fistful of bitcoins: Characterizing payments among men with no names. In Proceedings of the 2013 Conference on Internet Measurement Conference, IMC ‘13, pages 127-140, New York, NY, USA, 2013. ACM.

还有分析新交易发送方IP地址的方法:

  1. Sergio Lerner. New vulnerability: know your peer public addresses in 14 minutes. https://bitcointalk.org/?topic=135856 , 2015.3
  2. Kaminsky, D., Black Ops of TCP/IP, http://www.slideshare.net/dakami/black-ops-of-tcpip-2011-black-hat-usa-2011, 2015.4
  3. Philip Koshy, Diana Koshy, and Patrick McDaniel. An analysis of anonymity in bitcoin using p2p network traffic. 2014. Financial Cryptography, 2014,469-485.
  4. A. Biryukov, D. Khovratovich, I. Pustogarov, Deanonymisation of clients in Bitcoin P2P network, CoRR, vol. abs, 2014:1405.7418.
  5. A. Biryukov, D. Khovratovich, and I. Pustogarov, Bitcoin over Tor isn’t a good idea, CoRR, vol. 2014:1410.6079.

ATC方法(Analysis of the Transaction Chain)

  1. 交易网络和比特币用户网络(transaction network and the user network
  2. Taint analysis,是 Blockchain.info 提供的一种服务,用于计算一个地址中金额来自于其他地址的比例
  3. Amount analysis,一种用于鉴别混币的方法,每笔输入扣除一个固定比例的混币费用,变成了输出
  4. Timing sequence,混币时,混币请求者把资金转移给混币者,在一定时间内,混币者需要返还资金,攻击者可以通过估计返还的大概时间范围找到这些返还的资金。

An analysis of anonymity in the Bitcoin system,in SocialCom/PASSAT 2011

论文 F. Reid,H. Martin, An analysis of anonymity in the Bitcoin system,in SocialCom/PASSAT 2011. 指出比特币系统的三个显著特点:

  1. 比特币的完整交易历史是公开的,这是客户端可以验证新交易是否合法的必要条件
  2. 交易可以拥有多个输入和输入。而且往往一个比特币交易会有单个较大额的输入或者多个较小额的输入。而对于输出,则常常有两个输出,即一个用于支付,一个用于找零
  3. 收款人和付款人通过公钥、私钥标识,但是一个人可以拥有多个密钥对。

然后论文提出了比特币交易网络和比特币用户网络(transaction network and the user network)。

论文中提到的去匿名化方法:

  1. 发现找零地址:如果一个交易有两个输出,且确定其是某种特定客户端创建的,可以根据其源码确定那个输出是找零,并把找零地址关联到交易创建者地址。

  2. 可以猜测交易金额是某种法币的等价金额,可根据当时的汇率尝试发现法币种类。也可以根据交易所的交易记录关联到交易所。

  3. 如果某些地址经常在相同时间活跃,可以构建地址的共现网络。

onecloud-armbian

目录
  1. 编译安装 Python 3.9
  2. xrdp(来源)
    1. 配置
    2. 配置openbox

/etc/update-motd.d/30-armbian-sysinfo 显示温度,负载,存储,网络等信息的脚本。来源

编译安装 Python 3.9

1
2
3
4
5
6
7
8
9
10
11
12
wget https://www.python.org/ftp/python/3.9.0/Python-3.9.0.tgz
tar -xzvf Python-3.9.0.tgz
cd Python-3.9.0/
sudo apt build-dep python3 # https://devguide.python.org/setup/#build-dependencies
sudo apt install zlib1g.dev # zlib
sudo apt install libffi-dev # ctypes
sudo apt install libsqlite3-dev # sqlite3
./configure --enable-optimizations --enable-shared --disable-profiling # –-prefix=/usr/local
make -j2
sudo make install
sudo ldconfig
sudo ln /usr/local/bin/python3.9 /usr/local/bin/py -s
1
2
sudo update-alternatives --display x-window-manager
sudo update-alternatives --config x-window-manager

xrdp(来源

1
sudo apt install openbox tint2 xrdp xserver-xorg-core  xorgxrdp tightvncserver fonts-wqy-microhei pcmanfm

配置

编辑/etc/xrdp/startwm.sh文件,把

最后两行注释掉,

1
2
#test -x /etc/X11/Xsession && exec /etc/X11/Xsession
#exec /bin/sh /etc/X11/Xsession

然后增加

1
exec openbox-session

配置openbox

创建openbox自启目录:

1
mkdir ~/.config/openbox

创建启动脚本:

1
touch ~/.config/openbox/autostart

在里面添加下面内容:

1
tint2

JavaScript Base64编码

目录

浏览器内置了 btoa 和 atob 用于编码和解码 Base64。使用上主要有两个问题。

  1. 对于IE 浏览器,仅 IE 10 或以上的版本可以支持

  2. 对于非 ASCII 字符报错(参考MDN

    因为 JavaScript 的字符串占两个 byte。但是 Base64 的输入应该是 bytes,所以如果传入的字符串中,每个字符如果第二个 byte 非 0,那么btoa 就会报错。

解决方案:

  1. MDN 中提到的方法是

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // convert a Unicode string to a string in which
    // each 16-bit unit occupies only one byte
    function toBinary(string) {
    const codeUnits = new Uint16Array(string.length);
    for (let i = 0; i < codeUnits.length; i++) {
    codeUnits[i] = string.charCodeAt(i);
    }
    return String.fromCharCode(...new Uint8Array(codeUnits.buffer));
    }

    xxx = toBinary(‘你好’)

    得到的是

    1
    "`O}Y"

    再把这个字符串做 base64 编码,得到 YE99WQ==

    但是问题是解码后还需要通过函数转换才能得到原文

    1
    2
    3
    4
    5
    6
    7
    function fromBinary(binary) {
    const bytes = new Uint8Array(binary.length);
    for (let i = 0; i < bytes.length; i++) {
    bytes[i] = binary.charCodeAt(i);
    }
    return String.fromCharCode(...new Uint16Array(bytes.buffer));
    }
  2. 通过转义后再编码(参考

    1
    2
    3
    4
    5
    6
    7
    function utoa(str) {
    return window.btoa(unescape(encodeURIComponent(str)));
    }
    // base64 encoded ascii to ucs-2 string
    function atou(str) {
    return decodeURIComponent(escape(window.atob(str)));
    }

    utoa(‘你好’) 的结果是:5L2g5aW9

    好处是直接解码就得到原文,坏处是 unescape 方法已经不推荐使用了。

  3. 仅使用 encodeURIComponent 转义后再编码 (参考

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    function b64Encode(str) {
    return btoa(encodeURIComponent(str));
    }

    function b64Decode(str) {
    return decodeURIComponent(atob(str));
    }

    b64Encode('你好') // "JUU0JUJEJUEwJUU1JUE1JUJE"
    b64Decode('JUU0JUJEJUEwJUU1JUE1JUJE') // "你好"

    坏处是编码的结果变长,且解码后需要转义

北邮人搜索+页面快照查看

目录

折腾了一天,终于把北邮人搜索上线了!有关键词搜索和快照查看两个功能。关键词搜索只支持标题的搜索。因为我的服务器内存太少,无法加载内容的倒排索引。今后会再想办法优化。

image.png

image.png

image.png

8 月 1 日笔试-Python 版

目录
  1. 第一题
  2. 第二题
  3. 第三题 HTML 模板解析(没做出来)

第一题

小袁报了 N 个课程,每个课程有开始时间和结束时间。但是有一些重复的课程,求小袁最多需要同时听多少门课。

样例:

4
1 4
1 2
2 3
3 4

样例输出: 2

AC 代码:

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
n = int(input())
s = []
e = []

for i in range(n):
a, b = map(int, input().split(' '))
s.append(a)
e.append(b)
s.sort()
e.sort()
c = 0
m = 0
ii = 0
jj = 0
while ii < n and jj < n:
if jj != n and (ii == n or e[jj] <= s[ii]):
#print('end', e[jj])
jj += 1
c -= 1
else:
#print('start', s[ii])
ii += 1
c += 1
m = max(m, c)
print(m)

第二题

有 N 个同学,需要给没人分发一张奖券。一个人先拿着所有奖券,留下一张,然后剩余的分个其他人,其他人继续用同样的方法分,直到每人都有一张。

开奖时,每个奖券获得一个整数值(可以是负数),每个人可以选择自己的奖券值作为奖励,也可以额外选择全部或部分他发送出去的奖券,但是如果不选某个奖券,则也无法选择后续的奖券。例如,A 的开始有 1,2,3,4 四张。给了 B 奖券2,3,4,B 又把 3 给了 C, 4 给了 D。则 A 可以选:

1
1,2
1,2,3
1,2,3
1,2,3,4

但不能选如 1, 4

题目分析:

所有人构成一颗树,第一个发的人是树根。使用后序遍历遍历一次就可以得到答案。策略是叶子节点的值只能是自身,其他节点的值是自身加所有非负的孩子。

Python 需要注意的地方:如果书高度很高,会超递归限制,可以模拟递归或者使用 sys.setrecursionlimit 设置递归深度。第二 Python 整数不会溢出,其他语言可能需要考虑递归过程中的溢出问题。

代码:

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
import sys
sys.setrecursionlimit(1000000)
mod = 1000000003

n = int(input())
ch = [[] for i in range(n)]
v = [0] * n
root = -1
for i in range(n):
a, b = map(int, input().split(' '))
v[i] = a
if b != 0:
ch[b-2].append(i)
else:
root = i
ans = v[root]
# print(ch)
# print(v)
def vis(i):
global ans
x = v[i]
for child in ch[i]:
r = vis(child)
if r > 0:
x += r
ans = max(x, ans)
return x
vis(root)

print(ans % mod)

第三题 HTML 模板解析(没做出来)

给出一个 JSON 对象,一段 HTML 模板代码,要求返回渲染后的 HTML。

语法类似于 vue:

  1. {{}} 内的值替换为 JSON 对象中的值
  2. y-if 如果为 false 或者 undefined 则删除该 DOM 元素(含子元素)
  3. y-for 列表渲染

样例

{
"isMain": false,
"list": []
}

<div class="head">
<button y-if="{{isMain}}">首页</button>
</div>
<ul class="content">
<!– 卡片区域 –>
<li class="card isMain" y-for="lesson, index in list">
<div class="card-title">
<i y-if="{{lesson.label}}">{{lesson.label.type}}</i>
{{lesson.title}}
</div>
班课<span class="bold">-</span>老师:{{lesson.teacher}}
<div class="lesson-time">{{lesson.time}}<i class="tt"></i></div>
</li>
</ul>
end

这题没时间做了,感觉很麻烦。

力扣周赛 198 - python 解答

目录
  1. 5464 换酒问题
  2. 5465 子树中标签相同的节点数
  3. 5466 最多的不重叠子字符串
  4. 5467 找到最接近目标值的函数值

做出了四道题目,但后两道做的很勉强,也错了几次。刚看第三道题,虽然写着 medium,但是没思路,打开第四道看到反而已经有人过了,于是先做了第四道,才回来做第一道。

最后一道是纯暴力枚举加了几个条件:

  1. 去除相邻重复值
  2. 是函数输出为 0 时停止枚举,因为 0 按位与任何数都依然是 0.
  3. 因为在不断按位与的过程中函数输出是单调减的,所以,但差值大于当前最小差值也可以停止遍历

但是我感觉应该还有更好的解法

第三题用的模拟方法,依次寻找只含一个字母,两个字母 … 的串

5464 换酒问题

https://leetcode-cn.com/contest/weekly-contest-198/problems/water-bottles/

1
2
3
4
5
6
7
8
9
10
class Solution:
def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
c = numBottles
cc = numBottles
kp = numBottles
while kp >= numExchange:
cc = kp // numExchange
kp = kp % numExchange + cc
c += cc
return c

5465 子树中标签相同的节点数

https://leetcode-cn.com/contest/weekly-contest-198/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/

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
class Solution:
def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
ed = {}
for s, e in edges:
if s not in ed:
ed[s] = []
if e not in ed:
ed[e] = []
ed[s].append(e)
ed[e].append(s)
ans = [0] * n
vised = [False] * n
def vis(i):
vised[i] = True
c = {}
c[labels[i]] = 1
if i in ed:
for ch in ed[i]:
if not vised[ch]:
cc = vis(ch)
for k in cc:
if k not in c:
c[k] = 0
c[k] += cc[k]
ans[i] = c[labels[i]]
return c
vis(0)
return ans

5466 最多的不重叠子字符串

https://leetcode-cn.com/contest/weekly-contest-198/problems/maximum-number-of-non-overlapping-substrings/

代码有点长,但是思路还是清晰的。

贪心策略就是:

1. 尽可能选择出现字母数少的子串

2. 在 1 的前提下尽可能选择长度短的

对于出现字母数为 1 的子串,可以特别处理,因为他们一定不会干扰别人,所以可以直接挑出所有仅含一个字母的子串。

第一个循环用于统计每个字母第一次出现位置和最后一次出现位置,顺便还得出了这个字母是否都是连续出现的(如果除了第一次以外,如果有一个该字母前面是其他字母就不是连续出现了)。对每个字母得到三个值 [第一次出现的下标,最后一次出现的下标,是否是连续出现的]

然后定义 used 字典(其实用集合就行)保存有那些字母已经用过了。

ans 就是要返回结果。

nd 是去除了仅含一个字母的子串后的结果,后面会对这个 nd 排序。

循环二,挑出仅含一个字母的子串,这种仅含一个字母的子串自然就是循环一中标记为 True 的子串。

循环三,挑出每个字母构成的子串,并检验是否合法,对每个字母得到: [出现字母数, 长度, 字母, 出现的字母列表]

然后对上面得到的结果降序排序,在一次检验,合法的加入 ans 并在 used 记录。

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution:
def maxNumOfSubstrings(self, s: str) -> List[str]:
d = {}
for i, ch in enumerate(s): # 循环一,得到每个字母的起点和终点
if ch not in d:
d[ch] = [i, i, True]
else:
if d[ch][1] != i - 1:
d[ch][2] = False
d[ch][1] = i
#print(d)
used = {}
ans = []
nd = []
for ch in d: # 循环二,挑出仅含一个字母的子串
if d[ch][2]:
used[ch] = True
ans.append(s[d[ch][0]:d[ch][1]+1])
for ch in d: # 循环三,挑出每个字母构成的子串,并检验是否合法
if not d[ch][2]:
cc = 0
ccx = set()
f = True

mini = d[ch][0]
maxi = d[ch][1]
change = True
while change:
change = False
i = d[ch][0]
while i <= maxi:
if s[i] in used:
f = False
break
else:
if maxi < d[s[i]][1]:
change = True
maxi = d[s[i]][1]
if mini > d[s[i]][0]:
mini = d[s[i]][0]
change = True
ccx.add(s[i])
i += 1
i = d[ch][0]
while i >= mini:
if s[i] in used:
f = False
break
else:
if maxi < d[s[i]][1]:
change = True
maxi = d[s[i]][1]
if mini > d[s[i]][0]:
mini = d[s[i]][0]
change = True
ccx.add(s[i])
i -= 1
d[ch][1] = maxi
d[ch][0] = mini
if f:
nd.append([len(ccx), maxi-d[ch][0], ch, list(ccx)])
#print(d)
nd.sort()
for n in nd:
f = True
for cc in n[3]:
if cc in used:
f = False
break
if f:
for cc in n[3]:
used[cc] = True
ch = n[2]
ans.append(s[d[ch][0]:d[ch][1]+1])
return ans

5467 找到最接近目标值的函数值

https://leetcode-cn.com/contest/weekly-contest-198/problems/find-a-value-of-a-mysterious-function-closest-to-target/

方法并不太好,但是写起来简单。

两层循环,外层遍历 l 的取值(0 ~ len(arr)),内层遍历 r 的取值(当前 l ~ len(arr))

内层循环是一个不断按位与的过程,所以值一定是不断变小或者不变的,可以利用这个条件提前终止内层循环。

1. 先去除重复的相邻元素

2. 函数输出(ans)为 0 或这最小差(r) 为 0 则退出当前内层循环

3. 最小差为 0 则退出外层循环

4. 如果 target - 当前输出 大于已经得到的最小差,退出内层循环。

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 closestToTarget(self, arr: List[int], target: int) -> int:
arr2 = []
l = arr[0] -1
for v in arr:
if v != l:
arr2.append(v)
l = v
#print(len(arr), len(arr2))
arr = arr2
r = abs(-1000000000 - target)
for i in range(len(arr)):
ans = arr[i]
r = min(r, abs(ans - target))
for j in range(i+1, len(arr)):
ans = ans & arr[j]
r = min(r, abs(ans - target))
if ans == 0 or r == 0:
break
if target > ans and target - ans >= r:
break
if r == 0:
break
return r

C# 函数设置超时

目录

下面代码展示不能单纯使用 System.Threading.Tasks 的 Wait 函数来设置超时,因为只要主进程不退出,子线程扔持续执行。可参考 C# 文档 Wait 函数并不能结束线程,而事实上并没有好办法从线程外部结束线程,除非线程自身支持。

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
CancellationTokenSource tokenSource = new CancellationTokenSource();
System.Threading.Tasks.Task t = new System.Threading.Tasks.TaskFactory().StartNew(() => {
for (int i = 0; i < 10; i++)
{
System.Console.WriteLine(i);
Thread.Sleep(1000);
}
}, tokenSource);
t.Wait(3000);
t.Dispose();
for (int i = 0; i < 10; i++)
{
System.Console.WriteLine("hello");
Thread.Sleep(1000);
}
}
}
}

leetcode 785 判断二分图

目录

https://leetcode-cn.com/problems/is-graph-bipartite/

判断一个图是否是二分图

这道题可以用并查集做。

题目给出了每个点相邻的点,我们只需把与一个点相邻的所有点合并,因为与同一个点相邻的所有点一定在二分图的同一侧。

最后再遍历所有点,看每个点和他相邻的点是否在同一集合。如果有在同一集合的情况就不是二分图了。

另外这个题可以用搜索的方法做,给一个点染成红色,再把它所有邻点染为蓝色,并递归下去,如果有冲突则不可行。

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
from typing import List
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
fa = [ -1 for i in range(len(graph)) ]
cn = [ 1 for i in range(len(graph)) ]
def getfa(i):
# print(fa, i)
if fa[i] == -1:
return i
# input()
fa[i] = getfa(fa[i])
return fa[i]
def merge(a, b):
# print('merge', a, b)
faa = getfa(a)
fab = getfa(b)
if faa == fab:
return
if cn[faa] > cn[fab]:
faa, fab = fab, faa
fa[faa] = fab
cn[fab] += cn[faa]
# print(fa)
for x in graph:
for n in x[1:]:
merge(x[0], n)
s = set([getfa(i) for i in range(len(graph))])
# print(s)
# print(fa)
for i in range(len(graph)):
fai = getfa(i)
for n in graph[i]:
if fai == getfa(n):
return False
return True

更换域名

目录
  1. 重定向
    1. url 映射代码
    2. 测试
    3. 申请新 https 证书
  2. 博客部署到 blog 目录下
  3. 修改百度统计代码
  4. 域名解析
  5. Valine 评论和阅读统计

这次更换域名改动不少,让我想换域名的直接原因是实习的公司内网屏蔽了所有 .top 域名,而我的博客在百度的收录一直有问题,也怀疑是域名的问题。除了把域名从 codeplot.top 换到 es2q.com 外我还做了如下调整:

  1. 改写所有文章页面 url ,使只包含字母,数字、连字符和下划线
  2. 博客整体移入 blog 文件夹
  3. 部署时也部署到 GitHub Page 的 blog 目录下

因为我在 leetcode 和 SegmentFault 等网站还留了一些我博客的链接,而且在谷歌上还有几百的索引页面,所以需要做原域名的重定向,但是由于更改了很多页面的 url,所以需要做 url 的映射表。然后评论系统和阅读量统计也都需要修复。

重定向

我在新买的华为云服务器上部署了重定向程序,首先通过 sitemap 得到所有文章的 url, 然后手动改写 url,去除了中文和特殊符号等,要同步修改 hexo 的 source 下的 md 文件名。重定向的程序是用 Flask 写的,注意要指明状态码 301(Flask 的 redirect 默认是 302)即永久转移。

用到的 url.txt 文件每行内容是新 path\t原path

url 映射代码

不仅做了映射,还记录请求信息,帮助分析哪里还有未更新的链接

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
from flask import Flask, request, redirect
from urllib import parse
import json, time
app = Flask(__name__)

ud = {'index.html': '/blog/index.html', '/': '/blog/'}
f = open('url.txt', encoding='gbk')
for l in f:
nu, ou = l.split('\t')
ud[ou.strip()] = nu
host = 'http://127.0.0.1:4000' # 用于本地测试的域名
host = 'https://es2q.com' # 新域名
f.close()

@app.before_request
def be1():
to_url = host + '/blog' + request.path
Host = request.headers.get('Host')
ua = request.headers.get('User-Agent')
ac = request.headers.get('Accept')
ace = request.headers.get('Accept-Encoding')
acl = request.headers.get('Accept-Language')
try:
ip = request.headers['X-Forwarded-For'].split(',')[0]
except:
ip = request.remote_addr
try:
if request.path in ud:
to_url = host + ud[request.path]
elif parse.quote(request.path) in ud:
to_url = host + ud[parse.quote(request.path)]
elif (request.path+'/') in ud:
to_url = host + ud[request.path+'/']
except Exception as e:
with open('redirect.log', 'a') as f:
f.write(request.path + '\t' + 'err' + '\t' + str(e) + '\n')
with open('redirect.log', 'a') as f:
f.write('%d\t%s\t%s\t%s\t%s\t%s\t%s\t%s\t%s\t%s\n' %(int(time.time()), ip, Host, ua, ac, ace, acl, request.path, to_url, request.referrer))
return redirect(to_url, code=301)


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

测试

测试是否所有链接可以正常访问的脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import requests
from bs4 import BeautifulSoup
from tqdm import tqdm

ud = {}
f = open('url.txt')
for l in f:
nu, ou = l.split('\t')
ud[ou.strip()] = nu
host = 'http://127.0.0.1:8001'
l = []
for k in ud:
r = requests.get(host + k)
if r.status_code != 200:
print('error', k)
continue
b = BeautifulSoup(r.content.decode(), features='html.parser')
l.append([b.title, k])
#for ll in l:
# print(ll)

还写了一个检查 md 文件中是否有敏感词的脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dicts = ['xxx.txt']
wds = []
for d in dicts:
with open(d, encoding='utf8') as f:
for l in f:
wds.append(l.strip())
import os
from tqdm import tqdm
tdir = 'source\\_posts\\'
fs = os.listdir(tdir)
err = []
for fi in tqdm(fs):
with open(os.path.join(tdir, fi), encoding='utf8') as f:
txt = f.read()
for wd in wds:
if wd in txt:
print(fi, wd)
err.append((fi, wd))
for e in err:
print(e)

之前有一次我的百度索引量突然减到 1,我怀疑可能是一篇思政课笔记中有敏感词汇。

申请新 https 证书

原来是 GitHub Pages 给的证书,现在需要一个新的,这个网站:https://freessl.cn/ 非常好用。

博客部署到 blog 目录下

考虑以后整个网站可能有除了博客以外的内容,所以考虑把整个博客放到 https://es2q.com/blog/ 下。可以通过修改 _config.yml:

1
2
3
4
5
6
7
# URL
url: https://es2q.com/blog/
root: /blog/

# Directory
source_dir: source
public_dir: public/blog/

但是这样对 hexo-deployer-git 并不有效。

因为它的代码中直接复制了 public_dir 的内容,然后 push 到 github 上。

我是通过修改 hexo-deployer-git 的代码实现了 push 到 blog 目录下,需要修改的文件是:\node_modules\hexo-deployer-git\lib\deployer.js

首先修改代码开始的 publicDir,直接写成 ‘public’。

1
var publicDir = 'public';//this.public_dir;

第二找到这一句 return fs.copyDir(publicDir, deployDir, opts);

在下面添加:

1
2
3
4
5
6
7
8
9
10
11
  // 前面的内容这里省略了
return fs.copyDir(publicDir, deployDir, opts);
}).then(function() {
return fs.copyFile(publicDir+'/blog/CNAME', deployDir+'/CNAME'); // 复制 CNAME,Github Pages 绑定域名用的
}).then(function() {
return fs.copyFile(publicDir+'/blog/index.html', deployDir+'/index.html'); // 把 index 复制到根目录来一份
}).then(function() {
return fs.copyFile(publicDir+'/blog/sitemap.xml', deployDir+'/sitemap.xml'); // 把 sitemap 复制到根目录一份,如果没有生成 sitemap就不需要这个
}).then(function() {
return fs.copyFile(publicDir+'/blog/baidusitemap.xml', deployDir+'/baidusitemap.xml'); // baidu sitemap,同上一条
}) // 后面还有内容,是原来的代码

修改百度统计代码

更换了域名所以要重新生成百度统计代码。可以放到主题文件的 header 或者 footer 里。

域名解析

把新域名解析到 GitHub Pages,同时调整 GitHub 仓库配置,然后把旧域名解析到运行重定向服务的服务器上,并配置好 Nginx。

Valine 评论和阅读统计

阅读统计 id 前面要添加 /blog/。评论则需要修改后台数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<%- partial('_partial/article', {post: page, index: false}) %>
<script src='//unpkg.com/valine/dist/Valine.min.js'></script>
<!-- id 将作为查询条件 -->
<span id="/blog/<%= page.path %>" class="leancloud_visitors" data-flag-title="<%= page.title %>">
<em class="post-meta-item-text">阅读量 </em>
<i class="leancloud-visitors-count"></i>
</span>
<p>评论无需登录,可以匿名,欢迎评论!</p>
<div id="vcomments"></div>
<script>
new Valine({
el: '#vcomments',
appId: 'vdTqlvkiIk2AmomVRXrR9kb0-gzGzoHsz',
appKey: 'yrlSqvbHUJqqVzH2rb0t2X9B',
visitor: true
})
</script>