Skip to content

Latest commit

 

History

History
166 lines (116 loc) · 5.7 KB

arts-03.md

File metadata and controls

166 lines (116 loc) · 5.7 KB
Raw

1. Algorithm

88. 合并两个有序数组（简单）

描述：

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

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

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

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

解法：
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) 时间复杂度内解决这个问题吗？

示例：
输入: 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除的余数。
解法：
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，而是我们生活在了第三次工业革命的信息化时代，这才是最大的福气，所以，我们应该努力地提升自己，而不是把自己当劳动力一样的卖了！在这样的一个时代，你要做的不是通过加班和拼命来跪着挣钱，而是通过技能来躺着挣钱……