Algorithm

A+B for Polynomials

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

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

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

#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 的高度自定义,给项目的构建和发布带来了极大的便利性。

首先贴上这一周的成果:

# 目标语言。
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