1. Algorithm

35. 搜索插入位置(简单)

描述:

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。

示例:
输入: [1,3,5,6], 5
输出: 2
输入: [1,3,5,6], 7
输出: 4
思路:
  • 解法一:因为是排序的数组,直接从头遍历,然后找到大于或者等于目标值的下标,就是结果。
  • 解法二:使用二分法查找,然后找到目标值或者左边界(low)。
解法:
class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }

    public int searchInsertByBinary(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int min = 0;
        int max = nums.length - 1;
        while (min <= max) {
            int mid = (max + min) / 2;
            if (nums[mid] > target) {
                max = mid - 1;
            } else if (nums[mid] < target) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return min;
    }
}
分析:
  • 时间复杂度:解法一 O(n),解法二 O(logn)
  • 空间复杂度:O(1)

69. X 的平方根(简单)

描述:

实现 int sqrt(int x) 函数。计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例:
输入: 4
输出: 2
输入: 8
输出: 2
思路:
牛顿法 https://en.wikipedia.org/wiki/Integer_square_root
注意防止整形越界。
解法:
class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        int r = x / 2;
        while (r > x / r) {
            r = (r + x / r) / 2;
        }
        return r;
    }
}
分析:
  • 时间复杂度:O(logn)
  • 空间复杂度:O(1)

2. Review

What is readable code? 什么是可读的代码?

代码创建了接口,但是代码本身也是一种接口。就像生活中的门可以打开、关闭一样,开发者写代码可以添加新功能、修复错误。忘记代码的位置很容易,所以代码应该是可搜索的,简短通用的名称可以作为默认值表示。

可读的代码应当容易安全地编辑,前提是要理解代码的逻辑。当变量名称具有表现力时,代码更容易编辑。可读的代码一定可用,另外看起来也漂亮。

作者从 UI 层面举了几个例子,View 的状态和代码层面的变量产生对应关系,如果让用户清晰理解操作意图,那么代码也要保证逻辑是一致的。

3. Tip

读《码出高效:Java 开发手册》集合篇看到 fail-fast 有感,Java集合的fail-fast机制

4. Share

马蜂窝张矗:我对技术团队绩效考核管理的几点思考

技术人员绩效考核一般难以量化,不好的衡量标准有代码行数、Bug 数量等。要关注目标,而不是任务,目标可量化。不同级别的人员,考核的重点不同。按月或按季度进行评估,周期不宜太长。