ARTS-W02 (12.27 - 1.02)

Algorithm（一道算法题）

这周刷到的算法题：鸡蛋掉落
具体描述如下：你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

这道题是目前刷到最难的一道题了，完全不知道如下下手。看了leetcode上解答，看了好几遍，才稍微有了一点思路。大致用动态规划+二分查找法来做，由于大学一心多用，数学糟糕至极，先温习下什么是动态规划？

动态规划大致思想：通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，适用于 循环子问题 与 最优子结构。

 假设在x楼扔鸡蛋 d(k,n)，只分两种情况：蛋碎 与 没碎。

• 蛋碎：往上一层找，那么范围缩小至：d(k-1,n-x)
• 没碎：往下一层找，那么范围缩小至：d(k，x-1)

考虑到最差情况，所以要从这两种情况下查找出最大值 max(d(k-1,n-x),d(k,x-1)) ，题目说要确定F的最小移动次数，所以要求在 1-n范围内索引次数最少，由于楼层数是顺序的，所以可以用二分查找法来做。最终得出公式：

java题解：

public int superEggDrop(int K, int N) {
        return dp(K, N);
    }

    Map<Integer, Integer> memo = new HashMap();
    public int dp(int K, int N) {
        if (!memo.containsKey(N * 100 + K)) {
            int ans;
            if (N == 0) {
                ans = 0;
            } else if (K == 1) {
                ans = N;
            } else {
                int lo = 1, hi = N;
                while (lo + 1 < hi) {
                    int x = (lo + hi) / 2;
                    int t1 = dp(K-1, x-1);
                    int t2 = dp(K, N-x);

                    if (t1 < t2) {
                        lo = x;
                    } else if (t1 > t2) {
                        hi = x;
                    } else {
                        lo = hi = x;
                    }
                }

                ans = 1 + Math.min(Math.max(dp(K - 1, lo - 1), dp(K, N - lo)), Math.max(dp(K - 1, hi - 1), dp(K, N - hi)));
            }

            memo.put(N * 100 + K, ans);
        }

        return memo.get(N * 100 + K);
    }
}

此题难度过大，还需要多加消化。

Review（阅读并点评一篇英语技术文章）

How To Become a Web Developer in 2021
  以下是这篇文章的主要意思：总大体上介绍2021年成为web开发者要具备的技能，比较浅显的一篇文章，分别介绍了web开发者的，前端、后端、全栈工程师要学习的技能。前端：React JS, Angular, or Vue ； 后端：数据库设计，处理接口权限校验，版本控制能力，自动化测试能力等；

Tips（学习一个技术技巧）

在新公司待了半个月了，在这半个月里，有哪些印象深刻的东西呢？

1. 技术氛围是7年里，呆过的公司最好的。体现在哪些方面呢？
      - 工作外还会讨论技术与现实。
      - 会主动去优化系统。
      - 每周的code sharing都会找人介绍自己写的好的代码。
         代码的整洁；更好的实现方式；低耦合高内聚。
2. 基础设施还不够完善。
3. 部门架构不够清晰，第一次接触到这种类型的组织的架构。

Share（分享一篇有观点有思考的技术文章）

最近有学习activiti ， 比较浅显，只是使用级别的。从以下几个方面简单的介绍下：activiti是什么？activiti能解决什么问题？activiti开发的流程如何？ activiti的核心都有哪些？

看官网介绍：

Activiti is a light-weight workflow and Business Process Management (BPM) Platform targeted at business people, developers and system admins. Its core is a super-fast and rock-solid BPMN 2 process engine for Java. It's open-source and distributed under the Apache license. Activiti runs in any Java application, on a server, on a cluster or in the cloud. It integrates perfectly with Spring, it is extremely lightweight and based on simple concepts.

翻译下来的大致意思为：Activiti是一个面向业务人员、开发者、系统管理员的轻量级的工作流和业务流程管理（BPM）平台。它的核心是基于BPMN2规范的超级快速、稳定的流程引擎。它是开源的，在Apache下发布的，它能运行在任何的java应用程序，服务，集群或者云中。它能与spring完美集成，它足够轻量和简单。

• BPM（Business Process Management）是一种管理模式
• BPMN （Business Process Modeling Nation）是一种规范

简单概括为：让复杂可变的流程在计算机应用环境下进行自动化，对流程的各个步骤之间的业务规则进行抽象、概括。

1 画流程图
2 部署流程图(repositoryService)
3 启动一个流程实例(runtimeService)
4 查找个人待办任务(taskService)
5 执行任务(taskService.complete)
6 查看历史流程实例(historyService)

• RespositoryService
  流程仓库service，用于管理流程仓库，例如：部署、删除等。
• 
  身份service，管理用户与组之间的关系，activiti7删除了。
• RuntimeService
  运行时service，处理正在运行的流程实例，任务等。
• TaskService
  任务service，管理任务，例如：签收、办理、指派等。
• 
  表单service，查询流程相关的表单数据，activiti7删除了。
• HistoryService
  历史service，查询流程所有的历史数据。
• ManagementService
  引擎管理service，与业务无关，例如：数据库相关，配置（引擎配置查询）相关等。