Algorithm：42. 接雨水 Review： 应用函数编程原则 Tip/Tech： Share： 毛细血管的架构

Algorithm

42. 接雨水

https://leetcode-cn.com/problems/trapping-rain-water/ 这里属于经典问题，基本上有刷LeetCode都会遇到这个题目，而且有三层的优化思路。

首先，我们先确定一个基本的规则那就是到底应该如何去判断每个位置上能接多少水？

我们举个例子，数组height[i]的位置当前可用装多少水，是由这个位置的左右的两个位置的最小值决定的。

比如在上图中的索引1的位置上，可以装多少水是左、右两边的分别的最大的值中的最小值决定的。

所以这个思想的公式就是：

i的位置上的接水是数量 = max{min{左侧的最大值， 右侧的最大值} - height[i], 0}

这样我们就可以写出最初的暴力的遍历的做法：

public int trap1(int[] height) { int ans = 0; int size = height.length; for (int i = 1; i < size - 1; i++) { int max_left = 0, max_right = 0; for (int j = i; j >= 0; j--) { //Search the left part for max bar size max_left = Math.max(max_left, height[j]); } for (int j = i; j < size; j++) { //Search the right part for max bar size max_right = Math.max(max_right, height[j]); } ans += Math.min(max_left, max_right) - height[i]; } return ans; }

但是这里的时间复杂度是O(n^2)， 空间复杂度是O(1)，速度依然不够快。

空间换时间

我们可以考虑一下由空间换时间的思想。先遍历一下， 把每个位置的数组左边部分的最大值和数组右边部分的最大值给记下来，

分别用leftMaxArr，和rightMaxArr来进行记录，

然后每次按照每个值的最大和最小进行计算。

i的位置上的接水是数量 = max{min{leftMaxArr[i -1]，rightMaxArr[i + 1]} - height[i], 0}

直接上代码， Show The Code：

public int trap(int[] height) { if (height == null || height.length < 3) { return 0; } int len = height.length; int[] leftMax = new int[len]; int[] rightMax = new int[len]; int leftTemp = height[0]; for (int i = 0; i < len; ++i) { if (leftTemp < height[i]) { leftMax[i] = height[i]; leftTemp = height[i]; } else { leftMax[i] = leftTemp; } } int rightTemp = height[len - 1]; for (int i = len - 1; i >= 0; --i) { if (rightTemp < height[i]) { rightMax[i] = height[i]; rightTemp = height[i]; } else { rightMax[i] = rightTemp; } } int res = 0; for (int i = 1; i < len - 1; ++i) { res += Math.max(Math.min(leftMax[i - 1], rightMax[i + 1]) - height[i], 0); } return res; }

这样的时间复杂度是O(n) ，空间的复杂度是O(n)。

减少空间

这个在官方的解题中有非常好的解释，说实话我这里没有想到。就是依靠四个变量来进行判断，但是在判断的过程中比较复杂，就是需要注意每次根据条件进行一定下标

public int trap(int[] height) { if (height == null || height.length < 3) { return 0; } int res = 0; int leftMax = height[0]; int rightMax = height[height.length - 1]; int left = 1; int right = height.length - 2; while (left <= right) { // 注意，这里需要注意的是，你要注意的是， 要比较两个 // 左右值的大小，取小值来进行运算 if (leftMax <= rightMax) { res += Math.max(leftMax - height[left], 0); leftMax = Math.max(leftMax, height[left]); left++; // } else { res += Math.max(rightMax - height[right], 0); rightMax = Math.max(rightMax, height[right]); right--; } } return res; }

Review

https://97-things-every-x-should-know.gitbooks.io/97-things-every-programmer-should-know/content/en/thing_04/

构建你的编码标准

确保代码格式化是构建过程的一部分，以便每个人在每次编译代码时自动运行它。使用静态代码分析工具扫描代码以查找不需要的反模式。如果找到任何内容，请中断构建。 了解如何配置这些工具，以便您可以扫描自己的项目特定反模式。不仅要测量测试覆盖率，还要自动检查结果。再次，如果测试覆盖率太低，请中断构建。

这篇说的就是你需要在项目中去规定你的编码规范。虽然这些规范我们都知道了，但是文中还有一句：

最后，编码标准应该是动态的而不是静态的。随着项目的发展，项目需求的变化，以及最初可能看起来很明智的编码规范，在几个月之后并不一定是明智的。

Tip/Tech

重点学习了关于抓包的一些入门的知识，重点复习了关于http协议的一些内容。

Share

Spinach Leaf Transformed Into Beating Human Heart Tissue

https://news.nationalgeographic.com/2017/03/human-heart-spinach-leaf-medicine-science/ 3D打印器官可以做到，还差一个毛细血管组织，那个毛细血管过于精细，所以3D答应没法做到，那么就需要别的方案来代替，所以科学家就发明了用植物菠菜的来进行构建人的毛细血管的方案。 叶子的一个特征是细脉的分支网络，为细胞提供水和养分。现在，科学家们利用植物静脉来复制血液通过人体组织的方式。这项工作涉及修改实验室中的菠菜叶以去除其植物细胞，这留下了由纤维素制成的框架。

“纤维素具有生物相容性[和]已被用于各种再生医学应用，如软骨组织工程，骨组织工程和伤口愈合，