Algorithm

64. 最小路径和

// f(m,n) = min(f(m-1,n) + grid[m][n],f(m,n-1) + grid[m][n])
func minPathSum(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    results := make([][]int, m)
    for i := 0; i < m; i++ {
        results[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 && j == 0 {
                results[i][j] = grid[0][0]
                continue
            }
            if i == 0 {
                results[i][j] = results[i][j-1] + grid[i][j]
                continue
            }
            if j == 0 {
                results[i][j] = results[i-1][j] + grid[i][j]
                continue
            }
            results[i][j] = min(results[i-1][j]+grid[i][j], results[i][j-1]+grid[i][j])
        }
    }
    return results[m-1][n-1]
}

func min(a, b int) int {
    if a <= b {
        return a
    } else {
        return b
    }
}

Review

NA

TIP

这周做需求过程遇到一个问题：go里面使用interface{}对int64进行反序列化的时候，会有精度丢失的问题。
问题代码如下：

func fun1(t *testing.T) {
    tempStr := "{\"a\":7257733976671193917}"
    tempStruct := make(map[string]interface{})
    json.Unmarshal([]byte(tempStr), &tempStruct)
    fmt.Printf("tempStruct:%v\n", tempStruct)
    aValue := tempStruct["a"]
    fmt.Printf("aValue:%v\n", aValue)
    aFloat64 := aValue.(float64)  // 这里因为json.Unmarshal默认会把所有数字类型都反序列化为float64，所以只能断言为float64
    fmt.Printf("aFloat64:%v\n", aFloat64)
    aInt64 := int64(aFloat64) // 这里转换的时候丢失了精度，导致没有正确转换
    fmt.Printf("aInt64:%v\n", aInt64)
}
// tempStruct:map[a:7.257733976671194e+18]
// aValue:7.257733976671194e+18
// aFloat64:7.257733976671194e+18
// aInt64:7257733976671194112

可以看到最终反序列化得到的值是不符合预期的。那么怎么解决问题呢？答案是使用json.Number

func fun2() {
    tempStr := "{\"a\":7257733976671193917}"
    var tempStruct map[string]interface{}
    d := json.NewDecoder(bytes.NewBuffer([]byte(tempStr)))
    d.UseNumber()
    d.Decode(&tempStruct)
    fmt.Printf("tempStruct:%v\n", tempStruct)
    aValue := tempStruct["a"]
    fmt.Printf("aValue:%v\n", aValue)
    aInt64, _ := aValue.(json.Number).Int64()
    fmt.Printf("aInt64:%v\n", aInt64)
}
// tempStruct:map[a:7257733976671193917]
// aValue:7257733976671193917
// aInt64:7257733976671193917

来详细看下UseNumber和Decode的源码注释，可以看到关键在于调用UseNumber之后，就不会把默认把interface{}转换为float64了

// UseNumber causes the Decoder to unmarshal a number into an interface{} as a
// Number instead of as a float64.
func (dec *Decoder) UseNumber() { dec.d.useNumber = true }
// convertNumber converts the number literal s to a float64 or a Number
// depending on the setting of d.useNumber.
func (d *decodeState) convertNumber(s string) (any, error) {
    if d.useNumber {
        return Number(s), nil
    }
    f, err := strconv.ParseFloat(s, 64)
    if err != nil {
        return nil, &UnmarshalTypeError{Value: "number " + s, Type: reflect.TypeOf(0.0), Offset: int64(d.off)}
    }
    return f, nil
}

Share

学习“数据密集型应用系统设计”

第二章 数据模型与查询语言

关系模型与文档模型

关系模型数据库与文档模型数据库的差异性：

1. 关系型数据库在应用层代码开发更复杂。关系型数据库用户需要在dao层写许多复杂的逻辑来将应用层代码中的对象与数据库模型中的表、行和列进行关联。而文档型数据库一般使用json的形式，很容易就和应用代码中的对象映射起来。
2. 关系型数据库对多对一、多对多的数据模型处理起来更得心应手。对于关系数据库，由于支持联结操作，可以很方便地通过ID来引用其他表中的行。而在文档数据库中，通常不支持联结。
3. 文档数据库对数据schema的支持更加灵活。大多数文档数据库（以及关系数据库中的JSON支持）都不会对文档中的数据限制任何schema，也就是不对检查写入的数据是否一定需要某些字段或者内容。而关系型数据库则需要预先定义好表的字段，如果写入的数据缺少某些字段，则需要设置该字段允许为空。
4. 文档数据库在查询局部性数据是性能更优。一个文档一般都存储在同一个磁盘块中，访问起来效率更高。而关系型数据库可能需要将不同内容放在不同表中，需要更加多/频繁的IO操作，效率会更低。