ARTS(21)

1 Algorithm

给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。
请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。

由于信封包含了两个维度的长度,需要分别按照宽度和高度进行排序,用 $envelope(i)$ 表示排序后第 $i$ 信封能包含的最多的信封


其中 $w[i], h[i]$ 分别表示第 $i$ 个信封的宽和高。

func maxEnvelopes(envelopes [][]int) int {
    if len(envelopes) == 0 {
        return 0
    }
    enves := matrix(envelopes)
    sort.Sort(enves)
    result := make([]int, len(enves))
    result[0] = 1
    for i := 1; i < len(enves); i++ {
        result[i] = 1
        for j:=i-1; j>=0; j-- {
            if isMax(enves[i][0], enves[j][0]) && isMax(enves[i][1], enves[j][1]) {
                result[i] = max(result[j] + 1, result[i])
            }
        }
    }
    maxValue := result[0]
    for i:=1; i<len(result); i++{
        maxValue = max(maxValue, result[i])
    }
    return maxValue
}

func isMax(a, b int) bool {
    return a > b
}

func max(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

type matrix [][]int

func (m matrix) Len() int { return len(m) }
func (m matrix) Less(i, j int) bool {
    if m[i][0] < m[j][0] {
        return true
    } else if m[i][0] > m[j][0] {
        return false
    } else {
        if m[i][1] < m[j][1] {
            return true
        } else if m[i][1] > m[j][1] {
            return false
        } else {
            return true
        }
    }
}

func (m matrix) Swap(i, j int) {
    m[i], m[j] = m[j], m[i]
}

2 Review

Making peace with Simpon's Paradox
和 Simpon 悖论和平共处
两年之前你被诊断为肾结石,你去你们城市中最有名的肾专科专科 Alpha 医生,她说你有两个选择: 方案 A 和 方案 B。她推荐方案 A, 下述的数据表格来佐证她的建议:

因为你对医生引用的数据非常信服,你立即接受了方案 A。当麻醉师将你安放在手术台,你开始呐呐自语,并且希望这个统计数据是正确。
万幸的是,这个石头最终从你的身体中排。
这个问题还没有结束,你遵循医生的建议来防止将来的肾结石问题。一年后,你被诊断为第二颗结石。由于对 Alpha 医生的不信任,你这次预约了 Beta 医生。他解释道这次你还有两种选择: 方案 A 和方案 B。但是之前 Alpha 医生推荐方案 A, 而 Beta 医生却推荐方案 B, 他用下面的数据来佐证他的建议:

Beta 医生解释道:虽然方案 A 总体的治疗成功率比较高,但是方案 B在小和大的肾结石各自的治疗成功率都比较高。所以通过定义就知道,不管你含有小的或者大的肾结石,方案 B 的治疗成功率都比较高,所以应该选择方案 B
这时你发现有些不可能的事情居然发生了,为什么方案 B 拥有更高的小肾结石和大的肾结石成功治愈率,但是却是更低的总体成功率?这个是否意味着如果你不知道是大的结石还是小的结石,你应该选择方案 A,但是如果你被告知肾结石的大小,你应该选择方案 B,无论石头的大小?但是你这时候,你是手上并没有纸和笔来演算,而 Beta 医生变得不耐烦了,你被这些数字所疑惑,但是没有办法,你只好接受医生的建议并且接受了手术。
方案 B 非常成功,你也非常开心,但是你上述的不可能的数字感到非常疑惑。你非常想知道到底是什么回事,你在网络搜索网络上的数学家,发现了Steve Steveington,他是统计学家,而且就离你只有 3.8 里远,你希望他能够帮助弄明白是你疯了还是数学就是这样的。
"这就是Simpon悖论" Steveington 说道, "这个背后的数学非常无聊,仅仅是这个不等式是能成立的"。

“我对Simpon悖论唯一感兴趣的是为什么人们一开始对这个非常感到惊讶。它仅仅展示了统计学不那么直观和无用。拿你的肾结石场景来说,我可以很保证地来说,Beta 医生是正确。方案 B 肯定是在所有情况下的最好的治疗方案,因为我对后面的数字非常清楚”
“当我知道方案 A 比方案 B 便宜,这意味着对于小的肾结石医生更倾向于推荐方案 A。尽管它比方案 B 差一点,但是相对于更少的费用。因此医生们更喜欢将方案 B 留给那些更大的结石。”
"这就意味着方案 A 在小的肾结石中拥有更多的数字,然而方案B在更大的结石有稍差的表现。当你在计算整体成功率,方案 A 成功率是被简单的肾结石所决定。虽然方案 B 在小的和大的结石都拥有更高的成功率,但是它的总体成功率是由更大的或者更困难的肾结石决定的,所以它的总体成功率比较糟糕。"
"所以作为一个病人,你从医生中得到的理想的回复是:‘我认为你应该解释方案 A ’ 这也就意味着你认为你是简单的病例。但是如果你不相信他们,你应该是方案 B, 那么也就意味着你将得到最好的治疗。"
"这个显然的悖论发生在人们将那些本不应该直接合并的数字合并起来,或者至少应该小心地合并或者用一些控制变量。这样的错误可以用下面的描述来阻止,假设他们也不是这样说:'你可以既可以选择方案 A 也可以方案 B,而是坚持这样说:‘你既可以选择 因为它便宜通常用在小的肾结石的方案 也可以选择 因为它贵通常用在大肾结石的方案 ’。同时展示大小肾结石不同的治愈方案。你可能在做出决策之前,要求想知道你到底是哪种类型的肾结石。只要是给出重要的属性,你就能就能知道如何跳出这个统计学的陷阱。"
“或许这个例子太微不足道了,如果医生这样跟你说:‘我们已经检查了你的测试结果,我们会给出两种选择。你可以选择将肾结石取出,或者你需要理发。你可以选择手术A 和手术 B, 下面是他们手术和理发合并的成功率’,我想你这次就应该要求将上述的两个统计分开。这显然不应该将手术的成功率建立在理发店的成功率。”
“但是事实上肾结石的大小和理发上并没有实质性的区别。在第一个场景中,是否需要知道肾结石的大小这个重要变量被移除了。”
“我们也可以现实生活中看到这样更多的例子,最常引用的例子是棒球运动员David JusticeDerek Jeter 在1995和1996两个赛季拥有更高的得分,但是 Jeter 却取得了更高的总体得分。”
"如果我告诉你1995年是对所有击球手更好的年份,但是David Justice大部分赛季都受伤了? 亦或者对于投球手在1995年每一个击中都能得到2分,而David Justice在大部分赛季受伤了?你或许开始考虑当将两个年份叠加起来是不是要重新认真考虑一下,我并没改变任何数学上的东西。我只不过简单增增加了额外的信息来对比原本的比较。"
“我们大脑中有一种潜质,它能直觉的告诉我们哪些是不应该直接合并起来,也不需要其他额外的描述。其他一个体育的例子,假设你和我都是为100米和400米短跑训练,我在两个距离上都比你块,但是我大部分时候跑400米,然而你经常跑100米。如果你想证明你比我快,你可以将所有的跑过的距离中的速度合并起来。你的速度大部分是由100米的速度决定,而我的仅仅是由400米的速度决定的,你可以画出上述的表格,并且吹嘘你更高的平均速度。”
"但是没有人相信你,尽管这次和上次的肾结石的例子中没有本质的区别,但是现在你敏锐的感觉到了。这显然你不应该直接将100米和400米的耗时合并在一起,我们的大脑直觉性的感觉到了区别,并且区分出来。”
“假设你得病了,你正在尝试选择哪个药剂量来获得更快的恢复速度,你找到了如下的药剂量和恢复速度”

整个趋势非常明了,它暗示更高的药剂量带来更慢的恢复速度。正确吗?但是我们按照年龄将人群分组


“如果你20岁,你需要跟多的药;如果你30岁,你需要更多的药;如果你40岁,你也需要跟多的药。但是如果你不知道你多大,这意味着需要更少的药。这就是 Simpson 悖论,但是有着不同的应用场景。”
“这一次的关键变量是年龄,当你说‘我需要更小剂量的药,因此能够恢复的快点’, 你是意味着这样:‘我想成为左上角的部分’。然而左上角的点都是20岁年纪的样本,如果你是50岁,那么事实上你要选择的是不是更少的药剂量。如果医生拥有更多实验,这张图将会变得不那么悖论,但是变得更加不道德。”


"上述的意味着你不是想让医生给你更少的剂量,而是你需要成为那些医生认为需要更少的剂量的人。"
你仍然还有25分钟来完成1小时的咨询工作,你向 Steveington 能否得到 $7 * 25 / 60=$2.92的退款。他说不能,因为他的服务不能拆分出来。所以你又开始提问了其他问题,比如自然实验
一年以后,你得了第三块肾结石。不幸的的是,这一次没有方案 C, 也没有100%的治愈方案。没有再问什么,这一次你非常自信的选择了方案 B,当麻醉师将你放到,考虑到场景,你感觉到了其中的内容。

3 Tips

3.1 Golang 中的 Array 和 Slice

Golang 内存模型中,Array 是一块连续存储的空间,但是大小也是数据类型的一部分;而 Slice 是用来描述 Array 的一部分。Slice 关联了一个 sliceHeader 的结构:

sliceHeader{
    Length:        0,
    Capacity:      0,
    ZerothElement: *<array>,
}

如果函数的参数为 Slice类型,那么函数调用的时候,传递的是 sliceHeader 的拷贝。

3.2 异或

  • 任何数与自己 异或 结果为 0;
  • 任何数与 0 异或`为本身;
  • 异或`满足交换律;

3.3 厉害英语表达

  • awesome
  • terrific
  • incredible
  • impressive: That's an impressive show.
  • phenomenal
  • extraordinary
  • you are the man
  • way to go
  • You are the best
  • capable: She is capable of singing.
  • competent
  • talented/gifted
  • accomplished

4 Share

  • 在提交MR的时候,也就是自己最终要呈现的代码版本。
Comments
Write a Comment