By

统计一个二进制数里面1的个数

原题

This is not the fastest but maybe the most interesting way to count
how many bits are 1 in a binary number.

1
2
3
输入：3
输出：2
解释：3的二进制是101， 里面有2个1

解法

这个文章里面的算法不太通用，主要用了2个特性：

  1. 整数的除法，会向下取整。 比如 7/2结果是3
  2. x/2 + x/4 + x/8… == x

向右移位，刚好等于除以2. 满足上面第二个特性.
x - (x/2 + x/4 + x/8..) 在float情况下，应该刚好等于0，
但是在整型的情况下，就等于被向下取整的1的总和，也就是1的个数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main

import (
	"fmt"
)

func countbit(num int) int {
	temp := num
	sum := 0
	for temp > 0 {
		temp = temp >> 1
		sum += temp
	}
	return num - sum
}

func main() {
	fmt.Println(countbit(11))
}

普通解法

将数据的最后一位求和

总结

原作者给了如下解释。我觉得这个题比较巧，不太通用，意义不是特别大

The interesting thing about this algorithm is that we calculate
something that we can’t calculate directly, by calculating everything
except for that, and then looking at the difference.

By

第一题

很早之前就知道Leetcode的第一题叫two-sum

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

我的解法

两层for循环, 时间复杂度是O(n2)

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
package main

import "fmt"

func twoSum(arr []int, target int) []int {

	for i := 0; i < len(arr); i++ {
		temp := arr[i]
		if temp >= target {
			continue
		}
		another := target - temp

		for j := len(arr) - 1; j > i; j-- {
			if arr[j] == another {
				return []int{i, j}
			}
		}
	}
	return []int{}
}

func main() {
	s := []int{2, 7, 11, 15}
	ans := twoSum(s, 9)
	fmt.Println(ans)
}

别人的思路

构造一个HashMap，通过O(n)的时间复杂度即可找到结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func twoSum(arr []int, target int) []int {
	var table = make(map[int]int)
	for k, v := range arr {
	    if v >= target {
	        continue
	   	}
	    table[v] = k
	    another := target - v
	    if table[another] > 0 {
	        return []int{table[another], k}
	    }
	}
	return []int{}
}
思考

开始只考虑从左到右先找到第一个值，然后遍历找到另一个值，思维比较固化

这种一边构造hashmap一边找another的方法, 先找到的是another，然后再hashmap里找另一个。

By

问题: 输入一个数N，打印出1到N的全排列
比如输入数字是 3

1
2
3
4
5
6
123
132
213
231
312
321

思路

想象成老虎机上的N个格子，每个格子都是在进行1-N的循环，并且不能重复。

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
package main

import "fmt"

var (
	num    int
	bucket []int // 格子
	flag   []int // 用来记录1-N的数字是否已经使用，防止重复出现
)

func fill_bucket(n int) {
	if n > num { //当所有格子都填满，打印一次
		pretty_print(bucket)
		return
	}

	for i := 1; i <= num; i++ {
		if flag[i] == 1 {
			continue
		}
		bucket[n] = i
		flag[i] = 1
		fill_bucket(n + 1)
		flag[i] = 0
	}
}

func pretty_print(bucket []int) {
	for _, s := range bucket {
		if s != 0 {
			fmt.Print(s)
		}
	}
	fmt.Println()
}

func main() {
	fmt.Println("please input a number")
	fmt.Scanf("%d", &num)
	bucket = make([]int, num+1) // 用不到第0个元素
	flag = make([]int, num+1)   // 用不到第0个元素
	fill_bucket(1)              // 从左到右遍历
}

By

fibonacci数列: 1 1 2 3 5 8 13 21…

今天看到了fibonacci的非递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func fibonacci(n int) int {
	a, b := 0, 1
	for i := 2; i < n; i++ {
		a, b = b, a+b
	}
	return a + b
}

func fibonacci(n int) int {
	a, b := 0, 1
	for i := 2; i < n; i++ {
        // 有的编程语言不支持上面的那种a, b = b, a+b写法
        sum := a + b
        a = b
        b = sum
	}
	return a + b
}

递归写法

1
2
3
4
5
6
7
func fibonacci(n int) int {
    if n == 1 || n == 2 {
        return 1
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

By

介绍

早在2014年，Google就鼓励网站使用HTTPS协议，并优先考虑使用HTTPS的网站，从2017年开始，Google Chrome浏览器将非HTTPS的网站标记为不安全。
Let’s Encrypt 面向公众提供免费的HTTPS证书, 这里记录Nginx 开启https的过程。

注意点

我最初用Docker运行Tengine，希望将证书申请下来后mount到Docker里，目标是没有问题，但是操作起来过于麻烦，而且没成功，浪费了很多时间。
后来改用服务器直接跑Nginx， 并使用最基础的nginx.conf，一切都变得非常容易。

尝试新事物的时候，最好是先“跑”起来，然后再研究更优的办法。

  1. 申请HTTPS证书的域名需要可以被公网访问
  2. 如果使用Nginx，需要支持ssl, 编译的时候添加--with-http_ssl_module

操作步骤

安装Certbot

服务器需要使用ACME协议从Let’s Encrypt获取证书，我们使用官方推荐的 Certbot ACME客户端。

1
2
yum -y install epel-release
yum -y install certbot-nginx

安装Nginx

我的服务器无法通过yum安装Nginx，只好自己编译一个。

下载Tengine(Nginx) 源码, 编译

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
./configure --prefix=/usr/local/nginx \
      --conf-path=/usr/local/nginx/conf/nginx.conf \
      --sbin-path=/usr/local/nginx/sbin/nginx \
      --pid-path=/var/run/nginx.pid \
      --lock-path=/var/run/lock/nginx.lock \
      --user=www \
      --group=www \
      --http-log-path=/var/log/nginx/access.log \
      --error-log-path=/var/log/nginx/error.log \
      --http-client-body-temp-path=/var/lib/nginx/client-body \
      --http-proxy-temp-path=/var/lib/nginx/proxy \
      --http-fastcgi-temp-path=/var/lib/nginx/fastcgi \
      --http-scgi-temp-path=/var/lib/nginx/scgi \
      --http-uwsgi-temp-path=/var/lib/nginx/uwsgi \
      --with-pcre-jit \
      --with-http_dav_module \
      --with-http_geoip_module \
      --with-http_gunzip_module \
      --with-http_gzip_static_module \
      --with-http_random_index_module \
      --with-http_realip_module \
      --with-http_stub_status_module \
      --with-http_secure_link_module \
      --with-http_ssl_module \
      --with-stream \
      --with-stream_ssl_module \
      --with-http_v2_module \
      --with-http_stub_status_module \
      --with-http_addition_module \
      --with-http_degradation_module \
      --with-http_flv_module \
      --with-http_mp4_module \
      --with-http_sub_module \
      --with-file-aio \
      --with-mail \
      --with-mail_ssl_module \
      --with-jemalloc

make && make install

# certbot会在PATH下找nginx，这里通过软连把nginx放到PATH下
ln -s /usr/local/nginx/sbin/nginx /usr/local/bin/nginx
ln -s /usr/local/nginx/conf /etc/nginx

增加www用户

1
useradd -s /sbin/nologin www

配置Nginx

在网上随便找了个nginx.conf, 通过最低下的include /etc/nginx/conf.d/*.conf; 加载个人的配置段。

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
user  www;
# This number should be, at maximum, the number of CPU cores on your system.
worker_processes auto;

error_log  /var/log/nginx/error.log error;
pid        /var/run/nginx.pid;


events {
    # The effective method, used on Linux 2.6+, optmized to serve many clients with each thread.
    use epoll;
    # Determines how many clients will be served by each worker process.
    worker_connections 4000;
    # Accept as many connections as possible, after nginx gets notification about a new connection.
    multi_accept on;
}


http {
    include       /etc/nginx/mime.types;
    default_type  application/octet-stream;

    # Allow the server to close the connection after a client stops responding.
    reset_timedout_connection on;
    client_header_timeout 15;
    # Send the client a "request timed out" if the body is not loaded by this time.
    client_body_timeout 10;
    # If the client stops reading data, free up the stale client connection after this much time.
    send_timeout 15;
    # Timeout for keep-alive connections. Server will close connections after this time.
    keepalive_timeout 30;
    # Number of requests a client can make over the keep-alive connection.
    keepalive_requests 30;

    log_format  main  '$remote_addr - $remote_user [$time_local] "$request" '
                      '$status $body_bytes_sent "$http_referer" '
                      '"$http_user_agent" "$http_x_forwarded_for"';


    client_body_buffer_size 128k;
    client_max_body_size 10m;
    proxy_read_timeout 180s;

    # Compression.
    gzip on;
    gzip_min_length 10240;
    gzip_proxied expired no-cache no-store private auth;
    gzip_types text/plain text/css text/xml text/javascript application/x-javascript application/xml;
    gzip_disable "msie6";

    # Sendfile copies data between one FD and other from within the kernel.
    sendfile on;
    # Don't buffer data-sends (disable Nagle algorithm).
    tcp_nodelay on;
    # Causes nginx to attempt to send its HTTP response head in one packet,  instead of using partial frames.
    tcp_nopush on;


    # Hide web server information
    server_tokens off;
    server_info off;
    server_tag off;

    # redirect server error pages to the static page
    error_page 404             /404.html;
    error_page 500 502 503 504 /50x.html;

    include /etc/nginx/conf.d/*.conf;
}

配置vhost

下面是我的vhost配置文件, 使用最基础的配置文件

cikii.com.conf

1
2
3
4
5
6
7
server {
    listen 80 default_server;
    listen [::]:80 default_server;
    server_name     cikii.com www.cikii.com;
    root /usr/local/nginx/html/;
}

jiu.cikii.com.conf

1
2
3
4
5
6
7
server {
    listen 80;
    listen [::]:80;
    server_name     jiu.cikii.com;
    root /usr/local/nginx/html/;
}

重启一次Nginx

申请证书

给3个域名同时申请证书, 3个证书会写在同一个pem文件里

1
certbot --nginx -d cikii.com -d www.cikii.com -d jiu.cikii.com

如果没有报错的话， 我们自己的vhost配置文件已经被certbot改成支持HTTPS的配置了。

最后, 记得在crontab里定时renew证书

1
0 12 * * * /usr/bin/certbot renew --quiet

参考文档

https://www.nginx.com/blog/using-free-ssltls-certificates-from-lets-encrypt-with-nginx/

By

公司的安全团队扫描到我的系统后台直接暴露在公网，有安全问题，需要加上Basic Auth鉴权。

前置要求

需要安装httpd-tools（Centos）, Debian系列需要安装apache2-utils

1
yum install -u httpd-tools

操作步骤

  1. 创建htpasswd文件
1
htpasswd -c /usr/local/nginx/conf/htpasswd admin
  1. 在nginx.conf里配置鉴权
1
2
3
4
5
6
7
8
9
10
server {
    ...
    auth_basic  "Administrator's Area";
    auth_basic_user_file /usr/local/nginx/conf/htpasswd;

    # 不需要开启鉴权的path设置成auth_basic off
    location /test/ {
        auth_basic off;
    }
}

参考文档

https://docs.nginx.com/nginx/admin-guide/security-controls/configuring-http-basic-authentication/

By

0.背景

私有化部署的Tengine需要开启HTTPS，挂载自签名的证书

1.生成证书

1
2
# --nodes 不需要密码加密
openssl req -x509 -nodes -days 36500 -newkey rsa:2048 -keyout tls.key -out tls.crt

生成证书的几个字段说明

1
2
3
4
5
6
7
Country Name (2 letter code) [AU]:US
State or Province Name (full name) [Some-State]:New York
Locality Name (eg, city) []:New York City
Organization Name (eg, company) [Internet Widgits Pty Ltd]:Bouncy Castles, Inc.
Organizational Unit Name (eg, section) []:Ministry of Water Slides
Common Name (e.g. server FQDN or YOUR name) []:server_IP_address
Email Address []:admin@your_domain.com

2.证书Base64编码

The values for all keys in the data field have to be base64-encoded strings. If the conversion to base64 string is not desirable, you can choose to specify the stringData field instead, which accepts arbitrary strings as values.

1
2
cat tls.crt | base64 | xargs -n 100 | sed 's/ //g'
cat tls.key | base64 | xargs -n 100 | sed 's/ //g'

3.创建Secret对象

1
2
3
4
5
6
7
8
9
apiVersion: v1
kind: Secret
metadata:
  name: tls-certs
  namespace: {{ .Release.Namespace }}
type: kubernetes.io/tls
data:
  tls.crt: "将第2步的crt字符串粘贴在这里"
  tls.key: "将第2步的key字符串粘贴在这里"

4.定义Volume

1
2
3
4
5
6
7
8
9
10
11
12
13
volumes:
- name: certs
  secret:
    secretName: tls-certs
    defaultMode: 420
- name: nginx-config
  configMap:
    name: tengine-config
    items:
    - key: nginx.conf
      path: nginx.conf
- name: logdir
  emptyDir: {}

5.定义volumeMount

1
2
3
4
5
6
volumeMounts:
- mountPath: /etc/nginx/certs
  name: certs
- mountPath: /etc/nginx/nginx.conf
  name: nginx-config
  subPath: nginx.conf

6.参考文档

https://kubernetes.io/docs/concepts/configuration/secret/
https://blog.csdn.net/ljx1528/article/details/108491764
https://www.cnblogs.com/micro-chen/p/11794248.html
https://www.digitalocean.com/community/tutorials/how-to-create-a-self-signed-ssl-certificate-for-nginx-in-ubuntu-18-04

By

问题

如何判断一个数字是否是素数

思路

普通方法：从2..√n，如果n可以被整除， 那么n就不是素数

更高效方法:

We can improve this method further. Observe that all primes greater than 3 are of the form 6k ± 1, where k is any integer greater than 0. This is because all integers can be expressed as (6k + i), where i = −1, 0, 1, 2, 3, or 4. Note that 2 divides (6k + 0), (6k + 2), and (6k + 4) and 3 divides (6k + 3). So, a more efficient method is to test whether n is divisible by 2 or 3, then to check through all numbers of the form 6k +-1. This is 3 times faster than testing all numbers up to √n.

所有整数都可以用6k + i表示，其中i = -1, 0, 1, 2, 3, 4，其中6k + 0, 6k + 2, 6k + 4可以被2整除， 6k + 3 可以被3整除.
所以，素数一定是包含在 6k-1 或者 6k+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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool is_prime(int n) {

    if(n < 2) {
        printf("Input number must greater than 2 what we got is %d\n", n);
        exit(-1);
    }

    if(n == 2 || n == 3) {
        return true;
    }

    if(n%2 == 0 || n %3 == 0) {
        return false;
    }

    for (int i=5; i*i<n; i+=6) {
        if(n % i == 0 || n % (i+2) == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    int n;
    printf("please input a number: ");
    scanf("%d", &n);

    if (is_prime(n)) {
        printf("%d is prime number", n);
        return 0;
    } else {
        printf("%d is not prime number", n);
        return 1;
    }
}

参考链接

https://alexanderell.is/posts/rpc-from-scratch/
https://en.wikipedia.org/wiki/Primality_test

By

问题

写了一个通过Webrtc加入视频会议的html页面，使用iPhone手机打开，发现摄像头采集的视频画面旋转了90度, 在视频会议里面人是横向的..
PC和Android都没有这个问题

iPhone -> Janus -> OWT

原因分析

  1. 手机采集的视频就不是正向的
  2. OWT服务端渲染时对视频进行了转向

我这里手机采集到的是正向的，所以是服务端对视频进行了旋转.
在SDP协商里，通过a=extmap:13 urn:3gpp:video-orientation 控制视频旋转角度

注意：每个人遇到的extmap:后面的数字可能不一样

解决办法

判断是iPhone手机，就去掉SDP里面的CVO(Coordination of Video Orientation)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function iOS() {
 return [
    'iPhone Simulator',
    'iPhone'
 ].includes(navigator.platform)
}

function createdOffer(description) {
  if(iOS()) {
    var oldsdp = description["sdp"];
    var pattern=/a=extmap:13 urn:3gpp:video-orientation\r\n/gi;
    var newsdp = oldsdp.replace(pattern,"");
    description["sdp"]=newsdp;
  }

这个办法不是很好，会在真的有旋转画面需求的时候无法使用，在服务器合流的时候判断是否需要旋转应该更好一些。

参考文档

https://blog.csdn.net/epubcn/article/details/101451547
https://docs.flashphoner.com/display/WCS52EN/WebRTC+stream+picture+rotation
https://stackoverflow.com/questions/9038625/detect-if-device-is-ios

By

背景

需要使用Easy Connect链接到某单位的VPN，公司电脑不允许安装VPN客户端，因此考虑在阿里云Ubuntu Server上安装VNC，本地Mac通过VNC链接到Ubuntu

安装步骤

我这里直接使用root账号进行的操作，普通账号命令前面加上sudo

安装桌面环境

1
2
3
4
5
apt update
apt install xfce4 xfce4-goodies

# xdm 可能不需要安装
apt install xdm

安装tightvncserver

1
2
3
apt install tightvncserver
# xrdp 也是一个远程桌面服务，支持usb，音频
apt install xrdp

启动vncserver

1
vncserver

此时会提示设置密码, 设置一个自己熟悉的密码，如果需要更改密码，可以使用vncpasswd命令

配置vnc

需要配置VNC链接到哪个桌面环境
首先停掉当前的VNC实例

1
vncserver -kill :1

备份原始配置

1
mv ~/.vnc/xstartup ~/.vnc/xstartup.bak

编辑配置如下

1
2
3
4
5
# cat ~/.vnc/xstartup
#!/bin/sh
unset SESSION_MANAGER
unset DBUS_SESSION_BUS_ADDRESS
startxfce4 &

如果没有unset那两个变量，通过VNC链接到Ubuntu是灰屏

设置vnc安全链接

vnc默认没有使用加密通讯，需要使用SSH tunnel来建立安全链接

在你的Mac本地执行如下命令, Windows用户见“参考链接”里面的putty配置

1
2
# 这条命令需要一直运行
ssh -L 59000:localhost:5901 -C -N -l root 47.199.13.30

-L: 参数代表将我本地Mac的59000端口转发到目标机器(47.199.13.30)的IP：port上. 可以理解登录到目标机器以后，在目标机器上执行 localhost:5901
-C: 参数代表启用压缩传输
-N: 代表ssh只做端口转发，不会执行命令
-l: 代表login user

链接VNC

在Mac上打开Finder，点击Go，选择Connect to Server
链接到本机的59000端口

1
vnc://localhost:59000

问题

  1. VNC安装成功以后，EasyConnect还是没有搞定，可能与xfce桌面环境有关系，建议使用Gnome
  2. Ubuntu默认的浏览器无法使用，提供input/output error
    1
    2
    3
    4
    wget https://dl.google.com/linux/direct/google-chrome-stable_current_amd64.deb
    apt install ./google-chrome-stable_current_amd64.deb

    # 在设置里，找到Preferred Applications  -> Web Browser -> Other... 输入/usr/bin/google-chrome
  3. 浏览器显示中文乱码
    安装中文字库
    1
    2
    apt-get install ttf-wqy-zenhei
    apt-get install language-pack-zh-hans

参考链接

https://www.digitalocean.com/community/tutorials/how-to-install-and-configure-vnc-on-ubuntu-20-04
https://cat.pdx.edu/platforms/mac/remote-access/vnc-to-linux/
https://help.ubuntu.com/community/VNC/Servers