每周 ARTS 第 3 期

1. Algorithm

88. 合并两个有序数组(简单)

描述:

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

  • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
  • 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:
1
2
3
4
5
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]
思路:

从右往左遍历,比较 nums1 和 nums2 的元素大小,然后从右边开始填充 nums1,不需要额外的存储空间。

解法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
if (nums1 == null || nums2 == null) {
return;
}

int p = m + n - 1;
m -= 1;
n -= 1;
while (m >= 0 && n >= 0) {
if (nums1[m] > nums2[n]) {
nums1[p--] = nums1[m--];
} else {
nums1[p--] = nums2[n--];
}
}

while (n >= 0) {
nums1[p--] = nums2[n--];
}
}
}
分析:
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

258. 各位相加(简单)

描述:

给定一个非负整数 num,反复将各个位上的数字相加,直到结果为一位数。

进阶:你可以不使用循环或者递归,且在 O(1) 时间复杂度内解决这个问题吗?

示例:
1
2
3
输入: 38
输出: 2
解释: 各位相加的过程为:3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数,所以返回 2。
思路:
  • 解法一:直接按题目到意思来做,对数字对每位进行相加,结果不为一位数时一直循环。
  • 解法二:比较巧妙。假如一个三位数’abc’,其值大小为s1 = 100 a + 10 b + 1 c,经过一次各位相加后,变为s2 = a + b + c,减小的差值为(s1 -s2) = 99 a + 9 * b,差值可以被9整除,每个循环都这样,缩小了9的倍数。当num小于9,即只有一位时,直接返回num,大于9时,如果能被9整除,则返回9(因为不可能返回0也不可能返回两位数及以上的值),如果不能被整除,就返回被9除的余数。
解法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public int addDigits1(int num) {
int sum = 10;
while (sum >= 10) {
sum = 0;
int n = num;
while (n > 0) {
sum += n % 10;
n = n / 10;
}
num = sum;
}
return sum;
}

public int addDigits2(int num) {
if (num > 9) {
num = num % 9;
if (num == 0) {
num = 9;
}
}
return num;
}
}
分析:
  • 时间复杂度:解法一:O(logn),解法二:O(1)
  • 空间复杂度:O(1)

2. Review

SOLID Principles every Developer Should Know 每个开发者都该知道的 SOLID 原则,深度好文,推荐阅读。

作者主要讲了面对对象编程的 5 个原则:

  • S:Single Responsibility Principle(单一职责原则)
  • O:Open-Closed Principle(开闭原则)
  • L:Liskov Substitution Principle(里氏替换原则)
  • I:Interface Segregation Principle(接口隔离原则)
  • D:Dependency Inversion Principle(依赖倒置原则)
单一职责原则

当设计类的时候,我们应该把相关的功能放到一起,这样就算要修改也是因为相同的原因修改。同时,对于不同原因带来的改动要进行功能拆分。

开闭原则

软件实体(类、模块、函数)应该对扩展开放,对修改关闭。比如,要添加功能时,在原来的基础上修改 if-else 实现,还是把共有的方法抽取出来通过继承来实现呢,显然要扩展而不是修改。

里氏替换原则

子类可以替代它的父类。满足 LSP 的两个要求:

  • 如果父类有一个接收父类型参数的方法,那么它的子类应当接收父类型或者其子类型作为参数。
  • 如果父类方法的返回值是父类型,那么它的子类应当返回父类型或者其子类型。
接口隔离原则

使用类不应该被强制要求实现它们不需要的接口。一个全能的接口,什么事都可以干,我们不需要它,我们只要专心做一件事的接口。

依赖倒置原则

依赖倒置因该针对抽象而不是具体。

  • 高层模块不该依赖低层模块,它们都该依赖抽象类。
  • 抽象不该依赖具体,具体应当依赖抽象。

点评:文中举了几个例子,非常简洁易懂。为了写出可读可维护的代码,我们尽量还是要遵循SOLID 原则。

3. Tip

分享解决算法题的一个技巧:快慢指针,在数组和链表中非常好用。

4. Share

读完 左耳朵耗子:996不是福气,努力也未必成功 深有感触。最近工作上遇到类似的事,产品经理不懂得优化,一直让开发做些低级重复性的本该由其他人做的事,还是用手动像机械一样操作。程序员本该用代码解脱双手,最后搞得这么低效。

再次重复一次耗子叔的金句:

我们学计算机当程序员最大的福气不是可以到大公司里加班和996,而是我们生活在了第三次工业革命的信息化时代,这才是最大的福气,所以,我们应该努力地提升自己,而不是把自己当劳动力一样的卖了!在这样的一个时代,你要做的不是通过加班和拼命来跪着挣钱,而是通过技能来躺着挣钱……

本文标题:每周 ARTS 第 3 期

文章作者:落英坠露

发布时间:2019年04月20日 - 16:04

最后更新:2019年04月20日 - 16:04

原始链接:https://isuperqiang.cn/2019/04/20/每周ARTS第3期/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

赞赏是一种行为艺术