Posted on

问题描述

有 n 个字符串，每个字符串都是由 A-J 的大写字符构成。现在你将每个字符映射为一个 0-9 的数字，不同字符映射为不同的数字。这样每个字符串就可以看做一个整数，唯一的要求是这些整数必须是正整数且它们的字符串不能有前导零。现在问你怎样映射字符才能使得这些字符串表示的整数之和最大？

输入描述

每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n ， 接下来有 n 行，每行一个长度不超过 12 且仅包含大写字母 A-J 的字符串。 n 不大于 50，且至少存在一个字符不是任何字符串的首字母。

输出描述

输出一个数，表示最大和是多少

示例 1

输入

1
2
3
2
ABC
BCA

输出

1
1875

解题思路

我们可以通过计算权值，把权值最高的映射成9，次之映射成8，以此类推。

Read more »

Posted on | In

学习B-树

B-树（balance-tree）

B-树的定义

一颗 m 阶的 B-树， 或为空树， 或为满足下列特性的 m 叉树：

  1. 树中每个节点至多有 m 颗子树
  2. 若根节点不是叶子节点，则至少有两颗子树
  3. 除根之外的所有非终端节点至少有⌈m/2⌉颗子树，则至少有$\lceil m/2\rceil-1$个关键字（$\lceil m/2\rceil$ 为向上取整）
  4. 所有子节点都出现在同一层次上，并且不带消息，通常称为失败结点。
  5. 所有非终端节点最多有 m-1 个关键字

关键字个数n必须满足：$\lceil m/2\rceil-1 \le n \le m-1$

balance-tree

一棵含有N个总关键字数的m阶的B树的最大高度是多少?

设 m 阶B-树的高度为h+1。（+1表示最后一层叶子结点）
根据B-树的定义， 第一层至少有一个结点；第二层有2个结点，第三层有$2\times\lceil m/2\rceil$个结点，第四层有$2\times\lceil m/2\rceil^2$个结点，以此类推，第 h+1 层有$2\times\lceil m/2\rceil ^{h-1}$个结点
若 m 阶 B-树中具有 N 个关键字，则叶子结点既查找不成功的结点为 N+1.（如上图，失败结点有$3\times7+2=23$个，注意两个灰色结点）

$$N+1\ge 2 \times \lceil m/2\rceil ^{h-1}$$
$$h \le log_{\lceil m/2\rceil}(\frac{N+1}{2})+1$$

Posted on | In

使用ssh登录到远程服务器，切换到root账号。

关闭swap

1
swapoff -a

修改 /etc/fstab

1
2
3
4
5
6
7
8
9
10
11
12
# /etc/fstab: static file system information.
#
# Use 'blkid' to print the universally unique identifier for a
# device; this may be used with UUID= as a more robust way to name devices
# that works even if disks are added and removed. See fstab(5).
#
# <file system> <mount point>   <type>  <options>       <dump>  <pass>
/dev/mapper/cst--01--vg-root /               ext4    errors=remount-ro 0       1
# /boot was on /dev/cciss/c0d0p1 during installation
UUID=331095c3-4a02-450c-ad2b-176f2013b4d2 /boot           ext2    defaults        0       2
#/dev/mapper/cst--01--vg-swap_1 none            swap    sw              0       0
#/dev/mapper/cryptswap1 none swap sw 0 0

文件最后一行注释掉。

下载二进制文件

最新release版本
image.png

Read more »

Posted on | In

string

通过 reflect 包我们可以知道 string 的内部结构

1
2
3
4
type StringHeader struct {
	Data uintptr
	Len  int
}

Data 是指向底层数组的指针。
Len 是字符串的长度。
字符串是不可变的。

对一个字符串进行切割操作是不会发生底层数组拷贝，衍生字符串只是一个字符串的子串。（使用黑科技例外）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
s := "1,2,3,4"
ss := strings.Split(s,",")
for i,_ := range ss{
	t := (*reflect.StringHeader)(unsafe.Pointer(&ss[i]))
	fmt.Println(t.Data,ss[i])
}
sss := s[:3]
fmt.Println((*reflect.StringHeader)(unsafe.Pointer(&sss)))
fmt.Println((*reflect.StringHeader)(unsafe.Pointer(&s)))
//4952506 1
//4952508 2
//4952510 3
//4952512 4
//&{4952506 3}
//&{4952506 7}

slice

1
2
3
4
5
type SliceHeader struct {
	Data uintptr
	Len  int
	Cap  int
}

Data 是指向底层数组的指针。
Len 是slice的长度。
Cap 是slice的容量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func main() {

	sl := make([]int,0,10)
	sl = append(sl,1,2,3)
	sl2 := sl[:2]
	fmt.Println((*reflect.SliceHeader)(unsafe.Pointer(&sl)).Data)  //842350584048
	fmt.Println((*reflect.SliceHeader)(unsafe.Pointer(&sl2)).Data) //842350584048
	test(sl)
	a := (*reflect.SliceHeader)(unsafe.Pointer(&sl))
	fmt.Println(a) //&{842350584048 3 10}
	fmt.Println(sl) //[2 2 3]
	a.Len = 4
	fmt.Println(a) //&{842350584048 4 10}
	fmt.Println(sl) //[2 2 3 1]
}

func test(a []int){
	fmt.Println((*reflect.SliceHeader)(unsafe.Pointer(&a))) //&{842350584048 3 10}
	a[0] = 2
	a = append(a,1)
	fmt.Println((*reflect.SliceHeader)(unsafe.Pointer(&a))) //&{842350584048 4 10}
}

可以看出 slice 进行切割时，得出新的 slice 也是共享底层数据的。
以前看过一些文章说 slice 传参传的是引用，我认为不正确。其实也是值传递，传递时对 slice 结构体进行了拷贝。
从代码中可以看出，传 slice 参数进去后对 slice 进行了修改可能没有“影响”到原有 slice。
a[0] = 2和 a = append(a,1) 同时修改了底层数据，但是后者修改了结构体中的Len字段的值，而这个值只是一个拷贝值，对于原来的 slice 的 Len 没有进行修改。

我们要注意 slice 共享底层数据的特征。

官方栗子 译文

选取官方博客的一篇文章 “A possible “gotcha””

正如前面说到的，一个重新切片的切片并没有对底层数据进行拷贝。一个完整的数组会被保存在内存直到没有任何引用。有时候这会使得程序保存着所有数据在内存就算只用到其中的一小部分。

举个栗子，这 FindDigits 函数加载了整个文件到内存并且寻找第一个连续的数字，返回一个新的切片。

1
2
3
4
5
6
var digitRegexp = regexp.MustCompile("[0-9]+")

func FindDigits(filename string) []byte {
    b, _ := ioutil.ReadFile(filename)
    return digitRegexp.Find(b)
}

这段代码像预期那样运行，但是返回的[]byte 指向的数组保存在整个文件。因为这个切片引用了原始数组，只要这个切片保存引用那么垃圾回收机制就不会释放原始数组。使用了很少的字节但是保存了整个文件到内存。
为了解决这个问题，我们可以拷贝我们感兴趣的数据到一个新的 slice 再返回。

1
2
3
4
5
6
7
func CopyDigits(filename string) []byte {
    b, _ := ioutil.ReadFile(filename)
    b = digitRegexp.Find(b)
    c := make([]byte, len(b))
    copy(c, b)
    return c
}

一个更加简洁的方法可以使用 append，这留给读者作为练习。

这样？

1
2
3
4
5
6
7
func CopyDigits(filename string) []byte {
	var digitRegexp = regexp.MustCompile("[0-9]+")
	b, _ := ioutil.ReadFile(filename)
	b = digitRegexp.Find(b)
	c := append([]byte{},b...)
	return c
}

Posted on | In

问题描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

解题思路

找到二叉搜索树的根（遍历序列的最后一个元素），遍历序列的前一部分都比根小，后一部分都比根大。如果符合分别对前一部分和后一部分进行递归检验。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.size()==0)return false;
        return check(sequence,0,sequence.size());
    }
    bool check(vector<int> &sequence, int s, int e) {
        if (s >= e) return true;
        int i = e;
        while (i > s && sequence[i - 1] > sequence[e]) i--;
        for (int j = i - 1; j >= s; j--) if (sequence[j] > sequence[e]) return false;
        return check(sequence, s, i - 1) && check(sequence, i, e - 1);
    }
};

Posted on | In

在学习nsq源码时，再次重温一下 go 的 reflect 包。

variable of interface type 接口类型变量

A variable of interface type stores a pair: the concrete value assigned to the variable, and that value’s type descriptor.

接口类型变量存着两部分，具体的值和值类型描述符。

1
2
3
4
var t *int = nil
var i interface{}
i = t
fmt.Println(i == nil) //false

Anonymous

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// A StructField describes a single field in a struct.
type StructField struct {
	// Name is the field name.
	Name string
	// PkgPath is the package path that qualifies a lower case (unexported)
	// field name. It is empty for upper case (exported) field names.
	// See https://golang.org/ref/spec#Uniqueness_of_identifiers
	PkgPath string

	Type      Type      // field type
	Tag       StructTag // field tag string
	Offset    uintptr   // offset within struct, in bytes
	Index     []int     // index sequence for Type.FieldByIndex
	Anonymous bool      // is an embedded field
}

可以通过 field 的 Anonymous 判断该字段是否是内嵌字段

Elem vs Indirect

reflect.Value 是一个指针，那么 v.Elem() 和 reflect.Indirect(v) 等价的。
reflect.Value 不是指针，那么 reflect.Indirect(v) 返回自身。
reflect.Value 不是指针但是一个 interface 那么 v.Elem() 返回 interface 所包含的值
reflect.Value 不是指针也不是一个 interface 那么 v.Elem() 会发生panic。

reflect.ValueOf()

1
2
3
var x float64 = 3.4
v := reflect.ValueOf(x)
fmt.Println(v.CanSet()) //false 因为 v 是使用 x 的拷贝值创建的。
1
2
3
var x float64 = 3.4
v := reflect.ValueOf(&x)
fmt.Println(v.CanSet()) //flase 我们不需要修改指针本身，而是需要修改指针所指向的地方。
1
2
3
var x float64 = 3.4
v := reflect.ValueOf(&x).Elem()
fmt.Println(v.CanSet()) //true

反射是接口变量到反射对象
反射是反射对象到接口变量
要修改反射对象的值那么一定是要settable

Reference

https://blog.golang.org/laws-of-reflection

Posted on | In

在容器里面无法通过域名访问网络，但可以使用ip ping通。这可能是 dns 解析出现了问题。

1
2
3
4
nslookup security.debian.org
nslookup: can't resolve '(null)': Name does not resolve

nslookup: can't resolve 'security.debian.org': Try again

dns解析出现问题时可能与宿主机的 /etc/resolv.conf 文件相关。

关于container 的 /etc/resolv.conf 文件官方描述

docker dns 文档.png

container‘s /etc/resolv.conf 与 宿主机的 /etc/resolv.conf 相似，只是使用过滤器把 localhost 的地址进行过滤。

宿主主机是使用 ubuntu

ubuntu server

如果使用 ubuntu server 那么需要手动修改 /etc/network/interfaces

应该与下面相似

1
2
3
4
5
6
7
8
9
10
11
12
# This file describes the network interfaces available on your system
# and how to activate them. For more information, see interfaces(5).

source /etc/network/interfaces.d/*

# The loopback network interface
auto lo
iface lo inet loopback

# The primary network interface
auto enp0s3
iface enp0s3 inet dhcp

重启网卡

1
2
3
ifdown enp0s3
ifup enp0s3
resolvconf -u # 更新 /etc/resolv.conf

/etc/resolv.conf 与下面类似

1
2
3
4
5
# Dynamic resolv.conf(5) file for glibc resolver(3) generated by resolvconf(8)
#     DO NOT EDIT THIS FILE BY HAND -- YOUR CHANGES WILL BE OVERWRITTEN
nameserver 202.192.18.10
nameserver 202.192.18.1
nameserver 202.192.18.2

ubuntu 桌面版

因为ubuntu 桌面版是使用 network-manager 进行自动管理

检查 /etc/network/interfaces 应该与下面相似，不需要手动管理其他网卡

1
2
auto lo
iface lo inet loopback

更新 /etc/resolv.conf

1
2
service network-manager restart
resolvconf -u

这时候 /etc/resolv.conf 应该恢复正常，重新创建容器应该可以正常解析域名了。