Algorithm

A+B for Polynomials

这是甲级的第二道题目。主要的题意就是提供两个二项式,求两者之和。

这道题目和上次做的 B1010. 一元多项式求导很类似,不过那道题目的做法和常规的做法有些偏离,但是仍然得出了正确的答案。

那道题目的常规思路和这道题目是一样的,用一个数组存放各个项的系数,数组的索引即是每个项的幂。最后得到两个项目之和也就顺理成章了。

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
#include <stdio.h>
#include <stdlib.h>

int main() {
// Input A
int AK = 0;
float Aa[1001] = {0};

scanf("%d", &AK);
for(int i = 0; i < AK; i++) {
int N = 0;
float aN = 0;
scanf("%d %f", &N, &aN);
Aa[N] = aN;
}

// Input B
int BK = 0;
float Ba[1001] = {0};

scanf("%d", &BK);

for(int i = 0; i < BK; i++) {
int N = 0;
float aN = 0;
scanf("%d %f", &N, &aN);
Ba[N] = aN;
}

float resulta[1001] = {0};

int resultK = 0;
int max = -1;
for(int i = 1000; i >= 0; i--) {
resulta[i] = Aa[i] + Ba[i];
if(resulta[i]) {
resultK++;

if(max == -1) {
max = i;
}
}
}

printf("%d", resultK);

for(int i = max; i >= 0; i--) {
if(resulta[i]) {
printf(" %d %.1f", i, resulta[i]);
}
}

return 0;
}

Review

It Pays to Understand How Compilation Systems Work (Section 1.3)

Computer Systems: A Programmer’s Perspective, Third Edition

主要告诉我们程序员需要花时间了解编译系统是如何工作的。这对于我们优化程序的性能是很有帮助的,比如 ifswitchforwhile 哪个效率更高。

当然,这对于理解链接错误也是很有帮助的。什么是动态链接库静态链接库,以及它们有什么区别。

最后对于避免安全漏洞问题也是及其重要的。很少有程序员会去关心编译系统的原理,以及底层数据的存储,也就造成了之前很有名气的缓冲区溢出漏洞。

以上大多数内容都会在未来的章节中涉及到,目前仅需知道这么一回儿事儿即可,不需要过多的纠结。

Tips

基本弄清楚 Travis CI

最近贡献了 halo 项目。 随着 v1 版本的到来,需要对 halo 的 CI 和 CD 有一个自动化过程,尽可能少的人工干预。这不仅仅是 halo 应该做到的,是绝大多数项目应该实现的一个目标。

Travis CI 的高度自定义,给项目的构建和发布带来了极大的便利性。

首先贴上这一周的成果:

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
# 目标语言。
language: java
# 目标依赖。
jdk:
- oraclejdk8
# 这里需要删除与 gradle 相关动态内容。
before_cache:
- rm -f $HOME/.gradle/caches/modules-2/modules-2.lock
- rm -fr $HOME/.gradle/caches/*/plugin-resolution/
# 缓存 gradle 依赖和 gradle wrapper,因为我们采用 ./gradlew 进行构建。
# 当然最后也需要缓存 build/libs 用于后续的发布,不管是发不到 Github 还是 Docker Hub 上。
cache:
directories:
- $HOME/.gradle/caches/
- $HOME/.gradle/wrapper/
- $TRAVIS_BUILD_DIR/build/libs/
# 这是构建环境的发行版的设置
dist: trusty
# 这里可以自定义一些构建步骤。注意:这里仅仅是定义一些步骤,实际执行顺序和执行的条件建议在 stages 中进行定义。
jobs:
include:
- stage: test
# 常规的 check,包含 test task。
script: ./gradlew check
- stage: build
# 建议 build 之前进行 clean 操作,由于前面已经 check 过了,所以这里也就使用 -x 设置项,过滤了 test task。
script: ./gradlew clean build -x test
- stage: Build Docker Image for Release
# 在项目的根目录创建一个 scripts 文件夹,存放一系列命令,这样就实现了 bash script 的便捷操作。
script: ./scripts/docker-build-release.sh
- stage: Build Docker Image for Dev
script: ./scripts/docker-build-dev.sh
- stage: GitHub Release
# 根据官方文档,设置好必填项即可。(个人理解:这里实际上就是一系列官方定义好的 script 而已)
script: echo "Deploying to GitHub releases ..." && pwd
deploy:
provider: releases
api_key: $GITHUB_OAUTH_TOKEN
# 只有 file 中需要包含多个文件的时候,才需要设置此项,且必须设置此项才会生效,否则将会出现 build/libs/* 这个文件无法找到。
file_glob: true
file: $TRAVIS_BUILD_DIR/build/libs/*
skip_cleanup: true
on:
tags: true
# 这里定义了以上 jobs 的执行顺序和执行条件。
stages:
- test
- build
- name: GitHub Release
if: tag =~ /^v\d+\.\d+(\.\d+)?(-\S*)?$/
- name: Build Docker Image for Release
if: tag =~ /^v\d+\.\d+(\.\d+)?(-release)?$/
- name: Build Docker Image for Dev
if: tag =~ /^v\d+\.\d+(\.\d+)?-(beta|alpha)+(\.\d+)?$/
# 设置仅仅允许在哪些分支上进行构建。当然也可以设置正则表达式来进行筛选和过滤。
branches:
only:
- master
- dev
# 由于 travis ci 在 request 一个 release 的时候,会默认把 release 的 tag 当作成为一个 branch,所以必须得加上这么一个正则表达式来判断当前的 branch 是否为 tag。
# 正则表达式具体匹配的内容类似于:v1.0, v1.0.0, v1.0.0-beta, v1.0.0-beta.1, v1.0.0-alpha v1.0.0-alpha.123。
- /^v\d+\.\d+(\.\d+)?(-\S*)?$/

Share

这周想分享一下 OTP (One-Time Password Algorithm,主要用于两步验证) 的两种算法:HOTP 和 TOTP。

HOTP:https://www.ietf.org/rfc/rfc4226.txt

TOTP: https://www.ietf.org/rfc/rfc6238.txt