[Hard]鸡蛋掉落

887. 鸡蛋掉落

你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N  共有 N 层楼的建筑。

每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。

你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?

 

示例 1:

输入:K = 1, N = 2
输出:2
解释:
鸡蛋从 1 楼掉落。如果它碎了,我们肯定知道 F = 0 。
否则,鸡蛋从 2 楼掉落。如果它碎了,我们肯定知道 F = 1 。
如果它没碎,那么我们肯定知道 F = 2 。
因此,在最坏的情况下我们需要移动 2 次以确定 F 是多少。
示例 2:

输入:K = 2, N = 6
输出:3
示例 3:

输入:K = 3, N = 14
输出:4
 

提示:

1 <= K <= 100
1 <= N <= 10000
class Solution {
   public:
    //方法一:暴力动规(超时),比较好理解
    int superEggDrop(int K, int N) {
        vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
        //初始化
        for (int i = 1; i <= K; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = j;
            }
        }
        for (int i = 2; i <= K;) {
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k < j; k++) {
                    /**
                     * 最坏情况下的最少扔鸡蛋次数
                     * 当前鸡蛋总数为i,楼层总数为j,在第k层楼扔鸡蛋时,鸡蛋碎了往楼下走(dp[i-
                     * 1][k - 1],鸡蛋没碎dp[i][j - k],在第k层扔得算1次
                     */
                    dp[i][j] =
                        min(dp[i][j], max(dp[i - 1][k - 1], dp[i][j - k]) + 1);
                }
            }
        }
        return dp[K][N];
    }

    //方法二:数学动规,重新定义dp
    int superEggDrop2(int K, int N) {
        /**
         * dp[k][m]:当前状态为 k 个鸡蛋,尝试扔 m 次鸡蛋,
         * 返回这个状态下最高的确认楼层数
         */
        vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
        int m = 0;
        while (dp[K][m] < N) {
            m++;
            for (int k = 1; k <= K; k++)
                /**
                 * 1. 鸡蛋没碎: dp[k][m - 1] 就是楼上的楼层数,因为鸡蛋个数 k
                 * 不变,扔鸡蛋次数 m 减一;
                 * 2. 鸡蛋碎了: dp[k - 1][m - 1]
                 * 就是楼下的楼层数,因为鸡蛋个数 k 减一,同时扔鸡蛋次数 m
                 * 减一;
                 * 3.是当前楼层数
                 *
                 */
                dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
        }
        return m;
    }
}

 

mac读取ntfs

1.查看ntfs u盘名

(base) MacBook-Pro-3:~ gonenlei$ diskutil list
/dev/disk0 (internal):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:      GUID_partition_scheme                         500.3 GB   disk0
   1:                        EFI EFI                     314.6 MB   disk0s1
   2:                 Apple_APFS Container disk1         500.0 GB   disk0s2

/dev/disk1 (synthesized):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:      APFS Container Scheme -                      +500.0 GB   disk1
                                 Physical Store disk0s2
   1:                APFS Volume Macintosh HD            206.5 GB   disk1s1
   2:                APFS Volume Preboot                 106.7 MB   disk1s2
   3:                (base) MacBook-Pro-3:~ gonenlei$ diskutil list
/dev/disk0 (internal):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:      GUID_partition_scheme                         500.3 GB   disk0
   1:                        EFI EFI                     314.6 MB   disk0s1
   2:                 Apple_APFS Container disk1         500.0 GB   disk0s2

/dev/disk1 (synthesized):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:      APFS Container Scheme -                      +500.0 GB   disk1
                                 Physical Store disk0s2
   1:                APFS Volume Macintosh HD            206.5 GB   disk1s1
   2:                APFS Volume Preboot                 106.7 MB   disk1s2
   3:                APFS Volume Recovery                1.6 GB     disk1s3
   4:                APFS Volume VM                      1.1 GB     disk1s4

/dev/disk2 (external, physical):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:     FDisk_partition_scheme                        *256.6 GB   disk2
   1:               Windows_NTFS gongel                  255.3 GB   disk2s1
   2:                       0x1B                         469.2 MB   disk2s2APFS Volume Recovery                1.6 GB     disk1s3
   4:                APFS Volume VM                      1.1 GB     disk1s4

/dev/disk2 (external, physical):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:     FDisk_partition_scheme                        *256.6 GB   disk2
   1:               Windows_NTFS gongel                  255.3 GB   disk2s1
   2:                       0x1B                         469.2 MB   disk2s2

2. sudo vim /etc/fstab

增加一行:LABEL=u盘名 none ntfs rw,auto,nobrowse

3. 接下来可以在 /Volumns下看到你的u盘

4.(可选)sudo ln -s  /Volumns ~/Desktop/Volumns

注意事项:

1.用了几次之后发现不能识别了?

原因是u盘拔出时没有正确弹出,请再次插入windows电脑然后正确弹出即可

2.需要重启吗?

不需要

 

batch size过大导致泛化能力下降

今天跑实验发现batch size=4和batch size=2048的结果相差太大,下面依次是bs=4和bs=2048的生成结果

恐 怕 只 会 得 到 你 讨 厌
初 恋 的 日 记
为 了 爱
你 与 我 之 间 似 比 针 线
它 反 覆 骗 著 我
其 实 我 并 不 像 他 们 说 的
心 里 渐 奔 放
你 说 走 就 走
天 与 地 难 以 有 人 可 拯 救 到 我
随 风 飘 飘 天 地 任 逍 遥
岁 月 多 依 稀
怎 么 一 点 都 不 可 以 将
我 的 心 中 的 心 的 心
我 们 的 心 中
我 的 心
我 的 心 中 的 心 中 的 心
我 们 不 会 相 信
我 的 心 中 的 心 中 的 心 里
我 们 的 心 中
我 们 的 心 中
我 的 心 中 的 心 中 的 心 中 的 心
我 的 心 中 的 心 中 的 心
我 们 的 心 中
我 的 心 中 的 心 中 的 心

另外需要看一下paper《On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima

learning rate和batch size