写点什么

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

用户头像
John(易筋)
关注
发布于: 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 日阅读数: 63

版权声明: 本文为 InfoQ 作者【John(易筋)】的原创文章。

原文链接:【http://xie.infoq.cn/article/7390328fea0c3c81f68d085d4】。

本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。

ARTS 打卡计划
用户头像

John(易筋)

关注

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

工作10+年，架构师，曾经阿里巴巴资深无线开发，汇丰银行架构师/专家。开发过日活过亿的淘宝Taobao App，擅长架构、算法、数据结构、设计模式、iOS、Java Spring Boot。易筋为阿里巴巴花名。

评论

发布
暂无评论
Copyright © 2021, Geekbang Technology Ltd. All rights reserved. 极客邦控股（北京）有限公司 | 京 ICP 备 16027448 号 - 5京公网安备京公网安备 11010502039052号
动态规划算法重点在于找上一个的公式，Google Code Review，John 易筋 ARTS 打卡 Week 06