作者: Gryen7

  • ClickHouse 服务迁移记录

    ClickHouse 服务迁移记录

    旧的 ClickHouse 服务部署在 AWS EKS 集群中,与其他服务共享资源,现迁移到独立的 EC2 机器上,独享资源。考虑成本,新的机器使用 arm 处理器。

    使用到的工具是 clickhouse-backup

    备份原服务数据

    使用 clickhouse-backup 备份原服务数据到 S3,备份 example_schema schema 下的所有表到 S3 的命令如下:

    ./clickhouse-backup create_remote -c clickhouse-backup-config.yml -t [example_schema].*

    此操作会把 example_schema 下的表结构以及数据备份到 S3 的目录,S3 的相关配置在 clickhouse-backup-config.yml 里面。

    备份后会在 S3 生成以备份时间命名的文件夹:

    这个文件夹的名字作为备份的名字会在恢复数据的时候使用。

    在新服务上恢复数据

    使用原服务同样的 clickhouse-backup-config.yml 配置,把数据库相关配置换成新服务的:

    clickhouse:
      username: username
      password: "password"
      host: localhost
      port: 9000
      disk_mapping: {}
      skip_tables:
      - system.*
      timeout: 5m
      freeze_by_part: false
      secure: false
      skip_verify: false
      sync_replicated_tables: true
      skip_sync_replica_timeouts: true
      log_sql_queries: false

    之后,执行恢复数据的命令:

    ./clickhouse-backup restore_remote -c clickhouse-backup-config.yml 2023-03-24T01-46-40

    等待命令执行完毕,数据即可恢复成功。

    Clickhouse 安装

    使用 install.sh 安装脚本,代码如下,LATEST_VERSION 写死想要安装的版本,否则会根据服务器信息安装最新的版本。install.sh 脚本代码如下:

    LATEST_VERSION=22.3.6.5-arm64
    export LATEST_VERSION
    
    case $(uname -m) in
      x86_64) ARCH=amd64 ;;
      aarch64) ARCH=arm64 ;;
      *) echo "Unknown architecture $(uname -m)"; exit 1 ;;
    esac
    
    for PKG in clickhouse-common-static clickhouse-common-static-dbg clickhouse-server clickhouse-client clickhouse-keeper
    do
      curl -fO "https://packages.clickhouse.com/tgz/stable/$PKG-$LATEST_VERSION-${ARCH}.tgz" \
        || curl -fO "https://packages.clickhouse.com/tgz/stable/$PKG-$LATEST_VERSION.tgz"
    done
    
    tar -xzvf "clickhouse-common-static-$LATEST_VERSION-${ARCH}.tgz" \
      || tar -xzvf "clickhouse-common-static-$LATEST_VERSION.tgz"
    sudo "clickhouse-common-static-$LATEST_VERSION/install/doinst.sh"
    
    tar -xzvf "clickhouse-common-static-dbg-$LATEST_VERSION-${ARCH}.tgz" \
      || tar -xzvf "clickhouse-common-static-dbg-$LATEST_VERSION.tgz"
    sudo "clickhouse-common-static-dbg-$LATEST_VERSION/install/doinst.sh"
    
    tar -xzvf "clickhouse-server-$LATEST_VERSION-${ARCH}.tgz" \
      || tar -xzvf "clickhouse-server-$LATEST_VERSION.tgz"
    sudo "clickhouse-server-$LATEST_VERSION/install/doinst.sh" configure
    sudo /etc/init.d/clickhouse-server start
    
    tar -xzvf "clickhouse-client-$LATEST_VERSION-${ARCH}.tgz" \
      || tar -xzvf "clickhouse-client-$LATEST_VERSION.tgz"
    sudo "clickhouse-client-$LATEST_VERSION/install/doinst.sh"
  • 在 ubuntu 服务器上搭建 Gitlab 服务

    在 ubuntu 服务器上搭建 Gitlab 服务

    使用 omnibus 方式安装 gitlab 官方的 gitlab 服务,存在病毒,导致 CPU 跑满,改用 docker 方式安装。

    参考文档

    安装 docker: Install Docker Engine on Ubuntu

    安装 gitlab-jh: 极狐GitLab Docker 镜像

    安装过程

    1. 使用 Docker Engine 安装极狐GitLab:

    export GITLAB_HOME=/srv/gitlab
    
    docker run --detach \
      --hostname mygitlab.app \
      --publish 443:443 --publish 80:80 --publish 24:22 \
      --name gitlab \
      --restart always \
      --volume $GITLAB_HOME/config:/etc/gitlab \
      --volume $GITLAB_HOME/logs:/var/log/gitlab \
      --volume $GITLAB_HOME/data:/var/opt/gitlab \
      --shm-size 256m \
      registry.gitlab.cn/omnibus/gitlab-jh:latest

    以上代码执行,初始化 gitlab-jh,耗时较长。

    2. 安装 gitlab-runner: Run GitLab Runner in a container

    docker run -d --name gitlab-runner --restart always \
      -v /srv/gitlab-runner/config:/etc/gitlab-runner \
      -v /var/run/docker.sock:/var/run/docker.sock 
      gitlab/gitlab-runner:latest -m 

    3. 注册 docker runner,执行过程中会有交互式问答,记录如下:

    docker run --rm -it -v /srv/gitlab-runner/config:/etc/gitlab-runner gitlab/gitlab-runner register
    
    http://mygitlab.app/
    
    Runner token:xxxxxxxxxxxx_xxx
    
    alpine:lastest
    
    alpine:lastest
    
    docker
    
    alpine:lastest
    
    Configuration (with the authentication token) was saved in "/etc/gitlab-runner/config.toml"

    4. 修改 docker runner 的配置,添加卷:Advanced configuration

    nano /srv/gitlab-runner/config/config.toml
    
    volumes = ["/home/www/mygitlab.app:/build/mygitlab.app:rw"]

    其他记录

    重启服务,查看日志相关命令:

    docker restart gitlab-runner
    
    docker logs gitlab-runner -f

    进入 Docker 容器执行命令:

    docker exec -it xxxxxxxxxxx sh

    其他参考文档

    六. GitLab-CI/CD-实战:前端Vue项目

    极狐GitLab CI/CD如何在docker in docker 模式下将流水线的产物存储到宿主机上?

    在 Ubuntu 上开启 Swap

    dd if=/dev/zero of=/swapfile count=8096 bs=1M

    https://blog.csdn.net/qq_43557686/article/details/126028541

    https://blog.csdn.net/huyongfu2004/article/details/122710325

  • Amazon Sagemaker 常用方法

    Amazon Sagemaker 常用方法

    从 S3 下载文件:

    import boto3
    s3 = boto3.resource('s3')
    
    s3.meta.client.download_file('bucket', 'origin_object_key', 'local_path')

    往 S3 上传文件:

    s3.meta.client.upload_file('local_path', 'bucket', 'origin_object_key')

    python zip 解压

    import zipfile
    with zipfile.ZipFile(path_to_zip_file, 'r') as zip_ref:
        zip_ref.extractall(directory_to_extract_to)
  • Pandas DataFrame 常用操作

    Pandas DataFrame 常用操作

    Pandas 读取 Excel 或者 csv 文件:

    import pandas as pd
    
    pd.read_excel(r'filepath', sheet_name='sheet1')
    pd.read_csv(r'filepath')

    DataFrame 拼接:

    df1.append(df2)

    DataFrame 筛选:

    df.loc[df['A'] == 1],多条件 df.loc[(df['A'] == 1) & (df['B'] == 2)]

    DataFrame 分组:

    df.groupby(by=['A','B','C'])

    DataFrame 删除列:

    df.drop(labels=['A', 'B'], axis=1)

    DataFrame 去重:

    df.drop_duplicates(subset=['A','B','C','D'])

    从 DataFrame 的头部或者尾部截取数据输出:

    df.head()
    df.tail(3)

    不要在 for 循环中 append 数据,效率非常低

    Pandas 的数据不能直接修改,添加属性需要复制一份:

    import copy
    
    new_frame_data = copy.copy(old_frame_data)
    new_frame_data.attr = value
  • 为 AWS Python Lambda 函数添加层,支持使用 pandas 库

    为 AWS Python Lambda 函数添加层,支持使用 pandas 库

    参考:

    1. 创建和共享 Lambda 层
    2. How to use pandas in AWS Lambda

    步骤1~4需要在 AWS 的 EC2 实例上进行,以便使用相同的依赖环境,这里使用 AWS 的 Sagemaker 进行。

    步骤1:

    找到需要添加层的 Lambda 函数的 Python 版本,在 AWS EC2 环境创建层时需要使用相同的版本,创建 AWS Lambda 函数时能看到,可选用的 Python Lambda 函数版本为 3.9,EC2 环境使用 Python 3.9.13 版本。

    conda create -n aws_lambda_env python==3.9.13conda activate aws_lambda_env

    在 Sagemaker 环境下,激活 conda 虚拟环境需要使用:

    source activate aws_lambda_env

    步骤2:

    创建一个文件夹

    mkdir python

    步骤3:

    安装需要添加的库到这个环境中

    pip install openpyxl pandas -t python

    步骤4:

    打包目录

    zip -r pandas.zip python

    步骤5:

    在 AWS 控制台创建层,然后上传打包好的层 pandas.zip

    在 AWS 控制台上传打包好的层

    步骤6:

    创建一个新的 Lambda 函数,选择可以添加层的运行时环境,这里选择的是 Python 3.9

    创建 Lambda 函数

    步骤7:

    为创建的 Lambda 函数添加层:

    添加一个 Layer

    选择刚刚创建的层

    选择刚刚创建的层

    最后写一段代码测试一下,是否能 import 成功新添加层的库。

    import logging
    
    logger = logging.getLogger()
    logger.setLevel(logging.INFO)
    
    def lambda_handler(event, context):
         logger.info(pd.__version__)
  • 雷区

    雷区

    华莱士(烟台泰山路德胜店)

    汉堡中的肉不熟,吃完闹肚子

    劳伦米格尔父子系列红酒

    喝了之后,吃啥东西都巨咸

    野格利口酒

    香料味较重,偏甜

  • 读《中美相遇:大国外交与晚清兴衰(1784-1911)(美国人为何选择贸易战?美国妖魔化中国的源头在哪里?解读今日中美关系。)》

    读《中美相遇:大国外交与晚清兴衰(1784-1911)(美国人为何选择贸易战?美国妖魔化中国的源头在哪里?解读今日中美关系。)》

    读完了。中美近几年摩擦不断,从新闻报道上,感到美国正在从各个方面不择手段地围堵中国,很想知道是为什么,这本书好像能找到答案。

    在读这本书之前,了解到的一些原因可能包括:

    1. 美国要维护自己世界第一的位置
    2. 美国不希望一个社会主义国家崛起
    3. 中国的发展,抢了美国的生意
    4. 担心中国强大后会发动战争,美国作为“世界警察”要维护和平
    5. ……

    来华

    自古(比哥伦布、麦哲伦还古的古)以来,西方都称东方为神秘的东方,想象中的东方是生机盎然、富丽堂皇的,那时候的中国也确实是生机盎然、富丽堂皇的。周边的国家以天朝为榜样,作天朝的附属国,来华朝贡,在朝廷的许可下做生意。这个时期的天朝自然以为自己是世界的中心,皇帝是天下人的皇帝。

    西方通过工业革命快速迈入近代化,航海事业的发展终于让大量的西方人得以目睹天朝的风范…… 然而看到的却是一个虽依然富饶美丽,但在科技、军事等领域已极大的落后于世界而不自知的古国面貌。巨龙深卧潭底太久,膘肥体胖,已经不能起舞。

    第二次来做客的西方人,带来了他们的坚船利炮,撬开了古国的大门。在这些西方国家中,美国相比于其他国家,与中国的往来,表现上要好很多。彼时的中国,感到了自己的落后,也希望能融入新的诞生于欧美的世界文明体系中,但同时也不想失去天朝的尊严。欧洲来的洋人,整体表现上充满了对中国的蔑视。美国来的洋人,行事风格较为温和,也乐意帮助中国走出去看外面的世界,整体而言是平等友善的,这或许也与来华主事的人有关系。

    其中最著名的一个人是蒲安臣,曾发表过《勿扰她》演讲。他向世界介绍了中国的历史成就,中国曾经是个伟大的国家,只不过近来落后了。他呼吁欧美国家不要打扰中国,中国有自己的发展节奏。

    这或许与欧美各国不同的对华政策有关。一方希望通过枪炮彻底摧毁中国,然后以欧美的方式重塑中国,另一方希望缓慢友好地以外交、贸易、宗教等手段把中国变成一个西方国家。

    慈禧

    后来,来华的所有西方列强都加入了瓜分中国的战争中。从书中了解到了慈禧的另一面,也对义和团有了新的认识。义和团打着“扶清灭洋”的旗号直接攻击了西方驻京使馆区,清廷也出兵助力,这直接引发了八国联军侵华战争。而在此之前,慈禧刚刚首次邀请驻京大使的夫人们到宫廷,宴请送礼,友好交谈,试图以“夫人外交”的方式缓和与西方列强的关系,可义和团攻击使馆区的行为让慈禧的努力化为乌有。《辛丑条约》后,慈禧又做了一系列的外交努力,这改变了我以往对慈禧“丑恶的老太婆”的形象认知。

    大概慈禧终结了“维新”运动错误太大,使后来的人们对她深恶痛绝吧。书中提到康有为维新变法,但是从始至终是坚定的“保皇派”,而梁启超就对保有皇帝没有感觉,原因是康有为被皇帝召见过,梁启超没有。所有“面圣”过的人,几乎都会臣服于皇帝。西方驻京使者的夫人在受到慈禧召见后,也对慈禧赞不绝口,甚至评价为一生中的高光时刻。可见“帝王之术“对人心理的巨大作用力,皇帝可称之为最高端的 PUA 玩家。

    朝鲜

    我的认知里,朝鲜是一个和中国一样地位的国家,历史上包括韩国在内的整个朝鲜半岛都是中国的附属国,现在对此有了更深的理解。附属国(下国)实际上的意义在于遭到侵袭时,宗主国(上国)是不是可以合法出兵保护。此外,下国需要向上国朝贡,在军事、外交、政策上受上国制约,在礼仪上要显示低一等的地位,但是下国有自己的领土主权,有自己的经济发展自主权等,在国际交往上形同于宗主国一样的主权国家。现在似乎只是没了朝贡一说,从这里看,现在的朝鲜与中国的关系也还是基本未变的,而日本、韩国的国际地位与朝鲜也没啥不同,上国不同而已。

    文明

    西方的文明和中国的文明存在着一些不同,中国的文明给了中国人很高的道德感,名誉甚至比命重要。中国向来说话算数,被人指责后,道德羞耻感很重。中国跟西方相比,“脸皮”很薄。而西方基本上是从利益出发的,利益面前,可以不要脸。

    读完此书,尤其感到美国这个国家,几乎所有的政策、行为都是从利益出发的,真的是非常“单纯”的。大概西方文明国家都是以此为行为准则的吧,其他所有国际规则、条约都无关紧要。甚至,只要拳头硬,谁家的东西他们只要想要,都可以去拿。谁文明谁野蛮,可想而知。

    用书中一句话作为结束语:

    中国这个老大帝国,在周围地域乃至全球范围内,其实都是没有朋友的。

    《中美相遇》
  • 尝试一下生酮饮食

    尝试一下生酮饮食

    大概只坚持了1天完全无碳水的生酮饮食方式就放弃了。

    中午不吃碳水,餐后马上就有不舒服的感觉,和突然饥饿来袭的感觉一样。大概是身体习惯了餐后造糖,这次发现碳水没有,马上采取紧急措施,转而生酮来提供能量。

    实际上,在彻底生酮饮食之前,已经减少了很多碳水食物,早晨大概20克面包+牛奶,中午大概20克的米饭+肉类、蔬菜,晚上随机。饥饿感来袭的时候,马上补充糖。这样的饮食方式并没有让体重增长,配合不定期的运动,体重是有所下降的。

    “生酮”这个词是最近在一个网上兴趣社区看到的,那里面说到“生酮饮食”可以带来减肥,提升健康指数等好处,然而也有很多声音说“生酮饮食”会让心脑血管疾病的发病率提高 30% 之多,而且在放弃“生酮饮食”之后,对碳水的渴望会很强烈,体重会很快涨回来。

    网上的观点真的很难判断。科学的解释,听起来都很“科学”,却不一定正确。我只好:嗯,听起来很有道理,就这样吧,与我没啥关系。。。

  • 在 AWS Sagemaker 上使用 Paddlehub 搭建 OCR 文字识别服务,识别身份证、银行卡、票据等

    在 AWS Sagemaker 上使用 Paddlehub 搭建 OCR 文字识别服务,识别身份证、银行卡、票据等

    Paddlehub 是百度飞浆推出的预训练模型管理工具,Paddlehub 提供对预训练模型的安装、卸载、升级、部署等功能。

    Sagemaker 是 AWS 推出的机器学习工具平台,集成了 Jupyter Notebook,通过 Sagemaker WEB 工具或者 SDK 可快速完成机器学习相关的模型训练、部署等过程。

    在 Sagemaker 上面部署自己的机器学习模型分为以下几个步骤:

    1. 将服务封装成成符合 Sagemaker 要求的镜像托管到 AWS ECR 容器仓库;
    2. 在 Sagemaker 上将镜像制作成 Sagemaker 定义的模型;
    3. 创建终端节点配置,部署终端节点。

    其中,第一步是比较繁琐的,要按照 Sagemaker 平台的要求来合理规划代码及数据在 Docker 镜像中的路径。2、3步都可以通过 Sagemaker 的 WEB 界面完成。

    将服务封装成成符合 Sagemaker 要求的镜像托管到 AWS ECR 容器仓库

    Sagemaker 约定了推理模型的容器必须实施在端口 8080 上响应 /invocations 和 /ping 的 Web 服务器。也就是说推理模型必须部署一个端口为 8080 的 Web 服务,这个服务需要有两个 API:一个是 http://localhost:8080/invocations 用来接收数据,返回推理结果;一个是 http://localhost:8080/ping 用来响应健康检查。

    Paddlehub 提供了启动推理服务的快速命令:

    hub serving start -m chinese_ocr_db_crnn_mobile -p 8866

    其中,-p 参数用来指定端口,这里保持使用 8866 端口号。计划在镜像里面加一个 Nginx 的 server 配置,用来响应 8080 端口上 path 为/invocations 的推理请求,将请求转发到 Paddlehub 服务 的 8866 端口上,并添加另外一个 server 配置,响应 8080 端口上 path 为 /ping 的请求,来通过 Sagemaker 的健康检查。

    网络拓扑图

    基础镜像基于 ubuntu docker 基础镜像制作。

    docker run -it ubuntu /bin/bash
    apt-get update

    安装 nginx 并配置

    apt-get install nginx

    将准备好的 Nginx 配置文件上传到 docker 镜像中:

    docker cp /home/ec2-user/SageMaker/ocr/ocr.conf [启动的容器ID]:/etc/nginx/conf.d/ocr.conf

    Nginx 配置参考:

    server {
        listen 8080;
        server_name localhost;
    
        proxy_set_header X-Real_IP $remote_addr;
        proxy_set_header Host $host;
        proxy_set_header X_Forward_For $proxy_add_x_forwarded_for;
        proxy_http_version 1.1;
        proxy_set_header Upgrade $http_upgrade;
        proxy_set_header Connection 'upgrade';
    
        location /ping {
          add_header Access-Control-Allow-Origin * always;
          add_header Access-Control-Allow-Headers X-Requested-With;
          add_header Access-Control-Allow-Methods PUT,POST,GET,DELETE,OPTIONS;
          
          return 200 "OK";
        }
    
        location /invocations {
          add_header Access-Control-Allow-Origin * always;
          add_header Access-Control-Allow-Headers X-Requested-With;
          add_header Access-Control-Allow-Methods PUT,POST,GET,DELETE,OPTIONS;
          
          proxy_pass http://127.0.0.1:8866/predict/chinese_ocr_db_crnn_server;
        }
    }
    

    安装 python 3.6,移除默认的 python 3.8

    ubuntu 镜像中可能存在 python3.8 版本, 在我安装的时候,Paddlehub 在 python3.8 下运行会出现问题。

    apt-get install software-properties-common
    add-apt-repository ppa:deadsnakes/ppa
    apt-get update
    apt-get install python3.6
    apt-get purge remove python3.8
    echo alias python=python3 >> ~/.bashrc
    echo alias python3=python3.6 >> ~/.bashrc
    source ~/.bashrc

    安装 PaddlePaddle、PaddleHub

    apt-get install python3-pip
    echo alias pip=pip3>> ~/.bashrc
    source ~/.bashrc
    
    pip install paddlepaddle-gpu==2.0.0rc
    pip install paddlehub==2.0.0b

    安装 OCR 文字识别模型

    apt-get install git libgl1-mesa-glx
    pip install sentencepiece  shapely pyclipper
    hub install chinese_ocr_db_crnn_mobile==1.1.1

    将准备好的启动脚本上传到正在编辑的容器中

    这里有两个,一个是供 CPU 实例类型用的,一个是供 GPU 实例类型用的。

    docker cp /home/ec2-user/SageMaker/ocr/run-gpu.sh [启动的容器ID]:/root/run.sh # 或者
    docker cp /home/ec2-user/SageMaker/ocr/run.sh [启动的容器ID]:/root/run.sh

    run 脚本参考:

    #!/bin/bash
    
    # nginx
    /usr/sbin/nginx > /var/log/nginx.log 2>&1 &
    
    # ocr service
    hub serving start -m chinese_ocr_db_crnn_server --use_gpu > /var/log/chinese_ocr_db_crnn_server.log 2>&1 & # For gpu
    # hub serving start -m chinese_ocr_db_crnn_server > /var/log/chinese_ocr_db_crnn_server.log 2>&1 & # For cpu
    
    
    # just keep this script running
    while [[ true ]]; do
        sleep 1
    done

    打包上传基础镜像到 AWS ECR

    docker commit -m "[note]" -a "19050023" [启动的容器ID] [镜像名称]:[base-version]
    docker tag [镜像名称]:[base-version] [AWS ECR 地址].amazonaws.com.cn/[镜像名称]:[base-version]
    docker push [AWS ECR 地址].amazonaws.com.cn/[镜像名称]:[base-version]

    Dockerfile 配置参考:

    # FROM [镜像名称]:v1
    FROM [镜像名称]:v1-gpu
    
    # COPY run.sh /root/run.sh # For cpu
    COPY run-gpu.sh /root/run.sh # For gpu
    
    RUN chmod +x /root/run.sh
    
    ENTRYPOINT ["/root/run.sh"]
    
    EXPOSE 8080

    在 Sagemaker 上将镜像制作成 Sagemaker 定义的模型

    创建模型

    选择“创建模型”,进入创建模型的配置页面

    配置容器

    推理代码图像位置一栏填上面步骤中上传的推理镜像的 ECR 地址,模型构件指预训练模型等,可以上传到 s3 存储,SageMaker 运行的时候会拉去模型数据,解压到指定的目录中,这里不需要。完成配置,点“创建模型”即可。

    创建终端节点,部署终端节点

    在 SageMaker 终端节点模块选择创建终端节点

    创建新的终端节点配置,添加模型,并调整实例类型

    点击 创建终端节点配置 即创建好了配置文件。

    最后,点击页面底部的“创建终端节点”,服务就部署好了。

  • “整数反转”问题的 Javascript 解答

    “整数反转”问题的 Javascript 解答

    题目

    给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

    如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ,就返回 0。

    假设环境不允许存储 64 位整数(有符号或无符号)。
     

    示例 1:

    输入:x = 123
    输出:321


    示例 2:

    输入:x = -123
    输出:-321


    示例 3:

    输入:x = 120
    输出:21


    示例 4:

    输入:x = 0
    输出:0

    提示:

    -231 <= x <= 231 - 1

    分析

    将数当作字符串,反向遍历就能解决问题了,需要注意两个点:

    1. 负数的处理;
    2. 超出 32 位数范围,直接返回 0。

    解答

    /**
     * @param {number} x
     * @return {number}
     */
    var reverse = function (x) {
      var isNegativeNumber = false;
      if (x < 0) {
        isNegativeNumber = true;
      }
      var xStr = x.toString();
      var reverseXArr = [];
    
      for (var i = xStr.length - 1; i >= 0; i--) {
        reverseXArr.push(xStr[i]);
      }
    
      var result = parseInt(reverseXArr.join(""), 10);
    
      if (isNegativeNumber) {
        result = 0 - result;
      }
    
      if (result < -Math.pow(2, 31) || result > Math.pow(2, 31) - 1) {
        result = 0;
      }
    
      return result;
    };

    题目来源:力扣(LeetCode)

    链接:https://leetcode-cn.com/problems/reverse-integer

  • “Z 字形变换”问题的 Javascript 解答

    “Z 字形变换”问题的 Javascript 解答

    题目:

    将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。

    比如输入字符串为 “PAYPALISHIRING” 行数为 3 时,排列如下:

    P   A   H   N
    A P L S I I G
    Y   I   R
    之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"。
    请你实现这个将字符串进行指定行数变换的函数:
    
    string convert(string s, int numRows);

    示例 1:

    输入:s = "PAYPALISHIRING", numRows = 3
    输出:"PAHNAPLSIIGYIR"

    示例 2:

    输入:s = "PAYPALISHIRING", numRows = 4
    输出:"PINALSIGYAHRPI"
    解释:
    P     I    N
    A   L S  I G
    Y A   H R
    P     I

    示例3:

    输入:s = "A", numRows = 1
    输出:"A"

    思考:

    先找规律看看

    0123456
    0P[1]A[5]H[9]N[13]
    1A[2]P[4]L[6]S[8]I[10]I[12]G[14]
    2Y[3]I[7]R[11]
    示例1,numRows = 3
    0123456
    0P[0]I[6]N[12]
    1A[1]L[5]S[7]I[11]G[13]
    2Y[2]A[4]H[8]R[10]
    3P[3]I[9]
    示例2,numRows = 4

    设字符的下标为 n

    梯度(t) = numRows + (numRows -2),以示例2为例,梯度为 4 + (4 – 2) = 6

    计算列数(x) :

    nt = Math.floor(n / t) 得到字符 n 在第 nt 个梯度内(从 0 开始计数),每个梯度包含 tx 列,tx = numRows – 1

    n % t 将所有字符放在第一个梯度内考虑,有两种情况 :

    n % t < numRows 时,x 等于 0 + s[n] 所在的梯度乘以梯的长度,即: x = 0 + nt x tx,整理后是 x = nt x tx

    n % t >= numRows 时,也就是 s[n] 是在 “Z“ 字的折线位置的,放到第一个梯度里面看,x 应该就是 n % numRows 的值,属于其他梯度内的数,加上梯度即可,考虑到下标是从 0 开始的,所以 x = (((n % t) + 1) % numRows) + nt x tx;

    计算行数(y)

    行数的计算和列数的计算思路一样,把所有字符放到第一个梯度内考虑,而且不需要再加上梯度了。同样分两种情况:

    n % t < numRows 时,n % t 将 s[n] 放到第一个梯度内考虑,行数 y = n % numRows ,考虑梯度,最终结果为:y = n % t % numRows。

    n % t >= numRows 时,也就是计算 “Z” 字折线上的数字。n % t 将 s[n] 放到第一个梯度内考虑,观察 s[n] 的下标与行数的关系,可以得到 s[n] 不可能出现在第一行和最后一行,第一个梯度内,n + 1 – numRows 可得到 s[n] 到表格底部的距离,numRows – 1 再减去这个距离,就得到行数 y 了,因此结果为:y = numRows – 1 – ((n % t) + 1 – numRows)。

    还有一种情况是 numRows === 1 的时候,实际上把原字符串直接输出就是了。

    解答

    /**
     * @param {string} s
     * @param {number} numRows
     * @return {string}
     */
    var convert = function (s, numRows) {
      var matrix = [];
    
      for (var y = 0; y < numRows; y++) {
        // 构建行
        matrix[y] = [];
      }
    
      // 梯度
      var t = numRows + numRows - 2;
    
      for (var n = 0; n < s.length; n++) {
        // 测试列的判断逻辑是否正确
    
        // 初始化列位置
        var x = 0;
    
        // 初始化行位置
        var y = 0;
    
        // 得到元素在哪个梯度内
        var nt = Math.floor(n / t);
    
        // 每个梯度占据的列数
        var tx = numRows - 1;
    
        if (n % t < numRows) {
          x = 0 + nt * tx;
          y = (n % t) % numRows;
        } else {
          x = (((n % t) + 1) % numRows) + nt * tx;
          y = numRows - 1 - ((n % t) + 1 - numRows);
        }
    
        matrix[y][x] = s[n];
      }
    
      var result = "";
    
      matrix.forEach(function (element) {
        element.forEach(function (item) {
          if (item) result = result.padEnd(result.length + 1, item);
        });
      });
    
      return result;
    };
    

    题目来源:力扣(LeetCode)

    链接:https://leetcode-cn.com/problems/zigzag-conversion/