动态规划算法重点在于找上一个的公式,Google Code Review,John 易筋 ARTS 打卡 Week 06

发布于: 2020 年 06 月 28 日

每周完成一个 ARTS:

Algorithm: 每周至少做一个 LeetCode 的算法题

Review: 阅读并点评至少一篇英文技术文章

Tips: 学习至少一个技术技巧

Share: 分享一篇有观点和思考的技术文章

zgpeace 立个Flag:坚持ARTS 10年,今天是2020-05-04 ~ 2030-05-04,漏掉一次微信群发红包100大洋。

1. Algorithm: 每周至少做一个 LeetCode 的算法题

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

解决思路:这是动态规划的题目,突破口是要找到一个公式,使得dp[i] = x * dp[i-1] + y, 这样子就可以根据上一个数推断出下一个结果,达到O(n)解。

这里的突破口是当前数nums[i], 是从自己开始,还是与前面的数dp[i-1] 加起来一起。这里就要判断dp[i - 1] > 0 ? dp[i - 1] : 0, 上一个数的和是否大于0.

那么问题就迎刃而解了。

  1. 如果dp[i - 1] < 0, 就从自己开始 dp[i] = nums[i]

  2. 如果dp[i - 1] > 0, 就延续前任的记过 dp[i] = nums[i] + dp[i - 1];

  3. 如果最大数是历史最大,则替换max = Math.max(max, dp[i]);, 最终结果为max。

class Solution {
public int maxSubArray(int[] nums) {
// check edge
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException();
}
int length = nums.length;
int dp[] = new int[length];
dp[0] = nums[0];
int max = dp[0];
for (int i = 1; i < length; i++) {
dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
}

2. Review: 阅读并点评至少一篇英文技术文章

查看了Google Code View的标准,以及如何进行Code Review。感触比较深刻的是,Code Review评论的时候要有礼貌,评论不仅仅是要指出问题,还要有指导改进建议。code style对各种语言都进行了标准定义,这样子评论也会有依据。

Google How to do a code review

https://google.github.io/eng-practices/review/reviewer/

3. Tips: 学习至少一个技术技巧

博客:

问什么要试用 Singleton

问什么要试用 Singleton

Singleton 模式保证产生单一实例,就是说一个类只产生一个实例。试用 Singleton 有两个原因

  • 是因为只有一个实例,可以减少实例频繁创建和销毁带来的资源消耗。

  • 是当多个用户试用这个实例的时候,便于进行统一控制(比如打印机对象)。

前者是性能需求,后者是功能需求。

饿汉式 Singleton

public class HungrySingleton {
private static HungrySingleton instance = new HungrySingleton();
private HungrySingleton() {
}
public static HungrySingleton getInstance() {
return instance;
}
}

注意:一定要有私有的构造函数,保证实例只能通过getInstance() 方法获得。

尽量使用饿汉式构造单实例。单例中的成员变量是多线程重用的,可能会产生意想不到的结果,因此尽量将单例设计为无状态对象(只提供服务,不保存状态)。

饿汉式 Singleton 的问题是,应用一启动就加载对象进内存,就算从来未被用过。

懒汉式 Singleton

publci class LazySingleton {
private static LazySingleton instance = null;
private LazySingleton() {
}
public static synchronized LazySingleton getInstance() {
if (instance == null) {
instance = new LazySingleton();
}
return instance;
}
}

注意: getInstance() 的修饰符 synchronized 一定要加上,否则可能会产生多重实例。

懒汉式Singleton解决了饿汉式Singleton,当调用的时候才去加载对象到内存。但是引发了另外一个性能问题,每次访问对象都要加锁。

提升性能的 懒汉式 Singleton

publci class LazySingleton {
private static LazySingleton instance = null;
private LazySingleton() {
}
public static LazySingleton getInstance() {
if (instance == null) {
instance = LazySingleton.buildInstance();
}
return instance;
}
private static synchronized LazySingleton buildInstance() {
if (instance == null) {
instance = new LazySingleton();
}
return instance;
}
}

只有当对象为null的时候,才去加锁创建对象。

4. Share: 分享一篇有观点和思考的技术文章

极客大学架构师训练营 框架开发 模式与重构 JUnit、Spring、Hive核心源码解析 第6课 听课总结

框架设计原则 (SOLID)

开闭原则(OCP - Open–closed principle)

对扩展是开发,对现有修改是关闭。

使用多态,使用抽象。策略模式,适配器模式,观察者模式。

依赖倒置原则(DIP - Dependency inversion principle)

高层不依赖低层,低层也不依赖高层。高层定义抽象接口,低层实现高层定义的接口。

比如Tomcat,Spring,JUnit,我们不需要调用框架的代码。我们基于框架提供的接口来编程。 架构师要有开发框架的能力和思维,这才能区别于普通的工程师。

正常的调用顺序

依赖倒置以后

Liskov 替换原则(LSP - Liskov substitution principle)

所有的父类,都可以替换为子类。 子类比父类更严格,子类方法约束开放性要比父类大。比如父类是protected修饰,子类只能是protected或者public。

不是为继承而设计的类,那么就不要继承该类。

单一职责原则(SRP - Single-responsibility principle)

一个类只有一个引起其变化的原因。

如果一个类会有多个原因引起变化,则要分为多个类。

接口隔离原则(ISP - Interface segregation principle)

隐藏用户不需要的接口,以免被误操作。

JUnit 中的设计模式

如何写单元测试

public class BubbleSorterTests extends TestCase {
private Integer[] array;
private Sorter sorter;
protected void setUp() {
array = new Integer[] { 5, 4, 9, 7, 6, 3, 8, 1, 0, 2};
sorter = new BubbleSorter();
}
public void testSort() {
Sortable sortable = new ArraySortable(array);
Comparator comparator = new IntegerComparator();
sorter.sort(sortable, comparator);
for (int i = 0; i < 10; i++ ) {
assertEquals(i, array[i].intValue());
}
}
}

实现一个单元测试的步骤

创建测试类, 从 TestCase 派生

初始化

  • 覆盖基类的方法: protected void setUp()

消除环境

  • 覆盖基类的方法: protected void tearDown()

书写测试方法

  • 命名规则: public void testXyz()

JUnit 单元测试是如何执行的?

public abstract class TestCase extends Assert implements Test {
public boid runBare() throws Throwable {
Throwable exception = null;
setUp();
try {
runTest();
} catch (Throwable running) {
exception = running;
} finally {
try {
tearDown();
} catch (Throwable tearingDown) {
if (exception == null) exception = tearingDown;
}
}
if (exception != null) throw exception;
}
protected void runTest() throws Throwable {
// 利用动态机制调用 testXyz()
}
protected void setUp() throws Exception { }
protected void tearDown() throws Exception { }
}

JUnit 单元测试的执行

Idea 中运行单元测试通过的图片。

JUnit 单元测试的执行时序图

这里用到了三个策略模式:

  1. Eclipse定义了接口,策略的接口,策略的实现。定义一个plugin的规范。显示有多少个用例通过,多少个用例失败。

  2. Eclipse 调用runBare方法,调用TestCase。

  3. TestCase只有一个,实现有多个,XyzTests有多个。

发布于: 2020 年 06 月 28 日 阅读数: 13
用户头像

John(易筋)

关注

问渠那得清如许?为有源头活水来 2018.07.17 加入

前阿里巴巴资深无线开发,目前汇丰银行专家。客户端架构师,全栈工程师。擅长算法、数据结构、设计模式、iOS、Java、 Spring Boot、Spring Cloud、Docker

评论

发布
暂无评论
动态规划算法重点在于找上一个的公式,Google Code Review,John 易筋 ARTS 打卡 Week 06